Дискретный логарифм

Дискретный логарифм — это задача обращения показательной функции в конечной циклической группе, заключающаяся в нахождении целого показателя степени (логарифма) по заданным основанию и значению степени. Формально, для циклической группы \(G\) порядка \(n\) с образующим элементом \(g\) и произвольного элемента \(h \in G\) требуется найти целое число \(x\) (где \(0 \le x < n\)) такое, что \(g^x = h\). Задача дискретного логарифмирования (DLOG) является вычислительно трудной для некоторых групп, что лежит в основе многих криптографических систем.

История

Понятие дискретного логарифма неявно возникло ещё в работах по теории чисел XVIII—XIX веков. В 1798 году Карл Фридрих Гаусс в «Арифметических исследованиях» описал свойства примитивных корней по модулю простого числа и показал, что возведение в степень по модулю является периодической функцией. Однако термин «дискретный логарифм» был введён значительно позже, в середине XX века, в связи с развитием теории конечных полей и алгебраической теории чисел.

В 1976 году Уитфилд Диффи и Мартин Хеллман в своей работе «Новые направления в криптографии» предложили протокол обмена ключами, основанный на вычислительной сложности задачи дискретного логарифмирования в мультипликативной группе поля по модулю простого числа. Это стало отправной точкой для криптографии с открытым ключом. В 1985 году Тахер Эль-Гамаль разработал криптосистему шифрования и цифровой подписи, также опирающуюся на DLOG.

В 1990-х годах были предложены эффективные алгоритмы для решения задачи дискретного логарифмирования в некоторых группах, что привело к необходимости выбора групп с большим порядком и специальными свойствами. В 2000-х годах с развитием эллиптической криптографии задача дискретного логарифмирования на эллиптических кривых стала основой для современных стандартов, таких как ECDSA и EdDSA.

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

Пусть \(G\) — конечная циклическая группа порядка \(n\) с образующим элементом \(g\). Для любого элемента \(h \in G\) существует единственное целое число \(x\) по модулю \(n\) такое, что \(g^x = h\). Это число \(x\) называется дискретным логарифмом элемента \(h\) по основанию \(g\) и обозначается \(\log_g h\). В отличие от обычного логарифма над вещественными числами, дискретный логарифм определён только в конечных группах и принимает значения из кольца вычетов по модулю \(n\).

Примеры групп

Задача дискретного логарифмирования рассматривается в различных группах:

• **Мультипликативная группа простого поля \(\mathbb{Z}_p^*\)**: группа вычетов по модулю простого числа \(p\) порядка \(p-1\). Это классическая группа, используемая в протоколе Диффи — Хеллмана и системе Эль-Гамаля.
• **Мультипликативная группа конечного поля \(\mathbb{F}_{q}^*\)**: обобщение на поля характеристики \(p\) (например, \(\mathbb{F}_{2^m}\)). Используется в некоторых криптосистемах, но менее популярна из-за уязвимости к атакам с использованием спариваний.
• Группа точек эллиптической кривой: абелева группа, задаваемая на эллиптической кривой над конечным полем. В криптографии на эллиптических кривых (ECC) задача дискретного логарифмирования считается особенно сложной, что позволяет использовать меньшие размеры ключей при том же уровне безопасности.
• Группа классов идеалов мнимого квадратичного поля: используется в некоторых криптосистемах, но менее распространена.

Сложность и алгоритмы

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

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

• Полный перебор: проверка всех возможных значений \(x\) от 0 до \(n-1\). Требует \(O(n)\) операций, что неприемлемо для больших \(n\).
• Алгоритм «шаг младенца — шаг великана» (baby-step giant-step): предложен Дэниелом Шенксом в 1971 году. Имеет временную сложность \(O(\sqrt{n})\) и требует \(O(\sqrt{n})\) памяти. Работает для любой группы.
• Алгоритм Полига — Хеллмана: использует разложение порядка группы на простые множители. Эффективен, если порядок \(n\) является гладким числом (имеет малые простые делители). Сложность пропорциональна сумме простых делителей.
• Алгоритм ρ Полларда (Pollard’s rho): вероятностный алгоритм с ожидаемой сложностью \(O(\sqrt{n})\) и малым потреблением памяти. Широко применяется для эллиптических кривых.
• Алгоритм исчисления индексов (index calculus): субэкспоненциальный алгоритм, применимый к мультипликативным группам полей. Основан на факторизации чисел в поле. Для группы \(\mathbb{Z}_p^*\) сложность составляет \(L_p(1/3, c)\) (где \(c\) — константа), что значительно быстрее экспоненциальных методов.
• Алгоритм Копперсмита (Coppersmith): адаптация исчисления индексов для полей малой характеристики, например \(\mathbb{F}_{2^m}\). Имеет субэкспоненциальную сложность.

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

В 1994 году Питер Шор предложил квантовый алгоритм, который решает задачу дискретного логарифмирования за полиномиальное время \(O((\log n)^3)\) на квантовом компьютере. Это делает все криптосистемы, основанные на DLOG, уязвимыми при появлении достаточно мощных квантовых вычислителей. В ответ на это разрабатываются постквантовые криптосистемы, не основанные на задачах факторизации и дискретного логарифмирования.

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

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

• Протокол Диффи — Хеллмана: позволяет двум сторонам получить общий секретный ключ по незащищённому каналу. Безопасность основана на предположении, что вычисление дискретного логарифма вычислительно невозможно.
• Криптосистема Эль-Гамаля: схема шифрования с открытым ключом, использующая DLOG. Аналогично, безопасность опирается на сложность задачи.
• Цифровая подпись DSA (Digital Signature Algorithm) и её вариант на эллиптических кривых ECDSA: стандарты, принятые в США и других странах, включая Россию (ГОСТ Р 34.10-2012, использующий эллиптические кривые).
• Схемы обязательств (commitment schemes) и доказательства с нулевым разглашением: некоторые протоколы, такие как доказательство знания дискретного логарифма, используются в криптовалютах и системах анонимности.

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

Основной недостаток криптосистем на основе DLOG — потенциальная уязвимость перед квантовыми компьютерами. Кроме того, для мультипликативных групп простых полей и полей малой характеристики существуют субэкспоненциальные атаки, что требует выбора достаточно больших параметров (например, модуль \(p\) размером не менее 2048 бит для классического DSA). Для эллиптических кривых размер ключа обычно составляет 256 бит для эквивалентной безопасности, что делает их более эффективными.

В 2010-х годах были обнаружены уязвимости в некоторых реализациях, связанные с использованием слабых кривых или неправильной генерацией параметров. Например, в 2015 году исследователи показали, что некоторые кривые, рекомендованные NIST, могут содержать скрытые уязвимости, хотя это не было доказано.

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

• В 2019 году группа исследователей из Лейденского университета и компании CWI Amsterdam вычислила дискретный логарифм в группе \(\mathbb{Z}_p^*\) для 795-битного простого числа, что стало рекордом для классических алгоритмов.
• Для эллиптических кривых рекордным является вычисление дискретного логарифма для кривой над 114-битным простым полем (2018 год), что значительно меньше, чем для мультипликативных групп.
• Задача дискретного логарифмирования тесно связана с задачей факторизации целых чисел: обе являются основой для криптографии с открытым ключом и обе решаются квантовым алгоритмом Шора.

Источники

• Diffie, W., Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory.
• ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.
• Shor, P. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science.
• Odlyzko, A. (2000). Discrete Logarithms: The Past and the Future. Designs, Codes and Cryptography.