Algorithme de chiffrement RSA
Algorithme de chiffrement Rivest, Shamir, Adleman (RSA)
Usages
RSA, du nom de ces inventeurs, est un algorithme de chiffrement appartenant à la grande famille "Cryptographie asymétrique".
RSA peut être utilisé pour assurer :
- la confidentialité : seul le propriétaire de la clé privée pourra lire le message chiffré avec la clé publique correspondante.
- la non-altération et la non-répudiation : seul le propriétaire de la clé privée peut signer un message (avec la clé privée). Une signature déchiffrée avec la clé publique prouvera donc l'authenticité du message.
Sa robustesse réside dans la difficulté à factoriser un grand nombre.
Évènements clés
- 1978 : Ronald L. Rivest, Adi Shamir et Leonard Adleman publient « Une méthode pour obtenir des signatures électroniques et des clés publiques de cryptosystèmes. » dans la revue mensuelle de l'Association for Computing Machinery (ACM).
- 1982 : Rivest, Shamir et Adleman fondent la compagnie « RSA Data Security » (devenue en 2006 « RSA, The Security Division of EMC »). «Un système cryptographique de communications et de méthode.» est breveté en 1983 au Massachussets Institute of Technology (MIT), il est expiré depuis septembre 2000.
- 1991 : publication des premiers « Standards de cryptographie à clé publique » (PKCS), et ouverture de la « compétition de factorisation RSA » (clôturée en 2007), incitant le monde de la recherche à élaborer des méthodes pour factoriser les clés publiques (et donc décrypter n'importe quel message).
- 1994 : « L'algorithme en temps polynomial pour la factorisation sur ordinateur quantique » de Peter Shor, permet théoriquement de casser n'importe quelle clé RSA. Cependant la mise en pratique nécessite un ordinateur quantique (ce qui a relancé un vif intérêt pour ce domaine). En 2001, IBM réussi une factorisation quantique d'une clé RSA de 15 bits (expérience répétée en 2012).
- 2000 : publication des standards PKCS #15, les plus récents à ce jour (en version 1.1).
- 2010 : la clé RSA de 768 bits du concours de 1991 est craquée, c'est à ce jour le meilleur résultat (publiquement connu) de factorisation d'une clé RSA. En France, le Référentiel général de sécurité recommande l'usage de clés de 2048 bits pour la période 2010-2020.
Mise en oeuvre de RSA
Avertissement : cet article énonce le principe de base de l'algorithme publié en 1978.
Pour une implémentation rigoureuse, un certain nombres de précautions sont à prendre en compte afin d'éviter certaines vulnérabilités (se référer aux standards les plus récents).
Alice et Bob
- Bob possède un message confidentiel qu'il souhaite transmettre à Alice.
- Alice construit deux clés :
- une clé de chiffrement publique qu'elle transmet à Bob.
- une clé de déchiffrement privée qu'elle conserve soigneusement.
- Bob utilise la clé publique pour chiffrer le message, et le transmets à Alice.
- Alice utilise la clé privée pour déchiffrer le message reçu.
Génération des clés
- Soient deux grands nombres premiers « aléatoirement » choisis : p et q.
- Notons : n = p*q et φ = (p-1)*(q-1)
- Soient d un grand entier « aléatoirement » choisi, premier avec φ. Et e l'inverse de d modulo φ.
- La clé publique de chiffrement est le couple (n,e), la clé privée de déchiffrement le couple (n,d).
Chiffrement/Déchiffrement
Chiffrement
- Avant d'être chiffré, le message original doit être décomposé en une série d'entiers M de valeurs comprises entre 0 et n-1.
- Pour chaque entier M il faut calculer C≡M^e [n].
- Le message chiffré est constitué de la succession des entiers C.
Déchiffrement
- Conformément à la manière dont il a été chiffré, le message reçu doit être composé d'une succession d'entiers C de valeurs comprises entre 0 et n-1.
- Pour chaque entier C il faut calculer M≡C^d [n].
- Le message original peut alors être reconstitué à partir de la série d'entiers M.
Fiabilité
La sécurité de l'algorithme RSA repose sur la difficulté à factoriser n.
Pour décrypter le message, il est nécessaire de trouver d connaissant e, ce qui nécessite de recalculer φ, et donc de connaître p et q, les deux facteurs premiers de n.
Or, la factorisation d'un entier (de très grande taille) en facteurs premiers est extrêmement difficile, cette opération nécessitant une capacité de calcul très importante.
Pour exemple : en 2010, l'INRIA et ses partenaires ont réussi à factoriser une clé de 768 bits. Il leur a fallu deux ans et demi de recherche, et plus de 10^20 calculs. C'est à ce jour le meilleur résultat connu de factorisation.
Afin de se prémunir contre les puissances de calculs grandissantes, il est régulièrement recommandé d'utiliser des tailles de clés de plus en plus grandes (actuellement de 2048 bits).