Attaque de Wiener

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 ${\displaystyle \varphi (n)=(p-1)(q-1)}$ où ${\displaystyle \varphi }$ est la fonction indicatrice d'Euler. Bob choisit ensuite un entier e inférieur et premier à ${\displaystyle \varphi (n)}$ qui sera appelé exposant de chiffrement, puis calcule son inverse modulo n, c'est-à-dire que ${\displaystyle ed\equiv 1{\pmod {\varphi (n)}}}$.

Le théorème RSA stipule qu'on a alors ${\displaystyle 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 ${\displaystyle C\equiv M^{e}{\pmod {n}}}$ et elle transmet le message chiffré C à Bob. Pour déchiffrer, Bob calcule ${\displaystyle 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.

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 ${\displaystyle d<{\frac {1}{3}}n^{\frac {1}{4}}}$ (d trop petit) et ${\displaystyle 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 ${\displaystyle p<q<2p=>p+q-1<(2{\sqrt {2}}){\sqrt {n}}}$ (pour cela on multiplie simplement par ${\displaystyle q}$ l'inégalité de droite). Cela permet d'imposer une condition moins restrictive : ${\displaystyle d<{\frac {1}{2{\sqrt {\sqrt {2}}}}}n^{\frac {1}{4}}\approx {\frac {1}{2.38}}n^{\frac {1}{4}}}$.

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

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

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

On obtient alors : ${\displaystyle |{\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 {3k{\sqrt {n}}}{nd}}|}$

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

D'où : ${\displaystyle |{\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 ${\displaystyle {\frac {k}{d}}}$ (avec d<n) qui approchent ${\displaystyle {\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 ${\displaystyle {\frac {e}{n}}}$. L'attaquant n'a plus qu'à calculer les log(n) premiers développements en fraction continue de ${\displaystyle {\frac {e}{n}}}$, l'un d'eux sera égal à ${\displaystyle {\frac {k}{d}}}$ (qui est une fraction irréductible car comme ${\displaystyle ed-k\varphi (n)=1}$, on a ${\displaystyle pgcd(k,d)=1}$).

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