RSA (algorithme)
RSA est un système cryptographique, ou cryptosystème, pour le chiffrement à clé publique. Il est souvent utilisé pour la sécurisation des données confidentielles, en particulier lorsqu'elles sont transmises sur un réseau peu sûr comme Internet.
RSA a été décrit pour la première fois en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman du MIT (Massachusetts Institute of Technology). Le chiffrement à clé publique, également appelé chiffrement asymétrique, utilise deux clés différentes, mais mathématiquement liées, une publique et l'autre privée. La clé publique peut être partagée avec quiconque, tandis que la clé privée doit rester secrète. Dans le chiffrement RSA, tant la clé publique que la clé privée peuvent servir à chiffrer un message. Dans ce cas, c'est la clé opposée à celle ayant servi au chiffrement qui est utilisée pour le déchiffrement. C'est notamment grâce à cette caractéristique que RSA est devenu l'algorithme asymétrique le plus répandu : il offre en effet une méthode permettant d'assurer la confidentialité, l'intégrité, l'authenticité et la non-répudiabilité des communications électroniques et du stockage de données.
De nombreux protocoles, tels que SSH, OpenPGP, S/MIME et SSL/TLS reposent sur RSA pour leurs fonctions de chiffrement et de signature numérique. Cet algorithme est également utilisé dans des logiciels : les navigateurs en sont un exemple flagrant, car établir une connexion sécurisée sur un réseau peu sûr comme Internet ou valider une signature numérique font partie de leurs attributions. La vérification de signature RSA constitue l'une des opérations les plus couramment réalisées en informatique.
Comment expliquer la popularité de RSA
Si RSA offre autant de sécurité, c'est parce qu'il est très difficile de factoriser de grands entiers qui sont eux-mêmes le produit de deux grands nombres premiers. Multiplier ces deux nombres est facile, mais déterminer les nombres entiers d'origine à partir du total (la factorisation) est considéré comme une opération quasi impossible étant donné le temps qu'elle prendrait, même avec les ordinateurs superpuissants actuels.
L'algorithme de génération des clés publique et privée est la partie la plus complexe du chiffrement RSA. Deux grands nombres premiers, p et q, sont générés à l'aide du test de primalité de Rabin-Miller. Un module de chiffrement n est calculé en multipliant p et q. Ce nombre est utilisé par les deux clés (publique et privée) et constitue le lien entre elles. Sa longueur, généralement exprimée en bits, est appelée la longueur de clé. La clé publique se compose du module n et d'un exposant public, e, en principe défini à 65537, car il s'agit d'un nombre premier pas trop élevé. Il n'est pas nécessaire que le nombre e soit un nombre premier secrètement choisi, car la clé publique est partagée avec tout le monde. La clé privée se compose du module n et de l'exposant privé d, qui est calculé à l'aide de l'algorithme d'Euclide étendu pour donner l'inverse modulaire par rapport à la valeur de l'indicatrice d'Euler en n.
Un exemple simple
Alice génère ses clés RSA en choisissant deux nombres premiers : p=11 et q=13. Le module n=p×q=143. L'indicatrice d'Euler en n ϕ(n)=(p−1)x(q−1)=120. Elle choisit 7 comme clé publique RSA e et calcule sa clé privée RSA en utilisant l'algorithme d'Euclide étendu, ce qui lui donne 103.
Bob veut envoyer à Alice un message chiffré M ; il lui demande donc sa clé publique RSA (n, e) qui, dans cet exemple, est (143, 7). Son message en texte clair est simplement le chiffre 9. Il est chiffré dans le cryptogramme C comme suit :
Me mod n = 97 mod 143 = 48 = C
Lorsque Alice reçoit le message de Bob, elle le déchiffre à l'aide de sa clé privée RSA (d, n) comme suit :
Cd mod n = 48103 mod 143 = 9 = M
Si elle souhaite utiliser les clés RSA pour signer numériquement un message, Alice doit créer un hachage ou condensé de son message à Bob, chiffrer la valeur de hachage à l'aide de sa clé privée RSA puis l'ajouter au message. Bob peut alors vérifier que le message a bien été envoyé par Alice et qu'il n'a pas subi de modification en déchiffrant la valeur de hachage à l'aide de sa clé publique. Si cette valeur correspond au hachage du message d'origine, seule Alice peut l'avoir envoyé (authentification et non-répudiation) et le message est exactement tel qu'elle l'a rédigé (intégrité). Bien sûr, Alice pourrait chiffrer son message à l'aide de la clé publique RSA de Bob (confidentialité) avant de le lui envoyer. Un certificat numérique renferme des informations qui identifient le propriétaire du certificat et contient également la clé publique de ce propriétaire. Les certificats sont signés par l'autorité de certification qui les émet. Ils contribuent à simplifier le processus d'obtention des clés publiques et à vérifier leur propriétaire.
Sécurité de RSA
Comme indiqué plus haut, la sécurité de RSA repose sur la difficulté que représente la factorisation de grands entiers. Cependant, à mesure que la puissance de traitement augmente et que des algorithmes de factorisation plus efficaces sont découverts, il devient possible de factoriser des nombres de plus en plus élevés. La puissance du chiffrement est directement liée à la taille de la clé. De ce fait, un doublement de la longueur de la clé renforce le chiffrement de façon exponentielle, au détriment toutefois des performances.
Les clés RSA font généralement 1024 ou 2048 bits, mais les experts pensent que les clés de 1024 bits pourraient être déchiffrées à brève échéance. C'est la raison pour laquelle l'administration et le secteur privé commencent à adopter des clés d'une longueur minimale de 2048 bits. A moins d'une percée imprévue en informatique quantique, de nombreuses années devraient s'écouler avant que des clés plus longues soient nécessaires, mais la cryptographie à courbe elliptique (ECC, Elliptic Curve Cryptography) fait de plus en plus d'adeptes parmi les spécialistes de la sécurité pour mettre en oeuvre le chiffrement à clé publique en remplacement de RSA.
En effet, cette technologie permet de créer des clés de chiffrement à la fois plus rapides, plus petites et plus efficaces. La plupart des matériels et logiciels actuels sont déjà compatibles ECC et la popularité de la discipline devrait encore augmenter, car elle offre une sécurité équivalente pour une puissance de traitement et une consommation d'énergie moindres, ce qui la rend plus adaptée que RSA aux applications mobiles. Enfin, une équipe de chercheurs au nombre desquels Adi Shamir, co-inventeur de RSA, a réussi à déchiffrer une clé RSA de 4096 bits en utilisant la cryptanalyse acoustique. Cependant, n'importe quel algorithme de chiffrement est vulnérable à ce type d'attaque.
Les inventeurs de l'algorithme RSA ont fondé RSA Data Security en 1983. La société a ensuite été acquise par Security Dynamics, à son tour rachetée par EMC Corporation en 2006. L'algorithme RSA a été diffusé dans le domaine public par RSA Security en 2000.
Vidéo
