DI Management Home > Cryptography > RSA Algorithm

# RSA Algorithm

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 [RIVE78]. The basic technique was first discovered in 1973 by Clifford Cocks [COCK73] of CESG (part of the British GCHQ) but this was a secret until 1997. The patent taken out by RSA Labs has expired.

The RSA cryptosystem is the most widely-used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately.

The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.

Party A can send an encrypted message to party B without any prior exchange of secret keys. A just uses B's public key to encrypt the message and B decrypts it using the private key, which only he knows. RSA can also be used to sign a message, so A can sign a message using their private key and B can verify it using A's public key.

We look into the mathematics behind the algorithm on our RSA Theory page.

Our pages on public key cryptography using discrete logarithms look at a different kind of public key cryptography which relies on the difficulty of solving the discrete logarithm problem.
This page modified on 9 June 2018 to use the MathJax display engine for mathematics.

## Contents

Affiliate disclosure: we get a small commission for purchases made through the above links

## An aside on Post-Quantum Cryptography

Are you interested in Post-Quantum Cryptography (PQC)? Then see our pages on SPHINCS+, a stateless hash-based signature scheme chosen as one of the first quantum-resistant signature algorithms in NIST's post-quantum cryptography standardization project.

## Key Generation Algorithm

This is the original algorithm.

1. Generate two large random primes, $p$ and $q$, of approximately equal size such that their product $n = pq$ is of the required bit length, e.g. 1024 bits. [See note 1].
2. Compute $n = pq$ and $\phi = (p-1)(q-1)$. [See note 6].
3. Choose an integer $e$, $1 < e < \phi$, such that $\gcd(e, \phi) = 1$. [See note 2].
4. Compute the secret exponent $d$, $1 < d < \phi$, such that $ed \equiv 1 \bmod \phi$. [See note 3].
5. The public key is $(n, e)$ and the private key $(d, p, q)$. Keep all the values d, p, q and $\phi$ secret. [Sometimes the private key is written as $(n, d)$ because you need the value of n when using d. Other times we might write the key pair as $((N, e), d)$.]
• n is known as the modulus.
• e is known as the public exponent or encryption exponent or just the exponent.
• d is known as the secret exponent or decryption exponent.

## A practical key generation algorithm

Incorporating the advice given in the notes below, a practical algorithm to generate an RSA key pair is given below. Typical bit lengths are $k = 1024, 2048, 3072, 4096,...$, with increasing computational expense for larger values. You will not go far wrong if you choose $e$ as 65537 (=0x10001) in step (1).

Algorithm: Generate an RSA key pair.
INPUT: Required modulus bit length, $k$.
OUTPUT: An RSA key pair $((N,e), d)$ where N is the modulus, the product of two primes ($N=pq$) not exceeding $k$ bits in length; $e$ is the public exponent, a number less than and coprime to $(p-1)(q-1)$; and $d$ is the private exponent such that $ed \equiv 1 \bmod {(p-1)(q-1)}$.
1. Select a value of $e$ from ${3, 5, 17, 257, 65537}$
2. repeat
3.    p ← genprime(k/2)
4. until $(p \bmod e) \ne 1$
5. repeat
6.    q ← genprime(k - k/2)
7. until $(q \bmod e) \ne 1$
8. N ← pq
9. L ← (p-1)(q-1)
10. d ← modinv(e, L)
11. return $(N, e, d)$

The function genprime(b) returns a prime of exactly $b$ bits, with the $b$th bit set to 1. Note that the operation $k/2$ is integer division giving the integer quotient with no fraction.

If you've chosen $e = 65537$ then the chances are that the first prime returned in steps (3) and (6) will pass the tests in steps (4) and (7), so each repeat-until loop will most likely just take one iteration. The final value of $N$ may have a bit length slightly short of the target $k$. This actually does not matter too much (providing the message m is always < N), but some schemes require a modulus of exact length. If this is the case, then just repeat the entire algorithm until you get one. It should not take too many goes. Alternatively, use the trick setting the two highest bits in the prime candidates described in note 1.

## Encryption

Sender A does the following:-

1. Obtains the recipient B's public key $(n, e)$.
2. Represents the plaintext message as a positive integer $m$ with $1 < m < n$ [see note 4].
3. Computes the ciphertext $c = m^e \bmod n$.
4. Sends the ciphertext $c$ to B.

## Decryption

Recipient B does the following:-

1. Uses his private key $(n, d)$ to compute $m = c^{d} \bmod n$.
2. Extracts the plaintext from the message representative $m$.

## Digital signing

Sender A does the following:-

1. Creates a message digest of the information to be sent.
2. Represents this digest as an integer $m$ between 1 and $n-1$ [See note 5].
3. Uses her private key $(n, d)$ to compute the signature $s = m^{d} \bmod n$.
4. Sends this signature $s$ to the recipient, B.

## Signature verification

Recipient B does the following (older method):-
1. Uses sender A's public key $(n, e)$ to compute integer $v = s^{e} \bmod n$.
2. Extracts the message digest $H$ from this integer.
3. Independently computes the message digest $H'$ of the information that has been signed.
4. If both message digests are identical, i.e. $H=H'$, the signature is valid.
More secure method:-
1. Uses sender A's public key $(n, e)$ to compute integer $v = s^{e} \bmod n$.
2. Independently computes the message digest $H'$ of the information that has been signed.
3. Computes the expected representative integer $v'$ by encoding the expected message digest $H'$.
4. If $v=v'$, the signature is valid.

## Notes on practical applications

1. To generate the primes $p$ and $q$, generate a random number of bit length $k/2$ where $k$ is the required bit length of the modulus $n$; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of $n$ is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again until you find a prime. This is $p$. Repeat for $q$ starting with a random integer of length $k-k/2$. If $p<q$, swop $p$ and $q$ (this only matters if you intend using the CRT form of the private key). In the extremely unlikely event that $p = q$, check your random number generator! Alternatively, instead of incrementing by 2, just generate another random number each time.

There are stricter rules in ANSI X9.31 to produce strong primes and other restrictions on $p$ and $q$ to minimise the possibility of certain techniques being used against the algorithm. There is much argument about this topic. It is probably better just to use a longer key length.

2. In practice, the value of $e$ is chosen first. Common choices for $e$ are 3, 5, 17, 257 and 65537 $(2^{16}+1)$. These particular values are chosen because they are primes and make the modular exponentiation operation faster, having only two bits of value 1.
--> Aside: These five numbers are the first five Fermat numbers, referred to as $F_{0}$ to $F_{4}$, where $F_x=2^{2^x} + 1$. Just be careful, these first five Fermat numbers are prime ("Fermat primes"), but the numbers $F_{5}$ and above are not prime. For example, $F_{5} = 4294967297 = 641 \times 6700417$.
The usual choice for $e$ is $F_{4} = 65537$ = 0x10001. Also, having chosen $e$, it is simpler to test whether $\gcd(e, p-1)=1$ and $\gcd(e, q-1)=1$ while generating and testing the primes in step 1. Values of $p$ or $q$ that fail this test can be rejected there and then.
Even better: if $e$ is an odd prime then you can do the less-expensive test $(p \bmod e) \ne 1$ instead of $\gcd(p-1,e) = 1$.
Why is that? If $e$ is an odd prime then $\gcd(p-1, e) \ne 1$ if and only if $p-1$ is a multiple of $e$. If $p-1$ is a multiple of $e$ then $p - 1 \equiv 0 \pmod e$ or $p \equiv 1 \pmod e$. Conversely, if $p\not\equiv 1 \pmod e$ then $p-1\not\equiv 0 \pmod e$ and $p-1$ is not a multiple of $e$. So $\gcd(p-1, e)=1$.
3. To compute the value for $d$, use the Extended Euclidean Algorithm to calculate $d = e^{-1} \bmod \phi$, also written $d = (1/e) \bmod \phi$. This is known as modular inversion. Note that this is not integer division. The modular inverse $d$ is defined as the integer value such that $ed = 1 \bmod \phi$. It only exists if $e$ and $\phi$ have no common factors.
For more details of the extended Euclidean algorithm, see our page The Euclidean Algorithm and the Extended Euclidean Algorithm which shows how to use the Euclidean algorithm, answer exam questions on it, and gives source code for an implementation.
4. When representing the plaintext octets as the representative integer $m$, it is important to add random padding characters to make the size of the integer $m$ large and less susceptible to certain types of attack. If m = 0 or 1 or n-1 there is no security as the ciphertext has the same value. For more details on how to represent the plaintext octets as a suitable representative integer $m$, see PKCS#1 Schemes below or the reference itself [PKCS1]. It is important to make sure that $m < n$ otherwise the algorithm will fail. This is usually done by making sure the first octet of m is equal to 0x00.
5. Decryption and signing are identical as far as the mathematics is concerned as both use the private key. Similarly, encryption and verification both use the same mathematical operation with the public key. That is, mathematically, for $m < n$,
$m = (m^{e}\bmod n)^{d} \bmod n = (m^{d} \bmod n)^{e} \bmod n$

However, note these important differences in implementation:-

• The signature is derived from a message digest of the original information. The recipient will need to follow exactly the same process to derive the message digest, using an identical set of data.
• The recommended methods for deriving the representative integers are different for encryption and signing (encryption involves random padding, but signing uses the same padding each time).
6. The original definition of RSA uses the Euler totient function $\phi(n) = (p-1)(q-1)$. More recent standards use the Charmichael function $\lambda(n) = \text{lcm}(p-1, q-1)$ instead. $\lambda(n)$ is smaller than $\phi(n)$ and divides it. The value of $d'$ computed by $d' = e^{-1} \bmod \lambda(n)$ is usually different from that derived by $d = e^{-1} \bmod \phi(n)$, but the end result is the same. Both $d$ and $d'$ will decrypt a message $m^{e} \bmod n$ and both will give the same signature value $s = m^{d} \bmod n = m^{d'} \bmod n$. To compute $\lambda(n)$, use the relation
$\lambda(n) = \dfrac{(p-1)(q-1)}{\gcd(p-1, q-1)}$.
7. You might ask if there is a way to find the factors of $n$ given just $d$ and $e$. This is possible.
For more details, see our page RSA: how to factorize N given d.

## Summary of RSA

• $n = pq$, where $p$ and $q$ are distinct primes.
• $\phi = (p-1)(q-1)$
• $e \lt n$ such that $\gcd(e, \phi)=1$
• $d = e^{-1} \bmod \phi$
• $c = m^{e} \bmod n, 1\lt m \lt n$
• $m = c^{d} \bmod n$

For more on the theory and mathematics behind the algorithm, see the RSA Theory page.

## Key length

When we talk about the key length of an RSA key, we are referring to the length of the modulus, $n$, in bits. The minimum recommended key length for a secure RSA transmission is currently at least 1024 bits. A key length of 512 bits is no longer considered secure, although cracking it is still not a trivial task for the likes of you and me. The longer your information needs to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.

There is one small area of confusion in defining the key length. One convention is that the key length is the position of the most significant bit in $n$ that has value '1', where the least significant bit is at position 1. Equivalently, key length = $\lceil \log_{2}(n+1))\rceil$, where $\lceil x\rceil$ is the ceiling function, the least integer greater than or equal to $x$. The other convention, sometimes used, is that the key length is the number of bytes needed to store $n$ multiplied by eight, i.e. $\lceil\log_{256}(n+1)\rceil \times 8$.

The key used in the RSA Example paper [KALI93] is an example. The modulus is represented in hex form as
0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB
The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position 508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method. You can get into difficulties with the X9.31 method for signatures if you use the latter convention.

### Minimum key lengths

The following table is taken from NIST's Recommendation for Key Management [NIST-80057]. It shows the recommended comparable key sizes for symmetrical block ciphers (AES and Triple DES) and the RSA algorithm. That is, the key length you would need to use to have comparable security.

Symmetric key algorithmComparable RSA key lengthComparable hash functionBits of security
2TDEA*1024SHA-180
3TDEA2048SHA-224112
AES-1283072SHA-256128
AES-1927680SHA-384192
AES-25615360SHA-512256
* 2TDEA is 2-key triple DES - see What's two-key triple DES encryption.

Note just how huge (and impractical) an RSA key needs to be for comparable security with AES-192 or AES-256 (although these two algorithms have had some weaknesses exposed recently; AES-128 is unaffected).

The above table is a few years old now and may be out of date. Existing cryptographic algorithms only get weaker as attacks get better.

## Computational Efficiency and the Chinese Remainder Theorem (CRT)

Key generation is only carried out occasionally and so computational efficiency is less of an issue.

The calculation $y = x^{e} \bmod n$ is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve, let $e$ be represented in base 2 as

$e = e_{k-1}e_{k-2}\ldots e_{1}e_{0}$

where $e_{k-1}$ is the most significant non-zero bit and bit $e_0$ the least.

set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n   /* square */
if e(j) == 1 then
y = y * x mod n  /* multiply */
end
return y

The time to carry out modular exponentation increases with the number of bits set to one in the exponent $e$. For encryption, an appropriate choice of $e$ can reduce the computational effort required to carry out the computation of $c = m^{e} \bmod n$. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.

The bits in the decryption exponent $d$, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. Don't make the mistake of trying to contrive a small value for $d$; it will not be secure.

An alternative method of representing the private key uses the The Chinese Remainder Theorem (CRT).

For an explanation of how the CRT is used with RSA, see Using the CRT with RSA.

The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is about four times faster overall than calculating $m = c^{d} \bmod n$. The extra values for the private key are:-

dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p  where p > q

where the (1/e) notation means the modular inverse (see note 3 above). These values are pre-computed and saved along with $p$ and $q$ as the private key. To compute the message m given c do the following:-

m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq

Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.

[2008-09-02] Chris Becke has pointed out that most large integer packages will fail when computing h if m1 < m2. This can be easily fixed by computing

h = qInv(m1 + p - m2) mod p

or, alternatively, as we do it in our BigDigits implementation of RSA,

if (bdCompare(m1, m2) < 0)
bdSubtract(m1, m1, m2);
/* Let h = qInv ( m_1 - m_2 ) mod p. */
bdModMult(h, qInv, m1, p);

## A very simple example of RSA encryption

This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 55 can probably even do it by hand).

1. Select primes p=11, q=3.
2. n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
3. Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = (1/e) mod phi = (1/3) mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
5. Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works.
Now say we want to encrypt the message m = 7,
$c = m^e \bmod n = 7^3 \bmod 33 = 343 \bmod 33 = 13$.
Hence the ciphertext c = 13.
To check decryption we compute
$m' = c^d \bmod n = 13^7 \bmod 33 = 7$.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
$a = bc \bmod n = (b \bmod n)\cdot (c \bmod n) \bmod n$
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
Note that any number can be expressed as a sum of powers of 2. In particular 7 = 4 + 2 + 1.
So first compute values of $13^{2}, 13^{4}, 13^{8}, \ldots$ by repeatedly squaring successive values modulo 33.
$13^{2} = 169 \equiv 4, 13^{4} = 4.4 = 16, 13^{8} = 16.16 = 256 \equiv 25$.
Then, since 7 = 4 + 2 + 1, we have $m' = 13^{7} = 13^{(4+2+1)} = 13^{4}.13^{2}.13^{1}$
$\equiv 16 \times 4 \times 13 = 832 \equiv 7 \pmod{33}$

Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get

m  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
c  0  1  8 27 31 26 18 13 17  3 10 11 12 19  5  9  4

m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15  7  2  6 25 32

Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any $n$, no matter how large. But in practice, these shouldn't be a problem when we use large values for $n$ in the order of several hundred bits.

If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers $m_{1}, m_{2}, \ldots$

(9,6,13,13,16,24,16,19,13,5)
Using our table above, we obtain ciphertext integers $c_{1}, c_{2}, \ldots$
(3,18,19,19,4,30,4,28,19,26)
Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption.

Remember that calculating $m^{e} \bmod n$ is easy, but calculating the inverse $c^{-e} \bmod n$ is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.

## A slightly less simple example of the RSA algorithm

This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block. Please note that this method is not secure in any way. It just shows another example of the mechanism of RSA with small numbers.

For this example, to keep things simple, we'll limit our characters to the letters A to Z and the space character.

ATTACK AT SEVEN = ATT ACK _AT _SE VEN

In the same way that any decimal number can be represented uniquely as the sum of powers of ten, e.g. $135 = 1 \times 10^{2} + 3 \times 10^{1} + 5$,
we can represent our blocks of three characters as the sum of powers of 27 using SPACE=0, A=1, B=2, C=3, .. E=5, .. K=11, .. N=14, .. S=19, T=20, .. V=22, ..., Z=26.

ATT ⇒  1 x 27^2 + 20 x 27^1 + 20 = 1289
ACK ⇒  1 x 27^2 +  3 x 27^1 + 11 = 821
_AT ⇒  0 x 27^2 +  1 x 27^1 + 20 = 47
_SE ⇒  0 x 27^2 + 19 x 27^1 +  5 = 518
VEN ⇒ 22 x 27^2 +  5 x 27^1 + 14 = 16187

Using this system of integer representation, the maximum value of a block (ZZZ) is $27^{3}-1 = 19682$, so we require a modulus n greater than this value.

1. We choose e = 3
2. We select primes p=173 and q=149 and check
• gcd(e, p-1) = gcd(3, 172) = 1 ⇒ OK
• gcd(e, q-1) = gcd(3, 148) = 1 ⇒ OK.
3. Thus we have $n = pq = 173 \times 149 = 25777$, and
$\phi = (p-1)(q-1) = 172 \times 148 = 25456$.
4. We compute $d = e^{-1} \bmod \phi = 3^{-1} \bmod 25456 = 16971$.
• Note that $ed = 3 \times 16971 = 50913 = 2 \times 25456 + 1$
• That is, $ed \equiv 1 \bmod 25456 \equiv 1 \bmod \phi$
5. Hence our public key is (n, e) = (25777, 3) and our private key is (n, d) = (25777, 16971). We keep the values of p, q, d and φ secret.

To encrypt the first integer that represents "ATT", we have
$c = m^{e} \bmod n = 1289^{3} \bmod 25777 = 18524$.

Overall, our plaintext ATTACK AT SEVEN is represented by the sequence of five integers $m_{1}, m_{2}, m_{3}, m_{4}, m_{5}$:

m_i = (1289, 821, 47, 518, 16187)

We compute corresponding ciphertext integers $c_{i} = m_{i}^{e} \bmod n$, (which is still possible by using a calculator, honest):

$c_{1} = 1289^{3} \bmod 25777 = 18524 \\ c_{2} = 821^{3} \bmod 25777 = 7025 \\ c_{3} = 47^{3} \bmod 25777 = 715 \\ c_{4} = 518^{3} \bmod 25777 = 2248 \\ c_{5} = 16187^{3} \bmod 25777 = 24465$

We can send this sequence of integers, $c_{i}$, to the person who has the private key.

c_i = (18524, 7025, 715, 2248, 24465)

We can compute the inverse of these ciphertext integers using $m = c^{d} \bmod n$ to verify that the RSA algorithm still holds. However, this is now outside the realm of hand calculations.

For example, to compute $18524^{16971} \bmod 25777$, use the bd_modexp command:

bd_modexp 18524 16971 25777
18524^16971 mod 25777 = 1289
You should get the results:

$m_{1} = 18524^{16971} \bmod 25777 = 1289 \\ m_{2} = 7025^{16971} \bmod 25777 = 821 \\ m_{3} = 715^{16971} \bmod 25777 = 47 \\ m_{4} = 2248^{16971} \bmod 25777 = 518 \\ m_{5} = 24465^{16971} \bmod 25777 = 16187 \\$

To convert these integers back to the block of three letters, do the following. For example, given m = 16187,
16187 ÷ 27^2 = 16187 ÷ 729 = 22 rem 149, 22 → 'V'
149   ÷ 27^1 = 149   ÷ 27  = 5 rem 14,    5 → 'E'
14    ÷ 27^0 = 14    ÷ 1   = 14 rem 0,   14 → 'N'
Hence the integer m = 16187 represents the string "VEN".
Similarly, m = 47 is encoded as follows:
47 ÷ 27^2 = 0 rem 47, 0  → SPACE;
47 ÷ 27^1 = 1 rem 20, 1  → 'A';
20 ÷ 27^0 = 20 rem 0, 20 → 'T'
giving the string "_AT".

Question: Why can't we use this method of encoding integers into blocks of three letters to encode the ciphertext?

Note that this example is a very insecure method of encryption and should not be used in practice. We can easily factorize the modulus and hence break the cipher.

### Factorising a small RSA modulus

Starting with the knowledge that the modulus 25777 is the product of exactly two distinct prime numbers, and that one of these must be less than its integer square root (why?), a little testing of suitable candidates from a table of prime numbers will get you the answer pretty quickly.

Given n = 25777, compute √25777 = 160.55, and then work downwards through the prime numbers < 160, i.e. (157, 151, 149, 139, ...), and try to divide into $n$ in turn:
157: 25777 / 157 = 164 remainder 29, so not a factor;
151: 25777 / 151 = 170 remainder 107, so not a factor;
149: 25777 / 149 = 173 exactly, so we have it.

You could also write a simple computer program to factor n that just divides it by every odd number starting from 3 until it either finds an exact factor or stops when it reaches a number greater than the square root of n.

## A real example

In practice, we use a modulus of size in the order of 1024 bits. That is a number over 300 decimal digits long. One example is

n =
11929413484016950905552721133125564964460656966152763801206748195494305685115033
38063159570377156202973050001186287708466899691128922122454571180605749959895170
80042105263427376322274266393116193517839570773505632231596681121927337473973220
312512599061231322250945506260066557538238517575390621262940383913963

This is composed of the two primes

p =
10933766183632575817611517034730668287155799984632223454138745671121273456287670
008290843302875521274970245314593222946129064538358581018615539828479146469

q =
10910616967349110231723734078614922645337060882141748968209834225138976011179993
394299810159736904468554021708289824396553412180514827996444845438176099727

With a number this large, we can encode all the information we need in one big integer. We put our message into an octet string and then convert to a large integer.

Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES or AES-128. We then use the much slower public key encryption algorithm to encrypt just the session key.

The sender A then transmits a message to the recipient B in a format something like this:-

Session key encrypted with RSA = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx

The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the private key.

If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.

When signing, it is usual to use RSA to sign the message digest of the message rather than the message itself. A one-way hash function like SHA-1 or SHA-256 is used. The sender A then sends the signed message to B in a format like this

Hash algorithm = hh
Message content = xxxxxxxxx...xxx
Signature = digest signed with RSA = xxxx

The recipient will decrypt the signature to extract the signed message digest, $m$; independently compute the message digest, $m'$, of the actual message content; and check that $m$ and $m'$ are equal. Putting the message digest algorithm at the beginning of the message enables the recipient to compute the message digest on the fly while reading the message.

CAUTION: We cannot emphasise enough that you never use the unadorned versions of RSA described in the simple examples above. You must use a proper scheme like PCKS#1 below. In particular when encrypting a message, you must use random padding.

## PKCS#1 Schemes

The most common scheme using RSA is PKCS#1 version 1.5 [PKCS1]. This standard describes schemes for both encryption and signing. The encryption scheme PKCS#1v1.5 has some known weaknesses, but these can easily be avoided. See Weaknesses in RSA below.

There is an excellent paper by Burt Kalinski of RSA Laboratories written in the early 1990s [KALI93] that describes in great detail everything you need to know about encoding and signing using RSA. There are full examples right down to listing out the bytes. OK, it uses MD2 and a small 508-bit modulus and obviously doesn't deal with refinements built up over the last decade to deal with more subtle security threats, but it's an excellent introduction.

The conventions we use here are explained below in Notation and Conventions.

### Encryption using PKCS#1v1.5

Algorithm: Encryption using PKCS#1v1.5
INPUT: Recipient's RSA public key, (n, e), of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11.
OUTPUT: Encrypted data block of length k bytes
1. Form the k-byte encoded message block, EB,
EB = 00 || 02 || PS || 00 || D

where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e. at least eight random bytes).
2. Convert the byte string, EB, to an integer, m, most significant byte first,
m = StringToInteger(EB)

3. Encrypt with the RSA algorithm
c = m^e mod n

4. Convert the resulting ciphertext, $c$, to a $k$-byte output block, OB
OB = IntegerToString(c, k)

5. Output OB.

The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer. See What is the difference between a bit string and an integer?

‡2012-05-23: Thanks to "dani torwS" for pointing out a typo in the formula.

### Worked Example

Bob's 1024-bit RSA encryption key in hex format:

n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=010001
d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
A randomly-generated one-off session key for AES-128 might be
The encoded message block, EB, after encoding but before encryption, with random padding bytes shown in green,
E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038
After RSA encryption, the output is
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E

The above hex data in C format.

Note that the output for encryption will be different each time (or should be!) because of the random padding used.

### Encrypting a message

For a plaintext message, say,
PT="Hello world!"
that is, the 12 bytes in hex format,
PT=48656C6C6F20776F726C6421
Then, using the 128-bit session key from above,
and the uniquely-generated 128-bit initialization vector (IV)
IV=5732164B3ABB6C4969ABA381C1CA75BA
the ciphertext using AES-128 in CBC mode with PKCS#5 padding is,
CT=67290EF00818827C777929A56BC3305B

The sender would then send a transmission to the recipient (in this case, Bob) including the following information in some agreed format

Recipient: Bob
Key Encryption Algorithm: rsaEncryption
Encrypted Key:
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
Content Encryption Algorithm: aes128-cbc
IV: 5732164B3ABB6C4969ABA381C1CA75BA
Encrypted Content:
67290EF00818827C777929A56BC3305B

The usual formats used for such a message are either a CMS enveloped-data object or XML, but the above summary includes all the necessary info (well, perhaps "Bob" might be defined a bit more accurately).

Cryptographic Message Syntax (CMS) [CMS] is a less-ambiguous version of the earlier PKCS#7 standard (also of the same name) and is designed to be used in S/MIME messages. CMS enveloped-data objects (yes, that's enveloped not encrypted) use ASN.1 and are encoded using either DER- or BER-encoding. (DER-encoding is a stricter subset of BER).

The terminology for CMS and ASN.1 may sound messy, but the end results are well-defined and universally-accepted. On the other hand, the XML cryptographic standards are, to be honest, a complete mess: see XML is xhite. Pretty Good Privacy (PGP) also has a format for RSA messages, although PGP stopped using RSA because of patent issues back in the 1990s.

Nothing, of course, stops you and your recipient from agreeing on your own format and using that. But be careful, even the experts get these things wrong and accidentally give away more than they realise.

### Signing using PKCS#1v1.5

Algorithm: Signing using PKCS#1v1.5
INPUT: Sender's RSA private key, (n, d) of length k = |n| bytes; message, M, to be signed; message digest algorithm, Hash.
OUTPUT: Signed data block of length k bytes
1. Compute the message digest H of the message,
H = Hash(M)

2. Form the byte string, T, from the message digest, H, according to the message digest algorithm, Hash, as follows
HashT
MD530 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
SHA-130 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H
SHA-22430 2d 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1c || H
SHA-25630 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H
SHA-38430 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H
SHA-51230 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
where T is an ASN.1 value of type DigestInfo encoded using the Distinguished Encoding Rules (DER).
3. Form the k-byte encoded message block, EB,
EB = 00 || 01 || PS || 00 || T

where || denotes concatenation and PS is a string of bytes all of value 0xFF of such length so that |EB|=k.
4. Convert the byte string, EB, to an integer m, most significant byte first,
m = StringToInteger(EB)

5. Sign with the RSA algorithm
s = m^d mod n

6. Convert the resulting signature value, s, to a k-byte output block, OB
OB = IntegerToString(s, k)

7. Output OB.

### Worked Example

Alice's 1024-bit RSA signing key in hex format:

n=
E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D
12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CF
C6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6
F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F
e=010001
d=
F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282D
B7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21
The message to be signed is, of course,
M="abc"
that is, the 3 bytes in hex format,
M=616263
The message digest algorithm is SHA-1, so
H = Hash("abc") = A9993E364706816ABA3E25717850C26C9CD0D89D
The DigestInfo value for SHA-1 is
T=
3021300906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9C
D0D89D
The encoded message block, EB, after encoding but before signing is
0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00302130
0906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9CD0D89D
After RSA signing, the output is
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F

The above hex data in C format.

## Weaknesses in RSA

Small encryption exponent
If you use a small exponent like e=3 and send the same message to different recipients and just use the RSA algorithm without adding random padding to the message, then an eavesdropper could recover the plaintext.
For an example of this, see Cracking RSA on our page on the The Chinese Remainder Theorem.
Small encryption exponent and small message
If you use $e=3$ and just encrypt a small message $m$ without padding where $m^{3} < n$ then your ciphertext $c$ can easily be broken by simply computing its real cube root. For example, if we have the public key $(n, e) = (25777, 3)$ and just encrypt the small message $m = 10$ then the ciphertext is $c = 1000$. The secure properties of RSA encryption only work if $m^{e} > n$.
Using the same key for encryption and signing
Given that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted message using the same key then she gets the original.
Using a common modulus for different users
Do not use the same modulus $n$ with different $(e_{i}, d_{i})$ pairs for different users in a group. Given his own pair $(e_{1}, d_{1})$, user 1 can factorize the common $n$ into $p$ and $q$ and hence compute the private exponents $d_{i}$ of all the other users.
For more details, see our page RSA: how to factorize N given d.
Acting as an oracle
There are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. So don't do that.

### Solutions

1. Don't use the same RSA key for encryption and signing.
2. Don't encrypt or sign a blind message.
3. If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
4. Always format your input before encrypting or signing.
5. Always add fresh random padding - at least 8 bytes - to your message before encrypting.
6. When decrypting, check the format of the decrypted block. If it is not as expected, return an error message, not the decrypted string.
7. Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid Signature".

The underlying RSA operations

$c = m^{e} \bmod n, \; m' = c^{d} \bmod n; \quad s = m^{d} \bmod n, \; s' = s^{e} \bmod n$

are always the same, but there are many variants of how these can be used inside an encryption or digital signature scheme. Here are some of them.

### RSAES-OAEP

The OAEP encoding technique for encryption is described in PKCS#1 version 2 and in IEEE P136. It is more secure than the PKCS#1v1.5 encoding method described above, perhaps provably secure. The encoding technique involves a mask generation function (MGF) based on a hash function and there is no obvious structure in the encoded block, unlike the PKCS#1v1.5 encoding method. Despite being the recommended method for the last decade, OAEP is not used in practice as much as you'd expect. In fact, hardly at all. That said, if you have a choice in the matter, we recommend that you should use OAEP if you can.

### RSASSA-PSS

The PSS encoding method is used to encode before creating a signature. The technique is described in PKCS#1v2.1 and is similar in design to the OAEP encoding used for encryption involving an MGF based on a hash function. However, there were active patents associated with this method until recently and so it is still not supported well. There are currently no known weaknesses with the PKCS#1v1.5 signature scheme.

### X9.31 Signature Scheme

ANSI standard X9.31 [AX931] requires using strong primes derived in a way to avoid particular attacks that are probably no longer relevant. X9.31 uses a method of encoding the message digest specific to the hash algorithm. It expects a key with length an exact multiple of 256 bits. The same algorithm is also specified in P1363 [P1363] where it is called IFSP-RSA2. The scheme allows for the public exponent to be an even value, but we do not consider that case here; all our values of $e$ are assumed to be odd. The message digest hash, H, is encapsulated to form a byte string as follows

EB = 06 || PS || 0xBA || H || 0x33 || 0xCC

where PS is a string of bytes all of value 0xBB of length such that |EB|=|n|, and 0x33 is the ISO/IEC 10118 part number for SHA-1. The byte string, EB, is converted to an integer value, the message representative, f.

† ISO/IEC 10118 part numbers for other hash functions are: SHA-1=0x33, SHA-256=0x34, SHA-384=0x36, SHA-512=0x35, RIPEMD=0x31.

Algorithm: Forming an X9.31/RSA2 signature value from the message representative (for odd $e$).
INPUT: Signer's RSA private key, (n, d); integer, f, where $0 \le f < n$ and $f ≡ 12 \pmod{16}$.
OUTPUT: Signature, an integer s where $0 \le s < n/2$, i.e. a value at least one bit shorter than $n$.
1. $t = f^{d} \bmod n$
2. $s = \min(t, n-t)$
3. Output $s$.

The integer, $s$, is converted to a byte string of length |n| bytes.
Algorithm: Extracting the message representative from an X9.31/RSA2 signature value (for odd $e$).
INPUT: Signer's RSA public key, (n, e); signature, s.
OUTPUT: Message representative, f, such that $f \equiv 12 \pmod{16}$, or "invalid signature".
1. If $s$ is not in $[0,(n-1)/2]$, output "invalid signature" and stop.
2. Compute $t = s^{e} \bmod n$
3. If $t \equiv 12 \pmod{16}$ then let $f = t$.
4. Else let $f = n-t$. If $f \not\equiv 12 \pmod{16}$, output "invalid signature" and stop.
5. Output $f$.

The integer $f$ is converted to a byte string of length |n| bytes and then parsed to confirm that all bytes match the required format
EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
If not, output "invalid signature" and stop; otherwise output the extracted message digest hash, $H$.

### ISO/IEC 9796

IOS/IEC 9796 is an old standard devised before there was a recognised message digest function like MD5 or SHA-1. It allows the entire message to be recovered. Unfortunately, it is considered broken for signing plain text messages, but is still OK for signing message digest values. It is used in the AUTACK scheme described in [EDIFACT].

The encapsulation mechanism weaves the input bytes into a format exactly one bit shorter than the RSA key. The signing mechanism is similar to that in ANSI X9.31 described above, but the message representative, $f$, is required to be $f \equiv 6 \pmod{16}$, instead of modulo 12. In other words, make sure the last 4 bits are equal to 0x6 instead of 0xC.

### RSA-KEM

The RSA-KEM Key Transport Algorithm encrypts a random integer with the recipient's public key, and then uses a symmetric key-wrapping scheme to encrypt the keying data. KEM stands for Key Encapsulation Mechanism. The general algorithm is as follows

1. Generate a random integer $z$ between 0 and $n-1$.
2. Encrypt the integer $z$ with the recipient's RSA public key: $c = z^{e} \bmod n$.
3. Derive a key-encrypting key KEK from the integer $z$.
4. Wrap the keying data using KEK to obtain wrapped keying data WK.
5. Output $c$ and WK as the encrypted keying data.

This method has a higher security assurance than PKCS#1v1.5 because the input to the underlying RSA operation is random and independent of the message, and the key-encrypting key KEK is derived from it in a strong way. The downside is that you need to implement a key derivation method (of which there are many varieties) and a key wrapping algorithm. The encoding of the final data into the recommended ASN.1 format is messy, too. For more details, see the latest version of [CMSRSAKEM].

### Ferguson-Schneier Encryption

In their book [FERG03], Niels Ferguson and Bruce Schneier suggest a much simpler method of encryption. They suggest using the same modulus $n$ for both encryption and signatures but to use $e=3$ for signatures and $e=5$ for encryption. You need to make sure that the modulus $n = pq$ satisfies both $\gcd(3,(p-1)(q-1))=1$ and $\gcd(5,(p-1)(q-1))=1$.

Their method uses RSA to encrypt a random integer and use a hash function to derive the actual content encryption key, thus removing any structural similarities between the actual CEK and the data encrypted by the RSA. They recommend using the function, Hash(x):=SHA256(SHA256(x)), for hashing data.

Algorithm: Ferguson-Schneier Encrypt Random Key with RSA.
INPUT: Recipient's RSA public key, (n, e).
OUTPUT: Content encryption key, CEK; RSA-encrypted CEK, $c$.
1. Compute the exact bit length of the RSA key, $k = \lceil log_{2}(n+1)\rceil$.
2. Choose a random $r$ in the interval $[0, 2^{k}-1]$.
3. Compute the content encryption key by hashing $r$, CEK=Hash(r).
4. $c = r^{e} \bmod n$.
5. Output CEK and $c$.

For a plaintext message, $m$, the transmission sent to the recipient is IntegerToString(c)||E_CEK(m), where $E_{CEK}(m)$ is the result of encrypting $m$ with a symmetrical encryption algorithm using key, CEK. Given that the recipient knows the size of the RSA key and hence the exact number of bytes needed to encode $c$, it is a simple matter to parse the input received from the sender.

For example code of this algorithm in Visual Basic (both VB6 and VB.NET) using our CryptoSys PKI Toolkit, see Ferguson-Schneier RSA Encryption.

## Notation and Conventions

• A || B denotes concatenation of byte (or bit) strings A and B.
• |B| denotes the length of the byte (or bit) string B in bytes.
• |n| denotes the length** of the non-negative integer n in bytes, $|n| = \lceil log_{2}(n+1)\rceil$.
• IntegerToString(i, n) is an n-byte encoding of the integer i with the most significant byte first (i.e. in "big-endian" order). So, for example,
IntegerToString(1,4)="00000001"
IntegerToString(7658,3)="001DEA"

• StringToInteger(S) is the integer represented by the byte string S with the most significant byte first.
• $\lceil x\rceil$ is the smallest integer, $n$, such that $n \ge x$.

** Strictly speaking, this is the length of the shortest byte string that can encode the integer.

## What is the difference between a bit string and an integer?

A string is a contiguous sequence of symbols, so the string "cat" is a sequence of the letters 'c', 'a' and 't'. A bit string is sequence of binary digits (bits) '0' and '1'. A byte string is similar except it consists of bytes, which are in turn sequences of 8 bits. So a bit string and a byte string are the same thing, except the latter is restricted to multiples of 8 bits. For example, using hexadecimal representation, the byte string "8002EA" is a sequence of 3 bytes, 0x80, 0x02 and 0xEA; and is equal to the bit string "100000000000001011101010".

A note on notation: To differentiate between byte strings and integers here, we show byte strings in hexadecimal representation inside quotes, so "8002EA" denotes the string of three consecutive bytes with hexadecimal values 80, 02 and EA, respectively. We use the "0x" prefix to denote integers, so 0x80 denotes the integer with hexadecimal value 80 (decimal 128), and 0x8002EA denotes the integer with hexadecimal value 8002EA (decimal 8389354). Everything here is in "big-endian" order, with the left-most bits the most significant.

A string can be split into sub-strings (e.g. "8002" and "EA") and two strings can be concatenated (joined up) to make another string. The order of symbols is important. The usual convention is to write byte strings with the most significant byte first ("big-endian" or network byte order).

An integer is a whole number that obeys the usual rules of integer arithmetic ($1+1=2,\; 5-2=3,\; 3\times 2=6,\; 6/3=2$) and modular arithmetic ($10+6\equiv 4 \pmod{12})$). There is no limit in theory as to how large an integer can be: you can always add one to any integer. The integer 8,389,354 in decimal is the same as the number 0x8002EA in hexadecimal notation, but is not the same as the byte string "8002EA", even though it looks the same and may well be stored in your computer in the same form.

You can increment the integer 8389354 to get 8389354+1=8389355 (0x8002EB); but you cannot "increment" the byte string "8002EA". On the other hand, you can concatenate the byte strings "8002" and "EA" to make "8002EA"; but the integers 8389 and 354 do not add to make 8389354. The byte string "00008002EA" is strictly not the same as "8002EA" (the former has two extra bytes of value 0x00 at the start); but the integers 0x008002EA and 0x8002EA are equal (leading zeros do not count).

With RSA encryption, we typically want to encrypt a session key which is a bit string, but the RSA operation $c = m^e \bmod n$ is done with integers, so we need to represent the bit string as an integer first (in practice, we usually add some random bytes and other padding, but we'll ignore that for the time being). Once the RSA operation has been completed, we have another integer, c, but we need to store the result as a bit string, so we encode the integer as a bit (byte) string and pass that string onto our recipient.

Example: Suppose we wish to encrypt the 3-byte/24-bit key bit string "8002EA" using the RSA public key (n=25009997=0x017D9F4D, e=5). For simplicity in this insecure example, we will use the basic RSA algorithm with no padding.

1. The message block is the byte string "8002EA".
2. Compute the message representative
m = StringToInteger("8002EA") = 8389354

3. Encrypt with the RSA algorithm
c = 8389354^5 mod 25009997 = 2242555

4. Encode the result as a byte string
OB = IntegerToString(2242555, 4) = 002237FB

Note that the maximum length of the output block is 4 bytes, because the largest possible integer result is 0x017D9F4C ($= n-1$), which requires 4 bytes to store in encoded form.

† Thanks to "doctorjay" for pointing out that e=3 did not work for the earlier version of this example.

## Implementation in C and VB

We show an example implementation of the RSA algorithm in C in our BigDigits library. It's not necessarily the most efficient way, and could be improved in its security, but it shows the maths involved. Look in the BigDigits Test Functions.

There is an example in VB6/VBA code at RSA and Diffie-Hellman in Visual Basic.

For a professional implementation, see our commercial CryptoSys PKI Toolkit which can be used with Visual Basic, VB6, VBA, VB2005+, C/C++ and C# applications. There are examples using the "raw" RSA functions to carry out RSA Techniques and Doing RSA Encryption and Signing with C#.

## References

• [AX931] ANSI X9.31-1998 Digital Signatures using Reversible Public Key Cryptography for the Financial Services Industry (rDSA), Appendix A, American National Standards Institute, 1998.
• [CMS] RFC 5652. Cryptographic Message Syntax (CMS), R. Housley, September 2009 (obsoletes RFC3852, RFC3369, RFC2630).
• [CMSRSAKEM] RFC 5990 Use of the RSA-KEM Key Transport Algorithm in the Cryptographic Message Syntax (CMS), J. Randall, B.Kaliski, J. Brainard, S. Turner. September 2010.
• [COCK73] Clifford Cocks. A Note on 'Non-Secret Encryption', CESG Research Report, 20 November 1973.
• [EDIFACT] UN/EDIFACT Finance Group D6 SWG-F. Recommended Practice For Message Flow And Security For EDIFACT Payments, Version 2v03, 1 October 2000.
• [FERG03] Niels Ferguson and Bruce Schneier, Practical Cryptography, Wiley, 2003. Note that this book has since been re-issued in 2010 almost unchanged as Cryptography Engineering by Niels Ferguson, Bruce Schneier and Tadayoshi Kohno.
• [KALI93] Burton Kalinski. Some Examples of the PKCS Standards, RSA Laboratories, 1999, <link>.
• [NIST-80057] NIST Special Publication 800-57, Recommendation for Key Management - Part 1: General (Rev. 4), Elaine Barker et al, National Institute of Standards and Technology, January 2016, <link>.
• [P1363] IEEE P1363 Standard Specifications for Public Key Cryptography, IEEE, November 1993.
• [PKCS1] RSA Laboratories. PKCS #1 Cryptography Standard Version 2.2, October 2012. Republished as RFC 8017.
• [RIVE78] R. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21 (2), pp. 120-126, February 1978, <link>.

## Author

The content of this page is all original work written by David Ireland, who reserves all intellectual rights. You may freely link to this page. You may use parts of the work for fair dealing for the purposes of research or private study as permitted under copyright law, but you may not post any part of this content on another web site without the explicit permission in writing of the author.

## Feedback

[Go to last comment]

I learned this site from http://www.issociate.de/board/post/267506/Encryption_size.html. This is an excellent and indepth artical.

mimime | usa - Fri, Feb 19 2010 00:30 GMT

it is one of the most great tutorial about RSA , it was very helpful

Thank you very much

mallek balli | libya - Wed, Mar 10 2010 16:39 GMT

I PREPARED MY WHOLE PROJECT ABOUT RSA COMPLETLY,,,,,,,,, THANQ VERY MUCH

MANDA GOPAL | INDIA - Sun, Mar 14 2010 04:52 GMT

this explanation is better than the best

rishi | - Sat, Mar 20 2010 18:23 GMT

this is awsome article thank u very much

yogesh kumbhar | - Tue, Mar 23 2010 06:22 GMT

tHANKS A LOt....

vijac | iNDIA - Fri, Mar 26 2010 00:48 GMT

thankyou so much for such a great content....... now i can understand rsa in a better way and can prepare my project.......

shivani anand | - Sat, Mar 27 2010 14:14 GMT

really useful tutorial on rsa encryption - cheers! im a bit confused about calculating d from ed=1%phi though. in your example phi=20 and e=3 so i would have thought 1%20 = 1, therefore 3d=1, therefore d = 1/3. i know im wrong since this doesnt work, however i cant seem to make sense of it. if i try the other formula d=(e^-1)%phi then i get d=(3^-1)%20 = (1/3)%20 = 0??? im a bit stuck!

pete | australia - Thu, Apr 1 2010 09:48 GMT

pete, all calculations are done on integers. "1/e mod n" means "inverse of e, modulo n" (if it exists) and NOT a division of 1 by e. You cannot skip "mod n" part.

janisozaur | - Sat, Apr 3 2010 18:06 GMT

Be careful with the meaning of (mod). It's not the same as the % operator. We're also talking non-negative whole numbers here, so no fractions.

ed \equiv 1 (mod phi)

given e=3 and phi=20 means find an integer d such that when ed is divided by 20, the remainder is 1.

Try d=1, ed=3x1=3, 3 divided by 20 is 0 remainder 3, so no good
Try d=2, ed=3x2=6, 6 divided by 20 is 0 remainder 6.
...
Try d=6, ed=3x6=18, 18 divided by 20 is 0 remainder 18.
Try d=7, ed=3x7=21, 21 divided by 20 is 1 remainder 1 => HOORAY.

So d=7 satisfies the relationship. (There are other, larger values of d that work, too).

Dave | Moderator - Sun, Apr 4 2010 01:56 GMT

It's a great content, vry easy to understand and very helpfull.

bejhe | Indonesia - Thu, Apr 8 2010 09:06 GMT

In the Key Generation Algorithm section in point 2 you define

phi = (p-1)(q-1)

However, in a book of mine (by Ferguson and Schneier) it is mentioned that this value should actually be defined as

phi = lcm(p-1, q-1)

Now, having read all the values from gpg private key (see rfc 4880) it seems, that indeed

ed = 1 (mod lcm(p-1, q-1))

and if phi is defined in the former way, it produces some very large values (which only matters in a way that is unequal to 1). All other conditions are fulfilled - they are both the same in the book and here. Why is that and which is more correct?

janisozaur | Poland - Thu, Apr 15 2010 08:05 GMT

@janisozaur: Both methods are equally valid and both give identical results as far as encryption and decryption go. Bruce Schneier's earlier book "Applied Cryptography" used the (p-1)(q-1) form, as does Menezes (see ch 8). You will get different values for d, but it does not matter, as they both work and give exactly the same results.

IOHO it's not worth the extra hassle to compute the LCM, but you could -- it will always be at least half the value [why?] but this really doesn't matter with practical key sizes where you save one or two bits out of 2000.

Dave | Moderator - Sun, Apr 18 2010 10:49 GMT

SAI | CHENNAI - Sat, Apr 17 2010 17:27 GMT

All at one place. Good article.

Rajendra | - Mon, May 24 2010 06:38 GMT

a gr8 collection on RSA...but i dint find the strength of RSA....pls provide it as soon as possible

jigar | - Mon, May 31 2010 05:30 GMT

Thank you so much for this amazing article.

Is answer to "Question: Why couldn't we use e=17 here?" "Because there is no such d = 17^-1 mod 17680" ?

Another question, why is message to be signed padded with FF bytes? I understand that we need to expand it, but when encrypting we use random bytes, which is reasonable. Why can't (shouldn't) we use random bytes for signing as well?

Andrey | - Sat, Jun 5 2010 19:08 GMT

@Andrey. e=17: Yes, and that is because gcd(17,17680)>1 since phi = 17680 = 1040 x 17.

Padding with FF: Because we want the value of the signature to always be the same. Remember there is no secrecy with a signature. But for encryption we want to hide any structure and so we use random bytes (in fact, for encryption, if you don't use random bytes you can leak information).

Dave | Moderator - Sun, Jun 6 2010 04:40 GMT

Great article.. very informative!!

Rachel | - Fri, Jun 11 2010 09:42 GMT

Hi.

I really appreciated this article, but i have a doubt. Given an encrypted message (m), how do i estimate the key size, supposing i don't know the modulus.

Thanks, i really need this information.

Larissa Eglem | Brazil - Thu, Jul 8 2010 21:19 GMT

can u explain this method with different example for RSA Algorithm.

for eg. p=17 q=23

Thiyagu | Namakkal - Mon, Jul 12 2010 08:59 GMT

Excellent article! Thank you!

Quick question: on the alternative Chinese Remainder Theorem it is stated that "dP = (1/e) mod (p-1)". My understanding is that all divisions are integer, therefore "1/e" will almost always be zero (unless e is equal to 1, which will normally be the case). What am I missing?

Thanks again!

Jeff | - Thu, Aug 5 2010 13:28 GMT

@Jeff. "1/e" is the modular inverse, also written as e^{-1}. To use a simpler notation,

d = (1/e) mod n

is defined as the value of d such that ed = 1 mod n.

See the discussion around April 3 by pete and janisozaur.

Dave | Moderator - Sat, Aug 7 2010 20:34 GMT

sid | - Fri, Jun 25 2010 08:35 GMT

@sid. See our new page https://www.di-mgt.com.au/euclidean.html

Dave | Moderator - Sat, Aug 14 2010 02:53 GMT

Really excellent explanation, thank-you.

One thing I didn't understand: you say (in https://www.di-mgt.com.au/rsa_alg.html#simpleexample) that p=3,q=11 is the lowest value of n=pq for which RSA works.

I tried p=3,q=5 (n=15) and, using e=d=3, encrypted and decrypted all non-trivial messages m=2..(n-2) and it all seemed to work!

Simon | Bath, UK - Sat, Sep 11 2010 21:09 GMT

@Simon. Perhaps a better phrase would be "for which RSA is interesting".

With n=15 you always have e = d, so the private key is the same as the public one. So it "works" but isn't much use for a cryptosystem.

With n=15, e=3, all but 6 out of 15 ciphertexts are the same as m, and those that are different are related (eg 2^3 mod 15 = 8 and 8^3 mod 15 =2).

With n=15, e=5, *all* ciphertexts are the same, because raising to the 5th power modulo 15 is the identity transformation.

Dave | Moderator - Wed, Sep 15 2010 10:30 GMT

By identity transformation we mean a^5 == a (mod 15) for all integers a. (using == to mean 'is congruent to')

Proof. We have a^5 == a (mod 5) and a^3 == a (mod 3) by Fermat's Little Theorem for all integers a. Now a^5 = a^3.a^2 == a.a^2 = a^3 == a (mod 3). Since gcd(5,3)=1 then a^5 == a (mod 15) for all integers a.

Dave | Moderator - Wed, Sep 15 2010 17:48 GMT

hi i have a question any1 plx help me solving this..] alice wants to write message that look like it was digitally signed by Bob. She notices that Bob's public RSA key is (17,391). To what exponent should she raise her message?

Iman | pakistan - Sun, Sep 26 2010 05:46 GMT

145.

Given e=17, n=391. Factor n = 391 = 17 x 23. Phi = (17-1)(23-1) = 352. d = e^{-1} mod phi = 17^{-1} mod 352 = 145.

Check: Bob wants to sign message say m=101. Signature s = m^d mod n = 101^{145} mod 391 = 288.

Verify: s^e mod n = 288^{17} mod 391 = 101 = m => OK.

Dave | Moderator - Sun, Oct 3 2010 16:48 GMT

Since e is a small prime - * gcd(e, any large number) = mostly 1 and sometimes e, so * p is OK if ((p mod e) != 1), and * q is OK if ((q mod e) != 1)

So, there is no use checking for gcd(e,p-1)==1 and gcd(e,q-1)==1. These checks will always pass if p and q are OK.

For small prime e, * computing (p mod e) is faster than gcd(e, p-1) * computing (q mod e) is faster than gcd(e, q-1) So, compare former != 1 instead of latter == 1

Vishal | - Sun, Oct 10 2010 00:49 GMT

Correct and a nice explanation. See Note 2 (Notes on practical applications) above.

https://www.di-mgt.com.au/rsa_alg.html#note2

e does not have to be prime, but usually is.

Dave | Moderator - Sun, Oct 10 2010 03:25 GMT

Hello,

I have a problem with me which is similar to the RSA implementation with CRT, but not exactly the same.

The encryption process is C = M^e mod N, N = p*q Public key (N,e) is published on a server.

The decryption process however works on a different basis.

1. to get back the plain text one uses -

M1 = ((C mod p)^(d mod(p-1))) mod p

M2 = ((C mod q)^(d mod(q-1))) mod q

2. Calculate 2 constants

A = q^(p-1) mod N

B = p^(q-1) mod N

3. Calculate the coefficients

SH1 = (M1*A) mod N

SH2 = (M2*B) mod N

4. The final message is got back as follows -

M = SH1 + SH2, However id M>=N then M = M - N .

But this process has a fatal vulnerability, where if one were to change the method of calculating M2 and instead calculates a M2' such that M2' != ((C mod q)^(d mod(q-1))) mod q one can use it to find the keys.

Can someone of you help me in identifying the vulnerability and the ways to exploit it.

By the way, this process is followed in embedded devices.

Nishant | - Sun, Nov 14 2010 02:18 GMT

Nishant I can see you are putting a lot of effort for CSE565 project. All the best. Will be waiting for your paper tomorrow.

Ameya | Buffalo - Mon, Nov 15 2010 19:36 GMT

Solve the problem that is(1. N = 851; r = 5, encrypt 24, decrypt 111.

2. N = 247; r = 7, encrypt 100, decrypt 120 )

Avijeet Singh | Roorkee - Wed, Nov 17 2010 10:41 GMT

Dave | Moderator - Thu, Nov 18 2010 03:49 GMT

thanks..it is very helpful 4 me

jisha | coimbatore - Fri, Jan 7 2011 10:31 GMT

Hey very usefull stuff. It helped me a lot with my thesis. You should put a donation link!

dirtybit | - Tue, Jan 11 2011 09:29 GMT

can u please explain it for a very large value (about 1024bits) of P & Q.

premkumar | mysore - Thu, Jan 20 2011 18:23 GMT

Nice page, learned a lot about RSA. I would appreciate, if someone issues some Testvectors for RSA enc/dec with different padding schemes like PKCS1_V15 or ISO14888. Can only find PKCS1-OAEP test vectors. Need to be compatible with older implementations. Any links available to some testvectors?

regards Sid

Sid | - Mon, Jan 24 2011 12:21 GMT

@Sid: You mean like the worked examples in PKCS#1 Schemes above?

https://www.di-mgt.com.au/rsa_alg.html#pkcs1schemes
Dave | Moderator - Mon, Jan 24 2011 20:01 GMT

@Dave Yep! Would like to have more test vectors, especially for RSA_CRT decryption (a link would be sufficient). This page helped me a lot so far since two hints where mentioned nowhere: 1) qInv = (1/q) mod p "where p > q" 2) h = qInv(m1 + p - m2) mod p

Now it's time to stress my code ;-) best regards Sid

Sid | Germany - Tue, Jan 25 2011 05:22 GMT

@Sid|Germany: See our new page "Using the CRT with RSA" at https://www.di-mgt.com.au/crt_rsa.html.

Dave | Moderator - Mon, Feb 21 2011 14:13 GMT

THANK YOU! Tried for seven hours to make this work, and thanks to this article it finally did! It says in the simple-example that this was the smallest possible modulus n for RSA to work - could this be the reason why i couldnt succeed with p=3 & q=5 ?

rcn | - Tue, Feb 1 2011 20:09 GMT

@rcn: see the comment from Simon dated 11 Sep 2010 above and the responses.

Dave | Moderator - Tue, Feb 1 2011 22:21 GMT

Could u please write me the algorithm structure, round, key size, key type and created by whhom - all this for RSA. I would appreciate, if u answer by today, coz tomorrow I have to submit one work. thank u!

Altay | Malaysia - Sat, Feb 5 2011 04:45 GMT

Altay: what institution are you studying at? What is the email address for your tutor?

Dave | Moderator - Sun, Feb 6 2011 12:54 GMT

After reading through the above article I have the most basic understanding of all this but I do have a question which in comparison to what I read above should be simple for someone here to answer. Given two public keys of 221 and 11, what is the smallest possible integer private decoding key?

Cheers,

John | Kingston - Tue, Feb 8 2011 01:42 GMT

John: Try 53!

Dave | Moderator - Tue, Feb 8 2011 18:24 GMT

It turned out to be 35 was the correct answer but thanks for replying.

John | Kingston - Sun, Feb 20 2011 06:51 GMT

John: so it is! We have e=11, n=221=13x17, so phi=12x16=192 and d = (1/e) mod phi = 11^{-1} mod 192 = 35 since ed = 11x35 = 2x192 + 1.

Dave | Moderator - Mon, Feb 21 2011 22:03 GMT

thank you for this tutorial. It's a huge help :-)

soumik | - Tue, Feb 22 2011 02:35 GMT

its very usefull for students to do their project and clarify their doubts

divya | thrichy - Tue, Mar 1 2011 10:49 GMT

it is very useful for the students to do project

geet | lucknow - Mon, Mar 7 2011 10:11 GMT

h = qInv(m1 + p - m2) mod p

since m1 is computed mod p, and m2 is computed mod q, your suggestion is not sufficient if q > p

e.g. choose m1 = 1 and m2 = q-1 (2 extreme valid values) m1 + p - m2 = p - q and would still be "negative"

(the suggestion would not correct the problem of large number package already suffering from unsupported negative values)

Pierre | - Tue, Mar 8 2011 03:15 GMT

Pierre: That is why it is a requirement that p > q.

Dave | Moderator - Thu, Mar 10 2011 01:41 GMT

After having generated n, e and d, is it possible to swap the usage of d and e? Can I use (n, d) for encryption and use (n, e) for decryption? I know this is done when digitally signing, but can I use this for regular encryption/decryption without weakening the security of the algorithms?

The reason I ask is because I have an application where I need the decryption keys to be as small as possible (there are lots of decryption keys that need to be transferred and stored in a small space). Since e is usually chosen as 65537 but both n and d are large, I would much prefer to use d for encryption and e for decryption. Is this possible?

Mats | Uppsala, Sweden - Wed, Mar 16 2011 19:30 GMT

Mats: Any attempt to reduce the size of the private exponent d reduces security. Your suggestion completely removes it!

Dave | Moderator - Wed, Mar 16 2011 23:23 GMT

Great article, saved me quite a bit of time. A quick suggestion: set the test vector bytes to show up as 0x00, 0x01 type of notation -- I used some for tests and parsing bytes out was a bit of a pain. If you were to use the same keys throughout the article it would be much easier for those of us that ended up here looking for control tests :)

As a side note: with an implementation of Fast Hartley transformation for multiplication, CRT became more expensive than a the straight up method. I just tested both and CRT is running about 1.7x slower.

Arthur | NJ - Thu, Mar 24 2011 16:26 GMT

its much good also & very nice_ly explain

Vinay | - Fri, Mar 25 2011 04:48 GMT

Who wrote this? I'd like to use it as a reference :-) Thank you.

Joe | - Tue, Mar 29 2011 17:10 GMT
Dave | Moderator - Wed, Mar 30 2011 00:06 GMT

Very good article!

Igor | - Fri, Apr 1 2011 07:43 GMT

Hi Dave- I've been using your awesome tutorial to create my own RSA implementation. I've noticed that it is not stable- encrypting a message _m_ into ciphertext _c_ then decrypting _c_ does not always result in _m_. I think the problem has to do with messages larger than the modulus (n).

I've noticed that the problem happens with your example keys. You provided e: 3, d: 7, n: 33. This works great for low numbers (less than 33):

m = 31, c = 31^3 (mod 33) = 25, decrypted_message = 25^7 (mod 33) = 31

Our decrypted_message == our original message, so that works.

m = 33, c = 33^3 (mod 33) = 0, decrypted_message = 0^7 (mod 33) = 0

Decrypted_message (0) does not equal original message (33). Something failed.

The algorithm seems to fail for any message that is greater than or equal to the modulus. I'm not sure if this is by design or not, but I can not find any reference to this requirement in your tutorial or in other references. Can you help me figure out what I am doing wrong?

Topher | Rhode Island, USA - Thu, Apr 7 2011 16:16 GMT

Topher: As you have found, the algorithm only works for m < n. That is by the mathematics of the algorithm. See #note4 above.

Dave | Moderator - Tue, Apr 12 2011 00:08 GMT

Thanks Dave- now that you say that, m < n is brutally obvious from my own experiments, intuition, and every reference I have in front of me. Not sure how I missed it the first time, but thanks for the clarification!

Topher | Rhode Island, USA - Fri, Apr 15 2011 17:25 GMT

Thank you very much!It is a nice article.This is very useful for my design of graduation about the RSA algorithm.

forevercuit | China Chengdu - Wed, Apr 20 2011 06:58 GMT

its very helpful in understanding lets see can it be helpful in programming.......

t a | Pakistan - Thu, May 5 2011 14:46 GMT

This is an Awesome article about RSA :D thanks a ton

euronymus | - Sat, May 7 2011 04:59 GMT

can you help me in this question - http://math.stackexchange.com/questions/37604/breaking-rsa-in-a-special-case

Nitin | - Sat, May 7 2011 12:12 GMT

Nitin: Sorry, we don't help people do their homework.

Dave | Moderator - Sat, May 7 2011 22:15 GMT

Congratulations, very good document about RSA. New topics to be included in the next version of this electronic book: http://www.criptored.upm.es/guiateoria/gt_m001a_en.htm (RSA and others in chapter 14). You can use this freeware for RSA labs: http://www.criptored.upm.es/software/sw_m001d.htm (so sorry, english version is not available). Regards. Good work! Jorge RamiĆ³, Technical University of Madrid, Spain, cryptography professor.

Jorge Rami | Madrid, Spain - Thu, May 12 2011 10:50 GMT

Excellent tutorial. My question is if we know n (public) and we know n is the product of two primes, we can find the two primes (p and q as demonstrated by "145" on the Sun Oct 3 2010 post) and then knowing p and q we (public) easily calculate the totient, (p-1)x(q-1). Since e is also public and now the public has p and q it seems to me anyone can now compute the key, d=e^-1 (mod totient). Where is the secret here (I know there is one but I am not seeing it).

MDJ | - Fri, May 13 2011 01:31 GMT

MDJ: RSA only provides security when n is a *very* large number, in the order of hundreds of digits long. There is no known easy way to factorize a large number like we could with a small number like 391, where we just used a brute-force trial of all smaller primes. Even with the fastest computer and latest known factorization algorithms, it would still take centuries to find the factors p and q for a 1024-bit value of n.

Dave | Moderator - Sat, May 14 2011 02:45 GMT

The Formula is wrong in many books... The actual formula is ::

e*d mod z or phi = 1

CoolYo | - Fri, Jun 3 2011 04:10 GMT

And what would z be, CoolYo?

Dave | Moderator - Sun, Jun 5 2011 08:28 GMT

Hello thanks 4a gr8 content but can u tell me how can we limit the output size generated from this in rsa.for instance if i have a number as input of 10bit length and i want the crypted code being generated also of not more than 10bits in size than can i do this by limiting the values of p,q and e.if so,plz explain i will be highly obliged.

Himanshu | India - Tue, Jun 7 2011 13:26 GMT

How do you implement d=(1/e) mod Phi in C/C++?

Abe | India - Fri, Jul 1 2011 09:23 GMT

Abe: See the bdModInv and mpModInv functions in the BigDigits package

https://www.di-mgt.com.au/bigdigits.html
Dave | Moderator - Sat, Jul 2 2011 06:36 GMT

Thanks a lot for your information, I am working on my master thesis. I was trying combine a symmetric and asymmetric encryption algorithm for improving Cloud security, however, your document show me that isn't a new idea. Do you have any suggestion for me? Best regards, HR

Hossein | Malaysia - Tue, Jul 5 2011 05:55 GMT

Thanks for the excellent explanation of the PKCS#1 schemes. I've used your explanation to write Python code for my pure-Python RSA implementation at [xxxx]

Sybren A. Stvel | Amsterdam, The Netherlands - Sun, Jul 10 2011 12:19 GMT

Dave | Moderator - Tue, Jul 12 2011 00:20 GMT

I am a teacher from India. I appreciate the clarity and precision of this article. I learnt RSA and also learnt how to teach RSA, from this article. My grateful thnaks to the author.

partha

Parthasarathy | Secunderabad, India - Thu, Aug 25 2011 02:26 GMT

Give a sample code in RSA encryption.....

vicente | - Tue, Oct 4 2011 04:25 GMT

Vicente: Please see the section "Implementation in C and VB6" above

https://www.di-mgt.com.au/rsa_alg.html#implementation
Dave | Moderator - Tue, Oct 4 2011 12:13 GMT

Thanks! Here's a typo: m = StringToInteger("8003EA", 3) = 8389354 should be m = StringToInteger("8002EA", 3) = 8389354

iYak | - Tue, Nov 29 2011 20:27 GMT

iYak: Well spotted and thanks. It's fixed now.

Dave | Moderator - Wed, Nov 30 2011 07:53 GMT

I'm working in c code, and I've got everything working except for the part about splitting up the string into sets of three numbers and adding the numbers.

Also, how do we undo the multiplication/ addition of the three numbers, it makes sense if it was with powers of ten, but not with powers of 26

Jeff | - Mon, Dec 5 2011 20:48 GMT

Jeff: To split up a number into powers of 26, just keep dividing by 26 and keep the remainder. For example

14313 divided by 26 = 550 remainder 13
550 divided by 26   = 21 remainder 4
21 divided by 26    = 0 remainder 21

so our plaintext characters are 21 -> 'V', 4 -> 'E' and 13 -> 'N'

Dave | Moderator - Tue, Dec 6 2011 22:40 GMT

its an awesome tutorial for me....as i study it further....thanx...very much.

kuldeep | india - Sat, Dec 10 2011 21:44 GMT

Hi all, first this is a very nice tutorial. But I've got a (maybe stupid) question: Why is the key in ssl/openssl always represented like this: MIICXAIBAAKBgQDJFwAwCnWKiH8 ... = There around 1588 ascii-symbols for 2048-Bit. Why not 256 -ASCII-Character for 2048Bit / 8Bit/char?

rsaDummy | - Tue, Jan 17 2012 16:25 GMT

rsaDummy: That string MIICX... is a base64 encoding of the RSA key stored as an ASN.1 object using DER encoding!!!

A public RSA key has two parts, the modulus n which is 256 bytes long for a 2048-bit key, and the exponent e, which is usually only 3 bytes long. For the private key you need to add the private modulus d (also 256 bytes long) plus p, q, dP, dQ and qInv (see CRT above), all of which are 128 bytes long. So a 2048-bit key has components that take 256+3+256+(5*128) = 1155 bytes.

ASN.1 (Abstract Syntax Notation One) is a notation that allows you to define complex data types like all the components of an RSA key in a unique way. Distinguished Encoding Rules (DER) encoding is a specific way to represent an ASN.1 type as a sequence of bytes that can be read across different systems.

The DER encoding will add about 36 more bytes of overhead to the raw n, e, d, p, q, ... etc values in the key, so we'll end with about 1191 bytes to represent the key in binary DER format.

This binary form is not very computer friendly, so we encode again in base64 which only uses printable characters (like MIICX...). This expands again where every 3 bytes in binary form become 4 ASCII characters in base64, so the 1191 bytes become 1191*4/3 = 1588 ASCII characters

So that's how we get from the 256 bytes of the modulus for a 2048-bit RSA key to a 1588-character string in OpenSSL.

Dave | Moderator - Tue, Jan 17 2012 22:23 GMT

Thanks for an excellent article. At https://www.di-mgt.com.au/rsa_alg.html#stringvsinteger, pq = 25009997. p, q, therefore = 4999, 5003. phi(pq) 4998*5002 = 24999996. The chosen encryption key e, 3, is not valid because gcd(3, 24999996) = 3, not 1 (5 or 11 would work). Since 3 has no modular inverse mod 24999996, there's no decryption key!

doctorjay | Sudbury, MA, US - Thu, Jan 26 2012 22:50 GMT

Thanks, doctorjay. We should be more careful in checking! We've changed the public exponent to 5.

Dave | Moderator - Fri, Jan 27 2012 01:09 GMT

really nice stuff. I got clear of my doubts on encryption and used it for my project. thakzzzzz

Nathiya | tamilnadu - Sun, Jan 29 2012 12:45 GMT

Recipient: Bob Key Encryption Algorithm: rsaEncryption Encrypted Key: 3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5 8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621 EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E 609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B Content Encryption Algorithm: aes128-cbc IV: 5732164B3ABB6C4969ABA381C1CA75BA Encrypted Content: 67290EF00818827C777929A56BC3305B

This bit really helped me with my skills. thanks :)

Alex | Gold coast - Thu, Feb 2 2012 00:14 GMT

Very interesting and clear article.

I try to play the examples with the Bigdigit library but I encountered a problem with the "Encryption using PKCS#1v1.5".

I take your n = A9E167...A7EBh, e = 11h and d = 67CD484C9A0...B0319h. I try to encrypt a message m = 499602d2h = 1234567890 and get m' = m^e mod n. Then to decrypt

m'' = m'^d mod n. but I don't get m' = m''.

m := 1234567890 = 499602d2h

m'' := 306a34cd9c6fb196b22cdb0ac85785aa7c368e287c651030728b80827389869264c17b73fca773513ef90253c41649d6c581040b523bbc76661d5bb097e223b 3459cedd04a107dcd34f764866dd0e8c5be236b678e7a38b16a619d9052d1cb495b79a4f13aed021b9fd67bea5ac6357631152e9e5204e13ae91ace51ded237c1h

Do I make an error or is there a problem with the value that you give to d. I remark that n and e are the same (but in hexa in this second example) than in a previous example "A real example" but d is different. So I suppose that take the same q and p.

Do I miss something ?

Thierry | France - Thu, Feb 9 2012 21:19 GMT

Thierry: The value of e we used was 0x10001, not 0x11, so the value of d will not be the same.

Plus, the whole point of PKCS#1v1.5 is that a short message of a few bytes is encoded in a larger 1024-bit block before encrypting with RSA.

Dave | Moderator - Fri, Feb 10 2012 07:42 GMT

Thanks for the algorithm.

I used it for a prototype running in a smt32 mcu and it work flawlessly.

Brisa | Monterrey, Mxico - Sat, Feb 18 2012 07:10 GMT

can anyone help me to solve this problem......

Imagine that Fred sees your RSA signature on m1 and m2, (i.e., he sees (m1d mod n) and (m2d mod n)). How does he compute the signature on each of m1j mod n (for positive integer j), m1-1 mod n, m1 x m2 mod n, and in general m1j m2k mod n (for arbitrary j and k)?

sonia | surrey,canada - Tue, Feb 21 2012 03:00 GMT

Sonia: Good luck with your assignment.

Dave | Moderator - Tue, Feb 21 2012 23:06 GMT

Great blog.

santa | - Wed, Feb 22 2012 06:40 GMT

nice ....

vinay kasireddi | - Wed, Feb 29 2012 11:14 GMT

Hi this is a very useful site. Its amazing to use Bigdigit library and your information about solving big modulus problem. I have done a program of RSA cube root attack using bigdigit library and i got correct output as well o/p= 4461732066756572206d6f7267656e206665737467656c65677465204d656574696e67206d75737320756e626564696e677420737461747466696e64656e21 now i have to convert this hex value in Char to show plaintext but i am not getting how to use this bigdigit value to convert it into the char string of plaintext

Govind | - Wed, Mar 14 2012 03:32 GMT

Is it for real ! can I use RSA with Very Large Numbers on pic microcontroller I thought that it would take centuries

Usama | - Tue, Mar 27 2012 12:49 GMT

Usama: Most certainly you can use RSA on a microcontroller - and in a reasonable timeframe measured in milliseconds. It only takes centuries to crack (i.e. factorize) the key.

Dave | Moderator - Wed, Mar 28 2012 20:34 GMT

Dave: I hope you are still following it. I have a little confusion. I am taking up a cryptography course. My biggest confusion is what exactly is known to the parties (Alice and Bob)? In your article you have written that n, p, q are known to Bob. If this is so, can't Bob find Alice's private key da from Alice's public key ea using (ea)^-1 mod phi = (ea)^(phi-1) mod phi? Secondly we cannot say that for a key e there exist only one inverse d mod phi (because there will be one mod lcm(p-1,q-1) as well.

Aamer | Pakistan - Sat, Apr 21 2012 13:10 GMT

Aamer: Re what is secret and what is public: See https://www.di-mgt.com.au/rsa_alg.html#keygen above:

The public key is (n, e) and the private key (d, p, q).
Keep all the values d, p, q and phi secret.

Re different values of d: See https://www.di-mgt.com.au/rsa_alg.html#note6 above and also our RSA Theory page https://www.di-mgt.com.au/rsa_theory.html Using lambda(n) instead of phi(n). There is actually an infinite number of secret exponents.

Dave | Moderator - Mon, Apr 23 2012 01:43 GMT

Between sorry for me being mean. The article is splendidly written, well structured and rich in content. Thanks for putting in all the effort.

Aamer | Pakistan - Sat, Apr 21 2012 13:15 GMT

Just found out that N is different for different users! http://www.ams.org/notices/199902/boneh.pdf Thanks for the article though. But I feel either most of the texts on RSA forget to highlight this or perhaps there is a problem with my understanding. I asked many other students and they also could not answer. This might mean the texts should highlight this. Regards

Aamer | Pakistan - Sat, Apr 21 2012 14:11 GMT

Great! Extremely clear, congratulations for ordering things in a growing level of complexity!

VirgilioBF | Brasil - Sun, May 13 2012 18:28 GMT

Should I use RSA-PSS instead of PKCS#1v1.5? You said:"PSS is not used in practice very much ". Just Because There are no currently weaknesses with the PKCS#1v1.5 signature scheme. Thanks

Truong | - Tue, May 22 2012 16:51 GMT

Truong: Nothing stops you using RSA-PSS if you and the recipient of the signature agree. We've never seen it used in practice and we doubt whether many mainstream applications would accept it. We'd never include PSS in any of our products because there is still an active patent associated with it.

Dave | Moderator - Tue, May 22 2012 21:47 GMT

I have a question . In order to create public key, we must get p, q first by doing random. If there are two same public key (It mean that both p and q of two public key are the same). And the trouble is If I know the person who have the public key like I have. I can calculate his private key. And there is no-secure in this case.

JohnVan | - Thu, May 24 2012 15:40 GMT

JohnVan: What you say is true: if you just happen to have the same n as someone else, then you know their private key. But what are the odds of that in practice?

For a typical RSA key of 1024 bits, p and q will be about 512 bits long. So p and q are each of the order of 10 to the power 154. That's 10 followed by another 154 zeros. About 3 in 1000 of these will be prime. Now assume a decent random number generator and work out the probability of getting the same p and q as someone else.

Dave | Moderator - Thu, May 24 2012 20:51 GMT

Thanks Dave

JohnVan | - Sat, May 26 2012 02:28 GMT

Hi Dave, Do you know why p must be large then q when using CRT?

Joe | - Sat, Aug 4 2012 10:38 GMT

Joe: See the comment by Pierre on Tue, Mar 8 2011 and the response.

Dave | Moderator - Sun, Aug 5 2012 00:25 GMT

Hi... One of my project requirement is to implement RSA encryption and decryption algorithm with ISO 14888 padding scheme. Can anyone provide information about ISO 14888 padding scheme ??

Sha | - Sat, Aug 18 2012 10:37 GMT

Sha: I think it's the same as PKCS#1, but you never know with these ISO-\$-standards without paying the dollars for a copy or finding an old draft version that someone's left around.

Dave | Moderator - Sun, Aug 19 2012 10:17 GMT

I searched in internet but no where i am able to get information on ISO 14888 padding scheme.

Is it possible to decode the ISO 14888 padding scheme with the following information....

All values of the RSA operation are in Hex format.

Msg : 000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F

D ( Private Exponent ) : 9E0FA834765B7ECC894DA54327477EA7C8F11158A4F93D1DF87974F9452FD6CCC8EFF40AA66023805A51C2000381C24DE1DD84C5CB9B1B86BDC208BF6AEE3F51

E ( Public Exponent ) : 010001

M ( Modulus ) : d1392979475142eee4205c3f3fcaeb29ff99e1fd1094d72751ef5e5c888787e8895d4407ed72530ec7c4440c9fa29f10a16e068a2dde209ad30ccff4a5f78f3b

Cipher ( Encrypted Data ) : 5EECE83BBD3108B2AC9C81A69308598CA8EEE73DB3340316886312120BD41CF1DAB654FEAA556EB4D0EFCBC7AEF6338F6EB685832AB29664FB3EB9234F9325E0

Decrypted Data ( Encoded message ): 00024ae71336e44bf9bf79d2752e234818a524311d9abc4077123c2c9a167a00000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f

Sha | - Mon, Aug 20 2012 09:07 GMT

Sha: It looks like PKCS#1v1.5 to me. See "Encryption using PKCS#1v1.5" https://www.di-mgt.com.au/rsa_alg.html#encryptpkcs1 above. The encoded message you give breaks down as follows

00 02
4ae71336e44bf9bf79d2752e234818a524311d9abc4077123c2c9a167a
00
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f

with the actual message being the 32 bytes 00 01 02 ... 1e 1f.

IEEE P1363a/D12 hints that ISO/IEC 14888-3:1998 and PKCS #1 v2.1 may be compatible, but that's for digital signatures. I can't see anything where ISO 14888 is used for encryption. In fact, the description on the ISO site says "ISO/IEC 14888 specifies digital signatures with appendix". Who is asking you to do this?

Dave | Moderator - Tue, Aug 21 2012 11:12 GMT

Hi from Ottawa, Canada. Just wanted to say thank-you for the high quality wealth of information on RSA - very readable, digestible and usable. I have referenced you in a research paper on Zero Knowledge protocols. Focus is on RSA feasibility in three-pass scenario (no exchange of keys, instead using principle d(B.pri,d(A.pri,(e(B.pub,(e(A.pub,m))))= m.

Thanks, Karim

Karim Sultan | - Mon, Apr 1 2013 01:18 GMT

While looking for a RSA proof where the message M is not co-prime to the modulus N, I ended up in your site (thanks to Google) and read www.di-mgt.com.au/rsa_alg.html and also read the rsa_theory.pdf paper. This is by far the very simple and straight forward proof that I read on this topic. Excellent and crystal clear. Thank you so much for writing this up and other wealth of very very useful information on your site (e.g. CRT fine details).

with regards, Saravanan

Saravanan | Singapore - Wed Jan 17 05:16:45 2018 GMT
[Go to first comment]