Эллиптические кривые: математика

Зачем это нужно в блокчейне

Bitcoin и Ethereum используют эллиптическую кривую secp256k1 для подписей. Ваш приватный ключ — это число d. Публичный ключ — это точка Q = d*G на кривой. Почему нельзя из Q вычислить d? Разберемся.

Каждая транзакция, которую вы отправляете, подписана вашим приватным ключом через операции на эллиптической кривой. Каждый узел сети проверяет эту подпись с помощью вашего публичного ключа. Это фундамент безопасности блокчейна.

Эллиптические кривые — не эллипсы! Название исторически связано с вычислением длины дуги эллипса, где эти кривые впервые возникли.

Кривая над вещественными числами

Эллиптическая кривая определяется уравнением:

y^2 = x^3 + ax + b

Измените параметры a и b, чтобы увидеть, как меняется форма кривой:

Ключевые свойства

• Кривая симметрична относительно оси x (если (x, y) на кривой, то и (x, -y) на кривой)
• Дискриминант 4a^3 + 27b^2 != 0 гарантирует отсутствие самопересечений и острых точек
• Форма кривой зависит от параметров: при a = 0, b = 7 получаем кривую secp256k1

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

Главная операция на эллиптической кривой — сложение точек. Это геометрическая конструкция:

Алгоритм сложения P + Q

1. Проводим прямую через точки P и Q
2. Находим третью точку пересечения прямой с кривой — R’
3. Отражаем R’ через ось x — получаем R = P + Q

Формулы для вычисления

Если P = (x_1, y_1) и Q = (x_2, y_2), где P != Q:

lambda = (y_2 - y_1) / (x_2 - x_1)
x_3 = lambda^2 - x_1 - x_2
y_3 = lambda * (x_1 - x_3) - y_1

Для удвоения точки (P + P):

lambda = (3 * x_1^2 + a) / (2 * y_1)
x_3 = lambda^2 - 2 * x_1
y_3 = lambda * (x_1 - x_3) - y_1

Скалярное умножение

Повторное сложение точки с самой собой — это скалярное умножение:

nP = P + P + … + P (n раз)

Алгоритм double-and-add

Наивное сложение P n раз — O(n) операций. Для n ~ 2^256 это невозможно. Алгоритм double-and-add работает за O(log n) = 256 шагов:

def scalar_multiply(n: int, P: tuple, a: int, p: int) -> tuple:
    """nP через double-and-add (аналог square-and-multiply)."""
    result = None  # точка на бесконечности (нейтральный элемент)
    current = P
    while n > 0:
        if n & 1:  # если текущий бит = 1
            result = point_add(result, current, a, p)
        current = point_add(current, current, a, p)  # удвоение
        n >>= 1
    return result

Это аналог алгоритма быстрого возведения в степень из урока о модульной арифметике.

Код на Python

ECPoint: класс для работы с точками на кривой

class ECPoint:
    """Точка на эллиптической кривой y^2 = x^3 + ax + b над вещественными числами."""

    def __init__(self, x, y, a, b):
        self.x = x
        self.y = y
        self.a = a
        self.b = b
        # Точка на бесконечности
        if x is None and y is None:
            return
        # Проверяем, что точка на кривой
        assert abs(y**2 - (x**3 + a*x + b)) < 1e-10, \
            f"Точка ({x}, {y}) не на кривой y^2 = x^3 + {a}x + {b}"

    def __add__(self, other):
        # Точка на бесконечности — нейтральный элемент
        if self.x is None:
            return other
        if other.x is None:
            return self

        # P + (-P) = O (точка на бесконечности)
        if self.x == other.x and abs(self.y + other.y) < 1e-10:
            return ECPoint(None, None, self.a, self.b)

        # Вычисляем наклон
        if abs(self.x - other.x) < 1e-10:
            # Удвоение: P + P
            lam = (3 * self.x**2 + self.a) / (2 * self.y)
        else:
            # Сложение: P + Q
            lam = (other.y - self.y) / (other.x - self.x)

        x3 = lam**2 - self.x - other.x
        y3 = lam * (self.x - x3) - self.y
        return ECPoint(x3, y3, self.a, self.b)

    def __repr__(self):
        if self.x is None:
            return "O (бесконечность)"
        return f"({self.x:.4f}, {self.y:.4f})"

# Пример: кривая y^2 = x^3 - 3x + 5
P = ECPoint(-1, 7**0.5, -3, 5)
Q = ECPoint(1, 3**0.5, -3, 5)
R = P + Q
print(f"P = {P}")
print(f"Q = {Q}")
print(f"P + Q = {R}")

ECPointGF: точки над конечным полем GF(p)

Вспомните конечные поля GF(p) из урока 2. Те же формулы, но все операции выполняются по модулю простого числа p:

class ECPointGF:
    """Точка на эллиптической кривой над GF(p)."""

    def __init__(self, x, y, a, b, p):
        self.x = x
        self.y = y
        self.a = a
        self.b = b
        self.p = p
        if x is not None:
            assert (y * y) % p == (x**3 + a * x + b) % p

    def __add__(self, other):
        if self.x is None:
            return other
        if other.x is None:
            return self

        if self.x == other.x and (self.y + other.y) % self.p == 0:
            return ECPointGF(None, None, self.a, self.b, self.p)

        if self.x == other.x and self.y == other.y:
            lam = (3 * self.x**2 + self.a) * pow(2 * self.y, -1, self.p) % self.p
        else:
            lam = (other.y - self.y) * pow(other.x - self.x, -1, self.p) % self.p

        x3 = (lam**2 - self.x - other.x) % self.p
        y3 = (lam * (self.x - x3) - self.y) % self.p
        return ECPointGF(x3, y3, self.a, self.b, self.p)

    def __repr__(self):
        if self.x is None:
            return "O"
        return f"({self.x}, {self.y})"

# Пример: y^2 = x^3 + 7 mod 23 (маленький secp256k1)
P = ECPointGF(7, 11, 0, 7, 23)  # точка на кривой
Q = P + P  # удвоение
print(f"P = {P}")
print(f"2P = {Q}")

Переход к конечным полям

В криптографии мы работаем не над вещественными числами, а над конечными полями GF(p). Визуально это выглядит совершенно по-другому:

Вспомните конечные поля GF(p) из урока 2. Те же правила сложения точек работают, но:

• Координаты — целые числа от 0 до p-1
• Деление заменяется на умножение на обратный элемент (mod p)
• Визуально точки «разбросаны» по полю без видимой структуры

Важно: несмотря на хаотичный вид, алгебраическая структура сохраняется. Сложение точек, скалярное умножение и все свойства группы работают точно так же.

ECDLP: почему это безопасно

Задача дискретного логарифма на эллиптических кривых (ECDLP):

Дано: точка P (генератор) и точка Q = nP (публичный ключ) Найти: число n (приватный ключ)

Почему ECDLP сложна

• Прямое вычисление (nP из n и P): 256 шагов (double-and-add)
• Обратное вычисление (n из P и nP): ~2^128 операций (лучший алгоритм — Pollard’s rho)

Это аналог: вы видите, где оказалась точка после n «прыжков» по кривой, но не можете отмотать назад, потому что каждый прыжок непредсказуемо меняет положение.

Связь с приватным/публичным ключом

В Bitcoin и Ethereum:

• Приватный ключ d — случайное 256-битное число
• Публичный ключ Q = d * G, где G — фиксированная точка генератор
• Безопасность: зная Q и G, найти d невозможно за разумное время

Математический уровень

Точка на бесконечности (Identity)

Точка на бесконечности O — нейтральный элемент группы:

• P + O = P для любой точки P
• P + (-P) = O, где -P = (x, -y)

Групповой закон

Множество точек эллиптической кривой вместе с операцией сложения образует абелеву группу:

• Замкнутость: P + Q — снова точка на кривой
• Ассоциативность: (P + Q) + R = P + (Q + R)
• Нейтральный элемент: O
• Обратный элемент: для каждого P существует -P
• Коммутативность: P + Q = Q + P

Порядок кривой

Количество точек на кривой (включая O) называется порядком и обозначается #E(F_p). По теореме Хассе: p + 1 - 2sqrt(p) ≤ #E(F_p) ≤ p + 1 + 2sqrt(p).

Для криптографии важно, чтобы порядок был почти простым (или содержал большой простой делитель).

Практика

Откройте Jupyter notebook 06-elliptic-curves.ipynb для практических упражнений:

• Реализация ECPoint и ECPointGF классов
• Визуализация точек кривой над GF(p)
• Генерация ключей с ecdsa library
• Ручное скалярное умножение
• Челлендж: алгоритм baby-step giant-step для малых ECDLP

Что дальше

Мы разобрали общую математику эллиптических кривых. Теперь перейдем к конкретным кривым, которые используются в блокчейнах: secp256k1 (Bitcoin, Ethereum) и Ed25519 (Solana). Узнаем, чем они отличаются и почему были выбраны.