La curva Ed25519

Scalari, punti e l'unica operazione su cui si regge tutto Monero

Perché una curva

Ci serve una "funzione a senso unico con un lucchetto": da un segreto è facile ottenere qualcosa di pubblico, ma non tornare indietro. E vogliamo fare aritmetica sulle cose pubbliche: sommarle e moltiplicarle per dei numeri. Una curva ellittica offre esattamente questo.

Monero usa la stessa curva delle firme Ed25519 (Daniel J. Bernstein e altri): una curva di Edwards twisted

Un punto è una coppia di numeri (x, y) che soddisfa l'equazione. Tutti i calcoli sono modulo il numero primo p, quindi la "curva" è in realtà una nuvola di circa 2²⁵⁵ punti discreti.

Sommare punti

I punti si possono sommare: P + Q = R, dove anche R sta sulla curva. Sulle curve di Edwards un'unica formula copre tutti i casi (comodo e sicuro):

Questa addizione si comporta come quella ordinaria: è commutativa e associativa, esiste uno "zero" (il punto (0, 1)) e ogni punto ha un opposto (−x, y).

Moltiplicare per un numero

Moltiplicare un punto per x significa sommarlo a sé stesso x volte. Ovviamente nessuno fa 2²⁵² addizioni: il metodo "double-and-add" (raddoppia e somma) richiede solo ~256 raddoppi e ~128 addizioni.

Il punto base G e l'ordine l

Tutti usano lo stesso punto base G, concordato in anticipo. Moltiplica G per 1, 2, 3, … e dopo l passi torni a zero:

l è l'ordine del sottogruppo generato da G. In totale la curva ha 8 volte tanti punti (8·l); 8 si chiama cofattore. Questo cofattore è all'origine di diverse sottigliezze in Monero: vedrai un fattore 8 nelle formule degli indirizzi monouso e, nel 2017, i "punti di ordine piccolo" avrebbero potuto produrre più key image per lo stesso output (corretto verificando che l·I = 0).

Perché funziona per le chiavi

Prendi un x casuale: è una chiave privata. Calcola P = x·G: è una chiave pubblica. Pubblicare P è sicuro. Fondamentale: i punti supportano l'algebra:

La seconda identità è la base dello scambio di chiavi Diffie–Hellman: Alice conosce a e vede B = b·G; Bob conosce b e vede A = a·G. Entrambi possono calcolare lo stesso punto a·B = b·A = ab·G, ma un estraneo no. Su questo si basano gli indirizzi monouso.

La prima identità è la base dei commitment di Pedersen: gli importi nascosti nei punti si possono sommare.

Codificare un punto in 32 byte

Un punto si memorizza in forma compatta: si scrive la coordinata y (255 bit, little-endian) e si mette la parità di x nel bit più alto dell'ultimo byte. x si ricava da y tramite l'equazione della curva (a meno del segno, che è dato da quel bit). Sono questi i 32 byte che vedi in esadecimale quando guardi una chiave pubblica Monero.

Per esempio, il punto base G si scrive così:

5866666666666666666666666666666666666666666666666666666666666666

(la sua y = 4/5 mod p, e x è pari).

Codice

Un'implementazione JavaScript minimale con BigInt, presa da xmrcrypto.js e usata da tutti gli strumenti di questo sito:

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