Chapitre 1 · 5 h
Codes correcteurs
Décodage par syndrome et décodage générique, McEliece et Niederreiter, HQC : une sécurité très étudiée contre des clés publiques énormes.
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 sur est un sous-espace vectoriel de dimension dans . On y encode bits d'information en bits transmis, les bits supplémentaires servant à détecter et corriger les erreurs. La distance minimale est le plus petit poids d'un mot de code non nul ; un code corrige jusqu'à erreurs.
Deux matrices décrivent le code. La génératrice , de taille , encode : . La matrice de contrôle , de taille , vérifie : pour tout mot de code.
Le syndrome est la quantité centrale. Si l'on reçoit où est le vecteur d'erreur, alors
Le syndrome ne dépend que de l'erreur, jamais du message. Décoder, c'est retrouver à partir de — 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ù est inversible et une permutation. Chiffrer, c'est encoder le message avec puis ajouter volontairement erreurs. Déchiffrer, c'est retirer la permutation, décoder avec l'algorithme de Goppa, et défaire .
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.
Quiz · 1 question
Où se trouve la trappe dans McEliece ?
- Dans le vecteur d'erreur ajouté au chiffrement
- Dans la connaissance de la structure du code, que la matrice publique brouille
- Dans la matrice de permutation P, gardée secrète
Réponse : P et S servent à brouiller, mais ce ne sont pas elles le secret utile : c'est de savoir que le code EST un code de Goppa, et lequel, qui permet de décoder en temps polynomial. La matrice publique décrit exactement le même code, sans en laisser voir la structure. Décoder sans elle, c'est le problème NP-difficile du décodage générique.
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
Graphique
Clé publique, en octets
- X25519 : 3232
- ML-KEM-768 : 11841184
- HQC-128 : 22492249
- McEliece 348864 : 261120261120
- McEliece 6960119 : 10473191047319
| Classic McEliece | HQC-128 | ML-KEM-768 | |
|---|---|---|---|
| clé publique | 261 kio à 1 Mio | 2249 o | 1184 o |
| chiffré | 96 à 208 o | 4433 o | 1088 o |
| hypothèse | décodage générique, 1978 | décodage quasi-cyclique | Module-LWE |
| statut NIST | non retenu (ISO en cours) | retenu 2025, en secours | FIPS 203 |
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.
Quiz · 1 question
Pour quel usage Classic McEliece est-il un bon choix malgré sa clé d'un mégaoctet ?
- Un handshake TLS grand public
- Un tunnel VPN durable entre deux sites, où la clé s'échange à l'installation
- Une carte à puce à mémoire limitée
Réponse : McEliece produit les chiffrés les plus courts du paysage post-quantique — 96 octets. Ce qui coûte, c'est la clé publique, et elle ne coûte qu'UNE FOIS si elle est provisionnée à l'installation. Dans un tunnel durable, ce sont les chiffrés qui circulent en permanence, et McEliece y est optimal. En TLS, où chaque connexion retransmet la clé, il est disqualifié — et une carte à puce ne peut pas stocker un mégaoctet.
À vous
Exercice de code
Implémentez le décodage générique par énumération, puis comparez son coût à celui du décodage structuré — et lisez la dernière table.
Point de départ
// 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)}`);
}
Solution
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
Flashcards · 3 cartes
- Pourquoi le syndrome est-il la quantité centrale du décodage ?
- Parce que H·yᵀ = H·(c+e)ᵀ = H·eᵀ : le syndrome ne dépend QUE de l'erreur, jamais du message. Décoder revient donc à retrouver un vecteur de petit poids à partir de son syndrome — le problème NP-difficile sur lequel toute la famille repose.
- Qu'est-ce qui distingue la sécurité de McEliece de celle des réseaux ?
- Son ancienneté et sa stabilité. Le problème date de 1978 et le meilleur algorithme connu reste le décodage par ensembles d'information, dont soixante ans de raffinements n'ont amélioré que la constante dans l'exposant. Les estimations de sécurité des réseaux, elles, ont bougé plusieurs fois depuis 2016.
- Pourquoi le NIST a-t-il retenu HQC en secours de ML-KEM plutôt qu'un second schéma à réseaux ?
- Parce qu'un secours n'a d'intérêt que s'il repose sur une hypothèse DIFFÉRENTE. Deux schémas à réseaux tomberaient ensemble. HQC repose sur le décodage de codes quasi-cycliques : si les réseaux cédaient, il resterait debout. C'est le même raisonnement que l'hybridation du chapitre 13, appliqué au portefeuille de normes.