Découvre le secret du chiffrement RSA, le gardien de tes achats en ligne.
Imagine : tu veux envoyer un secret à ton ami Bob par la poste, mais le facteur est curieux. Avec les méthodes anciennes, vous devez utiliser la même clé pour fermer et ouvrir la boîte à secret. Le problème ? Comment transmettre cette clé à Bob sans que le facteur ne la vole ? C'est le problème de la cryptographie symétrique.
Trois génies (Rivest, Shamir, Adleman) ont trouvé la solution : La Cryptographie Asymétrique. C'est comme si Bob distribuait à tout le monde des cadenas ouverts dont lui seul possède la clé pour les ouvrir. Tout le monde peut fermer une boîte, mais seul Bob peut l'ouvrir.
Simulateur simplifié — en pratique RSA utilise des nombres à 2 048 bits, mais le principe est identique.
Choisis deux nombres premiers distincts :
Le RSA ne fonctionne que parce qu'il est très facile de multiplier deux grands nombres premiers, mais quasiment impossible pour un ordinateur de faire le chemin inverse (retrouver les facteurs à partir de n).
On choisit deux grands nombres premiers \(p\) et \(q\).
Module : \(n = p \times q\).
Indicatrice d'Euler : \(\varphi(n) = (p-1)(q-1)\).
On choisit \(e\) premier avec \(\varphi(n)\).
Clé Publique = \((e,\, n)\).
On calcule \(d\) tel que \(e \times d \equiv 1 \pmod{\varphi(n)}\).
Clé Privée = \((d,\, n)\).
Chiffrement : \(C = M^e \bmod n\) | Déchiffrement : \(M = C^d \bmod n\)
On sait calculer \(C = M^e \bmod n\), mais comment est-on certain que \(C^d \bmod n\) redonne exactement \(M\) ? Ce n'est pas une coïncidence : c'est une conséquence d'un grand théorème de mathématiques.
Si \(\gcd(M, n) = 1\), alors :
\[ M^{\,\varphi(n)} \equiv 1 \pmod{n} \]
Cas particulier quand \(n\) est premier : c'est le petit théorème de Fermat \(M^{p-1} \equiv 1 \pmod{p}\).
On a construit \(d\) de sorte que \(e \times d \equiv 1 \pmod{\varphi(n)}\), c'est-à-dire qu'il existe un entier \(k\) tel que : \[ e \times d = 1 + k \cdot \varphi(n) \] En déchiffrant, on calcule : \[ C^d \bmod n = \left(M^e\right)^d \bmod n = M^{e \cdot d} \bmod n \] On remplace \(e \cdot d\) : \[ M^{e \cdot d} = M^{1 + k\,\varphi(n)} = M \cdot \left(M^{\varphi(n)}\right)^k \] Par le théorème d'Euler, \(M^{\varphi(n)} \equiv 1 \pmod n\), donc : \[ M \cdot \left(M^{\varphi(n)}\right)^k \equiv M \cdot 1^k \equiv M \pmod{n} \] On retrouve bien \(M\) !
Bob reçoit \(C\) (le message chiffré) via le réseau. Ce nombre est public — l'espion peut le lire, mais ne peut rien en faire sans \(d\).
Bob utilise sa clé privée \(d\), connue de lui seul. Sans factoriser \(n\), il est impossible de retrouver \(d\) à partir de la clé publique \((e, n)\).
Bob calcule \(M = C^d \bmod n\) grâce à l'exponentiation modulaire rapide, même si \(d\) est énorme (des centaines de chiffres).
Bob obtient \(M\), le message original. La magie : seul lui pouvait faire ce calcul, car seul lui connaît \(d\).
En pratique, chaque lettre ou bloc de texte est converti en nombre. Voici un exemple avec \(p=13,\; q=17\) (donc \(n=221,\; e=5,\; d=77\)) :
| Lettre | Code M | Calcul C = M⁵ mod 221 | Chiffré C | Calcul M = C⁷⁷ mod 221 | Retrouvé |
|---|
Bob utilise les clés de son simulateur (partie 3). Essaie de déchiffrer un message chiffré toi-même en entrant un \(C\) ci-dessous.
⬆️ Ces valeurs sont synchronisées automatiquement avec le simulateur (partie 3).
L'espion connaît \((e, n, C)\) — tout ce qui circule en public. Pour trouver \(d\), il devrait calculer \(\varphi(n) = (p-1)(q-1)\), ce qui nécessite de connaître \(p\) et \(q\) séparément.
Or factoriser \(n\) (trouver \(p\) et \(q\) à partir de leur produit) est un problème exponentiellement difficile : avec des nombres à 2 048 bits, les meilleurs ordinateurs actuels mettraient des milliards d'années.
💡 C'est pour ça que RSA sera peut-être vulnérable aux ordinateurs quantiques (algorithme de Shor), ce qui explique le développement actuel de la cryptographie post-quantique.