Rivest Shamir Adleman

Infos
Rivest Shamir Adleman ou 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é http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US440
Rivest Shamir Adleman

Rivest Shamir Adleman ou 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é http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US4405829 par le MIT en 1983 aux États-Unis d'Amérique. Le brevet a expiré le 21 septembre 2000.

Fonctionnement général

Cet algorithme est fondé sur l'utilisation d'une paire de clés composée d'une clé publique pour chiffrer et d'une clé privée pour dé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. Schéma de principe : voir Chiffrement asymétrique

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 (Optimal Asymmetric Encryption Padding).

Création des clés

- On choisit p et q deux nombres premiers distincts
- On note n leur produit, appelé module de chiffrement : n = pq
- On calcule l'indicatrice d'Euler de n : \varphi(n) = (p-1)(q-1)
- On choisit e un entier premier avec \varphi(n), appelé exposant de chiffrement.
- 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). d est 'exposant de déchiffrement'. Le couple (n, e) est appelé clef publique alors que le couple (n, d) est appelé clef privée.

Chiffrement du message

Supposons que M soit un entier inférieur à n représentant un message. Le message chiffré sera alors représenté par : :C \equiv M^e \pmod

Déchiffrement du message

Pour déchiffrer C, on calcule d l'inverse de e \pmod\varphi(n), ensuite on calcule C^d \pmod. On a alors, :C^d \pmod \equiv (M^e)^d \pmod \equiv M^ \pmod Comme ed \equiv 1 \pmod\varphi(n) par définition de modulo, on a :ed = 1 + k \varphi(n), avec k \in \mathbb N. D'où, :M^ \pmod \equiv M \cdot M^k \varphi(n) \pmod \equiv M \cdot (M^\varphi(n))^k \pmod Dans le cas où x est premier avec n; on a x^\varphi(n) \equiv 1 \pmod, d'après le théorème d'Euler. Donc finalement, si le message M est premier avec n: :C^d \equiv M \pmod. Dans tous les cas (M pas forcément premier avec n) :
- ed \equiv 1 \pmod donc ed \equiv 1 \pmod et ed \equiv 1 \pmod
- Suivant le petit théorème de Fermat, M^ \equiv 1 \pmod et M^ \equiv 1 \pmod d'où M^ \equiv 1 \pmod et M^ \equiv 1 \pmod
- p et q sont premiers entre eux, donc M^\varphi(n) = M^ \equiv 1 \pmod grâce au théorème des restes chinois
- D'où C^d \equiv M \cdot M^k \varphi(n) \equiv M \pmod. 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.

Implémentation

Dans la pratique, deux problèmes majeurs apparaissent :
- le choix d'un nombre premier de grande longueur
- le calcul de M = c^e \mod Une méthode simple pour choisir un nombre premier de grande taille est de créer une suite aléatoire de bits (par exemple 2048) puis de tester si le nombre correspondant est premier avec un Test de primalité. Un problème apparaît sur cette dernière opération : en effet la méthode naïve serait d'utiliser le Crible d'Ératosthène , mais cette méthode est clairement trop lente. En pratique on utilisera un test de primalité probabiliste (Test de primalité de Fermat par exemple). Ce test ne nous assure pas que le nombre est premier mais il dit qu'il y a une forte probabilité pour qu'il soit premier. On peut également utiliser un test de primalité déterministe en temps polynomial qui nous assurera que le nombre est premier (comme l'algorithme AKS). Celui-ci, bien que moins rapide, nous assure la primalité du nombre. Le calcul de M = c^e \mod peut être assez long si on s'y prend mal. il est clair que calculer d'abord c^e puis ensuite de calculer le modulo avec n est une mauvaise idée car coûteuse en temps et en calculs. Dans la pratique on utilisera la méthode Exponentiation modulaire. On pourra également conserver 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.

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 25 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 :
- L'authentification des parties 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.

Attaques

Attaque de Wiener

L'attaque de Wiener (1989) est exploitable si l'exposant secret d est inférieur à N^\frac. On peut retrouver dans ce cas l'exposant secret à l'aide du développement en fractions continues de \frac. http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExponents.pdf

Attaque de Hastad

L'attaque de Hastad, l'une des premières attaques découvertes (en 1985), repose sur la possibilité que l'exposant public e soit suffisamment petit. En interceptant le même message envoyé à plusieurs destinaires différents, il est possible de retrouver le message originel à l'aide du théorème des restes chinois.Johan Håstad, On using RSA with low exponent in a public key network, Advances in Cryptology – CRYPTO’85, Lecture Notes in Computer Science, 218, Springer, pages 403-408

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 (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. ==
Sujets connexes
Adi Shamir   Algorithmique   Anneau (mathématiques)   Authentification   Chiffrement   Commerce électronique   Complexité algorithmique   Compétition de factorisation RSA   Crible d'Ératosthène   Cryptanalyse   Cryptographie   Cryptographie asymétrique   Cryptographie symétrique   Digital Signature Algorithm   Décomposition en produit de facteurs premiers   Exponentiation modulaire   Fonction à sens unique   Groupe (mathématiques)   Identité de Bézout   Indicatrice d'Euler   Internet   Johan Håstad   Langage de la cryptologie   Massachusetts Institute of Technology   Mathématiques   Nombre RSA   Optimal Asymmetric Encryption Padding   PKCS   Paul Kocher   Petit théorème de Fermat   Remplissage (cryptographie)   Signature numérique   Test de primalité   Test de primalité AKS   Test de primalité de Fermat   Théorème d'Euler (nombres)   Théorème des restes chinois   Transport Layer Security  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^