| |
|
RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique. Cet algorithme a été décrit en 1977 par Ron Rivest, Adi Shamir et Len Adleman; les lettres RSA sont les initiales de leurs noms.
La sécurité du système RSA repose sur la difficulté à factoriser de très grands nombres.
RSA a été breveté par le MIT en 1983 aux Etats-Unis, mais le brevet a expiré le 21 septembre 2000.
Ronald Rivest, Adi Shamir et Leonard Adelman, dans A Method for Obtaining Digital Signatures and Public-key Cryptosystems ont eu l'idée d'utiliser les anneaux Z/nZ et le théorème de Fermat
pour obtenir des fonctions à sens unique à brèche secrète. C'est à
l'heure actuelle le système à clef publique le plus utilisé (Netscape, la carte
bancaire française, de nombreux sites web commerciaux...). RSA repose sur le calcul dans les groupes Z/nZ, plus précisément sur l'exponentiation modulaire.
Supposons que M soit un entier représentant un message. On choisit p
et q deux nombres premiers et on note n leur produit. On choisit e
un entier premier avec p-1 et q-1. Comme
φ(n)=(p-1)*(q-1), e est premier avec φ(n)
donc d'après le théorème de Bezout il est inversible
modulo φ(n), i.e. il existe un entier d tel que ed = 1 mod
φ(n). Le message chiffré sera alors représenté par:
C=Me mod n.
Pour déchiffrer C, on calcule d l'inverse de e modulo
φ(n), ensuite on calcule Cd mod n. On a
alors,
Cd mod n = (Me)d mod n =
Me*d mod n
Comme ed= 1 mod φ(n) par définition de l'inverse modulo
φ(n), on a ed=1+r*φ(n). D'où,
Me*d mod n=M*Mr*φ(n) mod n=M*(Mφ(n))rmod n
Or xφ(n)=1 mod n, d'après le théorème d'Euler. Donc finalement,
Cd = M mod n.
Le couple n,e est appelé clef publique alors que le couple (n,d) est appelé clef privée. On constate que pour chiffrer un message, il suffit de connaître e et n. Par contre si pour déchiffrer, il faut d et n. Ainsi il suffit de connaître p, q et e puisque φ(n)=(p-1)*(q-1) et d= e-1 mod φ(n).
Dit d'une autre manière, il faut connaître la décomposition de n en facteurs premiers. Il existe une autre méthode pour déchiffrer C qui utilise le théorème chinois.
En fait, la sécurité de cet algorithme repose sur deux conjectures : casser RSA nécessite la factorisation du nombre n et la factorisation est un problème difficile. Par difficile, on entend qu'il n'existe pas d'algorithme rapide pour résoudre cette question. Si l'on veut être un peu plus précis, on pense qu'il n'existe pas d'algorithme ayant une complexité polynomiale en temps qui donne les facteurs premiers d'un nombre quelconque. Il est possible que l'une des deux conjecture soit fausse, voire même que les deux le soient. Si c'est le cas, alors RSA n'est pas sûr. Cependant, cela fait maintenant plus de 20 ans que RSA est cryptanalysé et il n'y a encore rien à lui reprocher, on peut donc raisonnablement lui faire confiance.