Attaque de Wiener

Un article de Wikipédia, l'encyclopédie libre.

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].

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 est la fonction indicatrice d'Euler. Bob choisit ensuite un entier e inférieur et premier à qui sera appelé exposant de chiffrement, puis calcule son inverse modulo n, c'est-à-dire que .

Le théorème RSA stipule qu'on a alors . 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 et elle transmet le message chiffré C à Bob. Pour déchiffrer, Bob calcule 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 trop petit) et (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 ( pour cela on multiplie simplement par l'inégalité de droite). Cela permet d'imposer une condition moins restrictive : .

Principe de l'attaque[modifier | modifier le code]

Comme , il existe un entier k vérifiant .

Alors on a et .

L'attaquant va alors utiliser comme approximation de car et donc (car q<p<2q).

On obtient alors :

Or, donc .

D'où : .

Le nombre de fractions (avec d<n) qui approchent de si près est borné par log2(n). En fait, toutes les fractions de cette forme sont des développements en fraction continue de . L'attaquant n'a plus qu'à calculer les log(n) premiers développements en fraction continue de , l'un d'eux sera égal à (qui est une fraction irréductible car comme , on a ).

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

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

  1. Wiener 2002.
  2. Menezes, van Oorschot et Vanstone 2001, Sec. 8.8 Notes and further references ; §8.2.

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,‎ (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, , 5e éd. (1re éd. 1996), 816 p. (ISBN 978-0-8493-8523-0, notice BnF no FRBNF37515673, présentation en ligne, lire en ligne [PDF]), chap. 8 (« Public Key Encryption »).

Liens externes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]