Mauvais choix de paramètres : module commun, Wiener

Même avec un bon remplissage, RSA tombe si les paramètres sont mal choisis. Voici les erreurs classiques sur p, q, d et n.

Le module commun

Croyance dangereuse : « on peut partager le même n entre plusieurs personnes, chacune ayant son propre couple (e, d) ». C'est faux. Deux utilisateurs qui partagent n peuvent lire les messages de l'autre : chacun connaît la factorisation de n (ou peut la retrouver depuis son propre d), donc reconstruit φ(n), donc la clé privée du voisin. Un module ne doit servir qu'à une seule paire de clés.

L'exposant privé trop petit : Wiener

On peut être tenté de choisir un petit d pour accélérer le déchiffrement. Erreur. L'attaque de Wiener (1990) exploite la relation e × d ≡ 1 (mod φ(n)). En développant la fraction e / n en fractions continues, on retrouve d dès que :

d < (1/3) × n^(1/4)

L'attaque est rapide et ne nécessite que la clé publique (n, e). Morale : on garde d grand (et l'on choisit plutôt un petit e, comme 65537, ce qui est sans danger).

Des premiers trop proches : Fermat

Si p et q sont proches l'un de l'autre, la factorisation de Fermat casse n en quelques essais. Elle cherche n = a^2 - b^2 = (a-b)(a+b) en partant de a = ceil(sqrt(n)) et en montant. Quand p et q sont voisins, a est à peine plus grand que sqrt(n) et b est petit : trouvé presque immédiatement. Il faut donc des premiers éloignés et bien aléatoires.

L'aléa faible : le PGCD partagé

Si deux modules n1 = p × q1 et n2 = p × q2 partagent par malchance un même facteur p (générateurs d'aléa défaillants), un simple PGCD les casse tous les deux :

pgcd(n1, n2) = p        puis   q1 = n1 / p,   q2 = n2 / p

En 2012, une étude a collecté des millions de clés publiques sur Internet et, en calculant les PGCD deux à deux, a factorisé des dizaines de milliers de clés RSA réelles, uniquement parce que leur aléa était mauvais. C'est la « débâcle des clés » (Mining your Ps and Qs).

Tableau des erreurs de paramètres

+---------------------------+------------------------+---------------------------+
| Erreur                    | Attaque                | Parade                    |
+---------------------------+------------------------+---------------------------+
| Module n partagé          | lecture croisée        | 1 module = 1 seule paire  |
| Exposant prive d trop petit| Wiener (fract. cont.) | d grand, e petit (65537)  |
| p et q trop proches       | factorisation de Fermat| premiers eloignes         |
| Alea faible (p commun)    | PGCD de deux modules   | bon generateur aleatoire  |
+---------------------------+------------------------+---------------------------+

En résumé

RSA exige des paramètres irréprochables : jamais de module commun, un d assez grand (sinon Wiener), des premiers p et q éloignés (sinon Fermat) et vraiment aléatoires (sinon PGCD partagé, comme en 2012). La sécurité de RSA se joue autant dans la génération des clés que dans l'algorithme.