Calcul quantique pour cryptographes

Ce chapitre a un objectif précis et une limite tout aussi précise. L'objectif : comprendre pourquoi Shor casse RSA et pourquoi Grover ne casse pas AES. La limite : nous ne ferons pas un cours de mécanique quantique. Un cryptographe a besoin de savoir ce que ces algorithmes prennent en entrée, ce qu'ils rendent, et à quel coût — pas de savoir résoudre l'équation de Schrödinger.

Le qubit, sans mysticisme

Un bit classique vaut 0 ou 1. Un qubit est décrit par deux nombres complexes $\alpha$ et $\beta$ tels que $|\alpha|^2 + |\beta|^2 = 1$ :

À la mesure, on obtient 0 avec probabilité $|\alpha|^2$ et 1 avec probabilité $|\beta|^2$, et l'état est détruit. Un registre de $n$ qubits est décrit par $2^n$ amplitudes.

C'est ici que naît le malentendu le plus répandu du domaine. On lit partout qu'un ordinateur quantique « essaie toutes les possibilités en parallèle ». C'est faux, et il faut le dire fermement à des étudiants qui l'ont lu ailleurs. Les $2^n$ amplitudes existent bien, mais la mesure n'en rend qu'une seule, tirée au hasard. Un parallélisme dont on ne peut extraire qu'un résultat aléatoire ne vaut rien.

Ce qui fait la puissance de l'algorithmique quantique n'est pas la superposition, c'est l'interférence. Les amplitudes sont des nombres complexes : elles peuvent s'annuler. Un algorithme quantique utile est un algorithme qui organise les annulations de sorte que les mauvaises réponses s'éteignent mutuellement et que les bonnes se renforcent, avant la mesure. Tout le métier est là.

L'intrication est le troisième ingrédient : l'état de deux qubits n'est pas toujours décomposable en deux états individuels. C'est ce qui rend le registre irréductible à $n$ qubits séparés, et donc l'espace des états exponentiel.

La transformée de Fourier quantique

L'outil central de Shor est la transformée de Fourier quantique, la QFT. C'est la transformée de Fourier discrète habituelle, appliquée au vecteur des amplitudes.

Sa propriété décisive : elle transforme une amplitude périodique de période $r$ en une amplitude concentrée sur les multiples de $N/r$. Autrement dit, elle convertit une période — information globale, invisible sur un échantillon — en une position, qu'une mesure révèle en une fois.

Le coût est ce qui surprend. La transformée de Fourier discrète classique sur $2^n$ points coûte $O(n \, 2^n)$ opérations, ou $O(n 2^n)$ ramené à $O(2^n \log 2^n)$ par la FFT. La QFT sur $n$ qubits coûte $O(n^2)$ portes. On passe d'exponentiel à quadratique — en le nombre de qubits, ce qui n'est pas un miracle mais un changement d'unité de compte : la QFT ne donne pas accès aux $2^n$ amplitudes, elle les transforme en bloc sans jamais permettre de les lire.

Shor : une seule ligne est quantique

La factorisation se ramène à un problème de période. Pour factoriser $N$, on choisit $a$ au hasard et on cherche l'ordre $r$ de $a$ modulo $N$, c'est-à-dire le plus petit $r$ tel que $a^r \equiv 1 \pmod N$. Si $r$ est pair et $a^{r/2} \not\equiv -1$, alors

sont des facteurs non triviaux de $N$. Cette réduction est entièrement classique et date d'avant Shor. Ce que Shor a apporté, c'est une méthode quantique pour trouver $r$.

Déroulez la trace et comptez : une ligne sur neuf est quantique. C'est la formulation correcte de la menace, et elle est plus utile que l'image de la machine qui essaie tous les facteurs. Le logarithme discret tombe de la même manière, parce que trouver $x$ tel que $g^x = h$ est également un problème de période déguisé — d'où le fait qu'un seul algorithme emporte RSA, Diffie-Hellman et les courbes elliptiques.

Le coût annoncé est polynomial : de l'ordre de $O(n^3)$ opérations quantiques pour un module de $n$ bits, contre un coût sous-exponentiel pour le meilleur algorithme classique connu, le crible algébrique.

Grover : pourquoi seulement la racine carrée

Grover résout un problème différent : chercher l'unique bonne entrée parmi $N$ possibilités, quand la seule chose qu'on sache faire est tester une entrée. Il y parvient en $O(\sqrt{N})$ évaluations au lieu de $N$.

Appliqué à une clé de 128 bits, cela donne $2^{64}$ évaluations au lieu de $2^{128}$ : la sécurité est divisée par deux en bits, pas effondrée. D'où la règle simple du chapitre précédent — doubler la taille des clés symétriques.

Trois précisions rendent Grover encore moins menaçant qu'il n'en a l'air, et méritent d'être connues.

D'abord, cette borne est optimale : on sait démontrer qu'aucun algorithme quantique ne fait mieux que $\sqrt{N}$ pour une recherche non structurée. Il n'y a pas de « Grover amélioré » à craindre.

Ensuite, Grover se parallélise mal. Répartir la recherche sur $k$ machines ne divise le temps que par $\sqrt{k}$, alors qu'une recherche exhaustive classique se divise par $k$. Les $2^{64}$ évaluations doivent donc être largement séquentielles, ce qui impose une durée de calcul et une profondeur de circuit considérables.

Enfin, chaque évaluation exige d'implémenter AES en circuit quantique réversible, ce qui coûte bien plus cher qu'un tour d'AES sur un processeur ordinaire. Le NIST en tient compte dans ses niveaux de sécurité, en plafonnant la profondeur de circuit admissible.

Où en est le matériel

C'est la question que tout auditoire pose, et la seule à laquelle il faut répondre avec des ordres de grandeur plutôt qu'avec une date.

La distinction décisive est celle entre qubit physique et qubit logique. Les qubits physiques sont bruités : leur état se dégrade en quelques dizaines de microsecondes. Un qubit logique est un qubit corrigé, construit à partir de nombreux qubits physiques par un code correcteur quantique. Le rapport dépend du taux d'erreur physique et se compte aujourd'hui en centaines à milliers de qubits physiques par qubit logique.

Les machines annoncées se comptent en centaines à un millier de qubits physiques, et le franchissement du seuil de correction d'erreur — le point où ajouter des qubits physiques réduit effectivement le taux d'erreur logique — a été démontré expérimentalement, ce qui constitue le jalon scientifique important de ces dernières années.

Les estimations de ressources pour casser RSA-2048 se comptaient, dans les travaux de référence de 2019, en une vingtaine de millions de qubits physiques bruités pour quelques heures de calcul. Des travaux ultérieurs ont fait descendre cette estimation d'un ordre de grandeur. La leçon à en tirer n'est pas un chiffre — il changera encore — mais une tendance : les estimations de ressources baissent régulièrement, sous l'effet de meilleurs algorithmes autant que de meilleur matériel. Un plan de migration qui suppose que $Z$ est figé est un plan fragile.

À vous

L'exercice remplace la sous-routine quantique par une recherche naïve. Tout le reste du code est le vrai Shor. Comptez le coût de chaque partie, et vous verrez précisément ce que l'ordinateur quantique achète — et ce qu'il n'achète pas.

// Shor, mais entièrement classique : on REMPLACE la sous-routine quantique
// par une recherche naïve de période. Le reste du code est le vrai Shor.
//
// L'exercice n'a donc rien de quantique. Son but est de vous faire toucher
// du doigt QUELLE ligne est chère, et pourquoi c'est la seule qu'un
// ordinateur quantique change.

const pgcd = (a, b) => (b === 0 ? a : pgcd(b, a % b));

// Exponentiation modulaire rapide — nécessaire dès que N dépasse quelques
// milliers, sinon a^x déborde.
function puissanceMod(a, x, n) {
  let r = 1n, base = BigInt(a) % BigInt(n), e = BigInt(x), m = BigInt(n);
  while (e > 0n) {
    if (e & 1n) r = (r * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(r);
}

let coutPeriode = 0;

// LA sous-routine que Shor confie au quantique. Ici, force brute.
function periode(a, N) {
  // À COMPLÉTER — cherchez le plus petit r ≥ 1 tel que a^r ≡ 1 (mod N),
  // en incrémentant coutPeriode à chaque essai. Renvoyez null si r dépasse N.
  return null;
}

function shor(N, essais = 20) {
  for (let k = 0; k < essais; k++) {
    const a = 2 + Math.floor(Math.random() * (N - 3));
    const d = pgcd(a, N);
    if (d > 1) return { p: d, q: N / d, a, r: null, chance: true };

    const r = periode(a, N);
    if (r === null || r % 2 !== 0) continue;

    const x = puissanceMod(a, r / 2, N);
    if (x === N - 1) continue;             // cas dégénéré, on retire un a

    const p = pgcd(x - 1, N);
    const q = pgcd(x + 1, N);
    if (p > 1 && p < N) return { p, q: N / p, a, r, chance: false };
  }
  return null;
}

for (const N of [15, 21, 91, 3599]) {
  coutPeriode = 0;
  const t = shor(N);
  console.log(
    t
      ? `N = ${String(N).padStart(5)}  →  ${t.p} × ${t.q}` +
        `   (a = ${t.a}, r = ${t.r ?? "—"}, ${coutPeriode} essais de période)`
      : `N = ${N} : échec`
  );
}

const pgcd = (a, b) => (b === 0 ? a : pgcd(b, a % b));

function puissanceMod(a, x, n) {
  let r = 1n, base = BigInt(a) % BigInt(n), e = BigInt(x), m = BigInt(n);
  while (e > 0n) {
    if (e & 1n) r = (r * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(r);
}

let coutPeriode = 0;

function periode(a, N) {
  // La boucle qu'un ordinateur quantique n'exécute PAS. Il n'essaie pas les
  // valeurs une par une : il prépare une superposition de tous les a^x, puis
  // la transformée de Fourier quantique fait ressortir la fréquence 1/r.
  let x = a % N;
  for (let r = 1; r <= N; r++) {
    coutPeriode++;
    if (x === 1) return r;
    x = (x * a) % N;
  }
  return null;
}

function shor(N, essais = 20) {
  for (let k = 0; k < essais; k++) {
    const a = 2 + Math.floor(Math.random() * (N - 3));
    const d = pgcd(a, N);
    if (d > 1) return { p: d, q: N / d, a, r: null, chance: true };

    const r = periode(a, N);
    if (r === null || r % 2 !== 0) continue;

    const x = puissanceMod(a, r / 2, N);
    if (x === N - 1) continue;

    const p = pgcd(x - 1, N);
    const q = pgcd(x + 1, N);
    if (p > 1 && p < N) return { p, q: N / p, a, r, chance: false };
  }
  return null;
}

for (const N of [15, 21, 91, 3599]) {
  coutPeriode = 0;
  const t = shor(N);
  console.log(
    t
      ? `N = ${String(N).padStart(5)}  →  ${t.p} × ${t.q}` +
        `   (a = ${t.a}, r = ${t.r ?? "—"}, ${coutPeriode} essais de période)`
      : `N = ${N} : échec`
  );
}

// Ce qu'il faut lire dans la colonne « essais de période ».
//
// Elle croît comme N, c'est-à-dire de façon EXPONENTIELLE en le nombre de
// chiffres. Pour N = 3599 = 59 × 61, on compte déjà quelques milliers
// d'essais ; pour un module RSA de 2048 bits, ce serait de l'ordre de 2^2048.
//
// Toutes les autres lignes — pgcd, exponentiation modulaire, tirage de a —
// sont polynomiales et resteraient parfaitement praticables sur un module de
// 2048 bits. Le pgcd de deux nombres de 2048 bits prend quelques
// microsecondes.
//
// Autrement dit : RSA ne tient debout QUE parce que cette seule fonction est
// coûteuse. La transformée de Fourier quantique la rend polynomiale, et tout
// l'édifice s'effondre sans qu'aucune autre ligne n'ait besoin de changer.

À retenir