Attaque de Wiener

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (mai 2016).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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

Rappels sur le RSA[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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^[3]^,^[4]. 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.

Notes et références[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

↑ Wiener 2002.
↑ Menezes, van Oorschot et Vanstone 2001, Sec. 8.8 Notes and further references ; §8.2.
↑ Arithmétique: primalité et codes, théorie analytique des nombres, équations diophantiennes, courbes elliptiques, Calvage et Mounet, 2008 (ISBN 2-916352-04-X), « chap. Équation de Pell-Fermat $x^{2}-dy^{2}=1$ »
↑ G. H. Hardy, E. M. Wright et Joseph Silverman, An Introduction to the Theory of Numbers, Oxford University Press, USA, 31 juillet 2008 (ISBN 978-0-19-921985-8), théorème 184

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[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[modifier | modifier le code]

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (juin 2016).

Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.

Articles connexes[modifier | modifier le code]

Portail de la cryptologie

[Wiener2002-1] Wiener 2002.

[Menezesvan_OorschotVanstone2001Sec._8.8_Notes_and_further_references_;_§8.2-2] Menezes, van Oorschot et Vanstone 2001, Sec. 8.8 Notes and further references ; §8.2.

[3] Arithmétique: primalité et codes, théorie analytique des nombres, équations diophantiennes, courbes elliptiques, Calvage et Mounet, 2008 (ISBN 2-916352-04-X), « chap. Équation de Pell-Fermat $x^{2}-dy^{2}=1$ »

[Hardy_Wright_Silverman_2008_p.-4] G. H. Hardy, E. M. Wright et Joseph Silverman, An Introduction to the Theory of Numbers, Oxford University Press, USA, 31 juillet 2008 (ISBN 978-0-19-921985-8), théorème 184

[1]

[2]

[3]

[4]