Les attaques de RSA

 

 

On a vu que le principe de base de RSA était la décomposition d'un nombre n en le produit de 2 nombres premiers. Une attaque assez évidente de RSA serait donc de tenter de trouver la factorisation de n=pq. Cependant les plus puissants algorithmes existants à ce jour ne peuvent résoudre ce problème pour plus de 130 chiffres alors qu'il existe des algorithmes très efficaces pour calculer les puissances de nombres entiers modulo k. Ce n'est donc pas une menace très dangereuse si on choisit n de 200 chiffres et p, q de 100 chiffres.

Les attaques de RSA les plus percutantes et les plus novatrices sont certainement ce qu'on appelle les timing attacks.RSA consiste en la programmation de la fonction R=y^x mod n, avec n public et y pouvant être intercepté par l'attaquant. Le but de l'attaquant sera alors de trouver x, la clef secrète.Pour l'atttaque, la victime doit calculer y^x mod n pour quelqes valeurs de y où y, n et le temps de calcul sont connus de l'attaquant. Notons au passage que si un nouvel exposant x est choisi pour chaque opération l'attaque ne fonctionne plus. L'information nécessaire et les mesures de temps de calcul peuvent être obtenus à l'aide d' un protocole interactif puisqu'un attaquant pourrait enregistrer les messages reçus par la cible et mesurer le temps mis pour répondre à chaque y.L'attaque peut être traitée comme un problème de détection de signal. Le signal consiste en la variation de temps due aux exposants inconnus et les propriétés du signal déterminent le nombre de mesures du temps requises pour l'attaque.Etant donnés j messages y0, y1, ..., yj-1 avec des mesures de temps correspondantes T0, T1, ..., Tj-1, la probabilité qu'une réponse xb pour le premier bit exposant b soit correcte est proportionnelle à :

où t(yi,xb) est le temps requis pour les b premières itérations du calcul de yi^x mod n en utilisant le bit exposant xb, et F est la probabilité attendue de distribution de T-t(y,xb) sur toutes les valeurs de y et xb correct. Comme F est définie comme la distribution de probabilité de Ti-t(yi,xb), si xb est correct c'est la meilleure fonction pour pour prédire Ti-t(yi,xb).