Key Generation 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).
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
1 (mod phi). [See note 3].
5. The public key is (n, e) and the private key is (n, d).
Keep all the values d, p, q and phi secret.

n is
e is
just
d is

known as the modulus.

known as the public exponent or encryption exponent or
the exponent.
known as the secret exponent or decryption exponent.

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
[see note 4].
3. Computes the ciphertext c = me mod n.
4. Sends the ciphertext c to B.

Decryption
Recipient B does the following:1. Uses his private key (n, d) to compute m = cd mod 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 0 and n-1.
[See note 5].
3. Uses her private key (n, d) to compute the signature s = md
mod n.
4. Sends this signature s to the recipient, B.

Signature verification
Recipient B does the following:1. Uses sender A's public key (n, e) to compute integer v = se
mod n.
2. Extracts the message digest from this integer.
3. Independently computes the message digest of the
information that has been signed.
4. If both message digests are identical, the signature is
valid.

Notes on practical applications

1. To generate the primes p and q, generate a random number of
bit length b/2 where b is the required bit length of 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 b-b/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 known 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, common choices for e are 3, 17 and 65537
(216+1). These are Fermat primes, sometimes referred to as
F0, F2 and F4 respectively (Fx=2^(2^x)+1). They are chosen
because they make the modular exponentiation operation
faster. 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 prime and greater than 2 then you can do
the less-expensive test (p mod e)!=1 instead of gcd(p1,e)==1.)

3. To compute the value for d, use the Extended Euclidean

Algorithm to calculate d = e-1 mod phi (this is known as
modular inversion).
4. When representing the plaintext octets as the
representative integer m, it is usual 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 n1 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 = (me mod n)d mod n = (md mod n)e mod 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.
o 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).
o

Summary of RSA

n = pq, where p and q are distinct primes.

phi, = (p-1)(q-1)
e < n such that gcd(e, phi)=1
d = e-1 mod phi.
c = me mod n, 1<m<n.
m = cd mod n.

An alternative method of representing the private key uses the

Chinese Remainder Theorem (CRT). 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 four
times faster overall than calculating m = cd mod n. For more
details, see [PKCS1]. 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

These 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)
bdAdd(m1, m1, p);
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 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 = e-1 mod phi = 3-1 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 = me mod n = 73 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = cd mod n = 137 mod 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 mod n = (b mod n).(c mod n) mod 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:m' = 137 mod 33 = 13(3+3+1) mod 33 = 133.133.13 mod 33
= (133 mod 33).(133 mod 33).(13 mod 33) mod 33
= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33
= 19.19.13 mod 33 = 4693 mod 33
= 7.
Now if we calculate the ciphertext c for all the possible values
of m (0 to 32), we get
m
c

0
0

1
1

2 3 4 5 6 7 8
8 27 31 26 18 13 17

9 10 11 12 13 14 15 16
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, higher
values 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 m1, m2, ...
(9,6,13,13,16,24,16,19,13,5)

Using our table above, we obtain ciphertext integers c1, c2, ...
(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 me mod n is easy, but calculating the
inverse c-e mod 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.
ATTACKxATxSEVEN = ATT ACK XAT XSE VEN

In the same way that a decimal number can be represented as the

sum of powers of ten, e.g.
135 = 1 x 102 + 3 x 101 + 5,
we could represent our blocks of three characters in base 26
using A=0, B=1, C=2, ..., Z=25
ATT
ACK
XAT
XSE
VEN

=
=
=
=
=

0 x 262 + 19 x 261 + 19 = 513

0 x 262 + 2 x 261 + 10 = 62
23 x 262 + 0 x 261 + 19 = 15567
23 x 262 + 18 x 261 + 4 = 16020
21 x 262 + 4 x 261 + 13 = 14313

For this example, to keep things simple, we'll not worry about
numbers and punctuation characters, or what happens with groups
AAA or AAB.
In this system of encoding, the maximum value of a group (ZZZ)
would be 263-1 = 17575, so we require a modulus n greater than
this value.
1. We "generate" primes p=137 and q=131 (we cheat by looking
for suitable primes around n)
2. n = pq = 137.131 = 17947
phi = (p-1)(q-1) = 136.130 = 17680
3. Select e = 3
check gcd(e, p-1) = gcd(3, 136) = 1, OK and
check gcd(e, q-1) = gcd(3, 130) = 1, OK.
4. Compute d = e-1 mod phi = 3-1 mod 17680 = 11787.
5. Hence public key, (n, e) = (17947, 3) and private key (n,
d) = (17947, 11787).
Question: Why couldn't we use e=17 here?
To encrypt the first integer that represents "ATT", we have
c = me mod n = 5133 mod 17947 = 8363.

We can verify that our private key is valid by decrypting

m' = cd mod n = 836311787 mod 17947 = 513.
Overall, our plaintext is represented by the set of integers m
(513, 62, 15567, 16020, 14313)

We compute corresponding ciphertext integers c = me mod n, (which

is still possible by using a calculator)
(8363, 5017, 11884, 9546, 13366)

You are welcome to compute the inverse of these ciphertext

integers using m = cd mod n to verify that the RSA algorithm
still holds. However, this is now outside the realms of hand
calculations unless you are very patient.
To help you carry out these modular arithmetic calculations,
download our free modular arithmetic command line programs (last
updated 18 June 2009).
Note that this is still a very insecure example. Starting with
the knowledge that the modulus 17947 is probably derived from
two prime numbers close to its square root, a little testing of
suitable candidates from a table of prime numbers would get you
the answer pretty quickly. Or just work methodically through the
table of prime numbers dividing n by each value until you get no
remainder. You could also write a simple computer program to
factor n that just divides by every odd number starting from 3
until it reaches a number greater than the square root of n.