Эллиптические кривые: точки, которые нельзя принимать на веру

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

Тема идёт от группы точек к атакам. Сначала арифметика: сложение, удвоение, скалярное умножение, порядок точки. Потом протокол ECDH и то, что происходит, когда сервер не проверяет, лежит ли присланная точка на кривой: формулы сложения не содержат коэффициента b, поэтому точка с чужой кривой даёт ответ, из которого извлекается d mod q для малого q, а по остаткам восстанавливается весь секрет. Затем ECDSA и повтор nonce — атака, которая в 2010 году стоила Sony мастер-ключа PlayStation 3. В конце — X25519, монтирование по постоянному времени и защита от подгрупп.

Арифметика эллиптических кривых

Кривая и группа точек

Кривая над простым полем задаётся уравнением y^2 = x^3 + a·x + b (mod p). Точки кривой вместе с «точкой на бесконечности» образуют абелеву группу: есть сложение, обратный элемент, нулевой элемент. Сложение двух точек — проведение прямой и отражение третьей точки пересечения; удвоение — касательная. Формулы содержат a, но не содержат b.

Параметры и кодирование точек стандартизованы в SEC 1 ¹. Порядок группы N близок к p (по теореме Хассе, |N − (p+1)| ≤ 2√p). Порядок точки P — наименьшее k с k·P = O; он делит N. Криптография использует точки большого простого порядка, чтобы дискретный логарифм был трудным.

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

Скалярное умножение k·P вычисляется удвоением и сложением за O(log k) операций. ECDH: Алиса и Боб выбирают секреты a, b, обмениваются a·G и b·G, общий секрет — a·b·G. Противник видит две точки и должен решить задачу Диффи — Хеллмана на кривой.

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

Недопустимая кривая

Идея атаки

Формулы сложения точек не используют b. Если сервер принимает точку Q и отвечает d·Q, не проверяя, что Q лежит на объявленной кривой, противник присылает точку на другой кривой y^2 = x^3 + a·x + b' с тем же a. На этой кривой можно найти точку малого простого порядка q; ответ d·Q позволяет перебором найти d mod q. Собрав остатки по нескольким q с произведением больше N, противник восстанавливает d по китайской теореме об остатках ².

Схема на рисунке 1.

Защита

Проверять, что точка лежит на кривой: y^2 = x^3 + a·x + b mod p. Проверять, что точка не является нулём и что её порядок — большой. Не использовать «голые» формулы без валидации входа. В X25519 та же проблема решена иначе: проверка не нужна, потому что скаляр кратен кофактору, а точки малого порядка дают нулевой общий секрет, который протокол обязан отвергнуть.

Инцидент с CurveSwap (2015) показал, что проверять надо и параметры кривой, а не только точку: подмена самой кривой на слабую ломает протокол целиком ⁴.

ECDSA и повтор nonce

Схема

Подпись ECDSA: r = (k·G)_x mod n, s = k^(−1)(z + r·d) mod n, где k — одноразовый nonce, d — закрытый ключ, а z — не сам хеш сообщения, а число, полученное из него: левые min(bitlen(n), bitlen(hash)) бит хеша, взятые как целое. Для P-256 с SHA-256 это все 256 бит, для P-256 с SHA-512 — только старшие 256 бит. Путать z с полным хешем нельзя: в формуле участвует именно усечённое значение. Проверка восстанавливает точку и сверяет r.

Если k повторился для двух сообщений, то r одинаков, и вычитание даёт k = (z_1 − z_2)/(s_1 − s_2) mod n, а затем d = (s_1·k − z_1)/r mod n. Два перехваченных сообщения — и ключ восстановлен ³. Схема на рисунке 2.

Реальные последствия

В 2010 году Sony использовала в подписи прошивки PlayStation 3 фиксированный k. Этого хватило, чтобы извлечь закрытый ключ и научиться подписывать произвольный код ⁵. В 2013 году та же ошибка встречалась в Android-кошельках: слабая случайность давала повтор k и потерю средств.

Защита: детерминированный k по RFC 6979 (выводится из ключа и сообщения через HMAC), либо качественный CSPRNG, либо EdDSA, где nonce выводится детерминированно по построению ⁶.

X25519 и монтирование

Кривая и скаляр

X25519 — функция Диффи — Хеллмана на кривой Curve25519. Скаляр «зажимается»: младшие три бита обнуляются, старший устанавливается, и это не случайность, а защита: скаляр становится кратным кофактору 8, поэтому точки малого порядка дают нулевой результат. Реализация работает с x-координатой, использует монтирование по лестнице и не имеет ветвлений, зависящих от данных ⁷.

Постоянное время

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

Проверка «точка на кривой» в X25519 не требуется, но требуется проверка результата: если общий секрет — ноль, протокол обязан прерваться. Иначе атакующий присылает точку малого порядка и получает предсказуемый секрет.

Итоги темы

• Безопасность ECC держится на выборе параметров и проверке входных точек.
• Формулы сложения не содержат b, поэтому точка с чужой кривой проходит без проверки.
• Малые порядки дают остатки d mod q; CRT собирает секрет.
• Повтор nonce в ECDSA раскрывает ключ по двум подписям; RFC 6979 и EdDSA решают проблему.
• X25519 спроектирован так, чтобы проверка входа была не нужна, но требует проверки результата на ноль.
• Ветвления по данным — источник утечек по времени и кэшу.

Литература

1. SEC 1: Elliptic Curve Cryptography. Standards for Efficient Cryptography Group, 2009. — параметры кривых, кодирование точек, ECDSA.
2. Biehl I., Meyer B., Müller V. Differential Fault Analysis on Elliptic Curve Cryptosystems. CRYPTO 2000. — ранняя работа о недопустимых точках и малых подгруппах.
3. Johnson D., Menezes A., Vanstone S. The Elliptic Curve Digital Signature Algorithm (ECDSA). 2001. — схема и требования к nonce.
4. Adrian D. et al. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. CCS 2015. — CurveSwap и подмена параметров.
5. Hotz G. Console Hacking 2010: PS3 Epic Fail. 27C3. — извлечение ключа из-за фиксированного nonce.
6. RFC 6979: Deterministic Usage of DSA and ECDSA. 2013. — детерминированный nonce.
7. RFC 7748: Elliptic Curves for Security. 2016. — X25519 и Curve25519.
8. Brumley D., Boneh D. Remote Timing Attacks are Practical. 2003. — почему ветвления по данным опасны.

Дополнительные материалы к апокрифу 10

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

1. Почему эллиптические ключи короче RSA при той же стойкости?
2. Как вычисляется k·P и сколько нужно операций?
3. Что такое порядок группы и порядок точки?
4. Почему для криптографии нужна точка большого простого порядка?
5. Что такое кофактор и как он связан с зажимом скаляра?
6. Почему формулы сложения не зависят от b?
7. Как атака на недопустимую кривую получает d mod q?
8. Сколько нужно остатков, чтобы восстановить d?
9. Какая проверка закрывает недопустимую кривую?
10. Как повтор nonce ломает ECDSA?
11. Почему RFC 6979 решает проблему?
12. Зачем X25519 зажимает скаляр?
13. Почему нулевой общий секрет нужно отвергать?
14. Почему ветвления по данным опасны?
15. Что такое атака по времени на скалярное умножение?

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

Шпаргалка

cp ec_template.py ec.py            && python3 check_ec.py
cp x25519_template.py x25519.py    && python3 check_x25519.py
cp recover_template.py recover.py  && python3 check_recover.py
cp invalid_template.py invalid.py  && python3 check_invalid.py

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

• SEC 1 — параметры кривых и кодирование.
• RFC 7748 — X25519 и Curve25519 с векторами.
• RFC 6979 — детерминированный nonce.
• Johnson, Menezes, Vanstone — ECDSA и требования к k.
• Hotz. Console Hacking 2010 — история с PS3.
• Adrian et al. Imperfect Forward Secrecy — CurveSwap.
• Brumley, Boneh. Remote Timing Attacks are Practical — почему ветвления опасны.
• Документация cryptography по EC — https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ec/.

Углубление: почему валидация точки — часть контракта

Функция ECDH принимает точку. Если она принимает любые 32 байта как точку, она принимает и точки вне кривой, и точки малого порядка. Формулы сложения при этом работают: они не проверяют b, а сервер не проверяет вход. Получается, что противник может задавать подгруппу, в которой живёт ответ.

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

Углубление: почему nonce в ECDSA нельзя переиспользовать

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

RFC 6979 делает k детерминированной функцией ключа и сообщения через HMAC: одинаковые входы дают одинаковый k, но разные сообщения — разные. Это устраняет зависимость от генератора случайных чисел, который как раз и подводил реализации.

Углубление: почему X25519 обходится без проверки точки

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

Лабораторная работа 10. Точки, которые нельзя принимать на веру

• Раздел курса: апокриф 10 «Эллиптические кривые: недопустимая точка, повтор nonce, сторонние каналы»

Введение

«Сейф» перешёл на эллиптическую криптографию: ECDH для сессий, ECDSA для подписи прошивок. Ключи короткие, библиотека современная — и всё равно есть три дырки. Сервер ECDH не проверяет, что присланная точка лежит на кривой, поэтому Мэллори присылает точки малого порядка и по остаткам собирает секрет. Библиотека подписи использует random вместо secrets, и две подписи с общим nonce отдают закрытый ключ. Реализация X25519 ветвится по битам скаляра, и время ответа зависит от секрета.

Работа идёт от арифметики к атакам. Сначала группа точек: сложение, удвоение, скалярное умножение, порядок. Потом X25519 по RFC 7748 и его монтирование. Затем ECDSA и восстановление ключа по двум подписям с одинаковым k. Кульминация — атака на недопустимую кривую с китайской теоремой об остатках.

Части: арифметика, X25519, повтор nonce в ECDSA, недопустимая кривая, продвинутая.

Цель работы

Научиться проверять корректность входных точек и nonce как часть криптографического контракта и показывать, что эллиптические схемы ломаются на валидации, а не на математике.

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

• реализовывать сложение, удвоение и скалярное умножение на кривой;
• реализовывать X25519 и сверять с RFC 7748;
• восстанавливать ключ ECDSA по двум подписям с общим nonce и подделывать подпись;
• проводить атаку на недопустимую кривую и собирать секрет по CRT;
• формулировать проверки, которые закрывают каждую атаку.

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

Разделы «Арифметика эллиптических кривых», «Недопустимая кривая», «ECDSA и повтор nonce», «X25519 и монтирование» апокрифа 10. Соотношения:

y^2 = x^3 + a·x + b (mod p)
P + Q, 2P, k·P — сложение, удвоение, скалярное умножение
ECDSA: r = (k·G)_x mod n;  s = k^(−1)(z + r·d) mod n
повтор k: k = (z1 − z2)/(s1 − s2) mod n;  d = (s1·k − z1)/r mod n
недопустимая кривая: R = d·Q, порядок Q = q  =>  d mod q

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

Ubuntu 24.04, Python 3.10+, cryptography. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-10 && cd ~/lab-apocrypha-10
unzip ~/lr-env.zip
cp ec_template.py ec.py
python3 check_ec.py

Заготовки копируются в файлы без суффикса _template: ec.py, x25519.py, recover.py, invalid.py.

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

В журнале фиксируйте: порядок группы и точки, число шагов CRT, число запросов к оракулу, восстановленный ключ. Провал проверки — с причиной: неверная формула удвоения, потерян кофактор, перепутан знак y.

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

Задание

1. Реализуйте inv, is_on_curve, neg, add, mul, enumerate_points, point_order.
2. Проверьте на кривой малого размера: число точек, порядок конкретной точки, ассоциативность на нескольких примерах.
3. Запустите python3 check_ec.py.
4. Ответьте: почему формула удвоения не содержит b и какое это имеет последствие для валидации.

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

Работающая арифметика, совпадающая с проверкой, и понимание, что формулы сложения «не знают» о коэффициенте b.

Часть 2. X25519

Задание

1. Реализуйте decode_scalar, decode_u, encode_u, cswap, x25519.
2. Проверьте на тестовом векторе RFC 7748.
3. Сверьте общий секрет с cryptography на случайных ключах.
4. Объясните, зачем скаляр «зажимается» и как это связано с кофактором 8.
5. Ответьте: почему в X25519 не нужна проверка точки на кривой, но нужна проверка результата на ноль.

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

Совпадение с RFC и библиотекой и понимание роли зажима скаляра.

Часть 3. Повтор nonce в ECDSA

Задание

1. Изучите nonce_reuse.json: две подписи, два сообщения, открытый ключ.
2. Реализуйте восстановление k и d по формулам выше.
3. Проверьте, что d·G совпадает с открытым ключом жертвы.
4. Подпишите произвольное сообщение восстановленным ключом; проверка check_recover.py должна принять подпись.
5. Ответьте: почему одного совпадения r достаточно для подозрения и как RFC 6979 закрывает проблему.

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

Восстановленный ключ и валидная подпись чужого документа.

Часть 4. Недопустимая кривая

Задание

1. Изучите invalid_curve_oracle.py: сервер отвечает d·Q и не проверяет точку.
2. Реализуйте attack(oracle): перебирайте b', находите число точек N', его малые простые делители q, точку порядка q и остаток d mod q.
3. Соберите остатки по CRT, пока произведение не превысит N, и верните d.
4. Запустите python3 invalid.py и python3 check_invalid.py: секрет должен совпасть, запросов — не больше сорока.
5. Проверьте ecdh_safe: она отвергает точку вне кривой. Объясните, какая именно проверка добавлена.
6. Ответьте: почему атака не работает, если сервер проверяет y^2 = x^3 + a·x + b.

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

Восстановленный секрет, число запросов и формулировка проверки, которая закрывает атаку.

Часть 5. Продвинутая: валидация и сторонние каналы

Задание

1. Соберите «плохую» реализацию скалярного умножения с ветвлением по битам и «хорошую» с монтированием; сравните распределение времени на разных скалярах.
2. Оцените, сколько подписей нужно, чтобы статистически отличить скаляр с ветвлением, и почему это практично для удалённого сервера.
3. Проверьте, что X25519 отвергает нулевой общий секрет, и покажите, что произойдёт без проверки.
4. Сформулируйте контракт функции ECDH: какие проверки входа и выхода обязательны.
5. Перечислите пять ошибок реализации ECC, которые встречались в реальных библиотеках, и защиту от каждой.

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

Замеры времени, нейтрализованная утечка и контракт, пригодный для ревью.

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

Фиксируйте: порядки точек, остатки и их произведение, число запросов, время восстановления ключа. Провал проверки — с причиной.

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

1. Как задаётся эллиптическая кривая и как складываются точки?
2. Почему формула удвоения не содержит b?
3. Что такое порядок точки и кофактор?
4. Как работает ECDH?
5. В чём суть атаки на недопустимую кривую?
6. Откуда берутся остатки d mod q и как они собираются?
7. Какая проверка закрывает атаку на недопустимую кривую?
8. Как повтор nonce раскрывает ключ ECDSA?
9. Что даёт RFC 6979 и что — EdDSA?
10. Зачем в X25519 зажимается скаляр?
11. Почему нужна проверка нулевого общего секрета?
12. Чем опасно ветвление по данным в скалярном умножении?