Fabriquer une paire de clés

RSA, publié en 1977 par Rivest, Shamir et Adleman, met en œuvre l'idée de la clé publique avec la factorisation.

Les cinq étapes

1. Choisir deux grands nombres premiers p et q.
2. Calculer n = p × q. C'est le module, il sera public.
3. Calculer φ(n) = (p - 1)(q - 1).
4. Choisir e premier avec φ(n). C'est l'exposant public — souvent 65537.
5. Calculer d, l'inverse modulaire de e modulo φ(n) : e × d ≡ 1 (mod φ(n)).

La clé publique est le couple (n, e). La clé privée est d.

Puis on détruit p, q et φ(n) : qui les connaît peut recalculer d.

Chiffrer et déchiffrer

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

Deux exponentiations modulaires — exactement l'opération vue au cours précédent.

Un exemple minuscule

Prenons p = 11 et q = 13 (ridiculement petits, mais lisibles).

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

Chiffrons le message m = 9 :

c = 9^7 mod 143 = 48

Déchiffrons :

m = 48^103 mod 143 = 9      ✔

Où est la sécurité

L'attaquant voit n = 143 et e = 7. Pour retrouver d, il lui faut φ(n), donc p et q, donc factoriser n.

Avec 143, c'est immédiat. Avec un n de 617 chiffres — la taille recommandée aujourd'hui — personne ne sait le faire.

Toute la sécurité de RSA tient dans cette phrase : factoriser n est aussi difficile que casser le chiffre.