🎛️ RSA jouet (petits nombres)
Choisis deux petits premiers p, q. La machine génère la paire de clés (publique e, privée d), chiffre puis déchiffre un message numérique. En vrai, p et q font 1024 bits chacun.
Module n = p×q
323
φ(n) = (p-1)(q-1)
288
Clé publique e
5
🔒 Clé privée d (telle que e·d ≡ 1 mod φ(n)) — À NE JAMAIS PARTAGER
173
🔐 Chiffré c = mᵉ mod n
211
🔓 Déchiffré cᵈ mod n
42
Voilà la magie : n = 323 est public, mais factoriser 323 = 17×19 à la main reste rapide. Pour n de 2048 bits, c'est impossible avant l'an 10⁵⁰.
🚀 Le problème pré-1976 : partager une clé sans canal sûr
Toute la cryptographie classique (César, Vigenère, Enigma) repose sur une clé secrète partagée par l'expéditeur et le destinataire. Mais comment partager cette clé sans qu'un espion l'intercepte ? Pendant des siècles, on utilise :
- Des messagers de confiance (vulnérables à la corruption).
- Des rencontres physiques (impraticable à l'ère du télégraphe et de la radio).
- Des livres de codes pré-distribués (capturables par l'ennemi).
En 1976, deux Américains révolutionnent tout : Whitfield Diffie et Martin Hellman publient « New Directions in Cryptography ». Ils proposent l'idée folle : une clé pour chiffrer, une autre pour déchiffrer. Tu peux publier la première au monde entier sans compromettre la seconde.
🎯 1977 : Rivest, Shamir, Adleman
À Pâques 1977, trois chercheurs du MIT — Ronald Rivest, Adi Shamir et Leonard Adleman — se penchent sur le défi de Diffie-Hellman. Rivest propose 42 candidats. Adleman les réfute tous, sauf le 43ᵉ. C'est RSA.
Publié en 1978 (« A Method for Obtaining Digital Signatures and Public-Key Cryptosystems »), RSA devient le premier système à clé publique pratique. Brevet déposé en 1983, expiré en 2000 (dans le domaine public depuis).
🧮 Le mécanisme de RSA en 5 étapes
- Choisir deux grands nombres premiers p et q (1024 bits chacun en pratique).
- Calculer n = p × q et l'indicatrice d'Euler φ(n) = (p−1)(q−1).
- Choisir e premier avec φ(n), souvent e = 65 537 = 2¹⁶+1 (puissance de 2 rapide).
- Calculer d, l'inverse modulaire de e modulo φ(n) (algorithme d'Euclide étendu).
- Publier la clé publique (n, e). Garder secret la clé privée d. Détruire p et q.
Chiffrement / déchiffrement RSA
Chiffrer : c = me mod n
Déchiffrer : m = cd mod n
🛡️ Pourquoi c'est sûr : la difficulté de factoriser
Pour casser RSA, un attaquant connaît (n, e) publiquement et veut retrouver d. Pour cela, il lui faut φ(n) = (p−1)(q−1), donc il doit factoriser n pour récupérer p et q.
Or, factoriser un nombre de 2 048 bits est computationnellement impossible. Le meilleur algorithme classique connu, le crible algébrique général (GNFS, General Number Field Sieve), a une complexité sous-exponentielle, mais reste hors d'atteinte pour n ≥ 1024 bits avec tous les ordinateurs de la planète réunis.
- RSA-768 (232 chiffres décimaux, 768 bits) : factorisé en 2009 après 2 ans de calcul distribué (4×10²⁰ opérations).
- RSA-829 (250 chiffres, 829 bits) : factorisé en 2020. Coût ≈ 2 700 années CPU.
- RSA-1024 : pas encore factorisé. Considéré peu sûr depuis 2010.
- RSA-2048 (standard actuel) : sûr pour ~50 ans selon les estimations classiques. Hors d'atteinte de tout ordinateur classique.
- RSA-4096 : ultra-paranoïaque, utilisé pour les communications classifiées critiques.
⚛️ La menace quantique : Shor 1994
En 1994, le mathématicien Peter Shor publie un algorithme quantique qui factorise un entier en temps polynomial. Sur un ordinateur quantique suffisamment grand, RSA s'effondre instantanément.
En 2024-2026 :
- Le plus grand entier factorisé par un vrai ordinateur quantique est ~21 (essais Google, IBM). Pour RSA-2048 il faudrait environ 20 millions de qubits stables et corrigés.
- État de l'art en 2026 : ~1 000-5 000 qubits physiques bruités. Il faut encore probablement 15-30 ans avant la menace devienne réelle.
- Mais la NSA, le NIST et toutes les grandes institutions ont déjà initié la transition vers la cryptographie post-quantique (PQC). NIST a finalisé en 2024 trois algorithmes standards (CRYSTALS-Kyber, CRYSTALS-Dilithium, SPHINCS+).
🌐 Où RSA est-il utilisé ?
- HTTPS / TLS : chaque connexion sécurisée (le cadenas dans ton navigateur) commence par un échange RSA ou ECC pour échanger une clé de session AES. Sans RSA, ni e-commerce Amazon, ni paiement bancaire en ligne, ni banque mobile.
- Signatures électroniques : eIDAS européen, signature des PDF, des documents officiels. La signature électronique a la même valeur légale qu'une signature manuscrite depuis 1999.
- Certificats SSL/TLS : autorités de certification (Let's Encrypt, DigiCert, Sectigo) signent ton certificat avec RSA-2048 ou ECC.
- SSH : connexion sécurisée à un serveur distant. Les clés SSH sont RSA ou Ed25519.
- PGP / GPG : chiffrement et signature d'emails (PGP date de 1991, créé par Phil Zimmermann ; toujours utilisé par les journalistes, militants, défense).
- Cryptomonnaies : Bitcoin et Ethereum utilisent ECC (variante elliptique de RSA) pour les signatures de transactions.
- Cartes à puce : cartes bancaires EMV, passeports biométriques, cartes d'identité électronique.
- Wi-Fi WPA2/WPA3 : RSA pour l'authentification des Access Points en mode entreprise.
📐 Le lien direct avec ton programme BAC SM
RSA est l'application phare du programme d'arithmétique 2BAC SM au Maroc. Tous les concepts mobilisés sont au programme :
- Nombres premiers : choix de p et q. Test de primalité.
- PGCD et algorithme d'Euclide : pgcd(e, φ(n)) = 1 pour que e soit inversible.
- Algorithme d'Euclide étendu : calcul de d (inverse modulaire de e).
- Congruences modulo n : tout RSA tourne dans ℤ/nℤ.
- Petit théorème de Fermat : a^(p−1) ≡ 1 mod p, généralisé par Euler-Fermat : a^φ(n) ≡ 1 mod n. C'est l'identité clé qui prouve que (m^e)^d ≡ m mod n.
- Exponentiation rapide : calcul de m^e mod n en O(log e). Vu en algorithmique 2BAC.
En clair : si tu maîtrises l'arithmétique 2BAC SM, tu peux comprendre et coder RSA. C'est l'un des plus beaux ponts entre les maths du lycée et la technologie qui fait tourner Internet.
🎓 Bonus : la preuve de correction
On veut prouver que (m^e)^d ≡ m mod n. Par construction, e·d ≡ 1 mod φ(n), donc e·d = 1 + k·φ(n).
Par Euler-Fermat (si pgcd(m, n) = 1) : m^φ(n) ≡ 1 mod n. Donc :
m^(ed) = m^(1 + k·φ(n)) = m · (m^φ(n))^k ≡ m · 1^k ≡ m mod n. ✓
Le cas pgcd(m, n) ≠ 1 (m multiple de p ou q, événement très rare) se traite séparément avec le théorème des restes chinois.