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

Задача дискретного логарифмирования на эллиптической кривой (ECDLP, от англ. Elliptic Curve Discrete Logarithm Problem) — это математическая задача, лежащая в основе криптосистем на эллиптических кривых. Она заключается в нахождении целого числа \( k \) (называемого дискретным логарифмом), такого, что для заданных точек \( P \) и \( Q \) на эллиптической кривой выполняется равенство \( Q = kP \), где \( kP \) обозначает \( k \)-кратное сложение точки \( P \) с самой собой по правилам групповой операции на кривой. Стойкость большинства современных криптографических алгоритмов с открытым ключом, таких как ECDH (протокол Диффи — Хеллмана на эллиптических кривых) и ECDSA (алгоритм цифровой подписи на эллиптических кривых), основана на практической неразрешимости ECDLP для правильно выбранных параметров.

Математическая формулировка

Пусть \( E \) — эллиптическая кривая, заданная над конечным полем \( \mathbb{F}_q \), где \( q = p^m \) — степень простого числа \( p \). Множество точек кривой \( E(\mathbb{F}_q) \) вместе с точкой на бесконечности \( \mathcal{O} \) образует абелеву группу относительно операции сложения точек. Для заданной точки \( P \in E(\mathbb{F}_q) \) простого порядка \( n \) и точки \( Q \in \langle P \rangle \) (циклической подгруппы, порождённой \( P \)) задача ECDLP состоит в нахождении целого числа \( k \in [0, n-1] \), такого, что:

\[ Q = kP = \underbrace{P + P + \dots + P}_{k \text{ раз}}. \]

Число \( k \) называется дискретным логарифмом точки \( Q \) по основанию \( P \). В криптографических приложениях обычно выбирают кривую с большим простым порядком \( n \) (например, порядка \( 2^{256} \) и выше), чтобы перебор всех возможных \( k \) был вычислительно невозможен.

Связь с задачей дискретного логарифмирования в конечных полях

ECDLP является аналогом классической задачи дискретного логарифмирования (DLP) в мультипликативной группе конечного поля, но с важным отличием: на эллиптических кривых не известны субэкспоненциальные алгоритмы решения, применимые ко всем кривым. Это позволяет использовать значительно меньшие размеры ключей (например, 256 бит для ECDLP против 3072 бит для DLP в поле) при сопоставимом уровне стойкости.

История и развитие

Первые предложения использовать эллиптические кривые в криптографии были сделаны независимо Нилом Коблицем и Виктором Миллером в 1985 году. Они показали, что группа точек эллиптической кривой над конечным полем может служить аналогом мультипликативной группы поля для построения криптосистем с открытым ключом. Основным преимуществом стала высокая вычислительная сложность ECDLP по сравнению с DLP.

В 1990-е годы были разработаны первые стандарты, включая ECDSA (адаптация DSA на эллиптические кривые) и ECDH. В 2000-х годах ECDLP стала основой для многих протоколов, в том числе в системах электронной подписи, шифрования и аутентификации. В России алгоритмы на эллиптических кривых регламентируются стандартами ГОСТ Р 34.10-2012 (цифровая подпись) и ГОСТ Р 34.11-2012 (хеширование).

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

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

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

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

• Метод «шаг младенца — шаг великана» (Baby-step giant-step). Предложен Дэниелом Шенксом. Требует \( O(\sqrt{n}) \) памяти и времени. Суть: предвычисляются точки \( iP \) для малых \( i \) (младенческие шаги), затем ищется совпадение с точками \( Q - jmP \) (великанские шаги).
• Ро-метод Полларда (Pollard’s rho). Вероятностный алгоритм, требующий \( O(\sqrt{n}) \) времени и \( O(1) \) памяти. Основан на поиске коллизий в псевдослучайных последовательностях точек. Существуют параллельные версии (например, метод ван Оорсхота — Винера).
• Метод Полига — Хеллмана (Pohlig — Hellman). Эффективен, если порядок \( n \) имеет малые простые множители. Сводит задачу к решению ECDLP в подгруппах простого порядка с последующим восстановлением \( k \) по китайской теореме об остатках.

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

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

• Алгоритм MOV (Менезеса — Окамото — Ванистона). Сводит ECDLP к DLP в расширении конечного поля, если кривая имеет малую степень вложения (embedding degree). Для суперсингулярных кривых (степень вложения ≤ 6) задача решается субэкспоненциально. Современные кривые (например, NIST P-256) выбираются с большой степенью вложения, чтобы избежать этой атаки.
• Атака Фрая — Рука (Frey — Rück). Аналогична MOV, но использует спаривания Тейта вместо спаривания Вейля.
• Атака на аномальные кривые (Smart, Semaev, Satoh — Araki). Если порядок кривой равен характеристике поля \( q \) (аномальная кривая), то ECDLP решается за полиномиальное время с помощью подъёма на кольцо p-адических чисел.
• Алгоритм Гессе — Кёлера — Штайнфельда (Xedni calculus). Попытка поднять точки на кривую над кольцом целых чисел, но практической эффективности не показал.

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

В 1994 году Питер Шор предложил квантовый алгоритм, решающий DLP (и, как следствие, ECDLP) за полиномиальное время. Для работы требуется квантовый компьютер с достаточным числом кубитов. На 2025 год такие компьютеры не существуют, но развитие квантовых технологий стимулирует разработку постквантовой криптографии.

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

Практическая стойкость ECDLP зависит от следующих факторов:

• Размер поля \( q \). Для кривых над простыми полями \( \mathbb{F}_p \) рекомендуется \( p \ge 256 \) бит. Для полей характеристики 2 (\( \mathbb{F}_{2^m} \)) — \( m \ge 250 \).
• Порядок кривой \( n \). Должен быть простым или содержать большой простой множитель (не менее 256 бит). Малые простые множители делают возможной атаку Полига — Хеллмана.
• Степень вложения. Должна быть достаточно большой (обычно \( \ge 20 \)), чтобы предотвратить атаки MOV и Фрая — Рука.
• Отсутствие аномальности. Порядок кривой не должен равняться \( q \).
• Случайность кривой. Кривые, выбранные по стандартам (NIST, SECG, ГОСТ), проходят проверку на отсутствие скрытых уязвимостей.

На 2025 год рекордом решения ECDLP является задача на кривой над полем размером 117 бит (решена в 2016 году с помощью параллельного ро-метода Полларда). Кривые размером 256 бит считаются безопасными для всех известных классических алгоритмов.

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

ECDLP используется в следующих алгоритмах и протоколах:

• ECDH (Elliptic Curve Diffie — Hellman) — протокол выработки общего секретного ключа.
• ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм цифровой подписи.
• EdDSA (Edwards-curve Digital Signature Algorithm) — вариант на кривых Эдвардса (например, Ed25519).
• ECIES (Elliptic Curve Integrated Encryption Scheme) — гибридная схема шифрования.
• Schnorr-подпись на эллиптических кривых — используется в криптовалютах (например, Bitcoin после активации Taproot).

В России стандартизированы аналоги: ГОСТ Р 34.10-2012 (цифровая подпись) и VKO (выработка ключа) на кривых, определённых в ГОСТ Р 34.11-2012.

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

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

Интересные факты

• В 2014 году исследователи из Университета Ватерлоо решили ECDLP для кривой над полем \( \mathbb{F}_{2^{112}} \) за 6 месяцев на 2000 ядрах.
• Алгоритм MOV назван в честь Альфреда Менезеса, Тацуаки Окамото и Скотта Ванистона, а атака Фрая — Рука — в честь Герхарда Фрая и Ханса-Георга Рука.
• Кривая secp256k1, используемая в Bitcoin, была выбрана для минимизации вероятности скрытых уязвимостей, но её параметры (в отличие от NIST P-256) не имеют публичного обоснования.

Источники

• Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. — 1987. — Vol. 48, № 177. — P. 203–209.
• Miller V. S. Use of Elliptic Curves in Cryptography // Advances in Cryptology — CRYPTO ’85. — LNCS, 1986. — Vol. 218. — P. 417–426.
• Menezes A., Okamoto T., Vanstone S. A. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Transactions on Information Theory. — 1993. — Vol. 39, № 5. — P. 1639–1646.
• Semaev I. Evaluation of discrete logarithms on some elliptic curves // Mathematics of Computation. — 1998. — Vol. 67, № 221. — P. 353–356.
• Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. — Springer, 2004.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.
• Шор П. Алгоритмы для квантовых компьютеров: дискретный логарифм и факторизация // SIAM Journal on Computing. — 1997. — Vol. 26, № 5. — P. 1484–1509.