Générer une clé RSA à la main

Rien ne vaut, pour comprendre RSA, de le dérouler à la main sur de petits nombres. Les entiers réels se comptent en milliers de bits, mais la mécanique est identique — et c’est elle que l’on éprouve ici, de la génération des clés à la vérification d’un aller-retour chiffrement / déchiffrement.

La méthode, étape par étape

On veut construire une clé publique $(e,n)$ et une clé privée $d$ à partir de la seule arithmétique élémentaire.

1. Choisir deux premiers distincts $p\ne q$. Petits ici pour le calcul manuel ; immenses en pratique.
2. Calculer le module $n=pq$, commun au chiffrement et au déchiffrement.
3. Calculer l’indicatrice d’Euler $\phi (n)=(p-1)(q-1)$ — la véritable clé mathématique du système.
4. Choisir l’exposant public $e$ tel que $1<e<\phi (n)$ et surtout $\gcd (e,\phi (n))=1$ ; cette dernière condition garantit l’existence de $d$.
5. Calculer l’exposant privé $d$, inverse modulaire de $e$ modulo $\phi (n)$, c’est-à-dire $ed\equiv 1(\mathrm{mod}\phi (n))$, par l’algorithme d’Euclide étendu.
6. Former les clés : publique $(e,n)$, privée $d$ (ou $(d,n)$).

Un exemple complet

Prenons délibérément de petits premiers, $p=11$ et $q=17$. Alors

$n=11\times 17=187,\phi (n)=10\times 16=160.$

On essaie l’exposant $e=7$ ; comme $\gcd (7,160)=1$, il convient. Reste à trouver $d$ tel que $7d\equiv 1(\mathrm{mod}160)$, par l’algorithme d’Euclide étendu.

Les divisions successives donnent

$160=7\times 22+6,7=6\times 1+1,6=1\times 6+0.$

La remontée de Bézout part de $1=7-6$, où l’on substitue $6=160-7\times 22$ :

$1=7-(160-7\times 22)=7\times 23-160,$

d’où $7\times 23\equiv 1(\mathrm{mod}160)$, soit $d=23$. On obtient ainsi la clé publique $(e,n)=(7,187)$ et la clé privée $d=23$.

Vérifier l’aller-retour

Un contrôle rapide ne coûte rien et rassure. Prenons un message $m=42$ (avec $m<n$). Le chiffrement par exponentiation modulaire donne

$c=42^7\mathrm{mod}187=15,$

et le déchiffrement restitue bien le clair :

$m^{\prime }=15^{23}\mathrm{mod}187=42.$

Le message retrouvé confirme la cohérence de la paire de clés — c’est l’identité $m^{ed}\equiv m(\mathrm{mod}n)$ vérifiée en acte.

Les points à ne pas confondre

L’exercice n’a d’intérêt que si l’on sait pourquoi chaque geste tient : pourquoi $e$ doit être premier avec $\phi (n)$, pourquoi $d$ existe alors (Bézout), et pourquoi $ed\equiv 1(\mathrm{mod}\phi (n))$ suffit à garantir le déchiffrement. Ces justifications sont développées dans les angles morts de RSA.

Pour un déroulé pédagogique complémentaire, on pourra consulter la section Key generation de la page RSA de Wikipédia ou le pas-à-pas de la Khan Academy.