Cryptographie · C4 Cryptographie asymétrique · Chapitre 3 · 6 h

Courbes elliptiques

Loi de groupe, ECDH, ECDSA, choix de courbes, et l'avantage en taille de clé à sécurité égale.

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

y^2 = x^3 + ax + b \pmod p

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.

Exercice de code

Implémentez la loi de groupe sur une courbe elliptique (sécante et tangente), vérifiez-la, et regardez ECDH en découler directement.

Point de départ

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

Solution

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.

Quiz · 1 question

Pourquoi une courbe elliptique de 256 bits offre-t-elle la sécurité d'un RSA de 3072 bits ?

Parce que l'addition de points est plus rapide que l'exponentiation modulaire — vitesse
Parce que le calcul d'indices, sous-exponentiel, n'a pas d'équivalent sur les courbes : seul le rho de Pollard en √n subsiste — absence de calcul d'indices
Parce que les courbes utilisent des corps plus grands — taille du corps

Réponse : Dans (Z/pZ)*, le calcul d'indices sous-exponentiel force des modules de 3072 bits. Sur une courbe bien choisie, aucun analogue n'est connu : la meilleure attaque reste générique, le rho de Pollard en O(√n). Un ordre de 256 bits donne donc 128 bits de sécurité — la moitié des bits, comme au chapitre 10. La rapidité de l'addition est un bonus, pas la raison de fond.

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.

Quiz · 1 question

Pourquoi une implémentation ECDH doit-elle vérifier que les points reçus sont sur la courbe ?

Pour éviter une erreur d'arrondi dans les calculs — précision
Parce qu'un point hors courbe, ou sur une courbe invalide, peut appartenir à un groupe faible où le logarithme discret est facile — courbe invalide
Parce qu'un point hors courbe ralentit la multiplication scalaire — performance

Réponse : L'attaque par courbe invalide envoie un point qui n'est pas sur la courbe attendue mais sur une autre, d'ordre non premier, où le logarithme discret est facile — l'implémentation naïve calcule quand même et fuit des bits de la clé. Valider l'appartenance à la courbe ferme cette porte. Curve25519 rend cette validation implicite, une raison de sa robustesse par défaut.

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

Flashcards · 3 cartes

Qu'est-ce qui fait des points d'une courbe elliptique un groupe utilisable en cryptographie ?: Une loi d'addition géométrique : la droite par P et Q recoupe la courbe en un troisième point, dont le symétrique est P + Q (tangente si P = Q), avec le point à l'infini pour neutre. La multiplication scalaire k·P qui en découle joue le rôle de l'exponentiation g^x, et son inverse — l'ECDLP — est le problème difficile.
En quoi ECDH est-il exactement le Diffie-Hellman du chapitre 10 ?: On remplace g^x par x·G. Alice publie a·G, Bob publie b·G, tous deux calculent a·b·G (la multiplication scalaire commute). L'espion doit résoudre l'ECDLP. Seule différence, décisive : pas de calcul d'indices sur les courbes, donc 256 bits de clé pour 128 bits de sécurité au lieu de 3072.
Quels pièges guettent le choix et l'usage d'une courbe, et que fait Curve25519 ?: Courbes supersingulières/anomales faibles, ordre non premier ouvrant les attaques par sous-groupe, points hors courbe injectant un groupe faible (courbe invalide). Curve25519 neutralise ces pièges par construction : temps constant naturel, validation implicite, constantes justifiées — l'implémentation correcte par défaut.

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.

QCM de bloc · 6 questions

Bloc III — Cryptographie asymétrique

1. Pourquoi une clé de courbe elliptique de 256 bits égale-t-elle un module RSA de 3072 bits à sécurité équivalente ?

Parce que l'addition de points est plus rapide que l'exponentiation
Parce que le calcul d'indices, sous-exponentiel, n'a pas d'équivalent sur les courbes : seul le rho de Pollard en O(√n) y subsiste
Parce que les courbes emploient des corps plus grands

Réponse : Dans (Z/pZ)*, le calcul d'indices sous-exponentiel force des modules de 3072 bits. Sur une courbe bien choisie, aucun analogue n'est connu : la meilleure attaque reste générique (rho de Pollard, O(√n)). Un ordre de 256 bits donne donc 128 bits de sécurité — la moitié des bits, comme pour tout logarithme discret. Cet écart explique l'adoption des courbes.

2. Le nonce rejoué, déjà vu au bloc I, réapparaît en signature. Que se passe-t-il si deux signatures DSA ou ECDSA partagent le même aléa k ?

Rien : k est public de toute façon
Deux équations linéaires à deux inconnues donnent k, puis la CLÉ PRIVÉE — la PlayStation 3 (k constant) et des portefeuilles Bitcoin en sont morts
La signature devient seulement déterministe, sans autre conséquence

Réponse : Deux signatures de même k forment un système linéaire dont on tire k, puis la clé privée. La PlayStation 3 signait avec un k constant (clé de Sony extraite en 2010) ; des portefeuilles Bitcoin à générateur défaillant ont été siphonnés. Même un k faiblement biaisé se casse par les réseaux. C'est le nonce rejoué des blocs précédents, transposé à la signature — un aléa, une fois.

3. Le RSA « textbook » avec e = 3 et un message court se casse par une simple racine cubique. Quelles DEUX fautes se combinent ?

Une clé trop courte et un mauvais générateur d'aléa
Un exposant minuscule (m³ peut ne pas déborder n, donc c = m³) ET l'absence de rembourrage, qui laisse le message trop petit
Un module non premier et une signature non vérifiée

Réponse : Si m³ < n, la réduction « mod n » ne retire rien : c est le cube exact de m, et la racine cubique entière rend m — sans clé privée ni factorisation. Deux fautes cumulées : e = 3 si petit que m³ ne déborde pas, et aucun rembourrage. OAEP corrige les deux — le message occupe alors tout l'espace modulo n, et le chiffrement devient probabiliste (et IND-CCA2).

4. Une signature RSA-PSS ou ECDSA signe le HACHÉ du message. Quelle conséquence sur sa sécurité ?

Aucune : le haché n'est qu'une optimisation de vitesse
Une collision sur la fonction de hachage est une signature forgée — un faux certificat X.509 a été fabriqué en 2008 via une collision MD5
Le haché doit être secret, sinon la signature fuit

Réponse : Puisqu'on signe le haché, deux messages de même empreinte ont la même signature : une collision est une signature valide transférée d'un message à un autre. C'est le pont avec le bloc II — la sécurité d'une signature n'excède jamais la résistance aux collisions de son haché. Un faux certificat a été forgé en 2008 exactement ainsi, sur une collision MD5.

5. La sécurité de RSA repose sur la difficulté de factoriser n. Qu'est-ce qui, précisément, n'est PAS prouvé ?

Que factoriser n donne la clé privée : ce n'est qu'une conjecture
Que casser RSA soit AUSSI dur que factoriser : un raccourci contournant la factorisation pourrait exister (hypothèse RSA)
Que n soit réellement un produit de deux premiers

Réponse : Factoriser n donne p, q, φ(n) puis d : la sécurité EXIGE donc que factoriser soit dur. Mais l'inverse — que retrouver m à partir de c soit aussi dur que factoriser — n'est pas démontré. Un raccourci contournant la factorisation pourrait exister ; on n'en connaît pas, mais c'est une hypothèse distincte (l'hypothèse RSA), que le bloc IV formalise.

6. Diffie-Hellman brut résiste à l'écoute mais s'effondre devant un attaquant ACTIF. Quelle attaque, et quelle parade annoncée pour plus tard ?

L'attaque par faute ; parade : vérifier la signature
L'homme du milieu : Mallory établit un secret avec chacun et relaie. Parade : authentifier l'échange (signatures, certificats), l'objet du bloc IV
Le calcul d'indices ; parade : agrandir le module

Réponse : Le secret DH est bien calculé, mais rien ne certifie l'identité : Mallory s'intercale, établit un secret avec Alice et un autre avec Bob, et relaie en déchiffrant tout. C'est la distinction passif/actif du bloc 0 dans toute sa force. La parade est l'échange de clés AUTHENTIFIÉ — signer les messages, attester par certificat — développé au bloc IV.