Making a set of keys

RSA, published in 1977 by Rivest, Shamir and Adleman, combines the concept of public-key cryptography with factorisation.

The five steps

1. Choose two large prime numbers, p and q.
2. Calculate n = p × q. This is the modulus; it will be made public.
3. Calculate φ(n) = (p - 1)(q - 1).
4. Choose e to be coprime with φ(n). This is the public exponent — often 65537.
5. Calculate d, the modular inverse of e modulo φ(n): e × d ≡ 1 (mod φ(n)).

The public key is the pair (n, e). The private key is d.

Then we destroy p, q and φ(n): anyone who knows them can recalculate d.

Encryption and decryption

chiffrer   : c = m^e mod n
déchiffrer : m = c^d mod n

Two modular exponentiations — exactly the operation we saw in the previous lesson.

A tiny example

Let’s take p = 11 and q = 13 (ridiculously small, but legible).

n   = 11 × 13 = 143
φ(n) = 10 × 12 = 120
e   = 7        (first with 120)
d   = 103      car 7 × 103 = 721 = 6 × 120 + 1 ≡ 1 (mod 120)

Let’s encrypt the message m = 9:

c = 9^7 mod 143 = 48

Let’s decrypt it:

m = 48^103 mod 143 = 9      ✔

Where is the security?

The attacker sees n = 143 and e = 7. To find d, they need φ(n), and therefore p and q, and so must factorise n.

With 143, this is instantaneous. With a 617-digit n — the size currently recommended — nobody knows how to do it.

The entire security of RSA rests on this statement: factoring n is as difficult as breaking the cipher.