Les classiques de RSA

Comme vous le savez très probablement, le produit de deux nombres premiers peut servir à former un modulus de RSA. La factorisation de grand nombre est pour l’instant un exercice complexe et cette même complexité à elle seule garantit la sécurité de l’algorithme de chiffrement RSA. Cependant plusieurs choses peuvent le fragiliser.

Outre, le cas bien connu du partage d’un même nombre premier p dans plusieurs modules distincts (au quel cas, un simple calcul de pgcd suffit à extraire les nombres premiers et donc à factoriser les moduli), dont nous avons donné un exemple avec les boitiers Juniper, il est parfois possible pour un attaquant de récupérer de l’information sans avoir à factoriser ces grands nombres.

Détaillons ici deux exemples bien connus :

Rappelons que dans le cas générale, la seule contrainte pour l’exposant public e est d’être premier avec \Phi{N}, et ce afin de garantir l’existence de son inverse d : l’exposant privé utilisé pour le déchiffrement  (ou la signature).

RSA et Bezout

Un premier cas classique est celui de l’utilisation du même modulus avec des exposants publics différents. Certes, nous ne pourrons pas à l’aide de cette technique factoriser le module RSA, mais nous pourrons facilement retrouver le message en clair.

Mathématiquement, cela se démontre ainsi :

Supposons que nous avons deux clés publiques {E1,N} et {E2,N}. Nous savons que pour un message donné le chiffré se calcule comme suit :

C_1 = M^{E_1} \mod N
C_2 = M^{E_2} \mod N.

Or si E1 et E2 sont premiers entre eux, nous savons d’après Bezout qu’il existe a et b tels que aE_11 + bE_2 = 1 et donc par conséquent que :

C1^a*C2^b = M^{a*E_1+b*E_2} = M^1 = M

Ce qui conclut notre démonstration.

Multiple chiffrement et théorème du reste chinois

De même, l’utilisation de moduli différents N_i  avec le même exposant public e permet également de casser le message.
Cependant, il y a une condition nécessaire : le nombre de messages chiffrés (avec des moduli tous différents) doit être au moins égal à « e ».

Avec les hypothèses, nous avons donc le système d’équation suivant :

C_1 = m^e \mod N_1
C_2 = m^e \mod N_2
\vdots
C_e = m^e \mod N_e

Ne reste alors plus qu’à résoudre ce système d’équation, en appliquant directement le théorème des restes chinois (dont nous en avons déjà évoqué ici. pour l’optimisation des ressources lors de calcul avec la clé privée).

En pratique, ces deux attaques  bien connues n’ont que peu d’application (en dehors des challenges :)), car généralement les hyptohèses ne sont pas vérifiées, notamment car la valeur de e est quasi-systématiquement 2^{16}+1 … Mais bon, sait-on jamais ?

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, RSA, Uncategorized, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

Un commentaire pour Les classiques de RSA

  1. Ping : RSA et le reste chinois | Cryptobourrin

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