Attaque de Wiener

L’attaque de Wiener, du nom du cryptologue Michael J. Wiener, est une attaque cryptographique contre le chiffrement RSA, utilisable lorsque l'exposant privé d est petit.

Rappels sur le RSA

Le système RSA est un système de chiffrement à clé publique. Alice et Bob sont deux personnes voulant communiquer de façon sécurisée. Plus précisément, Alice veut envoyer à Bob un message qu'il sera le seul à pouvoir déchiffrer. Tout d'abord Bob choisit deux nombres premiers p et q, puis il calcule le module n = pq. Il calcule ensuite $\varphi (n)=(p-1)(q-1)$ où $\varphi$ est la fonction indicatrice d'Euler. Bob choisit ensuite un entier e inférieur et premier à $\varphi (n)$ qui sera appelé exposant de chiffrement, puis calcule son inverse modulo n, c'est-à-dire que $ed\equiv 1{\pmod {\varphi (n)}}$.

Le théorème RSA stipule qu'on a alors $M\equiv M^{ed}{\pmod {n}}$. Bob envoie alors le couple (n,e) appelé clé publique et garde pour lui le couple (n,d) appelé clé privée. Pour chiffrer le message M, Alice fait l'opération $C\equiv M^{e}{\pmod {n}}$ et elle transmet le message chiffré C à Bob. Pour déchiffrer, Bob calcule $C^{d}\equiv (M^{e})^{d}\equiv M^{ed}\equiv M{\pmod {n}}$ et retrouve ainsi le message d'origine.

Si on connaît la factorisation de n, on peut facilement récupérer la clé secrète d en utilisant l'algorithme d'Euclide; et en connaissant la clé secrète d, on peut facilement retrouver la factorisation de n.

Conditions d'utilisation et énoncé du théorème

L'attaque de Wiener consiste à retrouver d à partir de la clé publique (n,e).

Le théorème de Wiener dit que lorsque les conditions $d<{\frac {1}{3}}n^{\frac {1}{4}}$ (d trop petit) et $q<p<2q$ (qui signifie que p et q ont le même nombre de chiffres en binaire, ce n'est pas une hyptohèse restrictive pour utiliser RSA) sont remplies, il est facile de retrouver d.

Ce résultat peut être amélioré en remarquant (dans la démonstration qui suit) que $p<q<2p$ entraîne $p+q-1<(2{\sqrt {2}}){\sqrt {n}}$ (pour cela on multiplie simplement par $q$ l'inégalité de droite). Cela permet d'imposer une condition moins restrictive : $d<{\frac {1}{2\cdot 2^{\frac {1}{4}}}}n^{\frac {1}{4}}\approx {\frac {1}{2.38}}n^{\frac {1}{4}}$.

Principe de l'attaque

Comme $ed\equiv 1{\pmod {\varphi (n)}}$, il existe un entier k vérifiant $ed=k\varphi (n)+1$.

Alors on a $|ed-k\varphi (n)|=1$ et $|{\frac {e}{\varphi (n)}}-{\frac {k}{d}}|={\frac {1}{d\varphi (n)}}$.

L'attaquant va alors utiliser $n$ comme approximation de $\varphi (n)$ car $\varphi (n)=(p-1)(q-1)=n-p-q+1$ et donc $n-\varphi (n)=p+q-1<3{\sqrt {n}}$ du fait que $q<p<2q$.

On obtient alors : $|{\frac {e}{n}}-{\frac {k}{d}}|=|{\frac {ed-kn}{nd}}|=|{\frac {ed-kn-k\varphi (n)+k\varphi (n)}{nd}}|=|{\frac {1-k(n-\varphi (n))}{nd}}|=|{\frac {k(n-\varphi (n))-1}{nd}}|=|{\frac {k(p+q-1)-1}{nd}}|<|{\frac {3k{\sqrt {n}}}{nd}}|$

Or, $ke<k\varphi (n)=de-1<de$ donc $k<d<{\frac {1}{3}}n^{\frac {1}{4}}$.

D'où : $|{\frac {e}{n}}-{\frac {k}{d}}|<{\frac {3}{d{\sqrt {(}}n)}}\times {\frac {n^{\frac {1}{4}}}{3}}<{\frac {1}{dn^{\frac {1}{4}}}}<{\frac {1}{3d^{2}}}$.

Le nombre de fractions ${\frac {k}{d}}$ (avec d<n) qui approchent ${\frac {e}{n}}$ de si près est borné par log₂(n). En fait, tous les nombres rationnels qui satisfont cette inégalité sont des réduites du développement en fraction continue de ${\frac {e}{n}}$, d'après un résultat classique sur les fractions continues. L'attaquant n'a plus qu'à calculer les log(n) premières réduites du développement en fraction continue de ${\frac {e}{n}}$, l'un d'eux sera égal à ${\frac {k}{d}}$ (qui est une fraction irréductible car comme $ed-k\varphi (n)=1$, on a $pgcd(k,d)=1$).

Un algorithme en temps linéaire suffit alors pour retrouver la clé secrète d.

Annexes

Bibliographie

• [Wiener 2002] (en) Michael J. Wiener, « Cryptanalysis of Short RSA Secret Exponents », IEEE Transactions on Information Theory,‎ 2002 (DOI 10.1109/18.54902, lire en ligne [PDF])
• [Menezes, van Oorschot et Vanstone 2001] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 2001, 5^e éd. (1^re éd. 1996), 816 p. (ISBN 978-0-8493-8523-0, BNF 37515673, présentation en ligne, lire en ligne [PDF]), chap. 8 (« Public Key Encryption »).
• « Twenty years of attacks on the RSA cryptosystem », Notices of the American Mathematical Society, vol. 46,‎ 1999, p. 203-213

Liens externes

• Nicolas Douziech et Thomas Jannaud, Attaque de clés RSA par la méthode de Wiener
• (en) Dan Boneh, Twenty years of attacks on the RSA cryptosystem
• Forum sur la cryptographie

Articles connexes

• Chiffrement RSA
• Cryptanalyse