RSA expliqué

Chaque fois qu'un navigateur affiche un cadenas, qu'un message est signé ou qu'un logiciel vérifie une mise à jour, la cryptographie à clé publique est à l'œuvre, et RSA en est la forme la plus connue. Son idée : la clé qui verrouille un message peut être publiée, tandis que celle qui l'ouvre reste privée. Fait remarquable, tout le système repose sur l'arithmétique enseignée à l'école : les nombres premiers, la multiplication et les restes.

Les nombres premiers secrets 61 et 53 donnent le module public 3233. Les lettres de HELLO deviennent 3000, 28, 2726, 2726 et 1307 avec l'exposant public 17, et l'exposant privé 2753 ramène 3000 à 72
Les nombres premiers secrets 61 et 53 donnent le module public 3233. Les lettres de HELLO deviennent 3000, 28, 2726, 2726 et 1307 avec l'exposant public 17, et l'exposant privé 2753 ramène 3000 à 72

Le problème que résout RSA

Les chiffrements plus anciens, du chiffre de César à l'AES moderne, utilisent la même clé pour verrouiller et déverrouiller, si bien que les deux parties doivent d'abord partager une clé secrète en privé. La cryptographie à clé publique supprime cette étape. Chaque personne possède deux clés : une clé publique que n'importe qui peut utiliser pour lui chiffrer un message, et une clé privée qu'elle seule détient et qui seule permet de le déchiffrer. Whitfield Diffie et Martin Hellman ont décrit cette idée en 1976, et un an plus tard Ron Rivest, Adi Shamir et Leonard Adleman, au MIT, ont trouvé un moyen de la réaliser, baptisé RSA d'après leurs initiales.

Martin Hellman (à gauche) et Whitfield Diffie (à droite), 1977
Martin Hellman (à gauche) et Whitfield Diffie (à droite), 1977

Fabriquer les clés

Choisissez deux grands nombres premiers, p et q, et multipliez-les : n = p × q. Calculez φ(n) = (p − 1)(q − 1), l'indicatrice d'Euler, qui compte les nombres inférieurs à n n'ayant aucun facteur commun avec lui. Prenez un exposant public e sans facteur commun avec φ(n) ; 65537 est le choix habituel. Trouvez ensuite l'exposant privé d tel que e × d laisse un reste de 1 dans la division par φ(n). L'algorithme d'Euclide étendu le fait rapidement. La clé publique est la paire (e, n) ; la clé privée est d. Avec p = 61 et q = 53, on obtient n = 3233, φ(n) = 3120, e = 17 et d = 2753.

Chiffrer et déchiffrer

Un message est d'abord transformé en un nombre m inférieur à n. Pour le chiffrer, on calcule c = mᵉ mod n, le reste de mᵉ dans la division par n. Pour déchiffrer, on calcule cᵈ mod n. Le théorème d'Euler garantit que l'on retrouve ainsi m, car e × d dépasse de 1 un multiple de φ(n). Avec les clés ci-dessus, la lettre A, de code 65, devient 65¹⁷ mod 3233 = 2790, et 2790²⁷⁵³ mod 3233 = 65 à nouveau. Des puissances aussi grandes ne sont jamais écrites en entier : l'élévation au carré répétée les calcule avec une élévation au carré par bit de l'exposant, en prenant le reste à chaque étape.

Signatures numériques

RSA fonctionne aussi à l'envers. Élever un message à l'exposant privé, s = mᵈ mod n, produit une signature que seul le propriétaire de la clé peut créer. N'importe qui peut la vérifier avec la clé publique : si sᵉ mod n redonne m, le message vient du détenteur de d et n'a pas été modifié en chemin. En pratique, on signe une courte empreinte (hash) du message plutôt que le message lui-même. De telles signatures protègent les mises à jour de logiciels, les sites web sécurisés et les documents électroniques.

Pourquoi il est sûr

Tout le monde peut voir n et e. Pour trouver d, un attaquant a besoin de φ(n), et pour trouver φ(n), il lui faut p et q : casser RSA revient donc à factoriser n. Multiplier deux nombres premiers prend à un ordinateur une fraction de microseconde ; décomposer le produit pour les retrouver est réputé extrêmement difficile. Le plus grand nombre du défi RSA factorisé à ce jour, RSA-250 en 2020, compte 829 bits et a demandé environ 2700 années de calcul. Les clés utilisées aujourd'hui comptent au moins 2048 bits, soit environ 617 chiffres.

Un secret découvert deux fois

En 1973, quatre ans avant RSA, le mathématicien britannique Clifford Cocks a trouvé le même schéma alors qu'il travaillait pour l'agence de renseignement GCHQ, en s'appuyant sur une idée de son collègue James Ellis. Ces travaux étaient classifiés et n'ont été rendus publics qu'en 1997. RSA lui-même a été breveté aux États-Unis en 1983 ; le brevet a expiré en septembre 2000, deux semaines après que l'algorithme a été placé dans le domaine public.

Ron Rivest, Adi Shamir et Len Adleman (de gauche à droite)
Ron Rivest, Adi Shamir et Len Adleman (de gauche à droite)

RSA en pratique

Le vrai RSA ne chiffre jamais un texte directement. Le message est complété par des octets aléatoires, selon un schéma comme OAEP, pour que le même message soit chiffré différemment à chaque fois et qu'aucune régularité ne puisse fuiter. Comme RSA est lent, on l'utilise surtout pour échanger ou protéger une courte clé destinée à un chiffrement symétrique rapide comme AES, ou pour signer. Des ordinateurs quantiques suffisamment grands pourraient factoriser n rapidement grâce à l'algorithme de Shor de 1994, c'est pourquoi de nouvelles méthodes post-quantiques sont introduites aux côtés de RSA.

À vous d'explorer

Ouvrez la démo du chiffrement RSA pour construire des clés à partir de vos propres nombres premiers ou de nombres premiers aléatoires de 2 à 8 chiffres, voir l'algorithme d'Euclide étendu trouver d ligne par ligne, chiffrer ou signer un message caractère par caractère et suivre l'élévation au carré répétée pour n'importe quel caractère. Laissez ensuite Eve factoriser n et regardez comment le temps dont elle a besoin augmente avec la taille des nombres premiers.

Questions fréquemment posées

Pourquoi RSA a-t-il besoin de nombres premiers ?

Parce que φ(n) n'est facile à calculer que si l'on sait comment n se décompose en facteurs premiers. Pour n = p × q avec p et q premiers, φ(n) = (p − 1)(q − 1). Les nombres premiers rendent aussi n aussi difficile que possible à factoriser pour sa taille, puisqu'il n'a aucun petit facteur.

Pourquoi e vaut-il souvent 65537 ?

65537 = 2¹⁶ + 1 est premier et ne contient que deux 1 en binaire, si bien que chiffrer avec lui ne demande que 16 élévations au carré et une multiplication. Il est aussi assez grand pour éviter les faiblesses des très petits exposants comme 3.

Quelle est la différence entre RSA et Diffie–Hellman ?

Diffie–Hellman permet à deux personnes de convenir d'une clé secrète partagée sur un canal ouvert ; à lui seul, il ne chiffre ni ne signe rien. RSA chiffre et signe directement avec une paire de clés. Tous deux reposent sur des problèmes faciles dans un sens et difficiles dans l'autre : la factorisation pour RSA, le logarithme discret pour Diffie–Hellman.

Les clés de la démo peuvent-elles servir à un vrai chiffrement ?

Non. Ses nombres premiers ont au plus une douzaine de chiffres, si bien que toute clé qu'elle produit peut être factorisée en quelques secondes ou moins, et elle chiffre chaque caractère séparément, sans remplissage. Elle sert à voir comment fonctionne RSA, pas à protéger quoi que ce soit.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir la démo du chiffrement RSA