Jusqu'ici, chiffrer supposait une clé déjà partagée. Comment deux personnes qui ne se sont jamais rencontrées en établissent-elles une sur un canal public ? La réponse — la cryptographie à clé publique — est l'une des grandes ruptures du XXe siècle, et RSA en est le premier exemple complet, publié en 1977 par Rivest, Shamir et Adleman.

L'idée est asymétrique : une clé publique pour chiffrer ou vérifier, que le monde entier peut connaître, et une clé privée pour déchiffrer ou signer, gardée secrète. Ce chapitre construit RSA, puis — fidèle au fil du cours — le casse partout où il est mal employé.

La construction

Elle repose entièrement sur l'arithmétique du chapitre 2.

1. Choisir deux grands premiers $p$ et $q$, et poser $n = pq$. Le module $n$ est public, mais $p$ et $q$ restent secrets.
2. Calculer $\varphi(n) = (p-1)(q-1)$.
3. Choisir un exposant public $e$ premier avec $\varphi(n)$ — en pratique $e = 65537$.
4. Calculer l'exposant privé $d = e^{-1} \bmod \varphi(n)$, par Euclide étendu.

La clé publique est $(n, e)$, la clé privée est $d$. Chiffrement et déchiffrement :

Le déchiffrement redonne le message parce que $ed \equiv 1 \pmod{\varphi(n)}$, donc $m^{ed} \equiv m \pmod n$ par le théorème d'Euler. La signature inverse simplement les rôles : on signe avec $d$, on vérifie avec $e$.

Sur quoi repose vraiment la sécurité

L'attaquant connaît $n$ et $e$. S'il savait factoriser $n$, il obtiendrait $p$ et $q$, donc $\varphi(n)$, donc $d$ : RSA serait mort. Sa sécurité repose donc sur la difficulté de la factorisation, un problème sous-exponentiel (chapitre 2) mais sans algorithme efficace connu sur machine classique.

Une nuance que les étudiants confondent souvent. Casser RSA — retrouver $m$ à partir de $c$ — n'est pas prouvé équivalent à factoriser : il pourrait exister un raccourci qui contourne la factorisation. On n'en connaît pas, mais l'équivalence n'est pas démontrée. C'est une hypothèse de plus, distincte de la difficulté de factoriser, et le chapitre 12 y reviendra en parlant de l'hypothèse RSA.

Les tailles se déduisent des records de factorisation : RSA-1024 est déconseillé, RSA-2048 est le minimum courant, RSA-3072 vise 128 bits de sécurité. À comparer aux 256 bits des courbes elliptiques du chapitre 11 pour la même sécurité — l'écart qui explique leur adoption.

RSA « textbook » est cassé, et vous allez le casser

Le RSA nu — $c = m^e \bmod n$, sans rembourrage — est un désastre pratique, pour deux raisons qui reprennent tout le chapitre 1. Il est déterministe : le même clair donne le même chiffré, donc un adversaire distingue et devine par dictionnaire. Et il est malléable : $(m_1 m_2)^e = m_1^e \, m_2^e$, l'attaquant transforme le chiffré d'un message en celui d'un multiple sans le déchiffrer.

Le cas le plus spectaculaire combine un petit exposant et un message court. Si $e = 3$ et si $m^3 < n$, la réduction modulo $n$ ne s'applique pas : le chiffré est le cube exact du message, et une simple racine cubique entière le rend — sans clé privée, sans factorisation. Montez-la.

// RSA jouet en BigInt. Le module est grand (RSA-ish), mais le message est
// COURT et le chiffrement n'a AUCUN rembourrage. C'est l'erreur.

// Deux premiers (petits pour l'exemple, la faille est indépendante de la taille).
const p = 32416190071n;
const q = 32416187671n;
const n = p * q;
const e = 3n;                 // exposant public minimal, très répandu

// Chiffrement TEXTBOOK : c = m^e mod n, sans OAEP, sans rien.
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;
}

const m = 1234567n;           // message court : un code PIN, un identifiant...
const c = puissanceMod(m, e, n);
console.log("chiffré c =", c.toString());

// ── L'observation qui tue ─────────────────────────────────────────────────
// Si m^e < n, la réduction « mod n » ne fait RIEN : c = m^e comme entier.
// Retrouver m ne demande alors ni la clé privée, ni de factoriser n —
// seulement une racine e-ième ENTIÈRE.
console.log("m^3 < n ?", m ** 3n < n);

// ── À COMPLÉTER : racine cubique entière par dichotomie ───────────────────
function racineCubiqueEntiere(x) {
  if (x < 2n) return x;
  let lo = 0n, hi = 1n;
  while (hi ** 3n <= x) hi <<= 1n;   // borne haute
  // à compléter : resserrer [lo, hi] jusqu'à la racine cubique entière
  return lo;
}

const retrouve = racineCubiqueEntiere(c);
console.log("m retrouvé :", retrouve.toString());
console.log("correct ?", retrouve === m, "| sans clé privée, sans factoriser n");

function racineCubiqueEntiere(x) {
  if (x < 2n) return x;
  let lo = 0n, hi = 1n;
  while (hi ** 3n <= x) hi <<= 1n;
  while (lo < hi) {
    const mid = (lo + hi + 1n) >> 1n;
    if (mid ** 3n <= x) lo = mid;
    else hi = mid - 1n;
  }
  return lo; // plus grand entier dont le cube est <= x
}

// m est retrouvé exactement. La clé privée n'a jamais servi, n n'a pas été
// factorisé : on a simplement pris la racine cubique d'un cube parfait.
//
// La faille tient à DEUX fautes cumulées :
//   1. e = 3, si petit que m^3 peut ne pas déborder n ;
//   2. aucun rembourrage, donc le clair est utilisé tel quel.
//
// La parade est OAEP, qui remplit le message d'un bourrage aléatoire
// structuré : m devient toujours du même ordre de grandeur que n (donc m^e
// déborde et « mod n » redevient une vraie barrière), et deux chiffrements du
// même clair diffèrent. C'est aussi ce qui rend RSA-OAEP sûr contre CCA au
// sens du chapitre 1, là où le RSA textbook est malléable et déterministe.
//
// Variante à connaître : même avec rembourrage, si le MÊME message est envoyé
// à trois destinataires ayant chacun e = 3 (modules différents), le théorème
// des restes chinois reconstitue m^3 modulo le produit des trois modules, puis
// la racine cubique le livre — c'est l'attaque de Håstad.

Les bons schémas : OAEP et PSS

La leçon n'est pas « RSA est mauvais » mais « RSA ne s'emploie jamais nu ». Deux rembourrages normalisés le rendent sûr.

OAEP (Optimal Asymmetric Encryption Padding) enrobe le message avant chiffrement d'une structure aléatoire construite sur des fonctions de hachage. Trois effets : le chiffrement devient probabiliste (deux chiffrements du même clair diffèrent), le message occupe toujours tout l'espace modulo $n$ (l'attaque à exposant faible s'effondre), et le résultat est sûr contre les attaques à chiffrés choisis — IND-CCA2, la cible du chapitre 12.

PSS (Probabilistic Signature Scheme) fait l'équivalent pour la signature. On ne signe jamais le message brut : on le hache, on lui adjoint un aléa, et l'on signe cette valeur. La signature devient inforgeable au sens EUF-CMA, avec une preuve dans le modèle de l'oracle aléatoire.

Le fil rouge du chapitre 7 se referme ici : puisqu'on signe le haché du message, une collision sur la fonction de hachage est une signature forgée. C'est concret — un faux certificat X.509 a été fabriqué en 2008 en exploitant une collision MD5, exactement de cette manière. La sécurité d'une signature n'excède jamais la résistance aux collisions du haché qu'elle emploie.

Les attaques qui restent, même bien rembourré

OAEP et PSS ferment les failles mathématiques, mais l'implémentation en ouvre d'autres.

Module commun, exposant faible. Un même message envoyé à trois destinataires d'exposant $e = 3$ (modules distincts) se reconstitue par les restes chinois puis racine cubique — l'attaque de Håstad. Deux clés partageant un facteur premier se factorisent par un simple pgcd de leurs modules ; un balayage de clés publiques réelles en 2012 a ainsi cassé des milliers de clés RSA dont les premiers avaient été mal tirés.

Coppersmith. Sa méthode, fondée sur la réduction de réseaux (le monde du bloc V), trouve les petites racines d'un polynôme modulaire. Elle casse RSA quand une partie du message est connue, ou quand une fraction des bits d'un facteur premier fuit. C'est un pont inattendu entre RSA et les réseaux euclidiens du post-quantique.

Canaux auxiliaires. L'exponentiation modulaire naïve du chapitre 2 n'est pas à temps constant : sa durée, sa consommation électrique, ses accès au cache dépendent des bits de $d$. Une mesure fine les révèle. La parade a un nom, le blinding : on randomise l'entrée avant l'exponentiation pour décorréler la fuite du secret. Et l'attaque par faute du chapitre 2 rôde toujours — d'où la vérification de signature avant publication.

Ce que la suite en fait

RSA a montré qu'une seule fonction à sens unique — la multiplication facile, la factorisation dure — suffit à bâtir chiffrement et signature. Le chapitre 10 rebâtit tout sur un autre problème difficile, le logarithme discret, avec un avantage décisif : il rend naturel l'échange de clés, là où RSA ne fait que transporter un secret choisi par l'un des deux. Le chapitre 11 y ajoutera les courbes elliptiques et leurs clés courtes, et le chapitre 14 rappellera que Shor, sur un ordinateur quantique, factorise et calcule les logarithmes discrets en temps polynomial — abattant RSA et le chapitre 10 d'un même coup.

À retenir

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

Le chapitre 10 a fondé l'échange de clés sur le logarithme discret dans $(\mathbb{Z}/p\mathbb{Z})^*$ — au prix de modules de 3072 bits, parce que le calcul d'indices y est redoutablement efficace. Ce chapitre change de groupe sans changer d'idée. Sur une courbe elliptique, le calcul d'indices n'a pas d'équivalent connu, seul le rho de Pollard subsiste, et une clé de 256 bits suffit là où RSA en réclame 3072. C'est pourquoi tout ce qui se déploie aujourd'hui — TLS, Signal, les passeports biométriques, Bitcoin — est elliptique.

Un groupe fait de points

Une courbe elliptique sur un corps fini $\mathbb{F}_p$ (le corps du chapitre 2) est l'ensemble des points $(x, y)$ vérifiant

auxquels on ajoute un point spécial, le point à l'infini $\mathcal{O}$. Ce qui transforme cet ensemble en un objet cryptographique, c'est qu'on peut additionner deux points pour en obtenir un troisième, et que cette addition fait des points un groupe.

La règle est géométrique. Pour additionner $P$ et $Q$, on trace la droite qui les joint ; elle recoupe la courbe en un troisième point, dont on prend le symétrique par rapport à l'axe des abscisses. Quand $P = Q$, la droite devient la tangente. Le point $\mathcal{O}$ joue le rôle du neutre — c'est le zéro du groupe.

Traduites en formules dans le corps, ces constructions géométriques deviennent quelques divisions et multiplications modulaires. Implémentez-les : tout le chapitre tient dans cette unique opération.

// Courbe  y² = x³ + ax + b  sur le corps F_p (chapitre 2).
// Le point à l'infini O est le neutre, noté null ici.

const p = 233n, a = 1n, b = 44n; // petite courbe pour l'exemple

function inverseMod(x, m) {
  let [oR, r] = [((x % m) + m) % m, m], [oS, s] = [1n, 0n];
  while (r !== 0n) { const q = oR / r; [oR, r] = [r, oR - q * r]; [oS, s] = [s, oS - q * s]; }
  return ((oS % m) + m) % m;
}
const mod = (x) => ((x % p) + p) % p;

function surLaCourbe(P) {
  if (P === null) return true;
  return mod(P.y * P.y) === mod(P.x * P.x * P.x + a * P.x + b);
}

// ── L'addition de deux points ─────────────────────────────────────────────
// Règle géométrique : la droite par P et Q recoupe la courbe en un troisième
// point ; son symétrique par rapport à l'axe des x est P + Q.
//   • pente sécante  λ = (yQ − yP) / (xQ − xP)      si P ≠ Q
//   • pente tangente λ = (3xP² + a) / (2yP)         si P = Q (doublement)
//   • xR = λ² − xP − xQ,   yR = λ(xP − xR) − yP
// Cas particuliers : O neutre, et P + (−P) = O quand xP = xQ, yP = −yQ.

function addition(P, Q) {
  if (P === null) return Q;
  if (Q === null) return P;
  if (P.x === Q.x && mod(P.y + Q.y) === 0n) return null; // P + (−P) = O

  let lambda;
  if (P.x === Q.x && P.y === Q.y) {
    // à compléter : pente de la TANGENTE (doublement)
    lambda = 0n;
  } else {
    // à compléter : pente de la SÉCANTE
    lambda = 0n;
  }
  const xR = mod(lambda * lambda - P.x - Q.x);
  const yR = mod(lambda * (P.x - xR) - P.y);
  return { x: xR, y: yR };
}

// Égalité de deux points (JSON ne sérialise pas les BigInt).
const egaux = (P, Q) =>
  (P === null && Q === null) ||
  (P !== null && Q !== null && P.x === Q.x && P.y === Q.y);

// Multiplication scalaire par doublements-et-additions : k·P.
function multiplier(k, P) {
  let R = null, base = P;
  while (k > 0n) {
    if (k & 1n) R = addition(R, base);
    base = addition(base, base);
    k >>= 1n;
  }
  return R;
}

// ── Vérifications ─────────────────────────────────────────────────────────
const G = { x: 3n, y: 105n }; // point de base, sur la courbe
console.log("G sur la courbe ?", surLaCourbe(G));

const P2 = addition(G, G);
console.log("2G =", P2, "| sur la courbe ?", surLaCourbe(P2));
console.log("2G == multiplier(2, G) ?", egaux(P2, multiplier(2n, G)));

// ── ECDH émerge de cette seule opération ──────────────────────────────────
const a_priv = 17n, b_priv = 23n;          // secrets d'Alice et Bob
const A = multiplier(a_priv, G);           // clé publique d'Alice
const B = multiplier(b_priv, G);           // clé publique de Bob
const secretAlice = multiplier(a_priv, B); // a·(b·G)
const secretBob = multiplier(b_priv, A);   // b·(a·G)
console.log("secret partagé identique ?", egaux(secretAlice, secretBob));

function addition(P, Q) {
  if (P === null) return Q;
  if (Q === null) return P;
  if (P.x === Q.x && mod(P.y + Q.y) === 0n) return null;

  let lambda;
  if (P.x === Q.x && P.y === Q.y) {
    // Tangente : dérivée implicite de y² = x³ + ax + b.
    lambda = mod((3n * P.x * P.x + a) * inverseMod(2n * P.y, p));
  } else {
    // Sécante : pente ordinaire, division dans le corps.
    lambda = mod((Q.y - P.y) * inverseMod(Q.x - P.x, p));
  }
  const xR = mod(lambda * lambda - P.x - Q.x);
  const yR = mod(lambda * (P.x - xR) - P.y);
  return { x: xR, y: yR };
}

// Tous les tests passent : 2G est sur la courbe, et le secret ECDH coïncide.
//
// Le point clé : ECDH est Diffie-Hellman (chapitre 10) où l'exponentiation
// g^x est remplacée par la multiplication scalaire x·G. Alice calcule a·(b·G),
// Bob calcule b·(a·G) — même point, car la multiplication scalaire commute.
// L'espion voit G, a·G, b·G et doit retrouver a·b·G : c'est le logarithme
// discret SUR LA COURBE, et seul le rho de Pollard s'y applique (pas de calcul
// d'indices). D'où 256 bits de clé pour 128 bits de sécurité, contre 3072 bits
// en RSA. Toute la construction tient dans cette unique addition de points.
//
// ECDSA signe avec la même structure — et hérite du même impératif que DSA :
// un nonce k unique et secret, sous peine de fuite de la clé privée.

ECDH et ECDSA : le chapitre 10, transposé

Une fois l'addition définie, la multiplication scalaire $k \cdot P = P + P + \dots + P$ ($k$ fois) se calcule par doublements-et-additions, exactement comme l'exponentiation rapide du chapitre 2. Et tout le chapitre 10 se réécrit mot pour mot, en remplaçant $g^x$ par $x \cdot G$ :

ECDH. Alice publie $a \cdot G$, Bob publie $b \cdot G$, et tous deux calculent $a \cdot b \cdot G$ — le même point, car la multiplication scalaire commute. L'espion voit $G$, $a \cdot G$, $b \cdot G$ et doit retrouver $a \cdot b \cdot G$ : c'est le logarithme discret sur la courbe (ECDLP). Vous l'avez vu émerger de l'exercice, sans rien de neuf.

ECDSA. La signature elliptique, celle de TLS, des certificats, du Bitcoin. Elle hérite intégralement de l'impératif de DSA : chaque signature exige un nonce $k$ secret et unique. Le chapitre 10 a raconté la PlayStation 3 ; l'histoire s'est répétée sur des portefeuilles Bitcoin dont le générateur d'aléa défaillant produisait des nonces répétés — et les clés privées, donc les fonds, ont été siphonnés. La même faute, encore, et le chapitre 13 dira pourquoi le générateur pseudo-aléatoire est un maillon aussi critique que la primitive elle-même.

Choisir une courbe : là où le diable se cache

Toutes les courbes ne se valent pas, et le choix des paramètres est un champ de mines. Une courbe mal choisie effondre la sécurité sans que rien ne le signale.

Certaines familles sont explicitement faibles : les courbes supersingulières et anomales admettent des attaques qui ramènent l'ECDLP à un logarithme discret facile. L'ordre du groupe doit être premier, ou presque, faute de quoi les attaques par sous-groupes (l'analogue du générateur d'ordre trop petit, chapitre 2) s'appliquent. Et l'implémentation doit valider que les points reçus sont bien sur la courbe — l'attaque par courbe invalide, sinon, injecte des points d'un groupe faible.

D'où l'usage de courbes normalisées et auditées : les courbes NIST (P-256), et surtout Curve25519 de Daniel Bernstein, conçue pour rendre l'implémentation correcte par défaut — arithmétique naturellement à temps constant, validation implicite, pas de choix piégeux laissé au développeur. C'est la courbe de Signal, de SSH moderne, de TLS 1.3.

Un mot sur la défiance. Les paramètres des courbes NIST ont été fournis sans justification publique de leurs constantes, ce qui a nourri le soupçon — jamais démontré — d'une porte dérobée, sur fond de l'affaire bien réelle du générateur Dual_EC_DRBG (chapitre 13). Vrai ou non, ce soupçon a suffi à pousser la communauté vers Curve25519, dont chaque constante est justifiée par un critère rigide et vérifiable. La transparence des paramètres est devenue, depuis, un critère de confiance à part entière.

Ce que la suite en fait

Le bloc asymétrique est complet : RSA, logarithme discret, courbes elliptiques — trois problèmes difficiles, un même schéma de clé publique. Le chapitre 12 prend enfin de la hauteur et formalise ce que « sûr » signifie pour ces objets : les jeux IND-CPA, IND-CCA2, EUF-CMA, et les réductions qui les démontrent — ces réductions qui restaient abstraites tant qu'on n'avait pas RSA et ElGamal en tête. Le chapitre 13 assemblera le tout en TLS 1.3, où ECDH authentifié établit la clé de session. Et le chapitre 14 posera la menace qui plane sur tout ce bloc : l'algorithme de Shor résout le logarithme discret elliptique aussi efficacement qu'il factorise — les clés courtes qui font la force des courbes ne sont d'aucun secours face à lui.

À retenir

QCM de synthèse — Bloc III — Cryptographie asymétrique

Le QCM ci-dessous porte sur l'ensemble du bloc : plusieurs questions relient les leçons entre elles. En cas d'erreur, le bilan indique le chapitre à revoir.