Codes correcteurs

Nous quittons les réseaux. La famille des codes correcteurs offre la plus vieille hypothèse post-quantique en service : McEliece date de 1978, la même année que RSA, et il n'a jamais été cassé. Ce chapitre explique pourquoi, et pourquoi cette solidité n'a pas suffi à en faire le standard.

Codes linéaires : le strict nécessaire

Un code linéaire $[n, k, d]$ sur $\mathbb{F}_2$ est un sous-espace vectoriel de dimension $k$ dans $\mathbb{F}_2^n$. On y encode $k$ bits d'information en $n$ bits transmis, les $n - k$ bits supplémentaires servant à détecter et corriger les erreurs. La distance minimale $d$ est le plus petit poids d'un mot de code non nul ; un code corrige jusqu'à $t = \lfloor (d-1)/2 \rfloor$ erreurs.

Deux matrices décrivent le code. La génératrice $G$, de taille $k \times n$, encode : $c = mG$. La matrice de contrôle $H$, de taille $(n-k) \times n$, vérifie : $Hc^{T} = 0$ pour tout mot de code.

Le syndrome est la quantité centrale. Si l'on reçoit $y = c + e$ où $e$ est le vecteur d'erreur, alors

Le syndrome ne dépend que de l'erreur, jamais du message. Décoder, c'est retrouver $e$ à partir de $He^{T}$ — et c'est exactement le problème sur lequel toute la famille repose.

Le décodage générique est difficile

Voici la dissymétrie qui fonde la cryptographie à base de codes.

Si l'on connaît la structure du code — qu'il est un code de Hamming, de Reed-Solomon, de Goppa — le décodage est un algorithme polynomial, souvent très rapide. C'est même la raison d'être de ces codes en télécommunications.

Si l'on ne dispose que d'une matrice quelconque, sans structure apparente, le problème du décodage par syndrome est NP-difficile, résultat établi par Berlekamp, McEliece et van Tilborg dès 1978. Le meilleur algorithme connu reste le décodage par ensembles d'information (ISD), dont l'idée remonte à Prange en 1962 : deviner un ensemble de positions sans erreur et résoudre linéairement. Soixante ans de raffinements — Stern, MMT, BJMM — n'ont amélioré que la constante dans l'exposant. Le coût reste exponentiel, et sa variante quantique n'apporte qu'un gain modeste.

C'est cette stabilité qui fait la réputation de la famille : la courbe de progression des attaques est remarquablement plate depuis quatre décennies. Pour comparer, l'estimation de sécurité des réseaux, elle, a bougé plusieurs fois depuis 2016.

McEliece : brouiller la structure

La construction de McEliece tient en une phrase. On choisit un code structuré, dont on sait décoder efficacement — historiquement un code de Goppa binaire — et on publie une matrice génératrice brouillée qui décrit le même code sans en laisser voir la structure.

où $S$ est inversible et $P$ une permutation. Chiffrer, c'est encoder le message avec $G_{\text{pub}}$ puis ajouter volontairement $t$ erreurs. Déchiffrer, c'est retirer la permutation, décoder avec l'algorithme de Goppa, et défaire $S$.

C'est la trappe du chapitre 4 transposée : même objet, deux descriptions, une seule exploitable. Ici, la « bonne base » est la structure de Goppa.

La variante de Niederreiter utilise la matrice de contrôle plutôt que la génératrice : le message est encodé dans le vecteur d'erreur lui-même, et le chiffré est un simple syndrome. Elle est équivalente en sécurité et produit des chiffrés bien plus courts — c'est la forme employée par Classic McEliece.

HQC : le retour de la structure

Classic McEliece a un défaut, un seul, et il est massif : sa clé publique est une matrice dense. Elle pèse 261 kilooctets au niveau de sécurité le plus bas et plus d'un mégaoctet au plus haut.

HQC — Hamming Quasi-Cyclic — répond à cela comme Ring-LWE a répondu à LWE plein : en introduisant de la structure. Les codes employés sont quasi-cycliques, donc décrits par un petit nombre de coefficients au lieu d'une matrice complète. Le gain est du même ordre : la clé publique tombe à quelques kilooctets.

HQC diffère de McEliece sur un point conceptuel important. Sa sécurité ne repose pas sur la dissimulation d'un code structuré, mais sur le décodage de codes aléatoires quasi-cycliques — le code servant à corriger est public, et le secret est ailleurs. Cela supprime une classe entière d'attaques, celles qui cherchent à distinguer un code masqué d'un code aléatoire.

Le prix, comme pour ML-KEM, est un taux d'échec de déchiffrement non nul qu'il faut dimensionner soigneusement.

Le NIST a retenu HQC en mars 2025 comme second mécanisme d'encapsulation, en secours de ML-KEM. La logique de ce choix mérite d'être explicitée en cours : il ne s'agit pas d'avoir deux schémas équivalents, mais deux schémas reposant sur des hypothèses de difficulté différentes. Si les réseaux tombaient, HQC resterait.

Le compromis, en chiffres

Regardez la ligne « chiffré » : McEliece produit les chiffrés les plus courts de tout le paysage post-quantique — 96 octets. Sa clé publique est énorme, mais elle peut être transmise une fois et réutilisée. Pour un tunnel VPN à long terme entre deux sites, où la clé s'échange à l'installation et les chiffrés circulent en permanence, McEliece est un excellent choix, et plusieurs agences européennes le recommandent explicitement pour les usages à long terme. Pour un handshake TLS où chaque connexion transporte la clé, il est inutilisable.

La bonne taille dépend de ce qui circule souvent. C'est la leçon d'ingénierie du chapitre, et elle revaudra au chapitre 13.

À vous

// Décodage par syndrome sur le code de Hamming [7, 4, 3].
// Il corrige une erreur. Le point de l'exercice n'est pas de le décoder —
// c'est de mesurer ce que coûte le décodage quand on ne connaît PAS la
// structure du code.

// Matrice de contrôle : les colonnes sont 1..7 écrits en binaire.
const H = [
  [0, 0, 0, 1, 1, 1, 1],
  [0, 1, 1, 0, 0, 1, 1],
  [1, 0, 1, 0, 1, 0, 1],
];

const syndrome = (mot) =>
  H.map((ligne) => ligne.reduce((s, h, i) => s ^ (h & mot[i]), 0));

// Décodage STRUCTURÉ : on connaît le code, le syndrome donne directement la
// position de l'erreur (lue en binaire).
function decoderAvecClef(recu) {
  const s = syndrome(recu);
  const position = s[0] * 4 + s[1] * 2 + s[2];
  if (position === 0) return { mot: recu, erreur: null };
  const corrige = recu.slice();
  corrige[position - 1] ^= 1;
  return { mot: corrige, erreur: position - 1 };
}

// Décodage GÉNÉRIQUE : on ne connaît que H. On énumère les motifs d'erreur
// par poids croissant jusqu'à retomber sur un syndrome nul.
let essais = 0;
function decoderSansClef(recu, poidsMax) {
  essais = 0;
  const n = recu.length;
  const cible = syndrome(recu);
  // À COMPLÉTER — énumérer tous les motifs d'erreur de poids ≤ poidsMax et
  // renvoyer le premier dont le syndrome égale la cible. Incrémentez essais.
  return null;
}

const MOT = [1, 0, 1, 1, 0, 1, 0];          // mot de code valide
const RECU = MOT.slice(); RECU[4] ^= 1;      // une erreur en position 4

console.log("reçu            :", RECU.join(""));
console.log("syndrome        :", syndrome(RECU).join(""));
console.log("avec la clef    :", JSON.stringify(decoderAvecClef(RECU)));
console.log("sans la clef    :", JSON.stringify(decoderSansClef(RECU, 1)), `(${essais} essais)`);

// Le vrai sujet : combien de motifs faut-il énumérer en taille réelle ?
const binom = (n, k) => { let r = 1; for (let i = 0; i < k; i++) r = (r * (n - i)) / (i + 1); return r; };
console.log("\nmotifs d'erreur à énumérer, C(n, t) :");
for (const [n, t] of [[7, 1], [1024, 38], [3488, 64], [6960, 119]]) {
  console.log(`  n = ${String(n).padStart(4)}, t = ${String(t).padStart(3)}  →  2^${Math.log2(binom(n, t)).toFixed(0)}`);
}

const H = [
  [0, 0, 0, 1, 1, 1, 1],
  [0, 1, 1, 0, 0, 1, 1],
  [1, 0, 1, 0, 1, 0, 1],
];

const syndrome = (mot) =>
  H.map((ligne) => ligne.reduce((s, h, i) => s ^ (h & mot[i]), 0));

function decoderAvecClef(recu) {
  const s = syndrome(recu);
  const position = s[0] * 4 + s[1] * 2 + s[2];
  if (position === 0) return { mot: recu, erreur: null };
  const corrige = recu.slice();
  corrige[position - 1] ^= 1;
  return { mot: corrige, erreur: position - 1 };
}

let essais = 0;
function decoderSansClef(recu, poidsMax) {
  essais = 0;
  const n = recu.length;
  const cible = syndrome(recu);
  const egal = (a, b) => a.every((x, i) => x === b[i]);

  // Énumération par poids croissant. C'est la stratégie de base du décodage
  // générique — et c'est aussi, à des raffinements près, ce que fait encore
  // le meilleur algorithme connu soixante ans plus tard.
  const motifs = [];
  const construire = (debut, restant, courant) => {
    if (restant === 0) { motifs.push(courant.slice()); return; }
    for (let i = debut; i < n; i++) { courant.push(i); construire(i + 1, restant - 1, courant); courant.pop(); }
  };
  for (let poids = 0; poids <= poidsMax; poids++) construire(0, poids, []);

  for (const motif of motifs) {
    essais++;
    const e = new Array(n).fill(0);
    for (const i of motif) e[i] = 1;
    if (egal(syndrome(e), cible)) {
      const corrige = recu.map((b, i) => b ^ e[i]);
      return { mot: corrige, erreur: motif };
    }
  }
  return null;
}

const MOT = [1, 0, 1, 1, 0, 1, 0];
const RECU = MOT.slice(); RECU[4] ^= 1;

console.log("reçu            :", RECU.join(""));
console.log("syndrome        :", syndrome(RECU).join(""));
console.log("avec la clef    :", JSON.stringify(decoderAvecClef(RECU)));
console.log("sans la clef    :", JSON.stringify(decoderSansClef(RECU, 1)), `(${essais} essais)`);

const binom = (n, k) => { let r = 1; for (let i = 0; i < k; i++) r = (r * (n - i)) / (i + 1); return r; };
console.log("\nmotifs d'erreur à énumérer, C(n, t) :");
for (const [n, t] of [[7, 1], [1024, 38], [3488, 64], [6960, 119]]) {
  console.log(`  n = ${String(n).padStart(4)}, t = ${String(t).padStart(3)}  →  2^${Math.log2(binom(n, t)).toFixed(0)}`);
}

// Ce que l'exercice met en scène est EXACTEMENT la trappe de McEliece.
//
// decoderAvecClef fait trois opérations : la structure du code (ici Hamming,
// là un code de Goppa) transforme le syndrome en position d'erreur. C'est la
// clé privée.
//
// decoderSansClef énumère. Sur n = 7 et t = 1, huit essais suffisent. Sur les
// paramètres de Classic McEliece — n = 6960, t = 119 — la dernière ligne
// donne l'ordre de grandeur, et il est astronomique.
//
// La clé publique de McEliece est une matrice génératrice BROUILLÉE : elle
// décrit le même code, mais ne laisse plus voir la structure de Goppa. Même
// objet, deux descriptions, une seule exploitable — exactement la trappe du
// chapitre 4, transposée des réseaux aux codes.
//
// Note : le décodage par ensembles d'information (ISD) fait bien mieux que
// cette énumération naïve, mais reste exponentiel. Soixante ans de
// raffinements n'ont amélioré que la constante dans l'exposant.

À retenir