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

В 1985 году Виктор Миллер и Нил Коблиц независимо друг от друга предложили использовать для схем с открытым ключом не мультипликативную группу конечного поля, а группу точек эллиптической кривой ^{1 2}. Идея оказалась на редкость удачной: та же стойкость достигается ключами в десять — двенадцать раз короче, а сами операции складываются из обычной модульной арифметики. Сегодня на эллиптических кривых стоит почти вся защищённая связь: TLS, SSH, мессенджеры, банковские приложения, электронные подписи и блокчейны.

Причина кроется в том, что в группе точек кривой нет известного алгоритма дискретного логарифмирования быстрее «универсального», требующего около √n операций. Для поля GF(p)* работают решето числового поля и индексный метод, которые используют гладкость чисел; для «общей» эллиптической группы такого понятия нет, и все известные алгоритмы упираются в √n. Отсюда и выигрыш: 256-битная кривая даёт те же 128 бит стойкости, что и 3072-битный RSA.

Вторая половина темы — про то, как это ломается. Математика эллиптических кривых прочна, а вот реализации — нет. Повтор одноразового числа в ECDSA выдаёт закрытый ключ из двух подписей; формулы сложения не содержат коэффициента b, и сервер, не проверяющий входную точку, послушно считает скалярное произведение на чужой кривой; ветвление по битам секрета утекает по времени. История знает и Sony PlayStation 3, и биткойн-кошельки на Android, потерявшие ключи именно так.

Порядок изложения такой: сначала кривая как группа и её геометрия, затем числовой пример на малой кривой и скалярное умножение с лестницей Монтгомери, потом задача ECDLP и выбор стандартных кривых, затем протоколы — ECDH, ECDSA, EdDSA, — и, наконец, ошибки реализации и сравнение с RSA.

Паспорт темы. Нужно знать: темы 4, 11. Освоите: складывать точки и объяснять группу кривой; выполнять ECDH и подписывать ECDSA и EdDSA; оценивать ECDLP и выбирать кривую; восстанавливать ключ при повторе nonce; защищаться от invalid curve. Проверяет: ЛР 13. Минимум: разделы 1–4. Углубление: разделы 5–6.

Кривая как группа

Уравнение и точки

Эллиптическая кривая в форме Вейерштрасса над полем K (характеристики не 2 и не 3) задаётся уравнением y² = x³ + a·x + b, где a, b ∈ K и 4a³ + 27b² ≠ 0. Условие на дискриминант означает, что кривая гладкая: у неё нет точек возврата и самопересечений, а значит, в каждой точке можно провести касательную. Именно гладкость обеспечивает групповой закон.

Над вещественными числами множество решений — знакомая кривая, симметричная относительно оси абсцисс. Над конечным полем GF(p) «кривая» превращается в конечный набор пар (x, y) с 0 ≤ x, y < p, удовлетворяющих уравнению, плюс одна особая точка. Никакой геометрии в привычном смысле там нет, но алгебраические формулы сложения остаются теми же, и этого достаточно.

Полезно сразу привыкнуть к масштабу: у кривой над 256-битным полем примерно 2^256 точек. Перебрать их нельзя, хранить нельзя, а работать с ними — можно, потому что все операции локальны.

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

Закон сложения определяется геометрически: через точки P и Q проводится прямая, она пересекает кривую в третьей точке R', и сумма P + Q — это отражение R' относительно оси абсцисс. Отражение нужно, чтобы операция оказалась ассоциативной.

В координатах это выглядит так. Для P ≠ ±Q наклон секущей равен λ = (y₂ − y₁)/(x₂ − x₁), а результат — x₃ = λ² − x₁ − x₂, y₃ = λ·(x₁ − x₃) − y₁. Когда P = Q, секущая вырождается в касательную, и в числителе появляется производная правой части: λ = (3x₁² + a)/(2y₁), x₃ = λ² − 2x₁. Обе формулы собраны в одном блоке.

сложение (P ≠ ±Q):        удвоение (P = Q):
λ = (y₂ − y₁)/(x₂ − x₁)   λ = (3x₁² + a)/(2y₁)
x₃ = λ² − x₁ − x₂          x₃ = λ² − 2x₁
y₃ = λ·(x₁ − x₃) − y₁      y₃ = λ·(x₁ − x₃) − y₁

Деление — это умножение на обратный элемент по модулю p. Каждое сложение требует одной инверсии; в реальных реализациях переходят в проективные координаты, где инверсия нужна только один раз в конце, а цена сложения — около десятка умножений. Инверсия в поле стоит примерно столько же, сколько возведение в степень, то есть сотни умножений, поэтому переход к проективным координатам даёт ощутимый выигрыш.

Три свойства, которые нужно проверить, чтобы убедиться, что перед нами группа: коммутативность (очевидна из симметрии формулы), существование нейтрального элемента и ассоциативность (самая мучительная; геометрически она следует из теоремы Паскаля, алгебраически проверяется прямым счётом). Лабораторная работа проверяет ассоциативность на сотнях случайных троек точек.

Удвоение и точка на бесконечности

Нейтральный элемент — точка на бесконечности O, лежащая на каждой вертикальной прямой. Формально O = (0 : 1 : 0) в проективных координатах; в коде её удобно представлять как None. Складывать с ней просто: P + O = O + P = P, и это первый случай, который разбирается в любой реализации.

Противоположная точка — отражение: −P = (x, −y). Тогда P + (−P) = O, потому что вертикальная прямая пересекает кривую ровно в этих двух точках и уходит в бесконечность. Отсюда и особый случай в формуле сложения: если x₁ = x₂ и y₁ + y₂ ≡ 0 (mod p), результат — O, а не деление на ноль.

Обратите внимание на важную деталь: коэффициент b не участвует ни в одной формуле сложения. Он задаёт, какие точки лежат на кривой, но не то, как они складываются. Через несколько разделов эта деталь станет основой атаки на недопустимую кривую.

Порядок, кофактор и теорема Хассе

Порядок точки P — наименьшее n ≥ 1, при котором n·P = O. Порядок группы #E(GF(p)) — число всех точек, включая O. По теореме Лагранжа порядок точки делит порядок группы.

Теорема Хассе ограничивает разброс числа точек: |#E(GF(p)) − (p + 1)| ≤ 2·√p. То есть точек «примерно p», и отклонение не больше 2√p. Для криптографии это удобно: порядок группы известен с точностью до узкого интервала, и его можно посчитать алгоритмом Шуфа — Элкиса — Аткина (SEA) за полиномиальное время. Без этого нельзя было бы ни выбрать кривую, ни проверить её стойкость.

Порядок группы раскладывается как #E = n·h, где n — порядок большой подгруппы, в которой и работают протоколы, а h — кофактор. Для криптографических кривых хотят h = 1 (тогда вся группа циклическая простого порядка) или, как у Curve25519, h = 8 при простом n размером около 2^252.

Простой порядок n — это требование, а не украшение. Если n раскладывается на множители, то задача дискретного логарифма распадается на подзадачи по каждой подгруппе (алгоритм Полига — Хеллмана), и стойкость определяется наибольшим простым множителем, а не длиной ключа. Кривая с 256-битным порядком, у которого старший простой множитель всего 40 бит, ломается за 2^20 операций — быстрее, чем перебор пароля.

Кривые над конечным полем: числовой пример

Перечисление точек

Чтобы увидеть группу целиком, возьмём крошечную кривую y² = x³ + 2x + 2 над GF(17).

Наивный способ перечислить точки — перебрать все p² = 289 пар (x, y). Для p = 10007 это уже сто миллионов проверок, а для настоящих кривых — невозможно. Быстрее так: сначала построить словарь «квадрат → корни» за p шагов, затем для каждого x вычислить правую часть и посмотреть, есть ли она в словаре. Сложность падает с p² до p.

def enumerate_points(curve):
    p, a, b = curve
    squares = {}
    for y in range(p):
        squares.setdefault(y * y % p, []).append(y)
    points = []
    for x in range(p):
        rhs = (x * x * x + a * x + b) % p
        for y in squares.get(rhs, ()):
            points.append((x, y))
    points.sort()
    return points

Для нашей кривой находится 18 аффинных точек, то есть #E = 19 вместе с O. Проверим теорему Хассе: |19 − 18| = 1 ≤ 2√17 ≈ 8,25. Порядок группы 19 — простое число, значит, группа циклическая и любая точка, кроме O, порождает её целиком.

Таблица кратностей

Возьмём G = (5, 1) и выпишем все кратности. Такая таблица — самый быстрый способ увидеть, что перед нами действительно циклическая группа.

 k   kG        k   kG         k   kG
 1  (5, 1)    8  (13, 7)    15  (3, 16)
 2  (6, 3)    9  (7, 6)     16  (10, 11)
 3  (10, 6)  10  (7, 11)    17  (6, 14)
 4  (3, 1)   11  (13, 10)   18  (5, 16)
 5  (9, 16)  12  (0, 11)    19  O
 6  (16, 13) 13  (16, 4)    20  (5, 1)
 7  (0, 6)   14  (9, 1)

Читать её нужно так: 19·G = O, поэтому 20·G = G, и дальше всё повторяется с периодом 19. Обратите внимание на 18·G = (5, 16) = −G — как и должно быть, 18 ≡ −1 (mod 19). Пары точек с одинаковой абсциссой — это P и −P, они дают в сумме O.

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

Считать k·P последовательным сложением — безнадёжно: для 256-битного k это 2^256 операций. Используют «удвоение и сложение» (double-and-add): заводим R = O и идём по битам k слева направо, на каждом шаге выполняя R = R + R, а если бит равен единице — ещё и R = R + P.

Стоимость — log₂ k удвоений и в среднем log₂ k / 2 сложений, то есть около 384 операций для 256-битного скаляра вместо 10^77. Это и есть причина, по которой эллиптические кривые вообще применимы на практике: скалярное умножение логарифмично по числу битов ключа.

У метода есть неприятное свойство: последовательность операций зависит от битов k. Если k — закрытый ключ, то по времени работы и по профилю энергопотребления можно восстановить его побитно (атаки Кохера и подобные). Поэтому в реальных библиотеках используют схемы с постоянным временем.

Лестница Монтгомери

Лестница Монтгомери выполняет на каждом бите одну и ту же пару операций — сложение и удвоение — независимо от значения бита. Меняются только входы, и то через условный обмен cswap, который реализуется маской и исключающим ИЛИ, без ветвления.

def cswap(swap, a, b):
    # в Python — ветвление; в реальной реализации маска и XOR:
    # mask = -swap; t = mask & (a ^ b); a ^= t; b ^= t
    return (b, a) if swap else (a, b)

# на каждом бите t скаляра k:
#   swap ^= bit;  (x2,x3) = cswap(swap, x2, x3);  (z2,z3) = cswap(swap, z2, z3)
#   swap = bit
#   A = x2+z2;  AA = A²;  B = x2−z2;  BB = B²;  E = AA−BB
#   C = x3+z3;  D = x3−z3;  DA = D·A;  CB = C·B
#   x3 = (DA+CB)²;  z3 = x1·(DA−CB)²;  x2 = AA·BB;  z2 = E·(AA+a24·E)
# в конце: cswap, затем x2 · z2^(p−2) mod p

Именно так устроен X25519: 255 итераций, на каждой — фиксированный набор умножений и сложений по модулю 2^255 − 19. Никаких ветвлений по секрету, никаких обращений к таблицам по индексу, зависящему от секрета. Цена — примерно вдвое больше операций, чем у оптимального double-and-add, и это осознанный обмен: константное время важнее скорости.

Стоит честно сказать: на Python постоянного времени добиться нельзя в принципе — интерпретатор, сборщик мусора и длинная арифметика вносят свой вклад. Учебная реализация показывает структуру алгоритма, а не обеспечивает защиту. Для настоящей работы берут cryptography, libsodium или OpenSSL.

Задача ECDLP и выбор кривых

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

Задача дискретного логарифмирования на эллиптической кривой (ECDLP) формулируется так: даны P и Q = k·P, найти k. Для 256-битной кривой k лежит в интервале порядка 2^256.

Лучший универсальный алгоритм — ро-метод Полларда с параллелизацией, он требует около √n ≈ 2^128 операций. Это число астрономически велико: даже при 10^12 операций в секунду перебор займёт порядка 10^19 лет. Никакого субэкспоненциального алгоритма для общей эллиптической группы не известно, и это принципиально: индексный метод, который ломает GF(p)* за субэкспоненциальное время, опирается на понятие гладкости, а в группе точек кривой такого понятия нет.

Из этого правила есть важные исключения — и все они про неправильно выбранные кривые.

• Аномальные кривые (#E = p) ломаются за линейное время алгоритмом Смарта через p-адические числа.
• Кривые с малой степенью вложения допускают MOV-атаку: спаривание переносит задачу в GF(p^k), где работает индексный метод. Так ломаются суперсингулярные кривые.
• Кривые с гладким порядком ломаются Полигом — Хеллманом по кусочкам.
• Кривые с малым кофактором и без проверки точек ломаются атакой на недопустимую кривую, о которой ниже.

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

P-256 и вопрос о происхождении параметров

Стандартная кривая NIST P-256 (она же secp256r1, prime256v1) задаётся так ⁵:

p  = 2^256 − 2^224 + 2^192 + 2^96 − 1
a  = p − 3
b  = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
n  = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
h  = 1

Модуль p объясним: это ближайшее к 2^256 число вида 2^256 − 2^224 + 2^192 + 2^96 − 1, удобное для вычислений с точки зрения редукции. Сложнее с b и координатами G. Они не выбраны произвольно: по процедуре ANSI X9.62 они получены из затравочного значения хешированием (так называемая «проверяемо случайная» генерация, verifiably random), и проверить соответствие параметров заявленной процедуре можно, пересчитав хеш.

Проблема в другом: проверяемость здесь означает лишь воспроизводимость вычисления, а не обоснованность выбора. Затравочное значение и причина, по которой оно взято именно таким, не объяснены; кроме того, сама процедура допускает достаточно свободы, чтобы перебором затравочных значений получить кривую с нужными свойствами. Поэтому «параметры проверяемы» и «параметры заслуживают доверия» — разные утверждения, и второе из первого не следует.

Бернстайн и Ланге посвятили этому проект SafeCurves и подробный разбор ⁹, а в отдельной работе показали, как именно параметры кривых можно подбирать в интересах атакующего ¹⁴. Их аргумент не в том, что P-256 точно сломана, а в том, что её происхождение нельзя обосновать так же строго, как происхождение Curve25519, где каждый параметр выбран по правилу «наименьшее подходящее». История с Dual_EC_DRBG, где в константах действительно оказался скрытый механизм, доверия не добавила.

Отсюда два лагеря. Регуляторы (NIST, FIPS, большинство корпоративных политик) требуют P-256 и P-384. Криптографы-практики всё чаще берут Curve25519 и Ed25519, у которых параметры выбраны по понятному правилу и всё поведение описано в RFC.

Curve25519

Кривая предложена Дэниелом Бернстайном в 2006 году как «быстрая и простая» ⁷. Она задаётся в форме Монтгомери v² = u³ + 486662·u² + u над полем GF(2^255 − 19); базовая точка — u = 9, порядок большой подгруппы — L = 2^252 + 27742317777372353535851937790883648493, кофактор — h = 8.

Почему именно так: 2^255 − 19 — простое число, допускающее быструю редукцию; коэффициент 486662 выбран как наименьший, при котором кривая и её скрученная форма имеют простой порядок большой подгруппы; базовая точка u = 9 — наименьшая подходящая. Все параметры объяснимы одной фразой «наименьшее подходящее», и это и есть проверяемость.

Функция X25519 описана в RFC 7748 ³. Она принимает 32-байтный скаляр и 32-байтную u-координату и возвращает 32 байта. Скаляр «зажимается» (clamping): три младших бита обнуляются (скаляр становится кратным 8), старший бит обнуляется, а бит 254 устанавливается — длина скаляра фиксируется на 255 битах.

Зажим решает сразу три задачи: убирает зависимость от малых подгрупп (скаляр кратен кофактору 8, поэтому точка порядка 2, 4 или 8 обнуляется), фиксирует длину и исключает вырожденные случаи. Кроме того, X25519 не различает точки на кривой и на её скрученной форме — это сделано намеренно, чтобы атака на недопустимую кривую не работала, а поведение не зависело от проверок.

from cryptography.hazmat.primitives.asymmetric.x25519 import (
    X25519PrivateKey, X25519PublicKey)
from cryptography.hazmat.primitives import serialization

raw = (serialization.Encoding.Raw, serialization.PublicFormat.Raw)
alice, bob = X25519PrivateKey.generate(), X25519PrivateKey.generate()
shared_a = alice.exchange(bob.public_key())
shared_b = bob.exchange(alice.public_key())
assert shared_a == shared_b

Тестовые векторы RFC 7748 стоит проверить руками: пара «скаляр, u → результат» из раздела 5.2 и обмен ключами из раздела 6.1. Студенческая реализация на Python проходит их все, но тратит около миллисекунды на вызов против микросекунд у библиотеки.

secp256k1 и ГОСТ

secp256k1 задаётся уравнением y² = x³ + 7 над другим полем: p = 2^256 − 2^32 − 977, тогда как у P-256 p = 2^256 − 2^224 + 2^192 + 2^96 − 1. Совпадает только длина координаты — 256 бит; сами поля, а значит и все вычисления, различны. Порядок группы у secp256k1 простой, кофактор равен 1. Известна тем, что её выбрал Биткойн. У неё есть инженерное преимущество: эффективный эндоморфизм позволяет ускорить скалярное умножение по методу GLV. С точки зрения стойкости она равноценна P-256; с точки зрения доверия к параметрам — та же проблема, что и у NIST-кривых, только параметры ещё проще подобрать «под себя».

В России действует ГОСТ Р 34.10-2012 ¹³, который определяет и параметры кривых (256 и 512 бит), и совсем другую схему подписи: подпись — пара (r, s), где r получается из x-координаты точки k·G, а s — из уравнения с обратным по модулю q. Схема не является ECDSA и несовместима с ней; для применения в регулируемой сфере нужны сертифицированные реализации, а не самостоятельная имплементация.

Протоколы: ECDH и подписи

ECDH

Обмен ключей Диффи — Хеллмана на кривой — прямое переложение схемы из темы 11. Алиса и Боб договариваются о кривой и базовой точке G. Каждый выбирает секретный скаляр d и публикует Q = d·G. Общий секрет — x-координата точки S = d_A · Q_B = d_A · d_B · G = d_B · Q_A.

Дальше x-координата (32 байта у X25519) не используется как ключ напрямую: из неё выводят ключи через HKDF, как в теме 10. Причина та же, что и в обычном DH: сырой общий секрет не равномерен и не привязан к контексту.

Обязательные проверки на принимаемой точке Q: она не O, лежит на кривой, и n·Q = O (то есть принадлежит подгруппе нужного порядка). Для X25519 эти проверки не нужны и вредны: зажим скаляра и отсутствие различия между кривой и скрученной формой делают атаку бессмысленной, а RFC 7748 прямо требует не отвергать «неканоничные» входы.

Требования к схемам установления ключей собраны в NIST SP 800-56A ¹²: там же описаны режимы с одноразовыми и долговременными ключами, подтверждение ключа и вывод ключевого материала. Для учебных целей достаточно запомнить: ECDH даёт общий секрет, но не аутентификацию; без подписи или сертификата он уязвим к атаке «человек посередине», разобранной в теме 11.

ECDSA

ECDSA — схема подписи, стандартизованная в FIPS 186 ⁵. Параметры: кривая, базовая точка G порядка n, хеш-функция H.

Подпись сообщения M закрытым ключом d вычисляется так: z = H(M) (берутся левые min(bitlen(n), bitlen(H)) бит), выбирается одноразовое k ∈ [1, n−1], считается R = k·G, r = R.x mod n, затем s = k⁻¹·(z + r·d) mod n. Если r или s оказались нулём, выбирается новое k. Подпись — пара (r, s).

Проверка открытым ключом Q = d·G: w = s⁻¹ mod n, u₁ = z·w mod n, u₂ = r·w mod n, X = u₁·G + u₂·Q; подпись верна, если X ≠ O и X.x mod n = r.

Корректность проверяется подстановкой: u₁·G + u₂·Q = (z·w + r·w·d)·G = w·(z + r·d)·G = k·G, потому что w = s⁻¹ = k·(z + r·d)⁻¹. Значит, X = R, и абсциссы совпадают.

Две технические детали, которые часто упускают. Первая: (r, s) кодируется в DER, и парсеры DER — отдельная поверхность атаки; именно так появились уязвимости в проверке подписей у нескольких библиотек. Вторая: подпись (r, s) и (r, n − s) обе корректны, поэтому ECDSA «ковка» (malleable) — в Биткойне это лечат требованием s ≤ n/2 (low-s).

EdDSA решает обе проблемы: подпись фиксированной длины, ровно один допустимый вид.

EdDSA и детерминированный nonce

Ed25519 определена в RFC 8032 ⁴ и построена на скрученной кривой Эдвардса −x² + y² = 1 + d·x²·y² с d = −121665/121666 над GF(2^255 − 19). У неё есть полная формула сложения (работает для всех пар точек, без исключений) и эффективная операция удвоения. Ключи: 32-байтный секретный, 32-байтный открытый, подпись — 64 байта.

Главное отличие от ECDSA — детерминированное вычисление одноразового числа. Секретный ключ расширяется хешем: h = SHA-512(seed), из первых 32 байт получается скаляр a, из вторых — префикс. Затем r = SHA-512(prefix ‖ M) mod L, R = r·B, S = (r + SHA-512(R ‖ A ‖ M)·a) mod L, подпись — (R, S).

Одноразовое число r — функция сообщения и секретного префикса. Оно никогда не повторяется для разных сообщений (если не повторяется сообщение) и не зависит от генератора случайных чисел. Именно поэтому утечка через повтор nonce, погубившая PS3 и Android-кошельки, для Ed25519 невозможна by design.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

key = ec.generate_private_key(ec.SECP256R1())
sig = key.sign(b"document", ec.ECDSA(hashes.SHA256()))
key.public_key().verify(sig, b"document", ec.ECDSA(hashes.SHA256()))

sk = bytes.fromhex("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60")
ed = Ed25519PrivateKey.from_private_bytes(sk)
assert ed.sign(b"") == ed.sign(b"")                        # детерминированно
assert ed.sign(b"").hex().startswith("e5564300c360ac72")   # вектор RFC 8032, TEST 1

Детерминированность — не только защита, но и удобство: подпись воспроизводима, тесты стабильны, а аудит проще. Цена — отсутствие рандомизации: если злоумышленник научится предсказывать хеш, он получит r. Поэтому seed Ed25519 должен быть по-настоящему случайным.

Для ECDSA аналог есть — RFC 6979 ¹¹, детерминированный k через HMAC-DRBG от закрытого ключа и сообщения. Это не делает ECDSA детерминированной схемой в смысле EdDSA (проверка всё равно принимает любую корректную пару), но убирает зависимость от качества RNG. Многие библиотеки, включая OpenSSL и cryptography, используют RFC 6979 по умолчанию.

Ошибки реализации

Повтор одноразового числа

Пусть один и тот же k использован для двух сообщений M_1 и M_2 с хешами z_1, z_2. Тогда r у подписей совпадает, а s_1 = k^{-1}(z_1 + r \cdot d) и s_2 = k^{-1}(z_2 + r \cdot d). Вычтем второе из первого и получим k, а из него — закрытый ключ d:

s_1 - s_2 = k^{-1} (z_1 - z_2) \implies k = (z_1 - z_2)(s_1 - s_2)^{-1} \pmod n

d = (s_1 k - z_1) r^{-1} \pmod n

Всё. Двух подписей достаточно, чтобы полностью восстановить ключ и подписывать что угодно от имени жертвы. Никакого перебора, никакой криптоаналитической сложности — только модульная арифметика.

Проверим на учебной кривой из этой темы. Параметры: n = 19, G = (5, 1), ключ d = 7, Q = 7G = (0, 6). Подпишем два «сообщения» с хешами z₁ = 4 и z₂ = 9 одним k = 3. Тогда kG = 3G = (10, 6), значит r = 10; s₁ = 3⁻¹·(4 + 10·7) = 13·74 ≡ 12 (mod 19) и s₂ = 3⁻¹·(9 + 10·7) = 13·79 ≡ 1 (mod 19). Восстановление: k = (4 − 9)·(12 − 1)⁻¹ = (−5)·7 ≡ 3, d = (12·3 − 4)·10⁻¹ = 32·2 ≡ 7. Исходный ключ d = 7 получен. На настоящей 256-битной кривой формулы те же, только числа длиннее.

История вопроса поучительна. В 2010 году группа fail0verflow обнаружила, что Sony использовала в подписи прошивки PlayStation 3 постоянное k. Консоль проверяла подпись корректно, кривая была настоящая, а закрытый ключ Sony оказался восстановлен и опубликован. В 2013 году похожая история произошла с Android-кошельками для Биткойна: дефект SecureRandom приводил к повторам k, и ключи уводили с кошельков. В обоих случаях алгоритм был исправен, а генератор — нет.

Хуже того, k не обязан повторяться целиком. Если он лишь немного смещён — скажем, старшие биты фиксированы, — задача восстановления ключа превращается в задачу о скрытом числе и решается решёткой (LLL). Работа Брайтнера и Хенингера показала, что такое смещение реально встречается в блокчейн-подписях и позволяет восстанавливать ключи массово ¹⁰. Отсюда вывод: k должен быть либо полноценно случайным, либо детерминированным по RFC 6979. «Почти случайный» — негоден.

Атака на недопустимую кривую

Вернёмся к детали из первого раздела: формулы сложения не содержат b. Значит, если сервер получает точку и просто умножает её на секретный скаляр d, он посчитает d·Q корректно по формулам — но эта точка может лежать не на той кривой, о которой договаривались.

Атака, описанная Билем, Мейером и Мюллером ⁸, выглядит так:

1. Атакующий выбирает b' ≠ b и берёт кривую y² = x³ + a·x + b' с тем же a.
2. Считает число точек N' этой кривой и находит у него малый простой делитель q.
3. Находит точку Q порядка q на «чужой» кривой.
4. Отправляет Q серверу и получает R = d·Q.
5. Перебирает t ∈ [0, q) и находит такое, что t·Q = R. Это d mod q.
6. Повторяет для нескольких q, пока произведение не превысит порядок группы, и собирает d по китайской теореме об остатках.

Каждый запрос даёт остаток по модулю q, а перебор внутри q дешёвый — q специально выбирается маленьким. Число запросов логарифмически зависит от размера d.

На учебной кривой лабораторной работы (p = 10007, a = 3, b = 6, N = 10039) хватает пяти запросов: остатки по модулям 3, 5, 7, 41, 71 дают произведение 305 655 > 10 039, и d восстанавливается однозначно. Защита — одна строка: проверить, что Q лежит на кривой, и отвергнуть иначе.

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

Малые подгруппы, кофактор и скрученные кривые

Даже на правильной кривой порядок группы может иметь малые множители. Если #E = n·h и h > 1, то существует точка T порядка h (или делителя h). Отправив её серверу, атакующий получает d·T, из чего узнаёт d mod h. При h = 8 это три бита; одного раза мало, но в протоколе с повторными обменами остатки накапливаются.

Лечится умножением результата на кофактор: h·(d·Q) обнуляет любую компоненту малого порядка. В X25519 это уже сделано зажимом скаляра, в протоколах на произвольных кривых кофактор нужно учитывать явно.

Отдельный сюжет — скрученные кривые (twists). У каждой кривой есть «квадратичный твист» — кривая с тем же a, но другим b, и точки твиста часто принимаются за точки исходной кривой при небрежной валидации. Если порядок твиста гладкий, атака становится ещё проще. Поэтому при выборе кривой смотрят не только на #E, но и на порядок твиста — свойство, которое SafeCurves называет twist security ⁹.

Валидация точек и сжатие

Точку можно передавать в двух видах. Несжатый — 65 байт для P-256: префикс 04 и две 32-байтные координаты. Сжатый — 33 байта: префикс 02 или 03 (чётность y) и только x. Восстановление y требует извлечения квадратного корня по модулю p; для p ≡ 3 (mod 4) работает y = (x³ + ax + b)^((p+1)/4) mod p, и остаётся выбрать нужный знак.

Сжатие экономит место, но добавляет поверхность атаки: нужно проверить, что x < p, что подкоренное выражение — квадратичный вычет, что префикс допустим. Неканоничные кодировки (например, x + p вместо x) в некоторых реализациях проходили проверку и приводили к приёму разных байтов как одной точки — а значит, к расхождению в вычислении хеша транскрипта.

Короткий чек-лист валидации для ECDH на произвольной кривой:

• точка не O;
• координаты в диапазоне [0, p−1];
• уравнение кривой выполняется;
• n·Q = O (принадлежность подгруппе порядка n);
• при h > 1 — умножение результата на h.

Для проверки подписи ECDSA добавляется: r, s ∈ [1, n−1], открытый ключ прошёл те же проверки, X ≠ O. Пропуск любого из этих пунктов — не теоретическая мелочь, а реальная уязвимость; библиотеки прошлых лет ломались именно на этом.

Сравнение с RSA

Длины ключей и подписей

Главный практический выигрыш эллиптических кривых — размер. Сравним при одинаковом уровне стойкости 128 бит (NIST SP 800-57 ⁶):

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

Обратная сторона: 256-битная кривая даёт 128 бит стойкости, то есть вдвое меньше, чем длина ключа. У RSA «запас» другой: 3072-битный модуль даёт те же 128 бит, но факторизация не имеет известного субэкспоненциального ускорения, поэтому рост длины ключа даёт больше. Парадокс: у ECC хуже «запас прочности» на бит ключа, но лучше — на байт хранилища.

Скорость

Замеры на одном ядре (openssl speed -seconds 2, OpenSSL 3.6.4, x86-64):

Подпись на кривой быстрее RSA примерно в 80 раз. Проверка, наоборот, у RSA в два раза быстрее, чем у ECDSA: у RSA проверка — это возведение в степень с малым показателем e = 65537, а у ECDSA — два скалярных умножения. Асимметрия важна при выборе: там, где подписывают часто, а проверяют редко (сервер, выдающий токены), кривые выигрывают с огромным отрывом; там, где проверяют много и часто (валидация сертификатов в браузере), выигрыш меньше, а иногда и отрицательный.

Ed25519 подписывает медленнее ECDSA (25 против 16 мкс), потому что вычисляет два хеша SHA-512, зато проверяет предсказуемо и не требует обращения к RNG.

Что выбирать

Короткие правила, которые стоит запомнить.

• Новые протоколы, свой код — X25519 для обмена ключами и Ed25519 для подписи. Просто, быстро, детерминированно, параметры проверяемы.
• Совместимость и регуляторика — P-256. Она есть везде, её требуют FIPS и большинство политик.
• Биткойн и совместимость с ним — secp256k1, но только потому, что так исторически сложилось.
• Регулируемая сфера в России — ГОСТ Р 34.10-2012 и сертифицированная реализация, не самостоятельная.
• Долгосрочная защита от квантового компьютера — ни то, ни другое: и RSA, и ECC ломаются алгоритмом Шора. Нужны постквантовые схемы (тема 16), а на переходный период — гибридные схемы, где ECDH комбинируется с ML-KEM.

И последнее. Какую бы кривую ни выбрали, нельзя писать её реализацию самому для рабочего кода. Арифметика проста ровно настолько, чтобы казаться безопасной, и ровно настолько коварна, чтобы утечь по времени, по кэшу, по ошибкам в обработке краевых случаев. Учебная реализация в этой теме нужна, чтобы понять устройство; рабочая — чтобы не изобретать её заново.

Итоги темы

Эллиптическая кривая — это множество точек, на котором определено сложение по формулам хорды и касательной. Вместе с точкой на бесконечности оно образует абелеву группу: коммутативную, ассоциативную, с нейтральным элементом O и противоположной точкой −P = (x, −y). Коэффициент b задаёт, какие точки лежат на кривой, но не участвует в сложении — и это наблюдение открывает дорогу атаке на недопустимую кривую.

Число точек группы #E лежит в узком интервале вокруг p + 1 по теореме Хассе, раскладывается как n·h и для криптографических кривых имеет простой большой множитель n и малый кофактор. Скалярное умножение выполняется за log₂ k удвоений и сложений, а лестница Монтгомери делает время работы независимым от битов секрета.

Стойкость опирается на сложность ECDLP: лучший универсальный алгоритм — ро-метод Полларда с √n операций, что даёт 128 бит для 256-битной кривой. Исключения — аномальные кривые, малая степень вложения и гладкий порядок — закрываются выбором стандартной кривой. P-256 удобна и распространена, но её параметры необъяснимы; Curve25519 и Ed25519 выбраны по проверяемым правилам и описаны в RFC.

Протоколы: ECDH даёт общий секрет из d_A·d_B·G, ECDSA — подпись (r, s) с одноразовым k, EdDSA — детерминированную подпись, где k выводится из ключа и сообщения. Именно детерминированность делает Ed25519 невосприимчивой к повтору nonce, который погубил PS3 и Android-кошельки: k = (z₁ − z₂)/(s₁ − s₂) и d = (s₁k − z₁)/r восстанавливают ключ из двух подписей за секунды.

Реализации ломаются чаще, чем математика: повтор или смещение nonce, отсутствие проверки точки, игнорирование кофактора, приём неканоничных кодировок, ветвления по секрету. Чек-лист валидации короткий, и его пропуск — не стилистическая погрешность, а уязвимость.

По сравнению с RSA кривые дают ключи и подписи в разы короче и подпись в десятки раз быстрее, но проверку — медленнее и с меньшим запасом стойкости на бит ключа. Следующая тема собирает всё это в инфраструктуру: сертификаты, удостоверяющие центры, цепочки доверия и отзыв — то, без чего открытый ключ остаётся просто числом.

Литература

1. Koblitz N. Elliptic Curve Cryptosystems. — Mathematics of Computation, 1987, Т. 48, № 177, С. 203–209. DOI: 10.1090/S0025-5718-1987-0866109-5
2. Miller V. S. Use of Elliptic Curves in Cryptography. — Advances in Cryptology — CRYPTO '85, Springer, 1986, С. 417–426. DOI: 10.1007/3-540-39799-X_31
3. Langley A., Hamburg M., Turner S. Elliptic Curves for Security. — RFC 7748, IETF, 2016. https://www.rfc-editor.org/rfc/rfc7748
4. Josefsson S., Liusvaara I. Edwards-Curve Digital Signature Algorithm (EdDSA). — RFC 8032, IETF, 2017. https://www.rfc-editor.org/rfc/rfc8032
5. NIST. Digital Signature Standard (DSS). — FIPS 186-5, 2023. DOI: 10.6028/NIST.FIPS.186-5
6. NIST. Recommendation for Key Management, Part 1: General. — SP 800-57 Part 1 Rev. 5, 2020. DOI: 10.6028/NIST.SP.800-57pt1r5
7. Bernstein D. J. Curve25519: New Diffie-Hellman Speed Records. — Public Key Cryptography — PKC 2006, Springer, 2006, С. 207–228. DOI: 10.1007/11745853_14
8. Biehl I., Meyer B., Müller V. Differential Fault Attacks on Elliptic Curve Cryptosystems. — Advances in Cryptology — CRYPTO 2000, Springer, 2000, С. 131–146. DOI: 10.1007/3-540-44598-6_8
9. Bernstein D. J., Lange T. SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography. — 2014. https://safecurves.cr.yp.to
10. Breitner J., Heninger N. Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies. — Financial Cryptography and Data Security — FC 2019, Springer, 2019, С. 3–20. DOI: 10.1007/978-3-030-32101-7_1
11. Pornin T. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). — RFC 6979, IETF, 2013. https://www.rfc-editor.org/rfc/rfc6979
12. Barker E., Chen L., Roginsky A., Vassilev A., Davis R. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. — NIST SP 800-56A Rev. 3, 2018. DOI: 10.6028/NIST.SP.800-56Ar3
13. ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. — М.: Стандартинформ, 2013.
14. Bernstein D. J., Chou T., Chuengsatiansup C., Heninger N., Lange T., van Lunteren J., Niederhagen R., Raman C., Ronen E., Sattler P. How to Manipulate Curve Standards: A White Paper for the Black Hat. — Security Standardisation Research — SSR 2014, Springer, 2014, С. 109–139. DOI: 10.1007/978-3-319-14054-4_7

Тема 13. Дополнительные материалы

Вопросы для самопроверки

1. Почему в формулах сложения нет b? Сложение определяется геометрией кривой в точке: наклон секущей и касательной зависит от a (через производную) и от координат точек, но не от свободного члена. b задаёт сдвиг кривой по вертикали, а сдвиг не меняет ни углов, ни точек пересечения прямой с кривой в этом смысле. Отсюда и атака: сервер, не проверяющий точку, считает скалярное произведение на кривой с другим b.
2. Что такое O и зачем она нужна? Точка на бесконечности — нейтральный элемент группы, пересечение всех вертикальных прямых. Без неё P + (−P) некуда положить, и группа не замыкается.
3. Как сформулировать теорему Хассе своими словами? Число точек кривой над GF(p) отличается от p + 1 не более чем на 2√p. Для p = 10007 допустимый разброс — от 10007 + 1 − 200 до 10007 + 1 + 200; наша кривая даёт 10039, отклонение 31.
4. Почему кофактор — проблема? Если #E = n·h с малым h > 1, существуют точки малого порядка. Противник присылает такую точку, получает d·T и узнаёт d mod h. Несколько обменов — несколько остатков. Лечится умножением на h или зажимом скаляра.
5. Что такое скрученная кривая? Кривая с тем же a, но другим b, получающаяся квадратичным твистом. Её точки иногда принимают за точки исходной кривой, если не проверять уравнение. Отсюда требование twist security при выборе кривой.
6. Почему 256-битная кривая даёт 128 бит стойкости? Из-за ро-метода Полларда: сложность √n = 2^128. Никакого алгоритма лучше для общей группы не известно.
7. Чем плох P-256, если её не взломали? Непроверяемостью параметров. b и G — константы неизвестного происхождения; нельзя доказать, что они не выбраны для удобства атакующего.
8. Почему ECDSA требует случайного k, а EdDSA — нет? В EdDSA r вычисляется хешем от секретного префикса и сообщения, то есть детерминированно. В ECDSA k приходит извне, и вся его случайность — на совести реализации.
9. Что не так с (r, n − s)? Обе подписи корректны, поэтому подпись «ковка»: по одной можно построить другую, не зная ключа. В блокчейнах это ломало идентификацию транзакций, поэтому ввели требование s ≤ n/2.
10. Зачем в ECDH умножать на кофактор? Чтобы обнулить компоненту малого порядка в общем секрете. Без этого противник может подмешать точку малого порядка и вытянуть остатки секрета.
11. Почему нельзя писать свою реализацию для продакшена? Ветвления и обращения к памяти по индексам, зависящим от секрета, утекают по времени и кэшу. Постоянное время — это дисциплина кодирования, а не свойство формулы.
12. Что общего у атаки на недопустимую кривую и атаки на малую подгруппу? Обе выдают d mod q для малого q, и обе собирают d по китайской теореме об остатках. Разница в том, откуда берётся точка малого порядка: с чужой кривой или из кофактора своей.
13. Почему проверка подписи у ECDSA дороже подписи? Подпись — одно скалярное умножение, проверка — два (плюс обратный элемент). У RSA наоборот: подпись — возведение в степень с большим d, проверка — с малым e = 65537.

Глоссарий темы

Шпаргалка по инструментам

OpenSSL: ключи и подписи на кривых

# ключ P-256
openssl genpkey -algorithm EC -pkeyopt ec_paramgen_curve:P-256 -out p256.pem
openssl pkey -in p256.pem -pubout -out p256.pub
openssl pkey -in p256.pem -text -noout | head -20

# ключ Ed25519
openssl genpkey -algorithm ED25519 -out ed.pem
openssl pkey -in ed.pem -pubout -out ed.pub

# подпись и проверка (Ed25519 и ECDSA одинаково)
openssl pkeyutl -sign -inkey ed.pem -rawin -in doc.txt -out doc.sig
openssl pkeyutl -verify -pubin -inkey ed.pub -rawin -in doc.txt -sigfile doc.sig

# то же через дайджест
openssl dgst -sha256 -sign p256.pem -out doc.sig doc.txt
openssl dgst -sha256 -verify p256.pub -signature doc.sig doc.txt

# список поддерживаемых кривых
openssl ecparam -list_curves | head -20

# обмен X25519
openssl genpkey -algorithm X25519 -out a.pem
openssl pkey -in a.pem -pubout -out a.pub
openssl pkeyutl -derive -inkey a.pem -peerkey b.pub -out shared.bin

Python: cryptography

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ec, x25519, ed25519
from cryptography.hazmat.primitives.asymmetric.utils import (
    decode_dss_signature, encode_dss_signature)

raw = (serialization.Encoding.Raw, serialization.PublicFormat.Raw)

# X25519
a = x25519.X25519PrivateKey.generate()
b = x25519.X25519PrivateKey.generate()
secret = a.exchange(b.public_key())

# ECDSA
k = ec.generate_private_key(ec.SECP256R1())
sig = k.sign(b"msg", ec.ECDSA(hashes.SHA256()))
r, s = decode_dss_signature(sig)
k.public_key().verify(sig, b"msg", ec.ECDSA(hashes.SHA256()))

# Ed25519
e = ed25519.Ed25519PrivateKey.generate()
esig = e.sign(b"msg")
e.public_key().verify(esig, b"msg")
print(len(esig))   # 64

Проверка чисел на глаз

Что смотреть при выборе кривой

• порядок n простой и не меньше 250 бит;
• кофактор h малый (1 или 8), и он учитывается;
• порядок скрученной кривой тоже имеет большой простой множитель;
• параметры объяснимы: либо «наименьшее подходящее», либо хеш от открытой строки;
• кривая есть в стандарте (FIPS 186, RFC 7748, RFC 8032, ГОСТ Р 34.10).

Что почитать и посмотреть

• RFC 7748 «Elliptic Curves for Security» — короткий и очень плотный документ: и X25519, и X448, псевдокод лестницы, тестовые векторы и требования к реализациям. Читать целиком, раздел 5 — построчно.
• RFC 8032 «EdDSA» — определение Ed25519 и Ed448, тестовые векторы, обоснование детерминированного nonce. Раздел 7 удобно использовать как набор тестов.
• FIPS 186-5 — стандарт подписи: ECDSA, RSA, EdDSA. Сухая формулировка, по которой можно сверять детали (например, усечение хеша).
• Bernstein D. J. «Curve25519: New Diffie-Hellman Speed Records» — исходная статья, из которой понятно, откуда взялись 486662 и u = 9.
• SafeCurves (safecurves.cr.yp.to) — таблица критериев и оценка популярных кривых. Хороший пример того, как выглядит инженерный аудит параметров.
• Biehl, Meyer, Müller «Differential Fault Attacks on Elliptic Curve Cryptosystems» — исходная работа про атаку на недопустимую кривую; читается тяжело, но полезна как первоисточник.
• Breitner, Heninger «Biased Nonce Sense» — про смещённые nonce и решётки; показывает, что «почти случайный» — это не случайный.
• RFC 6979 — детерминированный k для ECDSA; полезно сравнить с подходом EdDSA.
• SP 800-56A Rev. 3 — требования к схемам установления ключей: какие проверки обязательны, какие режимы допустимы.

Углубление (по желанию)

Спаривания и BLS. Если на кривой определено спаривание (Вейля или Тейта), можно строить схемы, которых нет в «обычной» группе: агрегацию подписей, пороговые схемы, короткие подписи BLS. Обратная сторона — MOV-атака: малое степень вложения делает ECDLP проще. Кривые для спариваний выбирают специально (например, BLS12-381), и они не годятся для ECDH.

Пороговые подписи и MPC. Закрытый ключ можно разделить между участниками так, чтобы подпись строилась совместно, а ключ ни у кого не собирался целиком. Это требует протоколов умножения по модулю n и аккуратной работы с nonce: если каждый участник выбирает свой k, суммарный nonce становится известен только в конце, и повтор исключён конструктивно.

Атаки по побочным каналам на конкретные реализации. Ветвление по битам — только начало. Есть атаки по кэшу (индексы предвычисленных таблиц), по энергопотреблению, по электромагнитному излучению, по ошибкам в вычислении (fault injection). Практический вывод один: реализация криптографии — отдельная специальность, и учебный код для этого не годится.

Квантовая угроза и гибриды. Алгоритм Шора решает и ECDLP, и факторизацию за полиномиальное время. Переходный период принято закрывать гибридными схемами: X25519 вместе с ML-KEM-768 в TLS, Ed25519 вместе с ML-DSA в подписи. Смысл — стойкость сохраняется, пока не сломан хотя бы один из компонентов. Подробнее — в теме 16.

Формальные доказательства. Модель EUF-CMA (existential unforgeability under chosen-message attack) — то, что должно выполняться для схемы подписи. ECDSA в этой модели доказывается с оговорками: нужно предполагать, что хеш ведёт себя как случайный оракул, а nonce — равномерен. EdDSA имеет более аккуратное доказательство, и это ещё один аргумент в её пользу.

Лабораторная работа 13. Эллиптические кривые: арифметика, X25519 и подпись

• Раздел курса: тема 13 «Эллиптические кривые»

Введение

Тема 13 показала, что группа точек эллиптической кривой устроена просто — сложение по формулам хорды и касательной, — но требует аккуратности в двух местах: в выборе кривой и в проверке входных данных. Лабораторная работа проходит путь от школьной арифметики по модулю 17 до настоящего X25519 и настоящей ECDSA, а заканчивается двумя атаками, которые в реальной жизни стоили Sony закрытого ключа прошивки, а владельцам Android-кошельков — биткойнов.

Работа опирается на темы 4 (модульная арифметика, обратный элемент, китайская теорема об остатках) и 12 (схемы с открытым ключом, подпись). Она готовит тему 14: сертификаты X.509 содержат открытые ключи на кривых P-256 и Ed25519, и разбирать их структуру проще, когда арифметика уже своя.

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

Цель работы

Реализовать арифметику точек над малой кривой, проверить теорему Хассе, освоить скалярное умножение и лестницу Монтгомери, выполнить обмен X25519 по RFC 7748, подписать и проверить данные через ECDSA и Ed25519, восстановить закрытый ключ по двум подписям с общим nonce и — в продвинутой части — провести атаку на недопустимую кривую.

После выполнения работы можно будет:

• реализовать сложение, удвоение, скалярное умножение и перечисление точек на Python;
• посчитать порядок группы и проверить теорему Хассе;
• объяснить, почему b не участвует в формулах сложения и чем это опасно;
• реализовать X25519 по псевдокоду RFC 7748 и сверить с тестовыми векторами;
• подписать документ через cryptography и OpenSSL и проверить подпись;
• восстановить закрытый ключ ECDSA по двум подписям с одинаковым k;
• провести атаку на недопустимую кривую и собрать ключ по китайской теореме об остатках;
• измерить и сравнить скорость RSA-3072, ECDSA P-256 и Ed25519.

Уровни работы

• Минимум (обязательно): части 1–3. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 4–5.
• Углубление (по желанию): 6 (сравнение скорости).

Теоретический минимум

Нужны разделы «Кривая как группа», «Кривые над конечным полем: числовой пример», «Протоколы: ECDH и подписи» и «Ошибки реализации».

кривая      y² = x³ + a·x + b над GF(p),  4a³ + 27b² ≠ 0
сложение    λ = (y₂−y₁)/(x₂−x₁),  x₃ = λ²−x₁−x₂,  y₃ = λ(x₁−x₃)−y₁
удвоение    λ = (3x₁²+a)/(2y₁),   x₃ = λ²−2x₁
порядок     #E = n·h,   |#E − (p+1)| ≤ 2√p   (Хассе)
ECDSA       r = (kG).x mod n,   s = k⁻¹(z + r·d) mod n
повтор k    k = (z₁−z₂)/(s₁−s₂),   d = (s₁k − z₁)/r

Перечень оснащения

• Ubuntu 24.04 (или WSL2), Python 3.10+, cryptography 3.4 или новее, OpenSSL 3.0 или новее. Права root не нужны.
• Архив окружения: lr-env.zip.

Ограничения ресурсов

Малая кривая p порядка 10^3–10^5; X25519 проверяется по вектору RFC 7748; скорость сравнивается командой openssl speed. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-13; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

Порядок выполнения работы

mkdir -p ~/lab13 && cd ~/lab13
unzip /path/to/lr-env.zip
cd lr-env
python3 check_ec.py -v
python3 check_x25519.py -v
python3 sign_template.py
python3 recover_template.py && python3 check_recover.py

Порядок важен: часть 5 использует функции из ec_template.py, поэтому без работающей части 1 она не запустится. Часть 4 формально независима, но её удобнее делать после части 3, когда уже понятно, откуда берутся r и s.

Часть 1. Арифметика точек

Задание

1. Реализуйте inv(x, p) через расширенный алгоритм Евклида или малую теорему Ферма. Встроенный pow(x, -1, p) используйте только для сверки. При x ≡ 0 (mod p) возбуждайте ZeroDivisionError.
2. Реализуйте is_on_curve, neg, add, mul, enumerate_points, point_order. В add разберите четыре случая: одна из точек O, P = −Q, P = Q, общий случай.
3. Проверьте на малой кривой y² = x³ + 2x + 2 над GF(17): 2G = (6, 3), 3G = (10, 6), 18G = (5, 16), 19G = O.
4. Перечислите точки кривой y² = x³ + 3x + 6 над GF(10007) с базовой точкой G = (0, 1973). Убедитесь, что точек 10039, и проверьте теорему Хассе.
5. Убедитесь, что 10039·G = O, и объясните, почему из этого следует, что порядок G равен 10039.

python3 check_ec.py -v

Ожидаемый вывод — двадцать три строки OK и итог «Все проверки пройдены». Проверка ассоциативности выполняется на 200 случайных тройках точек, поэтому ошибка в формуле сложения проявится почти сразу.

Что должно получиться

Работающий модуль, проходящий все проверки. В отчёте — таблица кратностей k·G для k = 1..19 на малой кривой и ответ на вопрос: почему для GF(10007) перечисление занимает доли секунды, а наивный перебор пар — нет.

Часть 2. X25519

Задание

1. Реализуйте x25519(k, u) по псевдокоду раздела 5 RFC 7748: x₁ = u, (x₂, z₂) = (1, 0), (x₃, z₃) = (u, 1), затем 255 итераций лестницы и финальное умножение на z₂^(p−2).
2. Не забудьте про decode_scalar (зажим) и decode_u (обнуление старшего бита). Эти две функции в заготовке уже написаны — разберитесь, что именно они делают и зачем.
3. Прогоните тестовые векторы RFC 7748: два вектора из раздела 5.2, итерационный тест на 1 и 1000 шагов, обмен ключами из раздела 6.1.
4. Сверьте результат с cryptography.
5. Замерьте время: сколько занимает тысяча вызовов вашей реализации и сколько — тысяча вызовов библиотечной.

python3 check_x25519.py -v

В выводе будет строка вида «1000 вызовов X25519 заняли 0,9 с» — это примерно миллисекунда на вызов. Библиотека тратит на порядки меньше, потому что работает с 64-битными словами и ассемблерными вставками.

Что должно получиться

Реализация, совпадающая с RFC на всех векторах, и понимание, почему на Python нельзя получить постоянное время.

Часть 3. Подписи ECDSA и Ed25519

Задание

1. Сгенерируйте ключи и подписи OpenSSL:

openssl genpkey -algorithm EC -pkeyopt ec_paramgen_curve:P-256 -out p256.pem
openssl pkey -in p256.pem -pubout -out p256.pub
openssl genpkey -algorithm ED25519 -out ed.pem
openssl pkey -in ed.pem -pubout -out ed.pub
printf 'Документ для подписи\n' > doc.txt
openssl pkeyutl -sign -inkey p256.pem -rawin -in doc.txt -out doc.p256.sig
openssl pkeyutl -sign -inkey ed.pem -rawin -in doc.txt -out doc.ed.sig

2. Проверьте подписи обратно:

openssl pkeyutl -verify -pubin -inkey p256.pub -rawin -in doc.txt -sigfile doc.p256.sig
openssl pkeyutl -verify -pubin -inkey ed.pub -rawin -in doc.txt -sigfile doc.ed.sig

3. Заполните sign_template.py: восстановите ключ Ed25519 из тестового вектора RFC 8032 (раздел 7.1, TEST 1), сравните открытый ключ и подпись пустого сообщения. Подпишите пустое сообщение дважды и объясните результат.
4. Сгенерируйте ключ P-256, подпишите одно сообщение дважды, разберите обе подписи через decode_dss_signature и сравните r и s. Испортите байт в сообщении и убедитесь, что verify() возбуждает InvalidSignature.
5. Загрузите p256.pub и ed.pub, проверьте подписи файлов doc.p256.sig и doc.ed.sig.

python3 sign_template.py

Что должно получиться

Две подписи ECDSA одного сообщения различаются (случайный k), две подписи Ed25519 совпадают (детерминированный r). Подписи, созданные OpenSSL, проверяются из Python, и наоборот — это и есть совместимость форматов.

Часть 4. Восстановление ключа при повторе nonce

Задание

1. Разберите nonce_reuse.json: два сообщения, две DER-подписи, открытый ключ. Убедитесь, что r₁ = r₂.
2. Вычислите z₁, z₂ как SHA-256 сообщений, приведённые к целому.
3. Вычислите k = (z₁ − z₂)·(s₁ − s₂)⁻¹ mod n и d = (s₁·k − z₁)·r⁻¹ mod n.
4. Проверьте, что d·G даёт тот же открытый ключ, что в файле.
5. Подпишите target_message восстановленным ключом и запишите подпись в forged.sig (DER), а открытый ключ — в victim_pub.pem.
6. Запустите проверку.

python3 recover_template.py && python3 check_recover.py

Ожидаемый результат: pub match: True и строка OK подпись документа «Сейф: доверенность на имя Мэллори, полные полномочия» проверяется открытым ключом жертвы. Проверка отдельно убеждается, что forged.sig не совпадает ни с одной исходной подписью, — подпись должна быть новой.

7. Сгенерируйте собственный вариант и повторите атаку на нём:

python3 gen_nonce_reuse.py --seed 42 -o my.json
python3 recover_template.py my.json && python3 check_recover.py my.json

Что должно получиться

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

Часть 5. Атака на недопустимую кривую

Задание

1. Разберите invalid_curve_oracle.py. Найдите ecdh() и ecdh_safe(): первая умножает присланную точку на секрет без проверки, вторая сначала проверяет уравнение кривой.
2. Заполните invalid_template.py: перебирайте b' = 1, 2, 3, ..., для каждой кривой (p, a, b') считайте число точек N' и его малые простые делители q ≤ 100.
3. Для нового q найдите на этой кривой точку P' и вычислите Q = (N'/q)·P'. Если Q ≠ O, её порядок равен q.
4. Отправьте Q оракулу, получите R = d·Q и перебором t ∈ [0, q) найдите d mod q.
5. Остановитесь, когда произведение модулей превысит N = 10039, и восстановите d по китайской теореме об остатках.
6. Проверьте oracle.check_secret(d) и повторите запрос через ecdh_safe(Q) — объясните, что произошло.

python3 invalid_template.py

Для учебной кривой достаточно пяти остатков — по модулям 3, 5, 7, 41, 71; их произведение 305 655 больше 10 039, поэтому d определяется однозначно. Число запросов к оракулу выводится в конце.

Что должно получиться

Восстановленный секрет, число запросов (единицы, не тысячи) и вывод: единственное отличие «уязвимой» версии от «безопасной» — одна проверка на входе.

Часть 6. Сравнение скорости

Задание

1. Сравните скорость подписи и проверки для RSA-3072, ECDSA P-256 и Ed25519:

openssl speed -seconds 2 ecdsap256 ed25519 rsa3072

2. Запишите в отчёт колонки sign/s и verify/s для трёх алгоритмов.
3. Объясните, почему у RSA проверка быстрее подписи, а у ECDSA — наоборот.
4. Сравните длины: сгенерируйте ключи и подписи и измерьте размеры файлов:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa.pem
openssl pkey -in rsa.pem -pubout -outform DER | wc -c

5. Сделайте вывод: в каком сценарии выигрывают кривые и в каком — RSA.

Что должно получиться

Таблица измерений и осмысленный вывод. Абсолютные числа зависят от процессора, поэтому важны отношения: подпись на кривой быстрее в десятки раз, проверка — в единицы раз медленнее.

Журнал работы

В журнал записываются конкретные числа, полученные на своей машине: время, число запросов, размеры файлов. Отчёт без чисел считается невыполненным.

Критерии проверки

Работа считается выполненной, если:

• проверки check_ec.py, check_x25519.py и check_recover.py завершаются без ошибок;
• порядок точки и теорема Хассе проверены, X25519 совпал с вектором, ключ восстановлен из двух подписей с общим nonce;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

Контрольные вопросы

1. Почему в формулах сложения точек нет коэффициента b и какое следствие это имеет для безопасности?
2. Что такое точка на бесконечности и почему без неё множество точек не образует группу?
3. Сформулируйте теорему Хассе. Какой интервал она даёт для p = 10007?
4. Чем порядок точки отличается от порядка группы и как они связаны?
5. Почему для криптографии нужен простой порядок большой подгруппы? Какую атаку включает гладкий порядок?
6. Как работает double-and-add и почему для секретных скаляров его заменяют лестницей Монтгомери?
7. Что делает зажим скаляра в X25519 и какие три задачи он решает?
8. Почему X25519 не проверяет, лежит ли входная точка на кривой, а ECDH на P-256 обязан проверять?
9. Выведите формулу восстановления k при повторе nonce. Что произойдёт, если k лишь смещён, а не повторён?
10. Почему Ed25519 невосприимчива к повтору nonce, а ECDSA — нет?
11. Опишите атаку на недопустимую кривую. Почему для неё нужны остатки по нескольким модулям?
12. Сравните RSA-3072, ECDSA P-256 и Ed25519 по размерам ключей, размеру подписи и скорости подписи.