Courbes elliptiques

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));

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.