Rivest Shamir Adleman

RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données confidentielles sur Internet. 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. RSA a été breveté par le MIT en 1983 aux États-Unis d'Amérique, mais le brevet a expiré le 21 septembre 2000.

Sommaire

1 Fonctionnement général

2 Fonctionnement détaillé

3 Sécurité

4 Applications

5 Articles connexes

Fonctionnement général

Cet algorithme est fondé sur l'utilisation d'une paire de clés composée d'une clé publique et d'une clé privée pour chiffrer des données confidentielles. La clé publique correspond à une clé qui est accessible par n'importe quelle personne souhaitant chiffrer des informations, la clé privée est quant à elle réservée à la personne ayant créé la paire de clés. Lorsque deux personnes, ou plus, souhaitent échanger des données confidentielles, une personne, nommée par convention Alice prend en charge la création de la paire de clés, envoie sa clé publique aux autres personnes Bob, Carole ... qui peuvent alors chiffrer les données confidentielles à l'aide de celle-ci puis envoyer les données chiffrées à la personne ayant créée la paire de clés, Alice. Cette dernière peut alors déchiffrer les données confidentielles à l'aide de sa clé privée.

Fonctionnement détaillé

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 $\mathbb Z/n\mathbb Z$ et le petit théorème de Fermat pour obtenir des fonctions trappes, ou 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 $\mathbb Z/n\mathbb Z$ , plus précisément sur l'exponentiation modulaire. Voici une description des principes mathématiques sur lesquels repose l'algorithme RSA.

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 $\varphi(n) = (p-1)(q-1)$ , e est premier avec $\varphi(n)$ on obtient d'après le théorème de Bachet de Méziriac, qu'il est inversible modulo $\varphi(n)$ , i.e. il existe un entier d tel que $ed \equiv 1 \pmod{\varphi(n)}$ .

Le message chiffré sera alors représenté par:

$C \equiv M^e \pmod{n}$

Pour déchiffrer C, on calcule d l'inverse de e modulo $\varphi(n)$ , ensuite on calcule C^d mod n.

On a alors,

$C^d \pmod{n} \equiv (M^e)^d \pmod{n} \equiv M^{ed} \pmod{n}$

Comme $ed \equiv 1 \pmod{\varphi(n)}$ par définition de modulo $\varphi(n)$ , on a

$ed = 1 + r \varphi(n)$ .

D'où,

$M^{ed} \pmod{n} \equiv M \cdot M^{r \varphi(n)} \pmod{n} \equiv M \cdot (M^{\varphi(n)})^r \pmod{n}$

Or $x^{\varphi(n)} \equiv 1 \pmod{n}$ , d'après le théorème d'Euler. Donc finalement,

$C^d \equiv M \pmod{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. En revanche 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 des restes chinois.

Sécurité

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 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 celui-ci n'a pas encore été cassé, on peut donc raisonnablement le considérer comme un algorithme sûr. Cependant si une personne venait à trouver un moyen « rapide » de factoriser ce nombre n, tous les algorithmes de chiffrement fondés sur ce principe seraient remis en cause et rendus non sûrs, remettant en cause par la même occasion toutes les données chiffrées auparavant à l'aide de ces algorithmes.

Applications

Lorsque deux personnes souhaitent s'échanger des informations numériques de façon confidentielle, sur Internet par exemple avec le commerce électronique, celles-ci doivent recourir à un mécanisme de chiffrement de ces données numériques. RSA étant un algorithme de chiffrement asymétrique, celui-ci hérite du domaine d'application de ces mécanismes de chiffrement. On citera :

L'authentification des partis entrant en jeu dans l'échange d'informations chiffrées avec la notion de signature numérique;
Le chiffrement des clés symétriques utilisées lors du reste du processus d'échange d'informations numériques chiffrées.

Articles connexes

Image manquante
Key-crypto-sideways.png

Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia.