Le système RSA en pratique
On va simplifier à l’extrême et choisir des nombres de tailles raisonnables.
Il s’agit de générer un quadruplet $\left( p, q, e, d\right)$avec, pour commencer, $\left( p,q\right)$ un couple de nombres premiers.
Choisissons : $p=11$ et $q=17$.
De là nous déduisons deux nombres : $n=p\times q=187$ et $\varphi\left( n\right)=\left( p-1\right)\times \left( q-1\right)=160$
Puis nous choisissons $e=83$ qui est premier avec $\varphi\left( n\right)$.
Le nombre $d$ est l’inverse de $e$ modulo $160$. Nous trouvons : $d=27$.
Notre quadruplet est alors : $\left( 11, 17, 83, 27\right)$. La clé secrète d’Alice est $\left( e,n\right)$, soit $\left( 83,187\right)$ et sa clé publique est le couple $\left( d,n\right)$, soit $\left( 27,187\right)$
Alice veut envoyer le message $F$ à Bob. Au préalable, elle le transforme en nombre : $F=6$.
Puis elle calcule : $6^{e}\left[ n\right]$, soit $6^{83}\equiv 29\left[ 187\right]$. C’est le message qu’elle envoie à Bob.
Pour le décoder, Bob se sert des nombres $d$ et $n$, et calcule $29^{d}\left[ n\right]$ et trouve : $29^{27}\equiv 6\left[ 187\right]$ qui est bien le message d’origine.
La meilleure attaque
En dépit de sa robustesse éprouvée par la pratique et de sa résistance aux attaques par force brute, le système RSA a essuyé quelques revers.
Le premier, en 1985, est Johan Håstad qui réussit une passe sur l’exposant public $e$ dès lors qu’il est assez petit. Pire encore, les chercheurs Dan Boneh de l’université de Stanford et Ramarathnam Venkatesan de la société Microsoft ont montré que dans ce cas, casser RSA était plus facile que factoriser $n$.
Quatre ans plus tard, le cryptologue Michael J. Wiener lance une attaque en supposant l’exposant secret $d$ inférieur à une certaine quantité. Puis en 1995, Paul Kocher exploite une brèche technique en chronométrant le temps mis par l’algorithme pour chiffrer un texte donné.
En réponse, la société fondée à la suite du dépôt de brevet précise les points suivants pour éviter les failles de sécurité :
• Les nombres premiers $p$ et $q$ doivent être de tailles respectives suffisantes.
• Leur différence absolue \delta=\left\lvert p-q\right\rvert aussi.
• $p-1$ et $q-1$ doivent être le produit de facteurs premiers de taille conséquente.
• De même pour $p+1$ et $q+1$.
Ce qui, comme on peut le comprendre, ajoute des contraintes supplémentaires à la primalité des nombres $p$ et $q$, laquelle n’est pas négligeable.
De plus, le temps que met à l’algorithme à chiffrer un texte est trop long pour un usage courant. C’est pourquoi on lui préfère des protocoles de chiffrement symétrique en réservant l’usage de RSA pour l’échange préalable des clés secrètes.