Эллиптические кривые: secp256k1 и ed25519

Идея открытого ключа у нас есть, но RSA дорог и громоздок. Блокчейн стоит на другой математике, эллиптической. При стойкости RSA-3072 ключ здесь всего 256 бит. Разберём, что такое точки на кривой и их сложение, что такое скалярное умножение и почему обратить его (задача дискретного логарифма) невозможно. На этом стоят все адреса Bitcoin, Ethereum и Solana.

Идея

Эллиптическая кривая в криптографии это уравнение y² = x³ + ax + b, но не над вещественными числами, а над конечным полем: координаты это остатки по большому простому модулю p. Точек на такой кривой конечное число, и они образуют решётку, а не гладкую линию.

Главное чудо: на точках кривой определена операция, которую называют сложением. Складывая две точки, получаешь третью, тоже на кривой. У этого сложения есть нейтральный элемент (особая точка на бесконечности O, аналог нуля), есть обратные элементы, оно ассоциативно. То есть точки кривой это математическая группа, и именно из этой структуры вырастает вся криптография.

Сложение и удвоение точек

Над вещественными числами сложение точек наглядно, метод «хорда и касательная». Чтобы сложить P и Q, проводишь через них прямую, она пересекает кривую в третьей точке, и её отражение по горизонтали и есть P + Q. Если складываешь точку саму с собой (P + P, удвоение), прямая это касательная в P. Если прямая вертикальна, результат это O, точка на бесконечности.

Над конечным полем картинки нет, но формулы те же, только всё считается по модулю p. Для разных точек наклон прямой λ = (y₂ − y₁) / (x₂ − x₁), для удвоения λ = (3x₁² + a) / (2y₁). Деление здесь это умножение на обратный по модулю, тот самый, что ты считал расширенным Евклидом в уроке про RSA. Дальше x₃ = λ² − x₁ − x₂ и y₃ = λ(x₁ − x₃) − y₁.

Скалярное умножение и дискретный логарифм

Теперь главная операция. Скалярное умножение kP это сложить точку P саму с собой k раз. Наивно это k сложений, но как и с возведением в степень в RSA, есть приём «удвой и прибавь» за log k шагов: для k = 13 = 1101₂ хватает нескольких удвоений и сложений.

И вот лазейка. Посчитать Q = kP из k легко. А обратно, зная P и Q, найти k это задача дискретного логарифма на кривой (ECDLP), и для правильной кривой над полем размером около 2²⁵⁶ она неразрешима за разумное время. Это и есть односторонняя функция с лазейкой, аналог факторизации в RSA, но куда более выгодный по размеру ключа.

Отсюда схема ключей. Берётся фиксированная публичная точка G (генератор). Закрытый ключ это случайный скаляр k. Открытый ключ это точка Q = kG. Опубликовать Q безопасно: вычислить из неё k означало бы решить ECDLP.

Соберём кривую руками на маленьком поле, чтобы скалярное умножение было видно числами:

const P: i64 = 17; // модуль поля (учебный, в проде это число под 2^256)
const A: i64 = 2;

fn modp(x: i64) -> i64 {
    ((x % P) + P) % P
}

/// Обратный по модулю через малую теорему Ферма: a^(P-2) mod P (P простое).
fn inv(a: i64) -> i64 {
    let (mut result, mut base, mut exp) = (1i64, modp(a), P - 2);
    while exp > 0 {
        if exp & 1 == 1 {
            result = modp(result * base);
        }
        base = modp(base * base);
        exp >>= 1;
    }
    result
}

type Point = Option<(i64, i64)>; // None это точка на бесконечности O

fn add(p1: Point, p2: Point) -> Point {
    match (p1, p2) {
        (None, q) | (q, None) => q,
        (Some((x1, y1)), Some((x2, y2))) => {
            if x1 == x2 && modp(y1 + y2) == 0 {
                return None; // P + (-P) = O
            }
            let lambda = if x1 == x2 && y1 == y2 {
                modp((3 * x1 * x1 + A) * inv(2 * y1)) // касательная: удвоение
            } else {
                modp((y2 - y1) * inv(x2 - x1)) // хорда: сложение разных точек
            };
            let x3 = modp(lambda * lambda - x1 - x2);
            let y3 = modp(lambda * (x1 - x3) - y1);
            Some((x3, y3))
        }
    }
}

/// kG методом «удвой и прибавь».
fn scalar_mul(mut k: u64, point: Point) -> Point {
    let mut result = None;
    let mut addend = point;
    while k > 0 {
        if k & 1 == 1 {
            result = add(result, addend);
        }
        addend = add(addend, addend);
        k >>= 1;
    }
    result
}

fn main() {
    let g = Some((5i64, 1i64)); // генератор кривой y² = x³ + 2x + 2 над F_17
    for k in 1..=6 {
        println!("{k}G = {:?}", scalar_mul(k, g));
    }
}

Покрути ту же кривую вживую: двигай k и смотри, как kG прыгает по решётке без всякого порядка. В этой непредсказуемости и спрятана трудность дискретного логарифма.

ECDH: общий ключ из ничего

Теперь решим задачу, на которой споткнулась симметрия, обмен ключами по открытому каналу. ECDH работает так. У Алисы секрет a и открытая точка A = aG, у Боба секрет b и B = bG. Они обмениваются A и B по открытому каналу. Теперь Алиса считает a·B = a·(bG) = abG, а Боб считает b·A = b·(aG) = abG. У обоих одна и та же точка abG, это и есть общий секрет, из которого выводят симметричный ключ.

Подслушивающий видит G, aG, bG, но чтобы получить abG, ему нужно вытащить a или b, а это ECDLP. Общий ключ родился прямо в открытом канале, и никто его не передавал.

fn ecdh_demo() {
    let g = Some((5i64, 1i64));
    let (a, b) = (7u64, 11u64); // секреты Алисы и Боба

    let pub_a = scalar_mul(a, g); // Алиса публикует
    let pub_b = scalar_mul(b, g); // Боб публикует

    let shared_a = scalar_mul(a, pub_b); // a·(bG)
    let shared_b = scalar_mul(b, pub_a); // b·(aG)

    assert_eq!(shared_a, shared_b); // одна и та же точка abG
}

Тот же протокол на настоящей кривой secp256k1 это несколько строк с крейтом k256, вся опасная арифметика спрятана внутри:

// Cargo.toml:
// k256 = { version = "0.13", features = ["ecdh"] }
// rand_core = { version = "0.6", features = ["getrandom"] }
use k256::ecdh::EphemeralSecret;
use k256::PublicKey;
use rand_core::OsRng;

fn main() {
    // Каждая сторона генерирует секретный скаляр и публикует свою точку.
    let alice_secret = EphemeralSecret::random(&mut OsRng);
    let alice_public = PublicKey::from(&alice_secret);

    let bob_secret = EphemeralSecret::random(&mut OsRng);
    let bob_public = PublicKey::from(&bob_secret);

    // Каждый умножает чужую точку на свой секрет: с обеих сторон выходит abG.
    let alice_shared = alice_secret.diffie_hellman(&bob_public);
    let bob_shared = bob_secret.diffie_hellman(&alice_public);

    assert_eq!(
        alice_shared.raw_secret_bytes(),
        bob_shared.raw_secret_bytes()
    );
    // В бою из общего секрета выводят симметричный ключ через KDF,
    // а не берут координату точки как есть.
}