RSA : chiffrement jouet

Choisissez deux nombres premiers, saisissez un message et observez RSA le chiffrer puis le déchiffrer.

Exemple résolu — RSA : chiffrement jouet

Clé privée (n, d)	1783

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — RSA : chiffrement jouet

RSA, c’est une seule opération employée deux fois. Chiffrer, c’est m^e mod n ; déchiffrer, c^d mod n — la même exponentiation modulaire, avec un autre exposant. L’astuce consiste à choisir le couple de sorte que l’appliquer deux fois redonne le message, alors que connaître l’un des exposants n’apprend rien sur l’autre. Tout ce qu’affiche le panneau est la recherche de ce couple. Publié par Rivest, Shamir et Adleman en 1978 — et, comme on ne l’a su qu’à la déclassification par le GCHQ en 1997, trouvé quatre ans plus tôt par Clifford Cocks et laissé dans un tiroir.

Ce que signifie chaque symbole

n: le module, p·q. Public. Le secret, ce sont ses facteurs, pas le nombre lui-même.
φ(n): l’indicatrice d’Euler, (p−1)(q−1). Le panneau peut l’afficher parce qu’on lui a donné p et q ; un attaquant ne disposant que de n ne le peut pas, et passer de n à φ est aussi difficile que factoriser.
e: l’exposant public. N’importe quel nombre premier avec φ(n) convient — c’est pourquoi il change quand on change un nombre premier.
d: l’exposant privé, e⁻¹ mod φ(n). Un seul inverse modulaire — immédiat si l’on connaît φ, et tout l’enjeu sinon.

D’où vient la formule

Multipliez les nombres premiers : n = p·q. Aux valeurs par défaut, 61 · 53 = 3233. Ce nombre est publié. Retrouver 61 et 53 à partir de 3233 prend un instant à la main, et c’est la raison honnête pour laquelle on parle ici d’un jouet.
Calculez φ(n) = (p−1)(q−1) = 60 · 52 = 3120. C’est le pivot de tout le schéma : n est public, φ(n) ne l’est pas, et le seul chemin connu de l’un à l’autre passe par la factorisation.
Choisissez e premier avec φ(n), puis résolvez e·d ≡ 1 (mod φ(n)) en d. Le panneau montre 7⁻¹ mod 3120 = 1783. Notez ce que cette étape n’est pas : elle n’est pas difficile. Connaissant φ, c’est un unique inverse modulaire. Le secret de d repose entièrement sur le secret de φ.
Pourquoi l’aller-retour fonctionne : par construction e·d = 1 + kφ(n), donc m^ed = m^1+kφ(n) ≡ m (mod n) — le théorème d’Euler. Le déchiffrement n’est pas une opération inverse inventée à part ; c’est la même exponentiation, avec l’exposant qui défait la première.

Comment lire ce que vous voyez

La ligne à surveiller est e, car ce n’est pas une constante. Aux nombres premiers par défaut elle affiche 7 ; changez p en 67 et elle devient 5. La raison est dans la ligne au-dessus : e doit être premier avec φ(n), et φ est passé de 3120 à 3432. Comparez ensuite les deux exposants à l’écran — e = 7 contre d = 1783. Le public est minuscule, le privé non, et ni l’un ni l’autre n’est un hasard : e est choisi petit exprès pour que le chiffrement soit bon marché, et d est ce que l’inverse donne. La dernière ligne est la preuve que cela a marché : m′ = 42, le nombre que vous avez tapé.

Suppose: Que le message est un nombre plus petit que n. Avec n = 3233, il n’y a rien à chiffrer au-dessus de 3232 — voilà pourquoi le vrai RSA ne chiffre jamais un message directement : il chiffre une clé symétrique complétée de quelques centaines de bits et laisse un chiffrement plus rapide transporter le texte. On suppose aussi p ≠ q, et que vous ne réutilisez jamais un nombre premier dans un second module : deux modules partageant un facteur sont brisés tous les deux par un seul PGCD.
Ne tient plus quand: Vous pouvez casser cette page sans rien factoriser. Mettez p = 67, q = 53 et le message à 3. Le panneau choisit e = 5 et affiche comme chiffré 243 — qui n’est que 3⁵. Comme 3⁵ est plus petit que n = 3551, la réduction modulaire n’a jamais eu lieu : le chiffré est une puissance ordinaire, et la racine cinquième de 243 vaut 3. Pas de clé, pas de factorisation, message retrouvé. Essayez m = 5 : vous obtenez 3125, soit 5⁵ ; à m = 8 la puissance dépasse enfin n et le chiffré devient un 809 inexploitable. Ce n’est pas un défaut de cette page — c’est la raison pour laquelle personne ne chiffre un nombre nu. Le vrai RSA complète d’abord le message par de l’aléa structuré, ce que spécifie la RFC 8017 et ce qui fait d’une exponentiation un cryptosystème.

La clé privée se déduit, elle ne se choisit pas 🖖

Regardez le panneau construire d. Avec les nombres premiers par défaut, il affiche φ(n) = 60 · 52 = 3120, se rabat ensuite sur e = 7 — son 65537 préféré dépasse ici φ lui-même — et calcule enfin d ≡ 7⁻¹ mod 3120 = 1783. Cette dernière étape est un seul inverse modulaire, instantané sur n'importe quelle machine. Rien dans d n'est secret en soi : il tombe directement de φ(n), et φ(n) tombe directement de p et q. RSA ne cache donc pas l'exposant privé, il cache la factorisation. Ici n = 3233, qu'un ordinateur portable casse avant que vous ayez fini cette phrase ; un module RSA-2048 compte 617 chiffres décimaux, et toutes les étapes à l'écran sont par ailleurs identiques.

Le cadenas que vous seul ouvrez 🖖

RSA donne à chacun un cadenas ouvert (votre clé publique) que l'on peut refermer autour d'un message, mais seule votre clé privée peut le rouvrir. Comme fermer et ouvrir utilisent des clés différentes, vous pouvez publier la clé publique au vu de tous sans révéler comment déchiffrer. Cet outil vous laisse parcourir tout le cycle avec de minuscules nombres premiers ; les vrais systèmes suivent les mêmes étapes avec des nombres de centaines de chiffres.

Le chiffrement à l'envers est une signature 🖖

La même opération RSA, exécutée dans l'autre sens, prouve qui a envoyé un message au lieu de le cacher. Si vous « déchiffrez » un message avec votre clé privée, n'importe qui peut le « chiffrer » à nouveau avec votre clé publique pour vérifier qu'il vient bien de vous : c'est une signature numérique. Ainsi un seul calcul assure à la fois la confidentialité et l'authentification, rien qu'en échangeant quelle clé passe en premier.

Problèmes entièrement résolus

Une paire de clés RSA pour p = 61 et q = 53 5 étapes
Générez la paire de clés RSA pour p = 61 et q = 53, puis chiffrez m = 42. Tous les nombres ci-dessous découlent de ces trois valeurs, y compris l'exposant public.
1. Le module est rendu public et l'indicatrice d'Euler est détruite, mais tous deux ne sont qu'à une multiplication près des nombres premiers. φ(n) compte les entiers inférieurs à n qui ne partagent aucun facteur avec lui, ce qui, pour un produit de deux nombres premiers distincts, vaut (p − 1)(q − 1).
  
  $n = 61 \cdot 53 = 3233, ϕ (n) = (61 - 1) (53 - 1) = 60 \cdot 52 = 3120$
2. L'exposant public doit être inversible modulo φ, c'est-à-dire premier avec lui. En factorisant φ, les candidats de petite taille s'éliminent d'eux-mêmes, laissant 7 comme plus petit exposant impair disponible. Les vraies clés utilisent 65537, mais cette valeur est supérieure à ce φ, l'outil se rabat donc sur le plus petit entier premier avec lui.
  
  $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13 ⟹ g cd (3, ϕ) = 3, g cd (5, ϕ) = 5, g cd (7, ϕ) = 1 ⟹ e = 7$
3. Inverser 7 modulo 3120 relève simplement de l'algorithme d'Euclide étendu. Trois divisions permettent d'atteindre un reste égal à 1, et remonter ces trois mêmes étapes exprime ce 1 comme une combinaison de 3120 et de 7.
  
  $3120 = 445 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 ⟹ 1 = 3 \cdot 3120 - 1337 \cdot 7$
4. Le coefficient de 7 dans cette combinaison est négatif, et un inverse négatif est rendu positif en lui ajoutant une fois le module. Le chiffrement est alors une simple exponentiation modulaire, effectuée par deux élévations au carré successives plutôt qu'en multipliant 42 par lui-même sept fois.
  
  $d \equiv - 1337 \equiv 1783 (mod 3120), c = 4 2^{4} \cdot 4 2^{2} \cdot 42 = 1550 \cdot 1764 \cdot 42 \equiv 240 (mod 3233)$
5. Le déchiffrement n'a jamais besoin d'être vérifié par force brute, et pour des tailles de clés réalistes, ce serait d'ailleurs impossible. Les deux exposants ont été construits pour que leur produit soit égal à un plus un multiple de φ, et le théorème d'Euler conclut pour tout m premier avec n — ce qui est le cas de 42.
  
  $e d = 7 \cdot 1783 = 12481 = 4 \cdot 3120 + 1 ⟹ c^{d} \equiv m^{e d} = m (m^{ϕ})^{4} \equiv m = 42$
Réponse

L'outil affiche n = 3233, φ = 3120, d = 1783 et c = 240, puis confirme que 240 se déchiffre bien en 42. Ce qu'il faut retenir, c'est ce qu'est réellement φ. Ce n'est pas un second secret aux côtés de p et q — c'est le même secret écrit différemment. Connaissant n et φ, on a p + q = n − φ + 1 = 114 et pq = 3233, une équation du second degré dont le discriminant est un carré parfait, ce qui redonne 61 et 53 en une seule ligne. Ainsi, un générateur de clés qui divulgue φ divulgue la factorisation tout aussi complètement que s'il avait affiché les nombres premiers ; c'est pourquoi φ est calculé une fois, utilisé pour trouver d, puis éliminé.

$p + q = n - ϕ + 1 = 114, pq = 3233 ⟹ x^{2} - 114 x + 3233 = 0 ⟹ x = 61, 53$
Factorisation de 3233 en 61 × 53 pour déjouer la sécurité RSA 6 étapes
Le panneau factorise 3233 en 61 × 53 avant que vous ayez fini de lire la page. Cette factorisation est toute la sécurité de RSA, apparemment brisée à l'instant. Calculez ce qui rend le même problème impossible une taille de clé plus loin.
1. Les deux nombres dont part le panneau : le module, et l'indicatrice d'Euler qui découle des deux facteurs premiers.
  
  $n = 61 \times 53 = 3233, ϕ (n) = 60 \times 52 = 3120$
2. Un attaquant n'a besoin que d'un fait : le plus petit facteur premier ne peut pas dépasser la racine carrée du module. Tout ce qui serait plus grand exigerait un partenaire plus petit que lui.
  
  $p \leq n ⟹ 3233 = 56.86, π (56) = 16$
3. La recherche parcourt donc les nombres premiers jusqu'à 56, et il y en a seize. Le seizième est 53. Seize divisions, ce n'est pas de la sécurité, c'est une erreur d'arrondi.
  
  $53 < 56.86 \in {2, 3, 5, \dots, 53} ⟹ k \leq 16$
4. Mettez maintenant un module que l'on emploie réellement. 2048 bits, c'est n voisin de 2²⁰⁴⁸, dont la racine carrée vaut 2¹⁰²⁴, soit environ 10³⁰⁸.
  
  $n \approx 2^{2048} ⟹ n = 2^{1024} \approx 1 0^{308}$
5. Chiffrez-le. À un milliard de divisions d'essai par seconde, cela fait 10²⁹⁹ secondes, contre un univers vieux d'environ 4 × 10¹⁷ secondes.
  
  $\frac{1 0 ^{308}}{1 0 ^{9} s ^{- 1}} = 1 0^{299} s \approx 1 0^{291} yr$
6. Le temps est la mauvaise unité pour un nombre pareil ; comparez-le plutôt à quelque chose de physique.
  
  $1 0^{308} ⋙ 1 0^{80}$
Réponse

Seize divisions contre 10³⁰⁸. Or, 10³⁰⁸ représente 10²²⁸ fois le nombre d'atomes de l'univers observable : vous ne pourriez donc même pas stocker le compteur. L'essentiel réside dans la forme plutôt que dans la taille. Le travail de l'attaquant croît en √n tandis que la clé croît en log n, de sorte qu'ajouter deux bits à votre clé double l'effort nécessaire pour la casser, tout en ne vous coûtant que deux bits. Cette asymétrie est l'essence même du système. La réponse instantanée de l'outil n'a rien d'une faille, c'est au contraire la démonstration elle-même. En effet, 3233 illustre précisément l'apparence d'un module lorsqu'on n'a pas laissé à l'asymétrie la place de s'exprimer.

$16 ⟷ 1 0^{308}; O (n), n = 2^{2048}$

Références (4)

The idea RSA is an instance of — public keys, two years earlier: W. Diffie & M. Hellman, "New directions in cryptography." IEEE Transactions on Information Theory 22(6), 644–654, 1976.
What real RSA wraps round the message, and why the bare exponentiation on this page is not a cryptosystem: K. Moriarty (Ed.), B. Kaliski, J. Jonsson & A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2." RFC 8017, November 2016 — RSAES-OAEP in §7.1.
The scheme the tool walks through, including e·d ≡ 1 mod φ(n): R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21(2), 120–126, 1978.
Why the security rests on factoring rather than on hiding d: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, §8.2. CRC Press, 1996. ISBN 978-0-8493-8523-0.

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

p=61, q=53 - p=61, q=53 : exemple classique de RSA pédagogique
Petits nombres premiers - p=7, q=11 : petits nombres premiers, faciles à suivre pas à pas
Nombres premiers plus grands - p=101, q=103 : espace de clés plus grand
Exemple de manuel - p=17, q=19 : exercice de manuel