RSA : les nombres premiers
13 × 17 = 221. Ça, tu le calcules de tête. Si on te donne 221 et la question de savoir quels étaient ces deux nombres premiers, il faut essayer : 3 ? 7 ? 11 ? 13, gagné. Une minute de travail. Prends des nombres de 300 chiffres et cette minute devient plus longue que l'âge de l'univers — alors que la multiplication, elle, se fait toujours en une fraction de seconde. C'est sur ce déséquilibre que repose RSA.
Les mots dont tu as besoin
- Nombre premier
- Un nombre qui n'est divisible que par 1 et par lui-même : 2, 3, 5, 7, 11, 13… Plus tu regardes loin, plus ils se font rares, mais ils ne s'arrêtent jamais — Euclide l'a déjà prouvé, il y a plus de deux mille ans.
- Décomposer en facteurs
- Ramener un nombre aux nombres premiers dont il est composé. 221 devient 13 × 17. C'est le calcul que RSA doit rendre impossible.
- Fonction à trappe
- Un calcul qui va facilement vers l'avant et qui est impossible à l'envers — sauf si tu connais un secret, et alors ça marche quand même. Comme une trappe : on y tombe sans peine, on n'en ressort plus, sauf si on sait où est la poignée.
- OAEP
- Le remplissage qu'on ajoute au message avant de le chiffrer : des octets aléatoires selon une recette fixe. Sans ce remplissage, le même message donne toujours le même texte chiffré, et c'est une fuite — le même problème qu'une IV manquante dans chapitre 4.
Comment ça marche, sans les formules
- Ton ordinateur choisit deux énormes nombres premiers et les garde secrets.
- Il les multiplie. Ce produit, tout le monde peut le voir ; il se trouve dans ta clé publique.
- Chiffrer est un calcul avec ce produit — du calcul sur une horloge, comme dans chapitre 5, mais sur une horloge de plusieurs centaines de chiffres de circonférence.
- Déchiffrer est le même genre de calcul, mais il te faut pour ça les deux nombres premiers eux-mêmes. Toi tu les as, et personne d'autre.
Qui a ta clé publique a donc le produit. Pour déchiffrer, il doit le décomposer. C'est possible — en théorie. Seulement, ça dure trop longtemps, et c'est là toute la sécurité. Aucune serrure, juste un calcul que personne n'arrive à terminer.
Essaie toi-même
La paire de clés est créée dans ton navigateur et disparaît dès que tu fermes cet onglet. Tu peux tranquillement regarder la clé privée ici : elle a été faite pour cette page et ne sert à rien d'autre. Avec une vraie clé, tu ne fais jamais ça.
- Clique sur Crée une paire de clés. Ça prend un moment : ton ordinateur cherche deux nombres premiers. Tu vois ta clé publique — ce bloc de texte, tu peux le donner à tout le monde.
- Clique sur Montre la clé privée. Compare les deux blocs : la privée est plus de quatre fois plus longue. En dessous se trouvent p et q, les deux nombres premiers de l'étape 1, et le produit qui se trouve dans ta clé publique.
- Clique sur Chiffrer avec la clé publique. Le texte chiffré fait toujours exactement 256 octets, même si ton message est très court.
- Clique sur Déchiffrer avec la clé privée. Ton message revient.
- Colle maintenant un texte long dans le champ du message — quelques paragraphes — et chiffre. Ça ne marche pas. Lis pourquoi.
Pourquoi tu t'es heurté à un mur
RSA avec une clé de 2048 bits ne peut chiffrer que 190 octets. Ce n'est pas un réglage qu'on peut augmenter : le message doit rester plus petit que le nombre avec lequel on calcule. Une clé plus grande n'aide presque pas et rend tout plus lent. Le chiffrement asymétrique n'est donc pas fait pour transporter des messages.
Pour quoi alors ? Pour deux choses : envoyer une clé AES toute fraîche à quelqu'un sans rien avoir convenu au préalable, et signer. Ce deuxième point fait l'objet de chapitre 7.1. La façon dont tout se rejoint, c'est chapitre 7.3.
Mais d'abord, quelque chose de plus beau. RSA calcule avec des nombres premiers de 600 chiffres. Il existe une manière plus élégante d'obtenir le même résultat avec des nombres bien plus petits : calculer avec des points sur une ligne courbe. Elle se trouve dans ta carte d'identité, dans ton navigateur, et dans Bitcoin. Le chapitre suivant te fait cliquer dessus.
Quelle taille doit faire une telle clé
| Clé | C'est un nombre de | Verdict |
|---|---|---|
| RSA-1024 | 309 chiffres | trop petite, déconseillée depuis des années |
| RSA-2048 | 617 chiffres | la norme aujourd'hui |
| RSA-4096 | 1234 chiffres | plus large, et nettement plus lente |
Cette lenteur n'est pas un détail. Créer une paire de clés prend un temps perceptible — tu l'as remarqué au premier bouton — parce que ton ordinateur doit chercher jusqu'à trouver deux nombres premiers. Et chaque doublement de la longueur de clé rend le calcul environ huit fois plus lourd. C'est exactement pour ça que le monde passe aux courbes, et c'est chapitre 6.2.
Voici les maths : les nombres premiers comme rue à sens unique
Multiplier et décomposer sont l'inverse l'un de l'autre, et pourtant un sens est trivial et l'autre impraticable. Le meilleur algorithme que nous connaissions pour décomposer un nombre de 617 chiffres — le crible général de corps de nombres — occuperait tous les ordinateurs du monde réunis plus longtemps que l'univers n'existe. Non pas parce que c'est impossible, mais parce que ça dure trop longtemps.
Et fais attention à ce qui est écrit là : le meilleur algorithme que nous connaissions. Personne n'a prouvé que décomposer est difficile. Si demain on trouve une méthode rapide, RSA tombe le jour même. Ce n'est pas du catastrophisme mais la façon dont le métier fonctionne : la sécurité d'internet repose sur des problèmes dont nous savons seulement que beaucoup de gens intelligents n'ont pas réussi à les résoudre. Ça, c'est la théorie des nombres, la matière qu'on a qualifiée pendant des siècles d'« inutile mais belle ».