Logarithme discret

RSA transporte un secret : Alice choisit une clé et l'envoie chiffrée. Diffie et Hellman, en 1976 — un an avant RSA — avaient résolu un problème plus subtil : comment deux personnes fabriquent ensemble un secret commun sur un canal public, sans que ni l'une ni l'autre ne l'ait choisi seule, et sans que l'espion qui écoute tout puisse le calculer. Ce chapitre repose sur un second problème difficile, le logarithme discret, et sur la famille de schémas qui en découle.

Le problème du logarithme discret

Dans un groupe cyclique — par exemple $(\mathbb{Z}/p\mathbb{Z})^*$ avec un générateur $g$ — calculer $h = g^x \bmod p$ est facile, par exponentiation rapide. Le problème inverse — retrouver $x$ à partir de $h$ — est le logarithme discret, et on ne connaît pas d'algorithme efficace pour le résoudre dans un groupe bien choisi.

L'asymétrie est celle qui fonde toute la clé publique : une direction aisée, l'autre infaisable. Ici $x$ est le secret, $g^x$ est public, et tout repose sur l'impossibilité de remonter.

Diffie-Hellman

Le protocole est d'une élégance qui tient en quatre lignes. Un premier $p$ et un générateur $g$ sont publics.

1. Alice tire $a$ au hasard, envoie $A = g^a \bmod p$.
2. Bob tire $b$ au hasard, envoie $B = g^b \bmod p$.
3. Alice calcule $B^a = g^{ba}$. Bob calcule $A^b = g^{ab}$.
4. Les deux obtiennent la même valeur $g^{ab} \bmod p$ : le secret partagé.

L'espion voit $g$, $p$, $A = g^a$ et $B = g^b$. Pour obtenir $g^{ab}$, il lui faudrait $a$ ou $b$ — donc résoudre un logarithme discret. Ni Alice ni Bob n'a choisi le secret : il a émergé de leurs deux aléas. C'est l'acte de naissance de la cryptographie moderne.

Une précision de vocabulaire pour le chapitre 12 : la sécurité repose non pas exactement sur le logarithme discret, mais sur l'hypothèse — un cran plus forte — que $g^{ab}$ est indistinguable d'un élément aléatoire (hypothèse décisionnelle de Diffie-Hellman, DDH). Retenez la distinction, le chapitre 12 la formalisera.

ElGamal et DSA

Diffie-Hellman établit un secret ; on en tire aussitôt un chiffrement et une signature.

ElGamal transforme l'échange en chiffrement. Pour envoyer $m$ à Bob de clé publique $B = g^b$, Alice tire un aléa $k$, envoie $(g^k,\; m \cdot B^k)$ ; Bob retrouve $B^k = (g^k)^b$ et divise. Le chiffrement est naturellement probabiliste — l'aléa $k$ neuf à chaque message — là où RSA devait y être forcé par OAEP.

DSA est le pendant en signature, standardisé par le NIST. Sa sécurité tient à une condition impérative : l'aléa $k$ de chaque signature doit être secret et unique. La suite du chapitre montre ce que coûte de la violer.

Résoudre le logarithme discret

Comme pour la factorisation, la taille des paramètres se déduit des meilleures attaques. Il y en a trois familles, et leur portée diffère radicalement selon le groupe.

Pas de bébé, pas de géant (baby-step giant-step). Générique — il marche dans tout groupe. En écrivant $x = im + j$ avec $m = \lceil\sqrt{n}\rceil$, il résout le logarithme discret en $O(\sqrt{n})$ opérations et $O(\sqrt{n})$ mémoire. Encore un compromis temps-mémoire, dans la lignée du chapitre 6. Vous allez l'implémenter.

// On cherche x tel que g^x = h (mod p), dans (Z/pZ)*.
// La force brute essaie x = 0, 1, 2, ... : jusqu'à p−1 multiplications.
// Baby-step giant-step le fait en ~2√p, au prix d'une table de √p entrées.

function puissanceMod(base, exp, mod) {
  let r = 1n; base %= mod;
  while (exp > 0n) {
    if (exp & 1n) r = (r * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return r;
}
function inverseMod(a, m) {
  let [oldR, r] = [((a % m) + m) % m, m];
  let [oldS, s] = [1n, 0n];
  while (r !== 0n) {
    const q = oldR / r;
    [oldR, r] = [r, oldR - q * r];
    [oldS, s] = [s, oldS - q * s];
  }
  return ((oldS % m) + m) % m;
}

const p = 1000003n;   // premier
const g = 2n;         // générateur
const x = 654321n;    // le secret, à retrouver
const h = puissanceMod(g, x, p);
console.log("instance : 2^x =", h.toString(), "(mod", p.toString() + ")");

// ── Principe ──────────────────────────────────────────────────────────────
// On écrit x = i·m + j  avec  m = ceil(√p),  0 <= i, j < m.
// Alors g^x = h  devient  g^j = h · (g^{-m})^i.
//   • BABY STEPS : tabuler g^j pour tous les j  →  table { g^j : j }
//   • GIANT STEPS : parcourir h·(g^{-m})^i pour i = 0,1,...  jusqu'à tomber
//     dans la table. Alors x = i·m + j.

function racineSup(n) {
  let r = 0n; while (r * r < n) r++; return r;
}

// ── À COMPLÉTER ───────────────────────────────────────────────────────────
function logDiscret(g, h, p) {
  const m = racineSup(p);

  // Baby steps : g^j pour j de 0 à m−1.
  const table = new Map();
  // à compléter : remplir la table

  // Facteur de saut : (g^{-1})^m = g^{-m}.
  const facteur = puissanceMod(inverseMod(g, p), m, p);

  // Giant steps : gamma = h, puis gamma *= facteur à chaque pas.
  let gamma = h % p;
  for (let i = 0n; i < m; i++) {
    // à compléter : si gamma est dans la table, renvoyer i*m + j
    gamma = (gamma * facteur) % p;
  }
  return null;
}

const t0 = Date.now();
const trouve = logDiscret(g, h, p);
console.log("x retrouvé :", trouve && trouve.toString(), "en", Date.now() - t0, "ms");
console.log("correct ?", trouve === x, "| ~2√p =", 2 * Number(racineSup(p)), "opérations, pas", p.toString());

function logDiscret(g, h, p) {
  const m = racineSup(p);

  // Baby steps.
  const table = new Map();
  let e = 1n;
  for (let j = 0n; j < m; j++) {
    if (!table.has(e)) table.set(e, j);
    e = (e * g) % p;
  }

  const facteur = puissanceMod(inverseMod(g, p), m, p);

  // Giant steps.
  let gamma = h % p;
  for (let i = 0n; i < m; i++) {
    if (table.has(gamma)) return i * m + table.get(gamma);
    gamma = (gamma * facteur) % p;
  }
  return null;
}

// x = 654321 est retrouvé en ~2·1000 = 2000 opérations au lieu de 10^6.
//
// C'est encore un compromis temps-mémoire (chapitre 6) : le TEMPS passe de p à
// 2√p, la MÉMOIRE coûte √p entrées. Le rho de Pollard obtient le même √p en
// temps SANS la mémoire — c'est lui qu'on utilise en pratique.
//
// La conséquence dimensionne les schémas : la sécurité d'un groupe d'ordre n
// n'est que de √n, soit la MOITIÉ des bits. Un logarithme discret « 128 bits »
// exige donc un sous-groupe d'ordre 256 bits. Sur les courbes elliptiques
// (chapitre 11), rho de Pollard EST la meilleure attaque connue, d'où une clé
// de 256 bits pour 128 bits de sécurité. Dans (Z/pZ)*, le calcul d'indices, lui
// sous-exponentiel, fait bien mieux — d'où des modules p de 3072 bits.

Rho de Pollard. Générique lui aussi, il atteint le même $O(\sqrt{n})$ en temps mais avec une mémoire négligeable — il exploite le paradoxe des anniversaires du chapitre 7 pour provoquer un cycle. C'est l'attaque de référence en pratique, et la seule qui compte sur les courbes elliptiques.

Calcul d'indices. Spécifique à $(\mathbb{Z}/p\mathbb{Z})^*$, il est sous-exponentiel, de la même forme que le crible de factorisation. C'est lui qui rend RSA et le Diffie-Hellman modulaire comparables, et qui impose des modules $p$ de 3072 bits pour 128 bits de sécurité. Le point décisif du chapitre 11 : ce calcul d'indices n'a pas d'équivalent sur les courbes elliptiques, où seul le rho de Pollard s'applique. D'où des clés de 256 bits pour la même sécurité.

La règle générique à retenir : un groupe d'ordre $n$ n'offre que $\sqrt{n}$ de résistance, soit la moitié des bits. Un logarithme discret « 128 bits » exige donc un sous-groupe d'ordre 256 bits — exactement la taille des clés de courbe.

Deux fautes classiques

L'homme du milieu. Diffie-Hellman brut n'authentifie personne. Mallory intercepte, établit un secret avec Alice d'un côté et avec Bob de l'autre, et relaie en déchiffrant tout au passage. Chacun croit parler à l'autre. C'est la distinction attaquant passif / actif du chapitre 1 dans toute sa force : le protocole résiste parfaitement au premier et s'effondre devant le second. La parade est d'authentifier les échanges — signatures, certificats — et c'est tout l'objet du chapitre 13. Diffie-Hellman n'est jamais déployé nu.

Le nonce rejoué de DSA. Si deux signatures DSA réutilisent le même aléa $k$, deux équations linéaires à deux inconnues suffisent à extraire $k$, puis la clé privée. Ce n'est pas théorique : la console PlayStation 3 signait son code avec un $k$ constant, et la clé privée de Sony en a été extraite en 2010. Même un $k$ simplement biaisé — quelques bits prévisibles — se casse par les réseaux euclidiens du bloc V. On retrouve, transposé à la signature, le nonce rejoué des chapitres 3 et 5 : la faute la plus tenace de la discipline.

Ce que la suite en fait

Le logarithme discret a fondé l'échange de clés, le chiffrement et la signature sur un problème autre que la factorisation. Le chapitre 11 change de groupe sans changer d'idée : il remplace $(\mathbb{Z}/p\mathbb{Z})^*$ par les points d'une courbe elliptique, où le calcul d'indices s'évanouit et où les clés deviennent courtes — ECDH et ECDSA sont les versions elliptiques de ce chapitre. Le chapitre 13 authentifiera enfin ces échanges pour clore l'homme du milieu, et le chapitre 14 rappellera que Shor abat le logarithme discret aussi sûrement que la factorisation.

À retenir