The RSA Algorithm

RSA encrypts messages through the following algorithm, which is divided into 3 steps:

1. Key Generation

I. Choose two distinct prime numbers p and q.

II. Find n such that n = pq.
n will be used as the modulus for both the public and private keys.

III. Find the totient of n, ϕ(n)


IV. Choose an e such that 1 < e < ϕ(n), and such that e and ϕ(n) share no divisors other than 1 (e and ϕ(n) are relatively prime).
e is kept as the public key exponent.

V. Determine d (using modular arithmetic) which satisfies the congruence relation

de ≡ 1 (mod ϕ(n)).

In other words, pick d such that de - 1 can be evenly divided by (p-1)(q-1), the totient, or ϕ(n).
This is often computed using the Extended Euclidean Algorithm, since e and ϕ(n) are relatively prime and d is to be the modular multiplicative inverse of e.
d is kept as the private key exponent.

The public key has modulus n and the public (or encryption) exponent e. The private key has modulus n and the private (or decryption) exponent d, which is kept secret.

2. Encryption

I. Person A transmits his/her public key (modulus n and exponent e) to Person B, keeping his/her private key secret.

II. When Person B wishes to send the message "M" to Person A, he first converts M to an integer such that 0 < m < n by using agreed upon reversible protocol known as a padding scheme.

III. Person B computes, with Person A's public key information, the ciphertext c corresponding to

c ≡ me (mod n).

IV. Person B now sends message "M" in ciphertext, or c, to Person A.

3. Decryption

I. Person A recovers m from c by using his/her private key exponent, d, by the computation

m ≡ cd (mod n).

II. Given m, Person A can recover the original message "M" by reversing the padding scheme.

This procedure works since

c ≡ me (mod n),
cd ≡(me)d (mod n),
≡ mde (mod n).

By the symmetry property of mods we have that

≡ mde (mod n).

Since de = 1 + kϕ(n), we can write

mde ≡ m
1 + kϕ(n) (mod n),
mde ≡ m(mk)ϕ(n) (mod n),
mde ≡ m (mod n).

From Euler's Theorem and the Chinese Remainder Theorem, we can show that this is true for all m and the original message

cd ≡ m (mod n), is obtained.

Why RSA Encryption is secure