Attaque de Wiener
From Wikipedia, the free encyclopedia
Cet article ne cite pas suffisamment ses sources ().
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].
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 où 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
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 (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 entraîne (pour cela on multiplie simplement par l'inégalité de droite). Cela permet d'imposer une condition moins restrictive : .
