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 , 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 M donné le chiffré se calcule comme suit :

.

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

Ce qui conclut notre démonstration.

Multiple chiffrement et théorème du reste chinois

De même, l’utilisation de moduli différents   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 :

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 … Mais bon, sait-on jamais ?