La curva Ed25519

Escalares, puntos y la única operación sobre la que descansa todo Monero

Por qué una curva

Necesitamos una «función de un solo sentido con candado»: a partir de un secreto es fácil obtener algo público, pero no al revés. Y queremos hacer aritmética con las cosas públicas: sumarlas y multiplicarlas por números. Una curva elíptica nos da exactamente eso.

Monero usa la misma curva que las firmas Ed25519 (Daniel J. Bernstein y otros): una curva de Edwards torcida

Un punto es un par de números (x, y) que cumple la ecuación. Todos los cálculos son módulo el primo p, así que la «curva» es en realidad una nube de unos 2²⁵⁵ puntos discretos.

Sumar puntos

Los puntos se pueden sumar: P + Q = R, donde R también está en la curva. En las curvas de Edwards una sola fórmula cubre todos los casos (cómodo y seguro):

Esta suma se comporta como la normal: es conmutativa y asociativa, hay un «cero», el punto (0, 1), y cada punto tiene un opuesto (−x, y).

Multiplicar por un número

Multiplicar un punto por x significa sumarlo consigo mismo x veces. Por supuesto, nadie suma 2²⁵² veces: el método «duplicar y sumar» (double-and-add) solo necesita ~256 duplicaciones y ~128 sumas.

El punto base G y el orden l

Todo el mundo usa el mismo punto base G, acordado de antemano. Multiplica G por 1, 2, 3, … y tras l pasos vuelves al cero:

l es el orden del subgrupo generado por G. La curva tiene en total 8 veces más puntos (8·l); a ese 8 se le llama cofactor. Este cofactor es el origen de varias sutilezas en Monero: verás un factor 8 en las fórmulas de las direcciones de un solo uso, y en 2017 los «puntos de orden pequeño» podían haber producido varias key images para una misma salida (se corrigió comprobando l·I = 0).

Por qué esto sirve para claves

Toma un x aleatorio: es una clave privada. Calcula P = x·G: es una clave pública. Publicar P es seguro. Y lo fundamental: los puntos admiten álgebra:

La segunda identidad es la base del intercambio de claves Diffie–Hellman: Alice conoce a y ve B = b·G; Bob conoce b y ve A = a·G. Ambos pueden calcular el mismo punto a·B = b·A = ab·G, pero un tercero no. Sobre esto se construyen las direcciones de un solo uso.

La primera identidad es la base de los compromisos de Pedersen: los importes ocultos en puntos se pueden sumar.

Codificar un punto en 32 bytes

Un punto se guarda de forma compacta: se escribe la coordenada y (255 bits, little-endian) y se pone la paridad de x en el bit más alto del último byte. x se recupera a partir de y mediante la ecuación de la curva (salvo el signo, que da ese bit). Estos son los 32 bytes que ves en hexadecimal cuando miras una clave pública de Monero.

Por ejemplo, el punto base G se escribe así:

5866666666666666666666666666666666666666666666666666666666666666

(su y = 4/5 mod p, y x es par).

Código

Una implementación mínima en JavaScript con BigInt, sacada de xmrcrypto.js, que usan todas las herramientas de este sitio:

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