Code RSA

Rivest Shamir Adleman

Pour les articles homonymes, voir RSA.

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é^[1] par le MIT en 1983 aux États-Unis. Le brevet a expiré le 21 septembre 2000.

En 2008, c'est le système à clef publique le plus utilisé (carte bancaire française, de nombreux sites web commerciaux…).

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 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. 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.

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

Création des clés

Choisir $\scriptstyle p$ et $\scriptstyle q$ , deux nombres premiers distincts
Noter $\scriptstyle n$ leur produit, appelé « module de chiffrement » : $\scriptstyle n = pq$
Calculer l'indicatrice d'Euler de $\scriptstyle n$ : $\scriptstyle \varphi(n) = (p-1)(q-1)$
Choisir $\scriptstyle e$ , un entier premier avec $\scriptstyle \varphi(n)$ , appelé « exposant de chiffrement ».
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)}$ . $\scriptstyle d$ est l'exposant de déchiffrement.

Le couple $\scriptstyle (n,e)$ est appelé clef publique, alors que le couple $\scriptstyle (n,d)$ est appelé clef privée.

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 $\varphi(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 \varphi(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\,$

$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 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é

La sécurité de cet algorithme repose sur deux conjectures :

« casser » RSA nécessite la factorisation du nombre n,
la factorisation est un problème difficile, car il n'existe pas d'algorithme suffisamment rapide. De façon plus précise, les mathématiciens affirment 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 les deux. 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 il 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 ainsi que toutes les données chiffrées auparavant à l'aide de ces algorithmes.

En 2005, le plus grand nombre factorisé, en utilisant une méthode de calculs distribués à la pointe de la technologie, é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 seront cassées dans un proche avenir (bien que 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 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 (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}$ . ^[2]

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

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 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.

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.

Liens externes

Cours sur les failles de RSA, Robert Rolland, Institut mathématiques de Luminy.
RSA expliqué aux débutants

Notes

↑ (en) esp@cenet document view
↑ http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExponents.pdf
↑ 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

Référence

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

Portail de la cryptologie

Ce document provient de « Rivest Shamir Adleman ».

Catégorie : Algorithme de cryptographie asymétrique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Code RSA de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

RSA-Algorithmus — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Kryptologiesystem — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Kryptosystem — RSA ist ein asymmetrisches kryptographisches Verfahren, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann.[1] Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder… … Deutsch Wikipedia
RSA-Schema — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Verfahren — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Verschlüsselung — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Verschlüsselungssystem — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA-Verschlüsselungsverfahren — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… … Deutsch Wikipedia
RSA — (аббревиатура от фамилий Rivest, Shamir и Adleman) криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для… … Википедия
RSA (Homonymie) — RSA Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}} Sigles d une seule lettre Sigles de deux lettres > Sigles de trois lettres … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Code RSA

Rivest Shamir Adleman

Sommaire

Fonctionnement général