Post-quantique et sujets avancés

Tout le bloc asymétrique de ce cours — RSA, Diffie-Hellman, ElGamal, les courbes elliptiques, la PKI qui les atteste — repose sur deux problèmes : la factorisation et le logarithme discret. En 1994, Peter Shor a montré qu'un ordinateur quantique les résout tous les deux en temps polynomial. Le jour où une telle machine existera à l'échelle, ce bloc entier tombera d'un coup. Ce dernier chapitre pose la menace, présente les familles qui y résistent, et fait de la migration une compétence — non une note de bas de page.

C'est un chapitre d'ouverture : chacune de ses sections est un cours en soi, et un module entier peut être consacré à la seule cryptographie post-quantique. On installe ici les idées maîtresses et le vocabulaire.

Shor et Grover : deux menaces de nature différente

Il faut distinguer nettement deux algorithmes quantiques, car ils ne font pas le même dégât.

Shor est catastrophique et ciblé. Il factorise et calcule les logarithmes discrets — y compris sur courbes elliptiques — en temps polynomial. Ce n'est pas une accélération : c'est un changement de classe de complexité. RSA-2048, ECDSA sur P-256, ECDH sur Curve25519 passent de « infaisable » à « facile ». Aucune augmentation de taille de clé n'y résiste, puisque le coût de Shor est polynomial en la taille. Toute la cryptographie asymétrique classique est concernée.

Grover est modéré et général. Il accélère quadratiquement toute recherche exhaustive, ramenant $2^n$ à $2^{n/2}$. Contre le symétrique, l'effet est gérable : AES-128 tomberait à 64 bits de sécurité quantique, mais AES-256 conserve 128 bits — d'où la recommandation d'AES-256 en perspective post-quantique. Le symétrique et les fonctions de hachage sont affaiblis, pas effondrés ; doubler les tailles suffit.

Le résumé tient en une ligne : Grover fait mal au symétrique mais on compense en doublant, Shor tue l'asymétrique et rien ne compense — il faut en changer.

« Récolter maintenant, déchiffrer plus tard »

La menace n'est pas seulement future, et c'est le point que les étudiants sous-estiment. Un adversaire peut enregistrer aujourd'hui du trafic chiffré et le déchiffrer dans dix ou vingt ans, quand la machine existera. Tout secret qui doit rester confidentiel au-delà de cet horizon est déjà exposé — dossiers médicaux, secrets d'État, données biométriques.

La confidentialité persistante du chapitre 13 n'y change rien : elle protège contre la compromission d'une clé de long terme, pas contre un adversaire qui casse le Diffie-Hellman éphémère lui-même une fois la machine disponible. C'est pourquoi la migration a commencé avant que l'ordinateur quantique n'existe, ce qui déconcerte, mais se justifie entièrement par cet horizon de rétro-déchiffrement.

Les familles qui résistent

La cryptographie post-quantique cherche des problèmes difficiles même pour un ordinateur quantique. Aucun ne bénéficie de la structure périodique qu'exploite Shor. Cinq familles émergent.

Les réseaux euclidiens dominent. Les problèmes SVP et CVP (trouver le vecteur le plus court, le point le plus proche) résistent au quantique, et surtout offrent de bonnes performances. Le NIST a normalisé en 2024 ML-KEM (issu de Kyber) pour l'encapsulation de clé et ML-DSA (issu de Dilithium) pour la signature, tous deux fondés sur les réseaux. Ils sont, à ce jour, le socle de la transition.

Les codes correcteurs. Décoder un code linéaire général est difficile ; McEliece l'exploite depuis 1978 et n'a jamais été cassé — au prix de clés publiques énormes, ce qui le réserve à des usages spécifiques.

Les fonctions de hachage. C'est le socle le plus sûr, car il ne suppose rien de plus que ce que ce cours a déjà utilisé : une fonction à sens unique résistante aux collisions. SPHINCS+, normalisé lui aussi, en fait des signatures. Vous allez en construire la brique de base.

Les isogénies (chemins entre courbes elliptiques) offraient les clés les plus courtes — mais le candidat vedette, SIKE, a été cassé classiquement en 2022, quelques semaines avant sa normalisation probable. Rappel salutaire : « post-quantique » ne veut pas dire « sûr », seulement « pas cassé par Shor ». Ces schémas sont jeunes, et leur cryptanalyse classique est encore en cours.

Le multivarié, enfin, fondé sur la difficulté de résoudre des systèmes polynomiaux, a connu des ruptures répétées et reste marginal.

// Signature à usage unique de Lamport (1979). Sa sécurité ne dépend d'AUCUN
// problème algébrique — ni factorisation, ni logarithme discret. Elle repose
// uniquement sur l'irréversibilité d'une fonction de hachage. Donc : rien que
// Shor puisse abattre. C'est le principe des signatures post-quantiques à base
// de hachage (SPHINCS+, normalisé par le NIST).

// Fonction de hachage jouet, à sens unique (chapitre 7).
function H(x) {
  let v = (x >>> 0) * 2654435761 >>> 0;
  v ^= v >>> 15; v = (v * 0x85ebca6b) >>> 0; v ^= v >>> 13;
  return v >>> 0;
}

const N = 8; // on signe des messages de 8 bits (jouet ; en vrai, 256)

// ── Génération des clés ───────────────────────────────────────────────────
// Clé privée : pour chaque bit, une PAIRE de secrets aléatoires (un pour 0,
// un pour 1). Clé publique : leurs empreintes.
function genererCle() {
  const priv = [], pub = [];
  for (let i = 0; i < N; i++) {
    const s0 = (Math.random() * 1e9) >>> 0;
    const s1 = (Math.random() * 1e9) >>> 0;
    priv.push([s0, s1]);
    pub.push([H(s0), H(s1)]);
  }
  return { priv, pub };
}

// ── À COMPLÉTER : signer ──────────────────────────────────────────────────
// Pour chaque bit du message, RÉVÉLER le secret correspondant à sa valeur :
// le secret « 0 » si le bit est 0, le secret « 1 » s'il est 1.
function signer(message, priv) {
  const signature = [];
  for (let i = 0; i < N; i++) {
    const bit = (message >> i) & 1;
    // à compléter : ajouter le bon secret à la signature
  }
  return signature;
}

// ── À COMPLÉTER : vérifier ────────────────────────────────────────────────
// Pour chaque bit, hacher le secret révélé et le comparer à l'empreinte
// publique du bon côté.
function verifier(message, signature, pub) {
  for (let i = 0; i < N; i++) {
    const bit = (message >> i) & 1;
    // à compléter : rejeter si H(signature[i]) ne correspond pas à pub[i][bit]
  }
  return true;
}

// ── Tests ─────────────────────────────────────────────────────────────────
const { priv, pub } = genererCle();
const message = 0b10110101;
const signature = signer(message, priv);

console.log("signature valide ?", verifier(message, signature, pub));
console.log("même signature sur un AUTRE message ?", verifier(0b10110100, signature, pub));

Migrer : l'agilité comme compétence

La leçon finale du cours n'est pas un algorithme, c'est une posture. On a longtemps câblé une primitive au cœur d'un système, pour découvrir ensuite qu'on ne pouvait plus l'en déloger — MD5 et SHA-1 ont survécu des années à leur condamnation, faute de pouvoir migrer.

L'agilité cryptographique est la capacité à changer de primitive sans refondre le système : négocier l'algorithme, le versionner, prévoir sa succession dès la conception. TLS 1.3 (chapitre 13) en posait déjà les bases en imposant des choix par défaut sûrs tout en gardant la négociation propre.

La transition post-quantique se fait aujourd'hui en hybride : on combine un schéma classique éprouvé (X25519) et un schéma post-quantique récent (ML-KEM) dans le même échange, et le secret n'est sûr que si les deux tiennent. On se protège ainsi à la fois de l'ordinateur quantique et d'une cryptanalyse classique surprise du nouveau venu — le sort de SIKE rappelle que ce risque est réel. C'est de l'ingénierie prudente : ne pas remplacer une certitude par un pari.

Aperçu : au-delà du chiffrer-et-signer

Le cours s'est concentré sur la confidentialité, l'intégrité et l'authenticité. La cryptographie moderne va bien plus loin, et trois idées méritent d'être nommées en clôture.

Le partage de secret (Shamir) découpe un secret en $n$ parts telles que $t$ d'entre elles le reconstituent, mais $t-1$ n'en révèlent rien — la sécurité inconditionnelle du chapitre 3, appliquée au contrôle d'accès. Le calcul multipartite permet à plusieurs acteurs de calculer une fonction de leurs données sans jamais se les dévoiler — voter, enchérir, comparer sans rien révéler d'autre que le résultat. Les preuves à divulgation nulle permettent de prouver qu'on connaît un secret sans le montrer — fondement des systèmes d'identité et des blockchains de confidentialité.

Ces sujets prolongent naturellement ce cours ; ils en sont l'horizon.

Le mot de la fin

Ce cours a suivi un fil constant : construire une garantie, puis la mettre à l'épreuve. Chaque primitive est venue avec son attaque — le masque rejoué, l'oracle de padding, la rencontre au milieu, l'exposant faible, le nonce de DSA, le pgcd des clés. Ce n'est pas du pessimisme : c'est la méthode. On ne fait confiance qu'à ce qui a résisté à une attaque sérieuse, et la seule façon de comprendre une défense est d'avoir tenu, un moment, le rôle de l'attaquant. Vous l'avez tenu quatorze fois. C'est le meilleur bagage pour la suite — y compris pour un monde où les règles du jeu, avec le quantique, sont en train de changer.

À retenir

QCM de synthèse — Bloc V — Ouvertures

Le QCM ci-dessous porte sur l'ensemble du bloc : plusieurs questions relient les leçons entre elles. En cas d'erreur, le bilan indique le chapitre à revoir.