Attaque de Wiener

L’attaque de Wiener, du nom du cryptologue Michael J. Wiener^[1], est une attaque cryptographique contre le chiffrement RSA, utilisable lorsque d'une part l'exposant privé d est faible, et d'autre part les deux nombres premiers secrets p et q utilisés pour fournir le module de chiffrement public (qui en est le produit normalement difficilement décomposable) sont trop proches ^[2].

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 ?

Rappels sur le RSA modifier

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

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$ (p et q trop proches) 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=>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{\sqrt {\sqrt {2}}}}}n^{\frac {1}{4}}\approx {\frac {1}{2.38}}n^{\frac {1}{4}}$ .

Principe de l'attaque modifier

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, toutes les fractions de cette forme sont des développements en fraction continue de ${\frac {e}{n}}$ . L'attaquant n'a plus qu'à calculer les log(n) premiers développements 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

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.

Annexes modifier

Bibliographie modifier

[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 »).

Liens externes modifier

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

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.

[1]

[2]