Visualisation du chiffrement RSA — Clés publiques et le piège de la factorisation

Choisissez deux nombres premiers p et q. L'app dérive la paire de clés (n = pq, φ = (p−1)(q−1), e·d ≡ 1 mod φ), anime le chiffrement comme multiplication pliée C = Mᵉ mod n, puis casse de petites clés en direct avec la rho de Pollard — pourquoi RSA 2048 bits reste sûr.

Multiplication pliée : C = Mᵉ mod n

Multiplier, puis replier le dépassement en soustrayant des multiples de n — les nombres n'explosent jamais. Petit e : un pli par puissance ; grand e : méthode élever-au-carré-et-multiplier (log₂ e étapes).

— —
—

Chiffrement par caractère

M est le point de code du caractère, C son chiffré. La colonne ✓ confirme que la clé privée déchiffre C pour retrouver M.

Caractère M C = Mᵉ mod n ✓

Rho de Pollard : tortue et lièvre sur f(x) = x² + 1

La tortue fait un pas, le lièvre deux. Quand leur différence partage un facteur avec n, gcd(|x−y|, n) scinde la clé. Travail attendu ≈ √(πp/2) — exponentiel en les chiffres de p.

Étape i x (tortoise) y (hare) gcd(|x−y|, n)

Coût de cassage : division d'essai vs ρ

Les deux attaques dépendent du plus petit premier p — la division d'essai linéairement en p, ρ comme √p. Le vrai RSA utilise n sur 2048 bits (617 chiffres) : même ρ est désespéré ; reste le crible algébrique, ~10¹⁸ cœurs-années.

Division d'essai
—
Rho de Pollard
—
—

Le trou de serrure caché dans la multiplication facile

Multiplier deux premiers est trivial ; les retrouver depuis le produit est (pour autant qu'on sache) difficile. RSA repose sur cet écart. La clé publique est (n, e) avec n = pq ; n'importe qui chiffre M en C = Mᵉ mod n. L'exposant privé d inverse e car e·d ≡ 1 (mod φ(n)), où φ(n) = (p−1)(q−1) est l'indicatrice d'Euler. Le théorème d'Euler garantit M^(ed) = M^(1+kφ) ≡ M (mod n), donc élever C à la puissance d restitue le message. Qui connaît p et q calcule φ puis d en millisecondes — le trou de serrure. Un attaquant ne voit que n et doit le factoriser.

Pourquoi plier après chaque multiplication

Mᵉ pour e = 65537 compte environ 5·e·log₁₀M chiffres — bien au-delà des atomes de l'univers. Le sauveur, c'est le modulo : après chaque multiplication, soustraire n autant de fois que possible (« plier »), en gardant la valeur sous n. La vue naïve exige e−1 plis ; l'échelle élever-au-carré-et-multiplier n'exige qu'environ log₂ e élévations au carré plus une multiplication par bit à 1 — 17 étapes pour e = 65537 au lieu de 65536. C'est exactement cette échelle logarithmique que les vraies implémentations exécutent.

1977 : Rivest, Shamir, Adleman — Turing 2002

RSA a été publié par Ron Rivest, Adi Shamir et Leonard Adleman en 1977 (une version secrète du GCHQ par Clifford Cocks est apparue en 1997). Ce fut le premier système à clé publique pratique : deux clés, une publique pour verrouiller, une privée pour ouvrir, sans partager de secrets à l'avance. RSA a rendu possibles le commerce électronique, HTTPS et les signatures numériques, et a valu à ses auteurs le prix Turing de l'ACM 2002. Sa sécurité repose toujours sur un fait : factoriser un semi-premier de 2048 bits avec le meilleur algorithme (le crible algébrique) coûte encore astronomiquement plus que les microsecondes du chiffrement.

Mode d'emploi

Commencez avec p=61, q=53 (la clé classique des manuels) : tapez un message, cliquez sur une ligne et lancez l'animation pliée — observez chaque produit revenir sous n. Appuyez sur Lancer l'attaque ρ : 3233 se scinde presque instantanément. Montez le curseur de chiffres et régénérez : les premiers de 8 chiffres tombent en un clin d'œil, ceux de 12 chiffres exigent une exécution visible, et à 16 chiffres le compteur dépasse visiblement votre patience — c'est tout l'objet de la visualisation. Comparez le panneau de coût quand n grandit : 2 chiffres de plus dans p multiplient le travail par ~10 en division d'essai mais seulement ~3,2 pour ρ — et les vraies clés utilisent 617 chiffres.