Rivest Shamir Adleman

Adi Shamir, un des auteurs de RSA.

Rivest Shamir Adleman (presque toujours abrégé en RSA) est un algorithme de cryptographie asymétrique, 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 Ronald Rivest, Adi Shamir et Leonard Adleman. RSA a été breveté^[1] par le Massachusetts Institute of Technology (MIT) en 1983 aux États-Unis. 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 (respectivement vérifier) et d'une clé privée pour déchiffrer (respectivement signer) 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 publié l'idée d'utiliser l'anneau Z/nZ et le petit théorème de Fermat pour obtenir des fonctions trappes, ou fonctions à sens unique à brèche secrète. RSA repose sur le calcul dans le groupe U(Z/nZ) des unités de Z/nZ, et sur l'exponentiation modulaire. Voici une description des principes mathématiques sur lesquels repose l'algorithme RSA.

Toutefois, 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'Optimal Asymmetric Encryption Padding (OAEP).

Création des clés

1. Choisir $\scriptstyle p$ et $\scriptstyle q$, deux nombres premiers distincts
2. Noter $\scriptstyle n$ leur produit, appelé « module de chiffrement » : $\scriptstyle n = pq$
3. Calculer l'indicatrice d'Euler de $\scriptstyle n$ : $\scriptstyle \varphi(n) = (p-1)(q-1)$.
4. Choisir $\scriptstyle e$, un entier premier avec $\scriptstyle \varphi(n)$, appelé « exposant de chiffrement ».
5. Comme $\scriptstyle e$ est premier avec $\scriptstyle \varphi(n)$, il est, d'après le théorème de Bachet-Bézout, inversible $\scriptstyle \mod \varphi(n)$, c'est-à-dire qu'il existe un entier $\scriptstyle d$ tel que $\scriptstyle ed \equiv 1 \pmod{\varphi(n)}$.

L'entier $\scriptstyle d$ est l'exposant de déchiffrement. Le couple $\scriptstyle (n,e)$ est appelé clé publique, alors que le couple $\scriptstyle (n,d)$ est appelé clé privée.

Remarques sur les clés et le groupe U(Z/nZ)

1. L'indicatrice d'Euler $\scriptstyle \varphi(n)$ est l'ordre du groupe U(Z/nZ).
2. La classe de $\scriptstyle e\mod \varphi(n)$ est un élément du groupe U(Z/nZ).
3. Dans le groupe U(Z/nZ) La classe de $\scriptstyle d \mod \varphi(n)$ est l'inverse de La classe de $\scriptstyle e\mod \varphi(n)$.
4. L'exponentiation modulaire est l'exponentiation dans le monoïde multiplicatif (Z/nZ, . ).

Chiffrement du message

Si $\scriptstyle M$ est un entier inférieur à $\scriptstyle n$ représentant un message, alors le message chiffré sera représenté par $\scriptstyle C \equiv M^e \pmod{n}$

Déchiffrement du message

Pour déchiffrer C, on utilise d, l'inverse de e modulo φ(n) et on calcule $C^d \pmod{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, on a

ed = 1 + kφ(n) = 1 + k(p − 1)(q − 1), avec $k \in \mathbb N$.

Or, pour tout entier M,

$M^{1+k(p-1)(q-1) }\equiv M \pmod p\,$

et

$M^{1+k(p-1)(q-1) }\equiv M \pmod q\,$.

En effet ,

• si M est premier avec p alors, d'après le petit théorème de Fermat, $M^{p-1} \equiv 1 \pmod p\,$ donc $M^{k(p-1)(q-1)} \equiv 1 \pmod p\,$ puis $M^{1+k(p-1)(q-1)} \equiv M \pmod p\,$
• si M n'est pas premier avec p, comme p est un nombre premier, cela signifie que M est multiple de p donc $M^{1+k(p-1)(q-1)} \equiv 0 \equiv M \pmod p\,$

(un raisonnement analogue prouve la congruence modulo q)

L'entier $M^{1+k(p-1)(q-1)} - M \,$ est donc un multiple de p et de q. Comme p et q sont premiers (et premiers entre eux), une conséquence du lemme de Gauss permet d'affirmer que $M^{1+k(p-1)(q-1)} - M \,$ est un multiple de pq, c'est-à-dire de n

On a donc

$C^d \equiv M^{ed} \equiv M^{1+k(p-1)(q-1)} \equiv M \pmod n\,$

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.

Pour calculer d à l'aide de e et n, il faut trouver l'inverse modulaire de e modulo (p - 1)(q - 1 ) ce qui nécessite de connaitre les entiers p et q, c'est-à-dire la décomposition de n en facteurs premiers.

Implémentation

Dans la pratique, deux problèmes majeurs apparaissent :

• choisir un nombre premier de grande taille
• calculer $\scriptstyle M = c^d \mod{n}$

Une méthode simple pour choisir un nombre premier de grande taille est de créer une suite aléatoire de bits, puis de le tester avec le test de primalité. Un problème apparaît pour cette deuxième opération : la méthode naïve serait d'utiliser le crible d'Ératosthène, mais elle est trop lente. En pratique, on utilise un test de primalité probabiliste (test de primalité de Fermat par exemple). Ce test n'assure pas que le nombre est premier, mais il y a une forte probabilité pour qu'il le soit. On peut également utiliser un test de primalité déterministe en temps polynomial qui assure que le nombre est premier (comme le test de primalité AKS). Bien que moins rapide, il assure la primalité du nombre.

Le calcul de $\scriptstyle M = c^d \mod{n}$ peut être assez long. Calculer d'abord $\scriptstyle c^d$, puis calculer le modulo avec $\scriptstyle n$ est coûteux en temps et en calculs. Dans la pratique, on utilise l'exponentiation modulaire.

On peut 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é

Il faut distinguer les attaques par la force brute, qui consistent à retrouver p et q sur base de la connaissance de n uniquement, et les attaques sur base de la connaissance de n mais aussi de la manière dont p et q ont été générés, du logiciel de cryptographie utilisé, d'un ou plusieurs messages éventuellement interceptés etc.

La sécurité de l'algorithme RSA contre les attaques par la force brute repose sur deux conjectures :

1. « casser » RSA de cette manière nécessite la factorisation du nombre n en le produit initial des nombres p et q,
2. avec les algorithmes classiques, le temps que prend cette factorisation croît exponentiellement avec la longueur de la clé.

Il est possible que l'une des deux conjectures soit fausse, voire les deux. Jusqu'à présent, ce qui fait le succès du RSA est qu'il n'existe pas d'algorithme connu du grand public pour réaliser une attaque force brute avec des ordinateurs classiques.

Le 12 décembre 2009, le plus grand nombre factorisé par ce moyen, en utilisant une méthode de calculs distribués, était long de 768 bits. Les clés RSA sont habituellement de longueur comprise entre 1 024 et 2 048 bits. Quelques experts croient possible que des clés de 1 024 bits seront cassées dans un proche avenir (bien que ce soit controversé^{[réf. nécessaire]}), mais peu voient un moyen de casser de cette manière des clés de 4 096 bits dans un avenir prévisible^{[réf. nécessaire]}. On peut donc présumer que RSA est sûr sur cette base 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 librement disponibles. Pour une taille allant jusqu'à 512 bits, et depuis 1999, il faut^{[réf. nécessaire]} 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 2 048 bits.

Si une personne possède un moyen « rapide » de factoriser le nombre n, tous les algorithmes de chiffrement fondés sur ce principe seraient remis en cause ainsi que toutes les données chiffrées dans le passé à l'aide de ces algorithmes.

En 1996, un algorithme permettant de factoriser les nombres en un temps non exponentiel a été écrit pour les ordinateurs quantiques. Il s'agit de l'Algorithme de Shor. Les applications des ordinateurs quantiques permettent donc de casser le RSA par la force brute, ce qui a activé la recherche sur ce sujet.

Les autres types d'attaques (voir Attaques ci-dessous), beaucoup plus efficaces, visent la manière dont les nombres premiers p et q ont été générés, comment e a été choisi, si l'on dispose de messages codés ou de toute autre information qui peut être utilisée. Une partie de la recherche sur ce sujet est publiée mais les techniques les plus récentes développées par les entreprises de cryptanalyse et les organismes de renseignement comme la NSA restent secrètes.

Il n'est pas exclu qu'un service secret comme la NSA ait réussi une percée considérable dans un des axes cités précédemment, et que pour lui, le décryptage du RSA ne soit plus qu'un jeu d'enfant. En 1996, le gouvernement américain abandonna les poursuites contre l'auteur du logiciel de cryptographie grand public Pretty Good Privacy sans donner de raison. D'autres logiciels américains comme les extensions JAVA de cryptographie de Sun Microsystems^[2] étaient précédemment interdites en téléchargement en dehors des États-Unis et sont maintenant en libre accès partout dans le monde. Ces revirements peuvent suivre d'une capacité à casser ces logiciels ou d'une stratégie.

Il faut enfin noter que casser une clé par factorisation du nombre n ne nécessite pas d'attendre d'avoir un message crypté à disposition. Cette opération peut débuter sur base de la connaissance de la clé publique seulement, qui est généralement libre d'accès. Dans ces conditions, si n est factorisé, la clé privée s'en déduit immédiatement. Les conséquences de cette observation sont également qu'un code peut être cassé avant même son utilisation, et que le volume total d'information à casser dans un système est proportionnel à son nombre d'utilisateurs et non au nombre de messages qu'ils envoient.

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 (nettement moins coûteuse en temps de calcul) utilisées lors du reste du processus d'échange d'informations numériques chiffrées.

Ce dernier est en fait intégré dans un mécanisme RSA. En effet, le problème des algorithmes symétriques est qu'il faut être sûr que la clé de cryptage ne soit divulguée qu'aux personnes qui veulent partager un secret. RSA permet de communiquer cette clé symétrique de manière sûre. Pour ce faire, Alice va tout d'abord choisir une clé symétrique. Voulant échanger un secret avec Bob elle va lui transmettre cette clé symétrique en utilisant RSA. Elle va, pour cela, chiffrer la clé symétrique avec la clé publique (RSA) de Bob, ainsi elle sera sûre que seul Bob pourra déchiffrer cette clé symétrique. Une fois que Bob reçoit le message, il le déchiffre et peut alors utiliser la clé symétrique définie par Alice pour lui envoyer des messages chiffrés que seuls lui et Alice pourront alors déchiffrer.

Attaques

Attaque de Wiener

L'attaque de Wiener (1989) est exploitable si l'exposant secret d est inférieur à $N^{\frac{1}{4}}$. On peut retrouver dans ce cas l'exposant secret à l'aide du développement en fractions continues de $\frac{e}{N}$^[3].

Attaque de Håstad

L'attaque de Håstad, 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 destinataires différents, il est possible de retrouver le message originel à l'aide du théorème des restes chinois^[4].

Attaque par chronométrage (timing attacks)

Paul Kocher a décrit en 1995 une nouvelle attaque contre RSA : en supposant que l’attaquante Ève en connaisse suffisamment sur les documents 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 implémentations (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 $\scriptstyle c^d \pmod n$, Alice choisit d'abord une valeur aléatoire secrète r et calcule $\scriptstyle (r^e c)^d \pmod n$. Le résultat de ce calcul est $\scriptstyle rm \pmod 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.

Notes et références

1. ↑ (en) esp@cenet document view
2. ↑ Aujourd'hui Java SE Security.
3. ↑ http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExponents.pdf
4. ↑ 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

Voir aussi

Articles connexes

• Chiffrement
• Chiffrement symétrique
• Chiffrement asymétrique
• Authentification
• Signature numérique
• Digital Signature Algorithm (DSA)
• Compétition de factorisation RSA (Défi RSA)
• Nombre RSA
• 2⁶⁷-1

Liens externes

• Cours sur les failles de RSA, Robert Rolland, Institut mathématiques de Luminy.
• RSA expliqué aux débutants
• Utilisation de la bibliothèque RSA en C++
• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978

Bibliographie

• Douglas Stinson, Cryptographie, théorie et pratique, 2^e éd., Vuibert, 2003.
• Bruce Schneier, Cryptographie appliquée, 2^e éd., Vuibert, janvier 2001. ISBN 2-7117-8676-5.
• Pierre Barthélemy, Robert Rolland, Pascal Véron et Hermes Lavoisier, Cryptographie, principes et mises en œuvre, 2005. ISBN 2-7462-1150-5.