Grand E veut-il dire petit d ?

Bon cela faisait longtemps que nous n’avions pas évoqué notre clé RSA préférée.

Après avoir trouvé que l’exposant public e était anormalement grand, plusieurs hypothèses peuvent venir à l’esprit.

En effet, les exposants public et privé de RSA sont liés par la fonction \Phi d’Euler . Mais au delà de cela, que pouvons nous dire ?

Dans le cadre général, e est fixé à 0x10001 (soit 65537 en décimal). Ceci convient pour 2 raisons : l’exposant public est suffisament grand pour résister à certaines attaques, mais aussi suffisament petit pour permettre des temps de calcul raisonnables lors de la vérification d’une signature ou chiffrement de données. Avec e fixé, l’exposant privé d se calcule en cherchant l’inverse de e par \Phi(N). De fait, d a une très forte probabilité d’être de l’ordre de \Phi(N) : d est grand !

Nous pourrions donc penser plus ou moins légitimement que si e est grand (de l’ordre de N) alors d est (ou à défaut, a de grandes chances d’être) petit.

D’ailleurs, pour ne rien vous cacher, lorsque nous avons vu la taille de e, notre premier réflexe aura été de tenter de déchiffrer avec tous les d inférieurs à 232. Mais ce challenge est plus subtile que cela et évidemment cette attaque échouera lamentablement.

Plus sérieusement, en faisant quelques recherches sur le sujet avec notre ami Google, nous trouvons trace d’une attaque sur RSA connue sous le nom d’attaque de Wiener :
Sans rentrer dans les détails (et moyennant quelques hypothèses), cette technique permet de factoriser N si d est inférieur à \frac{1}{3} N^\frac{1}{4}.

Après nous être lancés dans l’implémentation de cette attaque, nous avons pu la tester sur la clé RSA du challenge :

Sans succès !

Donc pour ceux qui suivent, « Non » serait la réponse à la question posée dans le titre.

Affaire à suivre…

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Challenge ANSSI, Cryptographie Asymétrique, est tagué . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s