Les problèmes difficiles qui rendent la clé publique possible
Les problèmes difficiles qui rendent la clé publique possible
Section intitulée « Les problèmes difficiles qui rendent la clé publique possible »La cryptographie à clé publique repose sur un pari : certains calculs sont faciles dans un sens et, en l’état des connaissances, infaisables dans l’autre. Ce pari n’est pas démontré, il est seulement très bien documenté par des décennies d’échecs à le gagner. Ce chapitre présente les objets mathématiques nécessaires pour comprendre ces hypothèses, sans transformer la page en manuel d’algèbre, et relie chaque difficulté à la famille d’algorithmes qui l’exploite.
→ Lire l’explication complète de la marmotte
Facile dans un sens
Section intitulée « Facile dans un sens »Une fonction à sens unique se calcule efficacement mais s’inverse difficilement pour une entrée tirée au hasard. Une fonction de hachage en donne l’intuition, mais une telle fonction ne suffit pas à chiffrer : si personne ne peut l’inverser, le destinataire non plus. Il faut une trappe, une information secrète qui rend l’inversion facile pour son seul détenteur. Une fonction à sens unique à trappe qui est en plus une bijection d’un ensemble sur lui-même s’appelle une permutation à trappe ; RSA en est l’exemple canonique : tout le monde calcule x^e mod n, seul le détenteur de la factorisation de n sait extraire la racine e-ième.
Ces objets servent à construire deux grandes primitives. L’encapsulation de clé (KEM, Key Encapsulation Mechanism) permet à n’importe qui de produire, avec la clé publique, un secret aléatoire et son « emballage » que seul le détenteur de la clé privée sait ouvrir. La signature inverse les rôles : seul le détenteur de la trappe produit une valeur que tout le monde peut vérifier avec la clé publique. Signer n’est pas « chiffrer avec la clé privée », formule commode et fausse qui a fait plus de dégâts que bien des attaques.
Arithmétique utile
Section intitulée « Arithmétique utile »Le calcul modulo n consiste à ne garder que le reste de la division par n : 17 mod 5 = 2. On travaille ainsi dans un ensemble fini où l’addition et la multiplication restent bien définies. Muni d’une opération, un tel ensemble forme un groupe : les entiers non nuls modulo un nombre premier p, avec la multiplication, en sont un, et les points d’une courbe elliptique, avec une addition géométrique, en sont un autre. Un élément g est un générateur si ses puissances successives parcourent tout le groupe.
L’exponentiation rapide (square-and-multiply) rend les grands exposants abordables. Pour calculer 5^13 mod 23, on écrit 13 en binaire, 1101, puis on élève au carré de proche en proche : 5^1 = 5, 5^2 = 25 ≡ 2, 5^4 ≡ 4, 5^8 ≡ 16 (mod 23). On multiplie les puissances correspondant aux bits à 1 : 5^13 = 5^8 × 5^4 × 5^1 ≡ 16 × 4 × 5 = 320 ≡ 21 (mod 23). Pour un exposant de 2048 bits, cela représente environ 2048 carrés et autant de multiplications au plus, une broutille. En Python, pow(5, 13, 23) renvoie 21 et applique la même méthode.
Le chemin inverse, retrouver x tel que 5^x ≡ 21 (mod 23), est le logarithme discret. Avec 23 éléments, on essaie toutes les valeurs ; avec un nombre premier de 2048 bits, les meilleurs algorithmes connus restent hors de portée. 5 est ici un générateur, car son ordre vaut 22, soit p − 1.
Les nombres premiers sont nombreux : près d’un entier sur 710 autour de 2^1024 l’est (le logarithme népérien de 2^1024 vaut environ 710), et vérifier qu’un nombre est premier est rapide grâce à des tests probabilistes comme Miller-Rabin. Le théorème des restes chinois permet de reconstituer un nombre à partir de ses restes modulo des facteurs premiers entre eux : si x ≡ 2 (mod 3) et x ≡ 3 (mod 5), alors x ≡ 8 (mod 15). RSA l’exploite pour accélérer le déchiffrement d’un facteur proche de 4, en calculant séparément modulo p et modulo q.
Dureté et classes
Section intitulée « Dureté et classes »La théorie de la complexité classe les problèmes selon la croissance du temps de calcul avec la taille de l’entrée. Un algorithme en temps polynomial (n², n³) est considéré comme efficace. Un temps superpolynomial, exponentiel comme 2^n ou sous-exponentiel comme le crible algébrique, devient rapidement prohibitif. La classe P rassemble les problèmes résolubles en temps polynomial ; la classe NP ceux dont une solution, une fois fournie, se vérifie en temps polynomial. Les problèmes NP-complets sont les plus durs de NP : un algorithme polynomial pour l’un d’eux en donnerait un pour tous. Savoir si P = NP reste ouvert, et une preuve que P ≠ NP ne suffirait même pas à garantir la cryptographie.
Car la cryptographie ne se contente pas de la difficulté dans le pire des cas, que mesure la NP-complétude : elle a besoin que presque toutes les instances tirées au hasard soient difficiles. Un problème NP-complet peut être facile pour l’immense majorité des instances, et ce sont celles-là qu’un générateur de clés produit.
La factorisation illustre la nuance inverse. Elle appartient à NP, mais aussi à co-NP, et elle n’est probablement pas NP-complète, car sinon NP serait égal à co-NP, ce que presque personne ne croit. Elle n’est pas pour autant facile : le meilleur algorithme classique connu, le crible algébrique (GNFS, General Number Field Sieve), est sous-exponentiel, et le record public de factorisation d’un module RSA tourne autour de 829 bits (RSA-250, en 2020). La sécurité de RSA repose donc sur une hypothèse empirique, pas sur un théorème.
Panorama des familles
Section intitulée « Panorama des familles »La factorisation porte RSA et le cryptosystème de Rabin (1979), qui chiffre par élévation au carré modulo n et dont la sécurité est prouvée équivalente à la factorisation, au prix d’un déchiffrement qui produit quatre racines candidates. Le logarithme discret dans un corps fini porte Diffie-Hellman et ElGamal (1985), chiffrement probabiliste et signature. L’algorithme de Pohlig-Hellman rappelle la condition indispensable : si l’ordre du groupe n’a que de petits facteurs premiers, le logarithme discret se découpe en petits problèmes faciles. On choisit donc des groupes d’ordre premier ou comportant un grand facteur premier. Sur les courbes elliptiques, aucun algorithme sous-exponentiel n’est connu pour les courbes bien choisies, et les meilleures attaques génériques, comme rho de Pollard, demandent environ la racine carrée de l’ordre du groupe : une courbe de 256 bits offre environ 128 bits de sécurité.
Les codes correcteurs portent McEliece (1978) : la clé publique est un code déguisé, la trappe est la structure cachée qui permet de décoder efficacement. Les treillis portent les standards post-quantiques ML-KEM et ML-DSA. Leur cas est remarquable : depuis les travaux d’Ajtai (1996), certains problèmes de treillis bénéficient d’une réduction du pire cas vers le cas moyen, exactement la garantie qui manque ailleurs.
Le knapsack, ou problème du sac à dos, est l’exemple historique de l’échec : le schéma de Merkle-Hellman (1978) reposait sur un problème NP-complet, et Shamir l’a cassé au début des années 1980, car les instances à trappe avaient une structure exploitable. Des propositions fondées sur des automates finis ou des automates cellulaires ont connu un sort comparable : intéressantes, restées marginales ou cassées, elles n’ont jamais porté de standard.
Deux familles conceptuelles complètent le tableau. Le chiffrement probabiliste, formalisé par Goldwasser et Micali en 1982, exige que chiffrer deux fois le même message donne deux chiffrés différents ; c’est aujourd’hui une exigence de base, que RSA brut ne remplit pas, d’où les rembourrages aléatoires. La cryptographie fondée sur l’identité (IBE, Identity-Based Encryption), proposée par Shamir en 1984 et réalisée en 2001 par Boneh et Franklin à l’aide de couplages sur courbes elliptiques, utilise une adresse électronique comme clé publique. Elle impose une autorité qui calcule toutes les clés privées, donc qui peut tout déchiffrer, ce qui en restreint fortement les usages.
Exemples et ateliers
Section intitulée « Exemples et ateliers »Exponentiation modulaire jouet. Le calcul de 5^13 mod 23 ci-dessus se reproduit à la main en trois carrés et deux multiplications. L’exercice inverse, chercher l’exposant donnant 21, oblige à énumérer les puissances une à une : avec 22 valeurs, c’est rapide ; avec 2^2048, il faudrait plus de temps que n’en a l’univers, et nettement plus de patience que n’en a un auditeur.
Taille des clés selon les familles. Pour un niveau d’environ 128 bits de sécurité :
| Famille | Exemple | Clé publique |
|---|---|---|
| Symétrique | AES-128 | 16 octets (clé secrète) |
| Factorisation | RSA-3072 | 384 octets |
| Logarithme discret, corps fini | DH 3072 bits | 384 octets |
| Courbe elliptique | X25519 | 32 octets |
| Treillis | ML-KEM-512 | 800 octets |
| Codes | Classic McEliece 348864 | environ 255 Kio |
L’écart entre courbe elliptique et corps fini vient de l’absence d’attaque sous-exponentielle sur les courbes.
Classer un schéma selon son hypothèse. Pour chaque algorithme rencontré, on note le problème sur lequel il repose, l’existence d’une réduction de sécurité, l’âge de la cryptanalyse et la résistance à un attaquant quantique. RSA-OAEP : factorisation (plus précisément le problème RSA), plus de 45 ans d’analyse, cassé par Shor. ECDH sur X25519 : logarithme discret sur courbe, cassé par Shor. ML-KEM : treillis modulaires, réduction partielle, analyse plus récente, résistant aux attaques quantiques connues.
Pièges classiques
Section intitulée « Pièges classiques »Croire que tout problème difficile convient à la cryptographie oublie qu’il faut aussi une trappe, des instances aléatoires difficiles et des paramètres raisonnables. Confondre NP-complet et sûr reproduit l’erreur du sac à dos. Choisir un groupe exotique, une courbe maison ou un corps « optimisé » expose à des attaques spécialisées que personne n’a encore cherchées pour le compte du concepteur ; d’autres finiront par les chercher pour le leur. Ignorer la génération des paramètres a fait de vraies victimes : l’attaque Logjam (2015) a exploité des groupes Diffie-Hellman de 512 bits partagés par de nombreux serveurs, ce qui rendait rentable un précalcul unique, et la vulnérabilité ROCA (2017) a touché des millions de clés RSA générées par une bibliothèque Infineon dont la structure des nombres premiers rendait la factorisation praticable.
À ne pas confondre
Section intitulée « À ne pas confondre »Factorisation et primalité : savoir qu’un nombre est composé est facile, trouver ses facteurs ne l’est pas ; un test de primalité ne livre aucun facteur. Dureté asymptotique et sécurité concrète : un problème difficile « quand n tend vers l’infini » peut être facile pour la taille réellement utilisée ; seule l’estimation du coût des meilleures attaques connues fixe les tailles de clés, comme le détaille la page sur l’évaluation de la force d’une protection. Fonction à sens unique et chiffrement : sans trappe, personne ne déchiffre. Cryptographie quantique et post-quantique : la première utilise la physique, la seconde des problèmes mathématiques présumés résistants aux ordinateurs quantiques, présentés dans la page sur la migration post-quantique. RSA est détaillé dans la page sur la trappe RSA et le rembourrage et les courbes dans la page sur les courbes elliptiques.
🐝 Ce qui arrive si on s’en passe
Section intitulée « 🐝 Ce qui arrive si on s’en passe »Adopter un schéma sans examiner l’hypothèse de dureté qui le porte revient à signer un chèque sur un compte qu’on n’a jamais consulté. Un groupe exotique, ou des paramètres générés sans les contrôles attendus, peuvent transformer un problème réputé difficile en calcul abordable, et toutes les clés produites avec ces paramètres tombent alors ensemble. Confondre dureté asymptotique et sécurité concrète conduit à des tailles de clés qui résistent sur le papier et cèdent sur du matériel réel. Et l’erreur ne se voit jamais à l’usage : un système cassé chiffre et signe exactement aussi bien qu’un système sûr, jusqu’au jour où quelqu’un d’autre le fait à sa place.
🦫 Explication de la marmotte 🍫
Section intitulée « 🦫 Explication de la marmotte 🍫 »La cryptographie à clé publique utilise deux clés : une clé publique, que tout le monde peut connaître, et une clé privée, gardée secrète. Pour que ce soit sûr, il faut un calcul facile dans un sens et très difficile dans l’autre, sauf pour qui possède une information cachée, appelée trappe. Premier exemple : multiplier deux grands nombres premiers est rapide, mais retrouver ces deux nombres à partir de leur produit, la factorisation, prend un temps énorme avec les méthodes connues. Deuxième exemple : élever un nombre à une puissance en ne gardant que le reste d’une division, ce qu’on appelle calculer modulo, est rapide ; retrouver l’exposant à partir du résultat, le logarithme discret, est très difficile, y compris sur des courbes particulières appelées courbes elliptiques. D’autres familles reposent sur les codes correcteurs d’erreurs ou sur des réseaux de points réguliers appelés treillis. Les informaticiens classent les problèmes selon le temps nécessaire pour les résoudre. Un problème classé parmi les plus durs en théorie n’est pas forcément utilisable : il peut être difficile dans le pire des cas mais facile dans les cas réellement rencontrés. C’est pourquoi certaines familles historiques, comme celles fondées sur le problème du sac à dos, ne sont plus employées. La sécurité réelle dépend aussi de la taille des clés et d’une fabrication correcte des paramètres : un groupe mal choisi ou mal généré peut rendre le problème facile.
À lire aussi
- Établir une clé : Diffie-Hellman, KEM et HPKEÉtablir une clé sans canal sécurisé : Diffie-Hellman pour fabriquer le secret commun, KEM pour l'interface encapsuler/décapsuler, HPKE (RFC 9180) pour assembler KEM, KDF et AEAD.
- Lire une garantie sans la surinterpréterDonner les outils pour comprendre une preuve de sécurité, une hypothèse de dureté et un modèle d’attaque, tout en rappelant leurs limites pratiques.
- Le post-quantique hybrideLes déploiements post-quantiques combinent ML-KEM et X25519 au lieu de choisir entre les deux. Ce n'est pas une hésitation d'ingénieur mais une défiance assumée envers des primitives jeunes, et elle se paie surtout en complexité et en code, beaucoup moins en octets.
- Dimensionner un HSM pour la migration post-quantiqueImpact des algorithmes post-quantiques sur la capacité, les performances et l'exploitation des modules cryptographiques matériels existants.
Pages voisines
La citent
- Lire une garantie sans la surinterpréter
- Prouver sans révéler : ZK et identification
- Le post-quantique hybride
Les problèmes difficiles qui rendent la clé publique possible
Elle cite