Les bases de la cryptanalyse de RSA

Ce post ne présentera rien de nouveau. Ce sera simplement une énième présentation de l’algorithme RSA et ses attaques les plus classiques.

L’algorithme
La force (ie : la solidité contre les attaques) de l’algorithme RSA repose principalement sur le difficulté à factoriser les grands nombres. Ainsi si je vous demande de multiplier 67 par 71, vous n’aurez pas de mal à trouver la solution avec un papier et un crayon (ou une calculatrice pour les plus fainéants). Par contre si à l’inverse je vous demande de me retrouver les 2 nombres que j’ai multiplié pour obtenir 4399, cela devient tout de suite plus compliqué.

RSA est donc un chiffre asymétrique : Pour chiffrer et déchiffrer, nous devons donc utiliser respectivement la clé publique et la clé privée.

Ces deux clés sont définies comme suit :

Soient p et q deux nombres premiers.

Nous définissons N tel que N = p \times q .
La fonction \Phi d’Euler vaut par définition pour N : \Phi(N) = (p-1)\times(q-1).

Choisissons e tel que pgcd(e,\Phi(N)) = 1.
Il existe alors un unique d tel que e\times d = 1 \mod \Phi(N).

La clé privée se définit alors comme le triplet (d,p,q).
La clé publique se définit alors comme le duplet (e,N).

Sa Cryptanalyse

Il existe de nombreuses techniques de cryptanalyse pour RSA. Nous ne les détaillerons pas toutes ici : Non seulement cela serait un très long travail, mais aussi nous n’avons pas la prétention les maitriser.  Le lecteur est libre d’aller chercher de plus amples informations sur le net

Nous contenterons de lister celles qui nous intéressent dans notre cas.

Nous devons donc nous pencher sur les méthodes qui permettent en fonction des informations connues de :

  • Retrouver p et .
  • Retrouver \Phi(N)
  • Retrouver d

Nous rappelons que dans le cadre général, ces problèmes sont d’une complexité égale.

Dans le cas de la clé RSA du challenge, nous n’avons que peu d’informations : la clé publique et un unique bloc de données chiffrées. Autrement les méthodes sont peu nombreuses : nous ne pouvons pas recourir à une étude de canaux cachés ou autre technique qui permettrait de révéler les bits de poids faibles de d. Il nous faut, dans un premier temps, travailler avec l’artillerie lourde : Les algorithmes de factorisation d’entier !

Il existe 6 grands types d’algorithmes tous ont une taille d’entier pour laquelle ils sont le plus efficace :

– Le crible d’Erathostène
– La méthode de Rho de Pollard
– Les algorithmes p-1 et p+1 de Pollard
– La méthode de factorisation par courbes elliptiques
– Le crible quadratique
– Le crible algébrique (et ses variantes)

Factoriser un entier de 4096 bits en brute force prendrait énormément de temps. Et lorsque nous écrivons énormément, cela se chiffre avec les moyens actuelles à plusieurs siècles de temps de calculs.

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