6 A6. L'algorithme RSA

6.1 principe

Cette méthode, qui tire son nom de ses trois auteurs: Rivest, Shamir et Adelman [40], se fonde sur le fait qu'un algorithme comme celui de Solovay-Strassen [44] dont le principe est donné dans la Table 16 permet assez facilement de savoir si un "grand" nombre entier possède ou non d'autres diviseurs que lui ou l'unité (c'est à dire s'il est "composé" ou s'il est "premier") tandis qu'il est très difficile de factoriser effectivement un nombre composé uniquement de nombres premiers de grande taille.

Table: Déterminer la factorisabilité.

méthode

Soit alors une entité communicante A. Elle choisit d'abord (secrètement) deux nombres premiers distincts $p$ et $q$, puis calcule $N=p q$ et $f=\phi \left( n\right) =\mathrm{lcm}\left( p-1, q-1\right)$ et enfin choisit un nombre $c$ tel que $\gcd \left( c, f\right) =1$. L'entité A calcule alors $d$ tel que $c d\equiv 1\mod f$. L'existence de ce nombre d est assurée par le théorème de Bezout et on sait le calculer effectivement par l'algorithme d'Euclide.

A fait alors connaître le couple $C=\left( c, N\right)$, qui constitue ce que l'on appelle la clef publique, ... et bien entendu, tout le reste est gardé secret. Le couple $D=\left( d, N\right)$ constitue ce que l'on appelle la clef privée. Un exemple est donné Table 17. Si B veut faire parvenir à A le nombre x avec $1<x<N$, il lui envoie : $y=\left\{ x\right\} _{C}\doteq x^{c}\mod N$. Et A calcule : $z=\left\{ y\right\} _{D}\doteq y^{d}\mod N$. Le fait que $z=x$ pour tous les choix de $x$ est une conséquence du théorème d'Euler et de ce que $N$ n'est pas divisible par un carré.

Table 17: RSA: un exemple (simpliste).

évaluation

Après en avoir décrit le principe, voyons maintenant la "résistance" de l'algorithme RSA. Deux choses sont claires : il n'a pas été publié à ce jour de méthode générale pour trouver la clef privée $\left( d, N\right)$ à partir de la clef publique $\left( c, N\right)$ qui soit meilleure que les essais systématiques (soit un ordre de grandeur de 1E150 essais pour N sur 64 octets...).

Et d'autre part, il est facile de voir que la connaissance d'un couple $\left( c, d\right)$ permet de factoriser le modulo : la résolution cryptanalytique du RSA est donc d'une complexité équivalente à celle de la factorisation d'un nombre composé n.

Or le meilleur algorithme connu pour factoriser un nombre $N$ connu pour être divisible a une complexité en $\mathrm{O}\left( \exp \left( \ln p \ln \ln p\right) \right)$, en désignant par $p$ le plus petit facteur premier de $N$. Pour un entier de 64 octets, produit de deux "grands" nombres premiers, $\ln _{2}p\approx 511$, soit une complexité en $\exp \left( \sqrt{511\times 9}\right) \approx 2E20$ opérations sur 64 octets, prenant quelques millions d'années à 1Mop/sec...

6.2 nécessité d'une expertise dans le choix des clefs

Mais d'une part il est peut être erroné d'appliquer des résultats généraux sur la complexité de la factorisation à des nombres dont on sait qu'ils sont le produit de deux premiers. Et d'autre part, on sait que certains choix de $p, q, c, d$ sont désastreux. Il pourrait y en avoir d'autres.

Donnons un exemple simple. Soit $n=206837$, produit de deux premiers $p$ et $q$. Nous convenons de $p>q$ et posons $2x=p+q$, $2y=p-q$. On a : $x^{2}-p q=y^{2}$. Soit $y=\sqrt{x^{2}-n}$. Comme $\sqrt{n}\approx 454.79$, on commence à essayer $x=455$ qui donne $y\approx 13.7$ (à rejeter), puis $x=456$ ... Et pour $x=459$, on trouve $y=62$, prouvant que l'on a réussi. On trouve alors $p=251$ et $q=397$. Moralité : $p$ et $q$ doivent être suffisamment différents.

Une attaque beaucoup plus subtile peut être menée en utilisant le développement en fraction continue de $c/N$ ou, mieux, de $c/\mathrm{floor}\left( \sqrt{N}-1\right) ^{2}$ (qui sont publics) [50]. Cet algorithme permet de trouver les fractions qui sont les meilleures approximantes d'un nombre donné. Or un résultat élémentaire est que, à dénominateur maximal fixé, deux fractions ne peuvent pas être trop proches sans devenir égales. La Table 18 indique comment il est possible, sous réserve de ce que$c d$ soit suffisamment petit, d'inférer la valeur d'une fraction contenant la clef secrète au dénominateur.

Table: Méthode de Wiener.

L'auteur de cette méthode a montré qu'elle échouait certainement si $c>n^{1.5}$... On est donc amené à publier comme exposant de chiffrement non pas $c$, mais $C=c+k f$, avec $k$ suffisamment grand. Cette "inflation" sur l'exposant public n'est pas bien grave pour les clefs du "petit" terminal, qui peut utiliser sa connaissance de la factorisation de son propre modulo pour minimiser les calculs (restes chinois), le "gros" serveur utilisant sa puissance de calcul pour passer outre. Mais dans l'autre sens, lorsque le "petit" terminal utilise la clef publique du "gros" serveur, il n'est pas possible de réduire son volume de calcul sans compromettre la sécurité.