Cryptographie RSA au Grand oral : l'arithmétique qui protège Internet

Chaque fois qu’apparaît un cadenas dans la barre d’adresse de ton navigateur, ton ordinateur fait de la cryptographie. Et la plupart du temps, une partie du travail repose sur un algorithme que trois chercheurs du MIT, Rivest, Shamir et Adleman, ont publié il y a près de cinquante ans : RSA.

Ce qui rend RSA remarquable, ce n’est pas qu’il chiffre des messages. Vigenère le faisait déjà, et des siècles avant lui, César. Ce qui rend RSA remarquable, c’est qu’il résout un problème que ces chiffres classiques n’ont jamais su résoudre : comment Alice et Bob peuvent-ils communiquer secrètement s’ils ne se sont jamais rencontrés ?

La réponse tient entièrement sur de l’arithmétique modulaire et sur un théorème vieux de 350 ans : le petit théorème de Fermat.

Le problème qu’on veut résoudre

Avec Vigenère ou César, Alice et Bob doivent partager une clé avant de pouvoir communiquer. Ils doivent s’être rencontrés, ou avoir utilisé un canal sûr pour échanger cette clé. Si tu veux comprendre pourquoi ces chiffres classiques finissent tous par céder, va lire l’article sur la cryptanalyse du chiffre de Vigenère : c’est la première moitié de l’histoire.

Le problème, c’est que dans la vraie vie, tu fais un achat sur un site que tu n’as jamais visité. Tu n’as jamais rencontré le vendeur, vous n’avez aucun canal sûr préalable. Pourtant, ton navigateur parvient à établir une communication chiffrée avec lui en quelques millisecondes. Comment ?

En 1976, Whitfield Diffie et Martin Hellman démontrent qu’une communication sécurisée sans échange préalable de clé est théoriquement possible. Ils posent les principes, mais pas la méthode concrète. Deux ans plus tard, Ronald Rivest, Adi Shamir et Leonard Adleman publient la première construction qui fonctionne. C’est RSA.

L’idée asymétrique

RSA repose sur une asymétrie volontaire. Chaque destinataire possède deux clés :

• Une clé publique que tout le monde peut connaître. Elle sert à chiffrer les messages qu’on veut lui envoyer.
• Une clé privée qu’il est seul à connaître. Elle sert à déchiffrer les messages qu’on lui a envoyés.

Les deux clés sont liées mathématiquement : ce que l’une chiffre, l’autre le déchiffre. Mais connaître la clé publique ne permet pas de retrouver la clé privée. C’est toute l’astuce.

Concrètement, Alice publie sa clé publique dans un annuaire. Bob, qui ne connaît pas Alice, récupère cette clé, chiffre son message avec, et envoie le résultat. Seule Alice, qui garde sa clé privée pour elle, peut déchiffrer. Même Eve, qui connaît la clé publique d’Alice aussi bien que Bob, ne peut rien tirer du message intercepté.

Sur le terrain mathématique, l’échange ressemble à ceci.

La construction de RSA, pas à pas

Voici la recette complète.

Étape 1 : deux grands nombres premiers. Alice choisit deux grands nombres premiers, notés $p$ et $q$. Dans les applications réelles, ils font chacun environ 1000 bits, soit 300 chiffres décimaux. Pour raisonner proprement, on va utiliser des premiers minuscules comme $p = 11$ et $q = 13$.

Étape 2 : le module. Alice calcule $n = p \times q$. Avec nos valeurs, $n = 143$. Elle rendra ce nombre public.

Étape 3 : l’indicatrice d’Euler. Elle calcule $\varphi(n) = (p-1)(q-1)$. Ici, $\varphi(143) = 10 \times 12 = 120$. L’indicatrice d’Euler $\varphi(n)$ compte les entiers entre 1 et $n$ qui sont premiers avec $n$. Quand $n = pq$ avec $p$ et $q$ premiers distincts, cette formule se démontre facilement.

Étape 4 : l’exposant public. Elle choisit un entier $e$ premier avec $\varphi(n)$. Pour $\varphi(n) = 120 = 2^3 \times 3 \times 5$, n’importe quel entier impair non divisible par 3 ni 5 fait l’affaire. Prenons $e = 7$. Dans les implémentations réelles, on prend souvent $e = 65537$, pour des raisons d’efficacité du calcul.

Étape 5 : l’exposant privé. C’est l’étape la plus mathématique. Alice cherche $d$ tel que

Comme $e$ et $\varphi(n)$ sont premiers entre eux, le théorème de Bézout garantit l’existence d’un couple d’entiers $(d, k)$ vérifiant $e \cdot d + k \cdot \varphi(n) = 1$. Autrement dit, $d$ est l’inverse modulaire de $e$ modulo $\varphi(n)$. L’algorithme d’Euclide étendu le calcule en quelques étapes. Pour $e = 7$ et $\varphi(n) = 120$, on trouve $d = 103$ (vérification : $7 \times 103 = 721 = 6 \times 120 + 1$).

• Clé publique : le couple $(n, e) = (143, 7)$.
• Clé privée : l’entier $d = 103$ (Alice connaît aussi $n$, qu’elle vient de calculer).

Alice publie $(n, e)$. Elle garde $d$ pour elle. Et surtout, elle détruit $p$, $q$ et $\varphi(n)$ : si Eve les récupérait, toute la sécurité s’effondrerait.

Chiffrer et déchiffrer

Une fois les clés construites, les deux opérations sont d’une simplicité surprenante.

Chiffrement. Bob a un message qu’il veut envoyer à Alice. Pour simplifier, ce message est un entier $m$ strictement plus petit que $n$. Bob récupère la clé publique $(n, e)$ et calcule

Il envoie $c$ à Alice.

Déchiffrement. Alice reçoit $c$. Elle applique sa clé privée :

et elle retrouve le message original. Rien de plus.

Prenons notre triplet $(n, e, d) = (143, 7, 103)$ et un message $m = 9$.

• Chiffrement : $c = 9^7 \bmod 143 = 4\,782\,969 \bmod 143 = 48$.
• Déchiffrement : $m = 48^{103} \bmod 143 = 9$. ✓

On retrouve bien le message original. Amuse-toi à essayer d’autres valeurs dans le composant ci-dessous.

Pourquoi ça marche

Pourquoi $(m^e)^d \equiv m \pmod{n}$ ? Tout découle du petit théorème de Fermat, généralisé par Euler.

Le petit théorème de Fermat

Pour tout nombre premier $p$ et tout entier $a$ non divisible par $p$,

Ce théorème date de 1640. Il se démontre proprement en quelques lignes : on remarque que les entiers $a, 2a, 3a, \dots, (p-1)a$ sont, modulo $p$, une permutation de $1, 2, \dots, p-1$ (parce que $a$ est inversible modulo $p$). Le produit des deux listes donne donc la même valeur modulo $p$, ce qui mène à $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$, puis à $a^{p-1} \equiv 1$.

L’extension d’Euler

Euler généralise ce résultat à n’importe quel entier $n$. Pour tout entier $a$ premier avec $n$,

Quand $n = pq$ est un produit de deux premiers distincts, $\varphi(n) = (p-1)(q-1)$, et on retrouve la formule qui apparaît dans la construction de RSA. Cette généralisation se démontre, mais la preuve dépasse le cadre d’un exposé de Grand oral. On l’admet, quitte à en esquisser l’idée si le jury la demande.

La preuve que RSA est correct

Par construction, $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Il existe donc un entier $k$ tel que $e \cdot d = 1 + k \cdot \varphi(n)$. Alors

par le théorème d’Euler, à condition que $m$ soit premier avec $n$. En pratique, c’est presque toujours le cas : les seuls $m$ qui posent problème sont les multiples de $p$ ou de $q$, et ils représentent une proportion négligeable des messages possibles. Le cas pathologique se traite par le théorème des restes chinois et ne remet pas en cause le résultat.

Pourquoi c’est sûr : la difficulté de factoriser

Plaçons-nous à la place d’Eve. Elle intercepte $c$, et elle connaît $(n, e)$ qui sont publics. Pour déchiffrer, il lui faut $d$. Pour calculer $d$, il lui faut $\varphi(n)$. Pour calculer $\varphi(n) = (p-1)(q-1)$, il lui faut $p$ et $q$. Pour trouver $p$ et $q$, il lui faut factoriser $n$.

C’est là que tient toute la sécurité de RSA : la factorisation des grands entiers est considérée comme un problème difficile. Si $n$ fait 2048 bits (environ 617 chiffres décimaux), tous les algorithmes classiques connus mettent un temps prohibitif à le factoriser.

Le graphique suivant résume trente ans de records de factorisation et les compare au seuil utilisé aujourd’hui pour HTTPS.

Aujourd’hui, les clés RSA utilisées pour sécuriser Internet font 2048 bits, parfois 3072 ou 4096 pour les applications les plus sensibles. La marge de sécurité reste confortable, mais elle s’érode à chaque record.

La menace quantique

Depuis 1994, une menace précise pèse sur RSA. Cette année-là, Peter Shor publie un algorithme qui factorise les grands entiers en temps polynomial, à condition de disposer d’un ordinateur quantique suffisamment grand.

Personne ne possède encore une telle machine, capable de s’attaquer à des clés RSA réelles. Il faudrait plusieurs milliers de qubits logiques stables, et on plafonne aujourd’hui à quelques dizaines. Mais le jour où ces ordinateurs existeront, toute la cryptographie asymétrique actuelle s’effondrera d’un coup. Non seulement RSA, mais aussi les courbes elliptiques et Diffie-Hellman.

La communauté s’est préparée. En août 2024, le NIST publie les premiers standards de cryptographie post-quantique : CRYSTALS-Kyber pour l’échange de clés, CRYSTALS-Dilithium pour les signatures. Ces algorithmes reposent sur la difficulté supposée de problèmes de réseaux euclidiens, et non sur la factorisation. L’idée est de bâtir une cryptographie qui résistera à Shor, avant même que les ordinateurs quantiques correspondants ne deviennent réalité.

Une inquiétude persiste, derrière toute cette préparation : le scénario dit « harvest now, decrypt later », que l’on peut traduire par « récolter aujourd’hui, déchiffrer plus tard ». Certains acteurs enregistrent dès maintenant des communications chiffrées en RSA, en attendant d’avoir la machine qui leur permettra de les lire, dans quelques années ou quelques décennies. Si tes données doivent rester secrètes pendant trente ans, ne te repose pas uniquement sur RSA.

Pour prendre la mesure des ordres de grandeur, voici les tailles de clés des différents systèmes cryptographiques rencontrés dans cet article et dans la vraie vie :

Ton plan Grand oral, minute par minute

L’épreuve du Grand oral se déroule en deux temps de 10 minutes : un exposé en monologue, puis un échange avec le jury. Voici un plan calibré pour la phase d’exposé. RSA est un sujet ambitieux, dense en arithmétique, qui demande de tenir un rythme soutenu sans jamais bâcler une étape.

Petite frise chronologique

graph LR
  A["Diffie-Hellman
1976"] --> B["RSA
1977-1978"]
  B --> C["PGP
1991"]
  C --> D["Shor
1994"]
  D --> E["NIST PQC
2024"]

Ta checklist avant le passage

Pour conclure

RSA est l’un des plus beaux ponts entre mathématiques pures et applications concrètes. Ce que Fermat découvre en 1640 en observant des propriétés des nombres premiers sert, près de 350 ans plus tard, à sécuriser des milliards de transactions financières chaque jour. Sans Fermat, pas d’Euler. Sans Euler, pas de RSA. Sans RSA, pas de commerce en ligne tel qu’on le connaît.

La leçon dépasse le Grand oral. Les mathématiques pures ont cette habitude déconcertante de devenir utiles bien longtemps après que leurs inventeurs les ont abandonnées. Quand Fermat jouait avec les congruences modulo un premier, il ne pouvait pas imaginer que ses observations deviendraient un jour l’infrastructure invisible du commerce mondial.

Si tu maîtrises la construction de RSA, la preuve appuyée sur Fermat généralisé par Euler, et la nuance sur la sécurité conjecturale, tu tiens un Grand oral de très bon niveau. Ambitieux, solidement arithmétique, et porteur d’une vraie leçon sur le rapport entre les mathématiques et le monde. C’est exactement ce qu’un jury espère sur un sujet de cette envergure.

Sources

• Rivest, R. L., Shamir, A., Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Communications of the ACM, 21(2), pp. 120-126. (L’article fondateur.)
• Diffie, W., Hellman, M. E. (1976). “New Directions in Cryptography”. IEEE Transactions on Information Theory, 22(6), pp. 644-654. (L’article qui pose l’idée de la cryptographie asymétrique sans en donner la construction.)
• Shor, P. W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing, 26(5), pp. 1484-1509. (L’algorithme quantique qui menace RSA.)
• NIST (2024). FIPS 203, FIPS 204, FIPS 205 : premiers standards post-quantiques. (Disponibles sur nist.gov.)
• Stern, J. (1998). La science du secret. Odile Jacob. (Vulgarisation de référence en français, par un cryptographe français de premier plan.)
• Singh, S. (1999). The Code Book. Anchor Books. (Vulgarisation grand public, excellent chapitre sur RSA.)