Rivest Shamir Adleman

Gelose | Tous les portails | Portail Medecine | Portail Biologie | Portail Biochimie | Portail Microbiologie | Portail Ecologie | Portail Botanique | Biologie cellulaire | Portail Zoologie | Science de la terre | Portail Eau |


 Inscrivez votre site en haut de cette page Soumission direct par Allopass, obtenez 1 lien de qualite en haut de cette page Rivest Shamir Adleman ainsi que sur la page des nouveaux sites inscrits pour seulement 20 euros!


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, d'où le sigle RSA. 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

[] 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éé 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 Adleman, 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. Il est toutefois important de remarquer que le passage des principes à la pratique requiert de nombreux détails techniques qui ne peuvent pas être ignorés, sous peine de voir la sécurité du système anéantie. Par exemple, il est recommandé d'encoder le message en suivant l'OAEP.


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 l'indicatrice d'Euler de n vaut \varphi(n)= (p-1)(q-1), e est premier avec \varphi(n) et 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 \equiv1\pmod{\varphi(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 \varphi(n), ensuite on calcule Cd 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 dans le cas où x est premier avec n; on a x^{\varphi(n)} \equiv 1 \pmod{n}, d'après le théorème d'Euler. Donc finalement, si le message M est premier avec n:

C^d \equiv M \pmod{n}.

Le cas où le message M n'est pas premier avec n est un peu plus compliqué mais le résultat reste le même:

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 \varphi(n)=(p-1)*(q-1) et d= e-1 mod \varphi(n).

Dit d'une autre manière, il faut connaître la décomposition de n en facteurs premiers.

Dans la pratique on conserve une forme différente de la clé privée pour permettre un déchiffrement plus rapide à l'aide du théorème des restes chinois :

  • p et q, les nombres premiers choisis pour calculer n
  • d mod (p-1) et d mod (q-1) (souvent nommés dmp1 et dmq1)
  • (1/q) mod p (souvent nommé iqmp).

[] 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 conjectures soit fausse, voire que les deux le soient. Si c'est le cas, alors RSA n'est pas sûr. Cela fait néanmoins 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.

En 2005, le plus grand nombre factorisé par les méthodes générales et l'état de l'art en matière de calculs distribués, était long de 663 bits. Les clefs RSA sont habituellement de longueur comprise entre 1024 et 2048 bits. Quelques experts croient possible que des clefs de 1024 bits soient cassées dans un proche avenir (quoique ce soit controversé) ; mais peu voient un moyen de casser des clefs de 4096 bits dans un avenir prévisible. On présume donc que RSA est sûr si la taille de la clé est suffisamment grande. On peut trouver la factorisation d'une clé de taille inférieure à 256 bits en quelques heures sur un ordinateur individuel, en utilisant des logiciels déjà librement disponibles. Pour une taille allant jusqu'à 512 bits, et depuis 1999, il faut faire travailler conjointement plusieurs centaines d'ordinateurs. Par sûreté, il est couramment recommandé que la taille des clés RSA soit au moins de 2048 bits.

[] 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 :

[] En pratique

[] Attaque par chronométrage (timing attacks)

Kocher décrit en 1995 une nouvelle attaque ingénieuse contre RSA : en supposant que l’attaquante Ève en connaisse suffisamment sur le matériel d'Alice et soit capable de mesurer les temps de déchiffrement de plusieurs documents chiffrés, elle serait en mesure d’en déduire rapidement la clef de déchiffrement. Il en irait de même pour la signature. En 2003, Boneh et Brumley ont montré une attaque plus pratique permettant de retrouver la factorisation RSA sur une connexion réseau (SSL) en s’appuyant sur les informations que laissent filtrer certaines optimisations appliquées au théorème des restes chinois. Une façon de contrecarrer ces attaques est d'assurer que l'opération de déchiffrement prend un temps constant. Cependant, cette approche peut en réduire significativement la performance. C'est pourquoi la plupart des mises en œuvre RSA utilisent plutôt une technique différente connue sous le nom d’aveuglement [cryptographique] (blinding).

L'aveuglement se sert des propriétés multiplicatives de RSA en insérant dans le calcul une valeur secrète aléatoire dont l'effet peut être annulé. Cette valeur étant différente à chaque chiffrement, le temps de déchiffrement n'est plus directement corrélé aux données à chiffrer, ce qui met en échec l'attaque par chronométrage : au lieu de calculer cd mod n, Alice choisit d'abord une valeur aléatoire secrète r et calcule (rec)d mod n. Le résultat de ce calcul est rm mod n et donc l'effet de r peut être annulé en multipliant par son inverse.

[] Attaque par 'chiffrement choisi' (Adaptive chosen ciphertext attacks)

RSA doit être utilisé avec un schéma de remplissage de manière telle qu'aucune valeur de message, une fois chiffré, ne donne un résultat peu sûr. En 1998, Daniel Bleichenbacher décrit la première attaque pratique de type 'chiffré choisi adaptable', contre des messages RSA. En raison de défauts dans le schéma de remplissage PKCS #1 v1, il fut capable de récupérer des clefs de session SSL. Suite à ce travail, les cryptographes recommandent maintenant l'utilisation de méthodes de remplissage formellement sûres telles que OAEP, et les laboratoires RSA ont publié de nouvelles versions de PKCS #1 résistantes à ces attaques.

[] Articles connexes

[] Bibliographie

  • Cryptographie, théorie et pratique, Douglas Stinson, 2e éd., Vuibert 2003.
  • Cryptographie appliquée, de Bruce Schneier, 2e éd. Vuibert, janvier 2001, ISBN 2711786765.
Portail de la cryptologie – Accédez aux articles de Wikipédia concernant la cryptologie.
Rivest_Shamir_Adleman_f5e4