title: Attaque de Wiener
text: # Attaque de Wiener
  
  L’attaque de Wiener, du nom du cryptologue Michael J. Wiener, 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.
  
  ## 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$ (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
  
  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}}$ (car 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 {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_2(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.
  
  