Isogénies et multivarié

Ce chapitre est le plus court du cours et le plus important pour la formation du jugement. Il porte sur deux familles qui ont échoué en public, devant témoins, après avoir passé plusieurs tours d'un processus de normalisation international. Ce n'est pas un chapitre d'histoire : c'est un chapitre de méthode.

Isogénies : l'idée

Une isogénie est une application entre deux courbes elliptiques qui préserve la structure de groupe. On peut la voir comme un morphisme reliant une courbe à une autre.

L'objet cryptographique n'est plus la courbe, mais le graphe dont les sommets sont des courbes elliptiques supersingulières et les arêtes des isogénies de petit degré. Ce graphe a une propriété remarquable : il est expandeur. En s'y promenant au hasard quelques dizaines de pas, on aboutit à un sommet impossible à relier à son point de départ — trouver le chemin entre deux courbes données est le problème difficile.

L'attrait était considérable : les clés étaient les plus petites de tout le paysage post-quantique, quelques centaines d'octets seulement, là où les réseaux en demandent plusieurs milliers.

SIKE, et l'après-midi du 30 juillet 2022

SIDH, proposé en 2011, était le protocole d'échange de clés fondé sur ces graphes. SIKE en était la version encapsulation, candidate au processus NIST, arrivée jusqu'au quatrième tour. Onze ans d'examen public.

Le 30 juillet 2022, Wouter Castryck et Thomas Decru publient une attaque qui récupère la clé secrète. Elle s'exécute en une heure environ sur un seul cœur de processeur ordinaire pour les paramètres du premier niveau de sécurité. Des optimisations publiées dans les semaines suivantes ramèneront ce temps à quelques minutes, et Damien Robert généralisera l'attaque en temps polynomial pour toute courbe de départ.

Le mécanisme mérite d'être compris, parce qu'il change complètement la leçon à en tirer. SIDH ne publiait pas seulement une courbe d'arrivée : pour permettre aux deux parties de calculer la même valeur commune, il publiait aussi l'image de points de torsion auxiliaires par l'isogénie secrète. C'est cette information supplémentaire que l'attaque exploite, en s'appuyant sur un théorème de Kani datant de 1997 — un résultat de géométrie algébrique qui n'avait jamais été rapproché de SIDH.

Autrement dit : le problème général des isogénies n'a pas été cassé. C'est la manière dont SIDH en révélait un morceau qui l'a été. La distinction est essentielle, et c'est elle qui explique que CSIDH et SQIsign, qui ne publient pas ces points de torsion, restent debout.

Ce que SIKE enseigne

Trois leçons, et elles valent pour tout le reste du cours.

L'examen public ne prouve pas l'absence d'attaque. SIDH a été scruté onze ans par une communauté active. Le résultat qui l'a tué existait depuis 1997, dans une branche voisine des mathématiques. Personne n'avait fait le rapprochement. « Personne n'a trouvé d'attaque » est une observation, pas une garantie.

Une cassure peut être totale et instantanée. Il n'y a pas eu d'érosion progressive des paramètres, pas de signal d'alerte, pas de fenêtre pour réagir. Le passage d'« il tient » à « une heure sur un portable » a été immédiat.

D'où l'hybridation. Un déploiement qui combinait X25519 et SIKE n'a rien perdu le 30 juillet 2022 : il lui restait la sécurité classique de X25519. Un déploiement SIKE seul était nu. C'est l'argument décisif en faveur de l'approche que l'ANSSI impose et que le chapitre 13 détaille — et sans SIKE, cet argument passerait pour une précaution excessive.

CSIDH et SQIsign

La famille n'est pas morte, et il serait injuste de la présenter ainsi.

CSIDH utilise une action de groupe commutative sur les courbes supersingulières définies sur $\mathbb{F}_p$. Sa commutativité est un atout — elle rend possibles des primitives que les réseaux ne fournissent pas facilement — et une faiblesse : l'algorithme quantique de Kuperberg pour le problème du décalage caché s'y applique, avec un coût sous-exponentiel. Le dimensionnement de CSIDH reste discuté pour cette raison.

SQIsign est une signature dont les objets sont d'une compacité sans rivale — une clé publique de quelques dizaines d'octets, une signature de moins de deux cents. Comparez aux 2420 octets de ML-DSA-44. Son défaut est la vitesse : signer et vérifier coûtent des ordres de grandeur de plus que ML-DSA. Elle est candidate au processus additionnel de signatures du NIST, et représente le meilleur espoir de la famille.

Le multivarié, et Rainbow

L'autre famille de ce chapitre repose sur la difficulté de résoudre un système d'équations quadratiques à plusieurs variables sur un corps fini — problème NP-difficile dans le cas général.

La trappe s'appelle huile et vinaigre. On construit un système central où les variables sont séparées en deux groupes, et où l'on s'interdit tout produit huile × huile. Fixer les variables de vinaigre au hasard rend alors le système linéaire en les variables d'huile : il se résout par élimination de Gauss. La clé publique est ce système composé avec un mélange linéaire secret, qui cache quelles combinaisons de variables forment l'espace d'huile.

Rainbow empilait plusieurs couches de cette construction pour réduire la taille des clés. Il était finaliste du troisième tour du NIST, à un cheveu de la normalisation.

En février 2022, Ward Beullens publie un article au titre sans équivoque : Breaking Rainbow Takes a Weekend on a Laptop. Les paramètres du premier niveau de sécurité tombent en une cinquantaine d'heures sur un ordinateur portable. L'attaque exploite précisément la structure en couches ajoutée pour gagner en taille : elle offrait une prise supplémentaire pour localiser l'espace d'huile.

Le point qui doit rester : la sécurité d'un schéma multivarié ne se lit pas dans la taille de l'espace de recherche. Elle se lit dans la difficulté de retrouver la structure cachée, et cette difficulté-là est bien plus délicate à estimer. Le schéma UOV originel, sans les couches de Rainbow, survit et reste candidat — avec des clés publiques de plusieurs dizaines de kilooctets, mais des signatures d'une centaine d'octets.

À vous

// La trappe « huile et vinaigre », celle de Rainbow et de UOV.
//
// n = 4 variables sur F_7 : deux VINAIGRE (x0, x1) et deux HUILE (x2, x3).
// Règle unique du système central : jamais de produit huile × huile.
// C'est cette absence qui rend le système inversible — et c'est elle que
// l'attaque de Beullens a fini par retrouver dans Rainbow.

const q = 7;
const V = [0, 1];   // indices vinaigre
const O = [2, 3];   // indices huile
const mod = (x) => ((x % q) + q) % q;
const inv = (a) => { for (let i = 1; i < q; i++) if (mod(a * i) === 1) return i; return null; };

// Deux polynômes quadratiques SANS terme huile × huile.
// coefQuad[k][i][j] = coefficient de x_i·x_j dans l'équation k.
const coefQuad = [
  [[3, 1, 2, 5], [0, 4, 6, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
  [[2, 6, 1, 3], [0, 5, 2, 4], [0, 0, 0, 0], [0, 0, 0, 0]],
];
// Les deux dernières LIGNES sont nulles : aucun terme ne commence par une
// variable d'huile, donc aucun produit huile × huile n'existe.

function evaluer(k, x) {
  let t = 0;
  for (let i = 0; i < 4; i++) for (let j = 0; j < 4; j++) t += coefQuad[k][i][j] * x[i] * x[j];
  return mod(t);
}

// INVERSION AVEC LA TRAPPE : on fixe le vinaigre, le système devient LINÉAIRE
// en l'huile, et deux équations à deux inconnues se résolvent.
function inverserAvecTrappe(cible, vinaigre) {
  // À COMPLÉTER — pour chaque équation k, construire la ligne linéaire
  // [a_k2, a_k3 | b_k] obtenue en fixant x0 et x1, puis résoudre.
  //
  // Indication : le coefficient de x_h (h dans O) vaut
  //   somme sur i dans V de ( coefQuad[k][i][h] + coefQuad[k][h][i] ) * x_i
  // et le terme constant est l'évaluation avec l'huile mise à zéro.
  return null;
}

// INVERSION SANS LA TRAPPE : force brute sur toutes les variables.
let essais = 0;
function inverserSansTrappe(cible) {
  essais = 0;
  for (let a = 0; a < q; a++) for (let b = 0; b < q; b++)
    for (let c = 0; c < q; c++) for (let d = 0; d < q; d++) {
      essais++;
      const x = [a, b, c, d];
      if (evaluer(0, x) === cible[0] && evaluer(1, x) === cible[1]) return x;
    }
  return null;
}

const CIBLE = [4, 2];
const VINAIGRE = [3, 5];

const avec = inverserAvecTrappe(CIBLE, VINAIGRE);
console.log("avec trappe  :", JSON.stringify(avec),
  avec ? "→ " + JSON.stringify([evaluer(0, avec), evaluer(1, avec)]) : "");
const sans = inverserSansTrappe(CIBLE);
console.log("force brute  :", JSON.stringify(sans), `(${essais} essais)`);

console.log("\ncoût de la force brute selon la taille :");
for (const [corps, n] of [[7, 4], [16, 40], [16, 100], [256, 112]]) {
  console.log(`  F_${String(corps).padStart(3)}, n = ${String(n).padStart(3)}  →  2^${(n * Math.log2(corps)).toFixed(0)}`);
}

À retenir

QCM du bloc II — Les autres familles

Neuf questions sur les codes, le hachage, les isogénies et le multivarié. Plusieurs demandent de CHOISIR une famille pour un usage donné : c'est la compétence que ce bloc vise réellement.