Кривая Ed25519

Скаляры, точки и одна операция, на которой держится весь Monero

Зачем нужна кривая

Нам нужна «односторонняя функция с замочком»: из секрета легко получить что-то публичное, а обратно — нет. Причём такая, чтобы над публичными штуками можно было делать арифметику: складывать их и умножать на числа. Эллиптическая кривая даёт ровно это.

Monero использует ту же кривую, что и подписи Ed25519 (Daniel J. Bernstein и др.): скрученную кривую Эдвардса

Точка — это пара чисел (x, y), удовлетворяющая уравнению. Все вычисления идут по модулю простого p, поэтому «кривая» на самом деле — облако из примерно 2²⁵⁵ дискретных точек.

Сложение точек

Для точек определено сложение: P + Q = R, где R — тоже точка кривой. На кривых Эдвардса формула единая для всех случаев (это удобно и безопасно):

Сложение ведёт себя как обычное: оно коммутативно, ассоциативно, есть «ноль» — точка (0, 1) — и у каждой точки есть противоположная (−x, y).

Умножение на число

Умножить точку на число x — значит сложить её саму с собой x раз. Конечно, никто не складывает 2²⁵² раз: используется метод «удвоения и сложения», которому нужно всего ~256 удвоений и ~128 сложений.

Базовая точка G и порядок l

Все используют одну и ту же заранее выбранную базовую точку G. Если умножать G на 1, 2, 3, … то через l шагов вернёшься в ноль:

Число l — порядок подгруппы, порождённой G. Всего точек на кривой в 8 раз больше (8·l); число 8 называется кофактором. Этот кофактор — источник нескольких тонких мест в Monero: например, в формулах одноразовых адресов вы увидите множитель 8, а в 2017 году через «точки малого порядка» можно было бы создать несколько key image для одного выхода (исправлено проверкой l·I = 0).

Почему это работает для ключей

Возьмём случайный x — это приватный ключ. Вычислим P = x·G — это публичный ключ. Публиковать P безопасно. А главное — с точками можно делать алгебру:

Второе равенство — основа обмена ключами Диффи–Хеллмана: Алиса знает a и видит B = b·G, Боб знает b и видит A = a·G. Оба могут вычислить одну и ту же точку a·B = b·A = ab·G, а посторонний — нет. На этом построены одноразовые адреса.

Первое равенство — основа обязательств Педерсена: суммы, спрятанные в точках, можно складывать.

Кодирование точки в 32 байта

Точку хранят компактно: записывают координату y (255 бит, little-endian), а в старший бит последнего байта кладут чётность x. По y координата x восстанавливается из уравнения кривой (с точностью до знака — его и задаёт бит). Именно эти 32 байта вы видите в hex, когда смотрите на публичный ключ Monero.

Например, базовая точка G записывается так:

5866666666666666666666666666666666666666666666666666666666666666

(у неё y = 4/5 mod p, а x чётный).

Код

Минимальная реализация на JavaScript с BigInt — из файла xmrcrypto.js, которым пользуются все инструменты сайта:

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

// точки в расширенных координатах (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) };
}

// умножение на скаляр: удвоение и сложение
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;
}