Задача дискретного логарифма на эллиптической кривой

Задача дискретного логарифма на эллиптической кривой (Elliptic Curve Discrete Logarithm Problem, ECDLP) — это математическая задача, лежащая в основе криптостойкости многих современных криптографических систем с открытым ключом, в частности, алгоритмов электронной подписи и шифрования на эллиптических кривых. Задача формулируется следующим образом: для заданной эллиптической кривой \(E\) над конечным полем \(\mathbb{F}_q\), заданной точки \(G\) на этой кривой (порождающей точки) и точки \(Q\), являющейся результатом скалярного умножения \(Q = kG\), требуется найти целое число \(k\) (дискретный логарифм). Сложность решения ECDLP при правильном выборе параметров кривой считается экспоненциальной, что делает её привлекательной для криптографии.

Математическая постановка задачи

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

Эллиптическая кривая \(E\) над конечным полем \(\mathbb{F}_q\) (где \(q = p^m\), \(p\) — простое число, \(m \ge 1\)) задаётся уравнением Вейерштрасса: \[ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6, \] где коэффициенты \(a_i \in \mathbb{F}_q\), и дискриминант кривой не равен нулю (условие несингулярности). Для простых полей \(\mathbb{F}_p\) (где \(p > 3\)) уравнение упрощается до: \[ y^2 = x^3 + ax + b, \] где \(a, b \in \mathbb{F}_p\) и \(4a^3 + 27b^2 \neq 0\).

Множество точек кривой вместе с бесконечно удалённой точкой \(O\) (нейтральным элементом) образуют абелеву группу с операцией сложения точек. Скалярное умножение \(kG\) определяется как \(G + G + \dots + G\) (\(k\) раз) для \(k > 0\), \(0G = O\), и для отрицательных \(k\) — как обратный элемент.

Формулировка ECDLP

Пусть \(E\) — эллиптическая кривая над \(\mathbb{F}_q\), \(G\) — точка порядка \(n\) (порождающая точка), \(Q\) — произвольная точка на кривой, принадлежащая циклической подгруппе, порождённой \(G\). Задача дискретного логарифма на эллиптической кривой состоит в нахождении целого числа \(k \in [0, n-1]\) такого, что: \[ Q = kG. \] Число \(k\) называется дискретным логарифмом точки \(Q\) по основанию \(G\).

Сложность и криптостойкость

Экспоненциальная сложность

В отличие от задачи дискретного логарифмирования в мультипликативной группе конечного поля (где существуют субэкспоненциальные алгоритмы, например, решето числового поля), для ECDLP на правильно выбранных кривых известны только алгоритмы с экспоненциальной сложностью, работающие за время \(O(\sqrt{n})\), где \(n\) — порядок подгруппы. Это связано с тем, что эллиптические кривые не имеют структуры, аналогичной мультипликативной группе поля, что затрудняет применение методов индекса.

Размер ключа

Из-за высокой сложности ECDLP для достижения уровня безопасности, эквивалентного, например, 1024-битному ключу RSA, достаточно использовать эллиптическую кривую с размером поля около 160–256 бит. Это делает криптосистемы на эллиптических кривых (ECC) более эффективными по памяти и вычислительным ресурсам по сравнению с традиционными системами, такими как RSA или DSA.

Алгоритмы решения ECDLP

Общие алгоритмы

Эти алгоритмы работают для любой циклической группы и не используют специфику эллиптических кривых:

• Алгоритм «шаг младенец — шаг великан» (Baby-step giant-step). Требует \(O(\sqrt{n})\) времени и памяти. Основан на компромиссе между временем и памятью: предварительно вычисляются \(\sqrt{n}\) точек (шаги младенца), затем ищется совпадение.
• Алгоритм Полларда — \(\rho\) (Pollard’s rho). Вероятностный алгоритм с ожидаемым временем \(O(\sqrt{n})\) и минимальным использованием памяти. Основан на поиске коллизий в псевдослучайных последовательностях точек.
• Алгоритм Полларда — \(\lambda\) (Pollard’s kangaroo, или лямбда-метод). Применяется, когда значение \(k\) известно в некотором интервале \([a, b]\). Эффективен для поиска логарифма в ограниченном диапазоне.

Специализированные алгоритмы

• Алгоритм MOV (Menezes–Okamoto–Vanstone). Использует спаривание Вейля или Тейта для сведения ECDLP к задаче дискретного логарифмирования в мультипликативной группе расширения поля \(\mathbb{F}_{q^k}\), где \(k\) — степень вложения. Если \(k\) мало (например, \(k \le 6\)), то задача становится субэкспоненциально разрешимой. Для кривых, устойчивых к MOV-атаке, требуется, чтобы \(k\) было большим (обычно \(k > 20\)).
• Алгоритм Фрея–Рюка (Frey–Rück attack). Аналогичен MOV, но использует спаривание Тейта и также требует малой степени вложения.
• Атака на аномальные кривые (Smart–Semaev–Satoh–Araki). Если порядок кривой равен характеристике поля \(p\) (так называемые аномальные кривые), то ECDLP решается за полиномиальное время с помощью подъёма кривой на кольцо \(p\)-адических чисел.

Квантовые алгоритмы

• Алгоритм Шора (Shor’s algorithm). В квантовой модели вычислений ECDLP может быть решена за полиномиальное время. Это делает все современные криптосистемы на эллиптических кривых уязвимыми перед квантовым компьютером достаточной мощности. Разработка постквантовых криптосистем является активной областью исследований.

Применение в криптографии

Криптосистемы на основе ECDLP

• ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм электронной подписи, стандартизированный в США (NIST) и других странах. Широко используется в блокчейн-технологиях (например, в биткойне и Ethereum для подписи транзакций).
• ECIES (Elliptic Curve Integrated Encryption Scheme) — гибридная схема шифрования, объединяющая асимметричное шифрование на эллиптических кривых с симметричным шифрованием.
• ECDH (Elliptic Curve Diffie–Hellman) — протокол выработки общего секретного ключа, основанный на сложности ECDLP.
• Схемы на основе спариваний (pairing-based cryptography) — используют билинейные спаривания на эллиптических кривых для реализации более сложных протоколов, таких как иерархическая криптография на основе идентичности (IBE) и короткие подписи (BLS).

Требования к параметрам

Для обеспечения криптостойкости ECDLP необходимо выбирать кривые, удовлетворяющие следующим условиям:

• Порядок кривой \(n\) должен быть простым или содержать большой простой делитель (чтобы избежать атаки Полига–Хеллмана).
• Степень вложения \(k\) должна быть большой (обычно \(k > 20\)) для предотвращения MOV-атаки.
• Кривая не должна быть аномальной (порядок не равен \(p\)).
• Поле должно быть достаточно большим (например, 256 бит для современных стандартов).

Примеры стандартизированных кривых

• secp256k1 — кривая, используемая в биткойне и Ethereum. Параметры: \(p = 2^{256} - 2^{32} - 977\), \(a = 0\), \(b = 7\). Порядок кривой — простое число.
• Curve25519 — кривая, предложенная Дэниелом Бернштейном, с уравнением \(y^2 = x^3 + 486662x^2 + x\) над полем \(\mathbb{F}_{2^{255} - 19}\). Используется в протоколе X25519 (ECDH) и Ed25519 (подписи).
• NIST P-256 — кривая, рекомендованная Национальным институтом стандартов и технологий США (NIST). Параметры: \(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\).

Критика и ограничения

• Квантовая уязвимость: с появлением квантовых компьютеров достаточной мощности все криптосистемы на основе ECDLP будут скомпрометированы. В связи с этим активно разрабатываются постквантовые алгоритмы, такие как криптосистемы на решётках (lattice-based), хэш-функциях и кодах.
• Стандартизация и доверие: некоторые кривые (например, NIST P-256) вызывали подозрения в возможном наличии скрытых уязвимостей, заложенных разработчиками, хотя доказательств этому не было. В ответ на это были созданы «ничьи» кривые, такие как Curve25519, с открытыми и прозрачными параметрами.
• Реализация: ошибки в реализации скалярного умножения (например, утечки по побочным каналам) могут привести к практическому взлому ECDLP, даже если сама математическая задача сложна.

Источники

1. Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. — 1987. — Vol. 48, No. 177. — P. 203–209.
2. Miller V. S. Use of elliptic curves in cryptography // Advances in Cryptology — CRYPTO ’85. — Springer, 1986. — P. 417–426.
3. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. — Springer, 2004.
4. Menezes A., Okamoto T., Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Transactions on Information Theory. — 1993. — Vol. 39, No. 5. — P. 1639–1646.
5. Semaev I. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p // Mathematics of Computation. — 1998. — Vol. 67, No. 221. — P. 353–356.
6. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Journal on Computing. — 1997. — Vol. 26, No. 5. — P. 1484–1509.
7. Bernstein D. J. Curve25519: New Diffie-Hellman speed records // Public Key Cryptography — PKC 2006. — Springer, 2006. — P. 207–228.