RSA de bout en bout

Stratégie. Dérouler sur des nombres concrets le protocole établi à l'exercice résolu 10 : paramètres publics, clef privée par Euclide étendu, chiffrement, puis déchiffrement par exponentiation rapide — on ne calcule jamais $17^{27}$, entier à $34$ chiffres, mais on réduit modulo $55$ à chaque carré.

Étape 1 — les paramètres publics. Avec $p=5$ et $q=11$ (premiers distincts) :

$$n=pq=5\times 11=55,\phi (n)=(p-1)(q-1)=4\times 10=40.$$

La clef publique est $(n,e)=(55,3)$. L'exposant $e=3$ est licite car $3\wedge 40=1$ : la classe $\overline{3}$ est inversible dans $\mathbb{Z}/40\mathbb{Z}$.

Étape 2 — la clef privée. $d$ est l'inverse de $e$ modulo $\phi (n)$, c'est-à-dire la solution de $3d\equiv 1[40]$. Euclide étendu sur $(40,3)$ s'arrête au premier pas :

$$40=13\times 3+1⟹1=40-13\times 3,$$

d'où $-13\times 3\equiv 1[40]$ et $d=\overline{-13}=\overline{27}$, soit

$$d=27.$$

Contrôle : $3\times 27=81=2\times 40+1\equiv 1[40]$.

Étape 3 — chiffrement de $m=8$. Le chiffré est $c=m^e\mathrm{mod}n$ :

$$8^3=512,512=9\times 55+17(9\times 55=495),$$

donc

$$c=17.$$

Étape 4 — déchiffrement : calculer $17^{27}\mathrm{mod}55$. On carre par étapes en réduisant à chaque pas :

• $17^2=289=5\times 55+14$, donc $17^2\equiv 14[55]$ ;
• $17^4\equiv 14^2=196=3\times 55+31$, donc $17^4\equiv 31$ ;
• $17^8\equiv 31^2=961=17\times 55+26$, donc $17^8\equiv 26$ ;
• $17^{16}\equiv 26^2=676=12\times 55+16$, donc $17^{16}\equiv 16$.

L'écriture binaire de l'exposant est $27=16+8+2+1$, soit $11011$ en base $2$. Donc

$$17^{27}=17^{16}\times 17^8\times 17^2\times 17\equiv 16\times 26\times 14\times 17[55],$$

produit qu'on réduit au fur et à mesure :

• $16\times 26=416=7\times 55+31$, donc $\equiv 31$ ;
• $31\times 14=434=7\times 55+49$, donc $\equiv 49$ ;
• $49\times 17=833=15\times 55+8$, donc $\equiv 8$.

$${\left(m^e\right)}^d=17^{27}\equiv 8=m[55].$$

Le message est retrouvé. Au total, $7$ carrés et multiplications ont remplacé $26$ multiplications naïves — et surtout aucun entier manipulé n'a dépassé $961$.

Pourquoi cela marche (rappel de l'exercice résolu 10). Par construction, $ed=1+k\phi (n)$ pour un entier $k$ : ici $3\times 27=81=1+2\times 40$, donc $k=2$. Si $m\wedge n=1$, le théorème d'Euler donne $m^{\phi (n)}\equiv 1[n]$, d'où

$${\left(m^e\right)}^d=m^{1+k\phi (n)}=m{\left(m^{\phi (n)}\right)}^k\equiv m[n].$$

Ici $8\wedge 55=1$ : l'hypothèse est bien satisfaite.

Une remarque qui va plus loin (et qu'on vérifie). Le déchiffrement fonctionne en réalité pour tous les messages $m$, y compris ceux non premiers avec $55$, c'est-à-dire les multiples de $5$ ou de $11$. Un balayage des $55$ classes $m\in \{0,1,\dots ,54\}$ confirme que ${\left(m^3\right)}^{27}\equiv m[55]$ sans aucune exception. La raison : $n=55$ est sans facteur carré, et l'exposant qui gouverne réellement le protocole est $\lambda (n)=\mathrm{ppcm}(p-1,q-1)=\mathrm{ppcm}(4,10)=20$, qui divise $ed-1=80$. Le théorème chinois recolle alors la congruence modulo $5$ et celle modulo $11$, chacune restant vraie quand $m$ est divisible par le facteur concerné — les deux membres y sont simplement nuls.

Récapitulatif des contrôles.

• $n=55$, $\phi (n)=40$, $e=3$, $d=27$, et $ed=81\equiv 1[40]$.
• Chiffrement $8\mapsto 17$ ; déchiffrement $17\mapsto 8$ : la composée est l'identité sur $m=8$, et en fait sur $\mathbb{Z}/55\mathbb{Z}$ tout entier.
• Ordre de $17$ dans ${\left(\mathbb{Z}/55\mathbb{Z}\right)}^{\times }$ : il vaut $20=\lambda (55)$, qui divise bien $\phi (55)=40$ — Lagrange à l'œuvre, et l'exposant $27$ ne « voit » que $27\mathrm{mod}20=7$, ce qui donne une seconde route : $17^7\equiv 8[55]$.

Ce qui est acquis. Toute la sécurité tient dans un écart de difficulté : chiffrer et déchiffrer coûtent quelques dizaines de multiplications (exponentiation rapide), tandis que retrouver $d$ exige $\phi (n)$, donc la factorisation de $n$. Avec $n=55$ elle est immédiate ; avec deux nombres premiers de plusieurs centaines de chiffres, elle est hors d'atteinte. Trois chapitres d'algèbre — Lagrange, Euler, le théorème chinois — tiennent dans une carte bancaire.