La courbe Ed25519

Scalaires, points et l’unique opération sur laquelle repose tout Monero

Pourquoi une courbe

Il nous faut une « fonction à sens unique avec cadenas » : à partir d’un secret, il est facile d’obtenir quelque chose de public, mais pas l’inverse. Et nous voulons pouvoir calculer sur les objets publics : les additionner et les multiplier par des nombres. Une courbe elliptique offre exactement cela.

Monero utilise la même courbe que les signatures Ed25519 (Daniel J. Bernstein et al.) : une courbe d’Edwards tordue

Un point est une paire de nombres (x, y) qui satisfait l’équation. Tous les calculs se font modulo le nombre premier p : la « courbe » est donc en réalité un nuage d’environ 2²⁵⁵ points discrets.

Additionner des points

On peut additionner des points : P + Q = R, où R est aussi sur la courbe. Sur les courbes d’Edwards, une seule formule couvre tous les cas (pratique et sûr) :

Cette addition se comporte comme l’addition ordinaire : elle est commutative et associative, il existe un « zéro » — le point (0, 1) — et chaque point a un opposé (−x, y).

Multiplier par un nombre

Multiplier un point par x, c’est l’ajouter à lui-même x fois. Bien sûr, personne n’additionne 2²⁵² fois : la méthode « doubler-et-ajouter » ne demande qu’environ 256 doublements et 128 additions.

Le point de base G et l’ordre l

Tout le monde utilise le même point de base G, convenu à l’avance. Multipliez G par 1, 2, 3, … et au bout de l étapes vous revenez à zéro :

l est l’ordre du sous-groupe engendré par G. La courbe compte au total 8 fois plus de points (8·l) ; 8 s’appelle le cofacteur. Ce cofacteur est la source de plusieurs subtilités dans Monero : vous verrez un facteur 8 dans les formules des adresses à usage unique, et en 2017, des « points d’ordre faible » auraient pu produire plusieurs key images pour une même sortie (corrigé en vérifiant l·I = 0).

Pourquoi cela fonctionne pour les clés

Prenez un x aléatoire — c’est une clé privée. Calculez P = x·G — c’est une clé publique. Publier P est sans danger. Point crucial, les points se prêtent à l’algèbre :

La seconde identité est la base de l’échange de clés Diffie–Hellman : Alice connaît a et voit B = b·G ; Bob connaît b et voit A = a·G. Tous deux peuvent calculer le même point a·B = b·A = ab·G, mais pas un observateur extérieur. Les adresses à usage unique reposent là-dessus.

La première identité est la base des engagements de Pedersen : les montants cachés dans des points peuvent être additionnés.

Encoder un point sur 32 octets

Un point est stocké de façon compacte : on écrit la coordonnée y (255 bits, petit-boutiste) et on place la parité de x dans le bit de poids fort du dernier octet. x se retrouve à partir de y grâce à l’équation de la courbe (au signe près — que donne ce bit). Ce sont ces 32 octets que vous voyez en hexadécimal quand vous regardez une clé publique Monero.

Par exemple, le point de base G s’écrit :

5866666666666666666666666666666666666666666666666666666666666666

(son y = 4/5 mod p, et x est pair).

Code

Une implémentation JavaScript minimale avec BigInt — tirée de xmrcrypto.js, utilisé par tous les outils de ce site :

const P = (1n << 255n) - 19n;
const L = (1n << 252n) + 27742317777372353535851937790883648493n;
const D = mod(-121665n * inv(121666n));

// points in extended coordinates (X:Y:Z:T), x = X/Z, y = Y/Z
function add(p, q) {
  const A = mod((p.Y - p.X) * (q.Y - q.X));
  const B = mod((p.Y + p.X) * (q.Y + q.X));
  const C = mod(2n * D * p.T * q.T);
  const Dd = mod(2n * p.Z * q.Z);
  const E = B - A, F = Dd - C, G = Dd + C, H = B + A;
  return { X: mod(E * F), Y: mod(G * H), Z: mod(F * G), T: mod(E * H) };
}

// scalar multiplication: double-and-add
function mul(k, p) {
  let r = ZERO, q = p;
  while (k > 0n) { if (k & 1n) r = add(r, q); q = add(q, q); k >>= 1n; }
  return r;
}