Petit exposant et messages courts

Parmi les défauts du RSA brut, l'un est spectaculaire : avec un petit exposant public, on peut parfois déchiffrer sans aucune clé, juste avec une calculatrice.

L'exposant public e = 3

Pour aller vite, on choisit souvent un petit e. Historiquement, e = 3 a été très utilisé. Le chiffrement devient :

c = m^3 mod n

Tout repose sur le mod n. Le modulo n'a d'effet que si m^3 dépasse n. Sinon, il ne se passe rien.

L'attaque de la racine cubique

Supposons que le message soit court, au point que m^3 < n. Alors :

c = m^3 mod n = m^3   (pas de réduction !)

Le chiffré est tout simplement le cube du message. Pour retrouver m, l'attaquant n'a qu'à prendre la racine cubique entière de c :

m = racine_cubique(c)

Aucune clé privée, aucune factorisation. Une opération que fait n'importe quel ordinateur en une fraction de seconde.

Exemple chiffré

Prenons un grand module n (des centaines de chiffres) et e = 3. On chiffre le petit message m = 42 :

c = 42^3 mod n = 74088 mod n = 74088   (car 74088 << n)

L'attaquant voit c = 74088. Il calcule :

racine_cubique(74088) = 42      ✔  message retrouvé

La variante de Håstad

Même si un message est trop grand pour un seul destinataire, il reste vulnérable s'il est envoyé à plusieurs. Håstad a montré que si le même message m est chiffré avec e = 3 vers trois destinataires ayant des modules différents n1, n2, n3 :

c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

alors, par le théorème des restes chinois, on reconstruit m^3 modulo (n1 × n2 × n3). Comme m^3 < n1 × n2 × n3, on obtient m^3 exact, et une racine cubique donne m. Trois chiffrés interceptés suffisent, sans casser aucune clé.

Pourquoi le padding sauve tout

Ici encore, le remplissage aléatoire est la parade. Avant chiffrement, OAEP transforme le petit m = 42 en un très grand nombre bourré d'aléa, occupant presque toute la largeur de n. Dès lors :

• m^3 dépasse largement n, la réduction mod n a bien lieu : plus de racine cubique.
• Le même message envoyé à plusieurs personnes donne des blocs différents à chaque fois (aléa distinct) : l'attaque de Håstad tombe.

Un petit e n'est donc pas dangereux en soi ; c'est le RSA brut avec petit e qui l'est.

En résumé

Avec e = 3 et un message tel que m^3 < n, le chiffré est le cube du message : une racine cubique le déchiffre sans clé. La variante de Håstad casse un même message envoyé à trois destinataires via le théorème des restes chinois. Le remplissage aléatoire (OAEP), qui gonfle le message, neutralise ces deux attaques.