RSA et la cryptographie à clé publique
Pour envoyer un secret à quelqu’un que vous n’avez jamais rencontré, il faut un moyen de lui transmettre la clé sans que personne ne la voie. La cryptographie à clé publique résout ce casse-tête : le destinataire publie une clé qui sert à fermer le cadenas, et lui seul garde celle qui l’ouvre. Le procédé le plus célèbre s’appelle RSA, d’après les initiales de ses trois inventeurs, et il protège depuis près de cinquante ans des achats en ligne, des connexions à distance et des signatures. Cet article en explique l’idée, les calculs (avec de tout petits nombres que vous pouvez refaire à la main), la raison pour laquelle il est difficile à casser, la manière dont on l’emploie vraiment, les erreurs qui l’ont mis en défaut et ce qui le remplacera face à l’ordinateur quantique.
- Rubrique
- Sécurité informatique
- Niveau
- Intermédiaire
- Lecture
- 25 min (essentiel)
27 min (complet) - Révision
- 4 novembre 2026
En bref
- RSA repose sur une paire de clés : la clé publique (que tout le monde peut connaître) chiffre, la clé privée (que seul le propriétaire possède) déchiffre.
- Sa sécurité vient d’un fait de calcul : multiplier deux très grands nombres premiers (des nombres qui n’ont pas d’autres diviseurs qu’eux-mêmes et 1) est immédiat, retrouver ces deux nombres à partir du produit est hors de portée.
- RSA est lent et ne chiffre que de petits blocs : on l’emploie surtout pour protéger une clé de session, puis un procédé rapide chiffre le message lui-même.
- Utilisé brut, RSA est dangereux : il faut un bourrage (des octets ajoutés suivant une norme), des clés d’au moins 2 048 bits (3 072 pour durer), et un générateur de nombres aléatoires fiable.
- L’ordinateur quantique, quand il sera assez puissant, cassera RSA : les autorités fixent déjà la sortie de RSA vers 2030-2035 et préparent des remplaçants.
Prérequis conseillés : La cryptographie
1Le problème que RSA résout
Imaginez que vous deviez écrire à une personne que vous ne connaissez pas encore, par exemple le site d’une banque, et que vous ne puissiez le faire que par un courrier que n’importe qui peut lire en chemin. Si vous chiffrez votre message avec un code, il faut que le destinataire connaisse ce code. Mais comment lui transmettre le code sans qu’on l’intercepte ? Pendant des siècles, la seule réponse a été de se rencontrer avant, ou de confier la clé à un messager sûr. C’est le chiffrement symétrique : la même clé sert à fermer et à ouvrir. Il est rapide et solide, mais il suppose que les deux personnes partagent déjà un secret (l’article sur la cryptographie détaille cette distinction).
On présente parfois RSA comme « le premier algorithme de chiffrement à clé publique ». L’idée de la clé publique est plus subtile et plus belle. Au lieu d’une seule clé, chaque personne en possède deux, liées mathématiquement :
- la clé publique, que vous pouvez afficher sur votre site, imprimer sur votre carte de visite ou envoyer à tout le monde ; elle permet de fermer un message à votre intention ;
- la clé privée, que vous gardez pour vous seul ; elle permet de l’ouvrir.
L’image classique est celle du cadenas : vous distribuez des milliers de cadenas ouverts à votre nom. Quiconque veut vous écrire met son message dans une boîte et la ferme avec l’un de vos cadenas. Une fois fermée, personne ne peut la rouvrir, pas même celui qui vient de la fermer. Vous seul avez la clé. On parle de chiffrement asymétrique, parce que les deux sens ne sont pas symétriques : ce que l’une des clés fait, l’autre seule peut le défaire.
1.1Une idée des années 1970
L’histoire officielle s’écrit en trois temps. En 1976, deux chercheurs américains, Whitfield Diffie et Martin Hellman, publient l’idée générale de la cryptographie à clé publique et proposent une méthode pour que deux personnes se mettent d’accord sur un secret commun en échangeant seulement des messages publics (cet « échange de clés » porte leur nom). Ils décrivent aussi, sans savoir comment la réaliser, un système où l’on chiffre avec une clé et où l’on déchiffre avec une autre. En 1977, trois chercheurs du MIT (un institut technologique américain), Ronald Rivest, Adi Shamir et Leonard Adleman, trouvent une réalisation concrète : c’est RSA, dont le nom reprend leurs initiales. Elle est exposée dans une revue savante en février 1978, et ses auteurs reçoivent en 2002 le prix Turing, la plus haute distinction de l’informatique.
Le troisième temps est resté secret vingt ans. Dès 1970-1973, des ingénieurs du service britannique de renseignement électronique (le GCHQ), James Ellis, Clifford Cocks et Malcolm Williamson, avaient imaginé les mêmes idées, y compris un procédé presque identique à RSA. Elles sont restées classées secret-défense et n’ont été rendues publiques qu’en 1997. Voir l’encadré d’anecdotes plus bas.
1.2Ce qu’on fait avec une paire de clés
Une paire de clés RSA sert à deux choses, qui sont les deux faces d’une même pièce :
- Garder un secret : on chiffre avec la clé publique du destinataire, il déchiffre avec sa clé privée. Personne d’autre ne peut lire (cet article).
- Prouver qui l’on est : on « signe » un message avec sa clé privée, et chacun peut vérifier avec la clé publique que la signature est bonne. Personne d’autre n’a pu la produire (voir la signature électronique).
Dans les deux cas, la règle est la même : la clé publique ne sert qu’à des opérations que tout le monde a le droit de faire ; la clé privée ne quitte jamais son propriétaire. Reste une question que RSA seul ne règle pas : comment être sûr que la clé publique que vous avez reçue appartient bien à la personne annoncée ? C’est le rôle des certificats, présentés dans l’article sur les infrastructures à clés publiques.
1.3Le plan de l’article
La partie 2 pose les quelques notions de calcul nécessaires. La partie 3 fabrique une paire de clés avec de petits nombres (figure 1). La partie 4 chiffre et déchiffre un message (figure 2). La partie 5 explique pourquoi le calcul tombe juste et la partie 6 pourquoi on ne sait pas le casser. La partie 7 montre comment on utilise RSA vraiment (figure 3) et la partie 8 les erreurs qui l’ont mis en défaut. La partie 9 traite de l’avenir et la partie 10 corrige quelques idées reçues.
Pour s’exercer
Exercice 1 : quelle clé pour quoi ?
Bob veut écrire à Alice un message que seule elle pourra lire. (a) Quelle clé de qui utilise-t-il ? (b) Alice veut ensuite prouver qu’un message vient bien d’elle : quelle clé utilise-t-elle, et qui peut vérifier ?
Voir la réponse
(a) Bob chiffre avec la clé publique d’Alice ; seule la clé privée d’Alice peut déchiffrer. La clé de Bob n’intervient pas. (b) Alice signe avec sa clé privée ; tout le monde peut vérifier avec sa clé publique. La règle : on chiffre avec la clé publique du destinataire, on signe avec sa propre clé privée.
2Les notions de calcul dont on a besoin
Pas d’inquiétude : tout RSA tient avec quatre idées de collège, que l’on retrouve aussi dans l’article sur les nombres.
2.1Nombres premiers et factorisation
Un nombre premier est un entier plus grand que 1 qui n’a pas d’autre diviseur que 1 et lui-même : 2, 3, 5, 7, 11, 13, 17… Tout entier se décompose de façon unique en un produit de nombres premiers : 3 233 = 53 × 61, et 3 233 ne se décompose pas autrement. Trouver cette décomposition s’appelle factoriser.
Une asymétrie est au cœur de tout : multiplier est facile, factoriser est difficile. Multiplier deux nombres de mille chiffres chacun, un ordinateur ordinaire le fait en une fraction de seconde. Retrouver ces deux nombres à partir de leur produit, avec les méthodes connues, demanderait des milliers d’années de calcul pour des nombres de cette taille. On ne sait pas démontrer qu’il n’existe pas de méthode rapide ; on n’en connaît simplement pas, malgré des siècles de recherches. Cette asymétrie est ce qu’on appelle une fonction à sens unique : facile dans un sens, pratiquement impossible dans l’autre.
2.2Le calcul « modulo »
Quand on dit « 17 modulo 5 », on demande le reste de la division de 17 par 5 : 17 = 3 × 5 + 2, donc 17 modulo 5 vaut 2. On écrit souvent « mod ». Pensez à une horloge à cinq heures : après 4 on revient à 0. Ainsi 3 + 4 = 7 devient 2 sur cette horloge. Le calcul modulo reste exact pour les additions et les multiplications : on peut réduire à chaque étape sans changer le résultat final. Les nombres ne dépassent alors jamais la taille du nombre n choisi. Notez que l’on écrit souvent « mod(n) » à la fin de chaque ligne, ce qui fait régulièrement poser la question : cela signifie simplement « on ne garde que le reste de la division par n ».
2.3L’indicatrice d’Euler
Pour un nombre n qui est le produit de deux nombres premiers distincts p et q, le mathématicien suisse Leonhard Euler (XVIIIe siècle) a défini une quantité notée φ(n) (lire « phi de n »), qui compte les nombres entre 1 et n sans diviseur commun avec n. Pour ce cas, elle vaut simplement φ(n) = (p − 1) × (q − 1). On l’appelle aussi « indicateur d’Euler ». Une propriété remarquable, le théorème d’Euler, dit que pour tout nombre M sans diviseur commun avec n, on a Mφ(n) mod n = 1. C’est le moteur caché de RSA : s’élever à la puissance φ(n) ramène toujours à 1.
2.4L’inverse modulaire
Dans les nombres ordinaires, l’inverse de 3 est 1/3, car 3 × (1/3) = 1. Dans le calcul modulo φ(n), on cherche de même un nombre d tel que e × d mod φ(n) = 1 : on dit que d est l’inverse de e modulo φ(n). Il existe si et seulement si e et φ(n) n’ont pas de diviseur commun, et un algorithme vieux de plus de deux mille ans, celui d’Euclide (étendu), le trouve très vite, même avec de très grands nombres. On trouve parfois l’écriture « e = 1/d mod(…) », qui revient à la même idée, mais reste un peu trompeuse.
Pour s’exercer
Exercice 2 : une paire de clés minuscule
On choisit p = 5 et q = 11. Calculez n et φ(n). Avec e = 3, trouvez d (indice : cherchez d tel que 3 × d vaut 1 plus un multiple de φ(n)). Chiffrez M = 9, puis vérifiez le déchiffrement.
Voir la réponse
n = 5 × 11 = 55 et φ(n) = 4 × 10 = 40. On cherche d tel que 3d = 1 + 40k : pour k = 2, 3d = 81, donc d = 27. Chiffrement : 93 = 729 ; 729 = 13 × 55 + 14, donc c = 14. Déchiffrement : 1427 mod 55 = 9 (on le vérifie avec une calculette qui sait réduire modulo à chaque étape, ou en décomposant la puissance). Le message est retrouvé.