Rivest Shamir Adleman

Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, particulièrement utilisé dans le commerce électronique, et d'une façon plus générale pour échanger des données confidentielles sur Internet.



Catégories :

Algorithme de cryptographie asymétrique

Recherche sur Google Images :


Source image : ebook-cours.com
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • RSA Rivest - Shamir - Adleman. Méthode particulièrement sécurisée de cryptage des données faisant appel à deux clés : l'une privée, conservée sur les machines des ... (source : journaldunet)
  • In cryptography, RSA (which stands for Rivest , Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography.... (source : en.wikipedia)
  • R. L. Rivest , A. Shamir, and L. Adleman. ∗. Abstract. An encryption method is presented with the novel property that publicly re-... (source : people.csail.mit)

Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, particulièrement utilisé dans le commerce électronique, et d'une façon plus générale 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 dispositif à 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. Quand deux personnes, ou plus, souhaitent échanger des données confidentielles, une personne, appelé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 avec 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 avec 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 exactement sur l'exponentiation modulaire. Voici une description des principes mathématiques sur lesquels repose l'algorithme RSA.

Cependant, 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 dispositif anéantie. A titre d'exemple, il est recommandé d'encoder le message en suivant l'OÆP (en anglais : Optimal Asymmetric Encryption Padding).

Création des clés

  1. Choisir et, deux nombres premiers différents
  2. Noter leur produit, nommé «module de chiffrement» :
  3. Calculer l'indicatrice d'Euler de  :
  4. Choisir, un entier premier avec, nommé «exposant de chiffrement».
  5. Comme est premier avec, il est , selon le théorème de Bachet-Bézout, inversible, c'est-à-dire qu'il existe un entier tel que. est l'exposant de déchiffrement.

Le couple est nommé clé publique, tandis que le couple est nommé clé privée.

Chiffrement du message

Si est un entier inférieur à représentant un message, alors le message chiffré sera représenté par

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\,

et

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

En effet,

(un raisonnement analogue prouve la congruence modulo q)

L'entier Mˆ{1+k(p-1)(q-1)} - M  \, est par conséquent 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. Par contre pour déchiffrer, il faut d et n.

Pour calculer d avec 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 :

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 aussi utiliser un test de primalité déterministe en temps polynomial qui assure que le nombre est premier (comme le test de primalité AKS). Quoique moins rapide, il assure la primalité du nombre.

Le calcul de peut être assez long. Calculer en premier lieu, puis calculer le modulo avec 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é

On peut distinguer les attaques par la force brute, qui consistent à retrouver p et q sur base de la connaissance de n seulement, et les attaques sur base de la connaissance de n mais également de la manière dont p et q ont été générés, du logiciel de cryptographie utilisé, d'un ou plusieurs messages peut-être 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 d'origine 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 envisageable que l'une des deux conjectures soit fausse, ou alors les deux. Jusqu'désormais, 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 généralement de longueur comprise entre 1024 et 2048 bits. Quelques experts croient envisageable que des clés de 1024 bits seront cassées dans un proche avenir (bien que ce soit controversé), mais peu voient un moyen de casser de cette manière des clés de 4096 bits dans un avenir prévisible. On peut par conséquent 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 faire travailler conjointement plusieurs centaines d'ordinateurs. Par sûreté, il est fréquemment recommandé que la taille des clés RSA soit au moins de 2048 bits.

Si une personne possède un moyen «rapide» de factoriser le nombre n, l'ensemble des algorithmes de chiffrement fondés sur ce principe seraient remis en cause mais aussi l'ensemble des données chiffrées dans le passé avec ces algorithmes.

En 1996, un algorithme servant à 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 par conséquent 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), bien 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 on dispose de messages codés ou de toute autre information qui est parfois 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 est envisageable qu'un service secret comme la NSA ait réussi une percée énorme dans un des axes cités auparavant, 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 auparavant interdites en téléchargement en dehors des États-Unis et sont désormais 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 uniquement, qui est le plus souvent 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 aussi qu'un code peut être cassé avant même son utilisation, et que le volume total d'information à casser dans un dispositif est proportionnel à son nombre d'utilisateurs et non au nombre de messages qu'ils envoient.

Applications

Quand 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, ce dernier hérite du domaine d'application de ces mécanismes de chiffrement. On citera :

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 sert à communiquer cette clé symétrique de manière sûre. Pour ce faire, Alice va dans un premier temps 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 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 envisageable 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 servant à 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 diminuer significativement la performance. C'est pourquoi la majorité 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, Alice choisit en premier lieu une valeur aléatoire secrète r et calcule. Le résultat de ce calcul est et par conséquent 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. À cause 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 désormais l'utilisation de méthodes de remplissage formellement sûres, telles que OÆP, et les laboratoires RSA ont publié de nouvelles versions de PKCS #1 résistantes à ces attaques.

Bibliographie

Liens externes

Notes

  1. (en) esp@cenet document view
  2. Actuellement Java SE Security.
  3. http ://www3. sympatico. ca/wienerfamily/Michæl/MichælPapers/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

Référence

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu