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

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

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

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

Сложность задачи

Сложность DLP существенно зависит от выбора группы. В некоторых группах (например, в аддитивной группе кольца вычетов по модулю \(n\)) задача решается тривиально с помощью алгоритма Евклида. В других группах, таких как мультипликативная группа простого поля \(\mathbb{F}_p^\) или группа точек эллиптической кривой над конечным полем, задача считается экспоненциально сложной для достаточно больших параметров (например, размер поля \(p\) порядка 1024–2048 бит для \(\mathbb{F}_p^\) и 256–384 бит для эллиптических кривых). Это свойство используется в криптографии с открытым ключом.

История

Первые упоминания задачи дискретного логарифмирования в контексте криптографии относятся к работе Уитфилда Диффи и Мартина Хеллмана 1976 года, где они предложили протокол обмена ключами, основанный на сложности DLP в мультипликативной группе простого поля. В 1985 году Тахер Эль-Гамаль разработал криптосистему, также опирающуюся на эту задачу. Параллельно, в 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать эллиптические кривые, что привело к появлению эллиптической криптографии (ECC), где DLP формулируется для группы точек эллиптической кривой.

Классификация групп

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

• Мультипликативная группа простого поля \(\mathbb{F}_p^*\): классическая постановка, используемая в протоколах Диффи-Хеллмана и Эль-Гамаля. Сложность оценивается субэкспоненциальными алгоритмами (например, решето числового поля).
• Группа точек эллиптической кривой (ECC): считается наиболее сложной для атак — наилучшие известные алгоритмы имеют экспоненциальную сложность относительно размера поля. Используется в современных криптосистемах (например, ГОСТ Р 34.10-2012, ECDSA).
• Группа целых чисел по модулю составного числа \(\mathbb{Z}_n^*\): задача может быть сведена к факторизации \(n\), что делает её уязвимой при наличии эффективных алгоритмов факторизации.
• Группа классов идеалов мнимых квадратичных полей: использовалась в некоторых криптосистемах, но показала меньшую стойкость.
• Группа матриц или группа подстановок: в некоторых случаях задача может быть решена полиномиальными алгоритмами.

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

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

• Полный перебор: проверка всех \(x\) от 0 до \(n-1\). Требует \(O(n)\) операций, неприменим для больших \(n\).
• Алгоритм «шаг младенца — шаг великана» (Baby-step giant-step, Д. Шенкс, 1971): детерминированный алгоритм со сложностью \(O(\sqrt{n})\) по времени и памяти. Работает для любой группы.
• Алгоритм Полларда \(\rho\) (Дж. Поллард, 1978): вероятностный алгоритм со сложностью \(O(\sqrt{n})\) по времени, но с незначительным использованием памяти. Широко применяется на практике.
• Алгоритм Полларда \(\lambda\) (метод кенгуру): используется, когда искомый логарифм лежит в известном интервале.

Субэкспоненциальные алгоритмы

Для мультипликативных групп простых полей и полей малой характеристики существуют субэкспоненциальные алгоритмы, основанные на методе решета числового поля (NFS) и его вариантах. Сложность таких алгоритмов оценивается как \(L(1/3, c)\) для полей простой характеристики и \(L(1/2, c)\) для полей малой характеристики. Это делает группы с малым полем (например, \(\mathbb{F}_{2^m}\) при \(m<1000\)) уязвимыми.

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

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

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

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

• Протокол обмена ключами Диффи-Хеллмана (1976): позволяет двум сторонам получить общий секретный ключ по открытому каналу.
• Криптосистема Эль-Гамаля (1985): асимметричная схема шифрования, основанная на DLP.
• Цифровая подпись (DSA, ECDSA, ГОСТ Р 34.10-2012): схемы, безопасность которых основана на сложности DLP.
• Схемы идентификации (например, Шнорра) и протоколы с нулевым разглашением.

Безопасность и криптоанализ

Стойкость криптосистем, основанных на DLP, определяется размером группы и выбором параметров. Для мультипликативных групп простых полей рекомендуемый размер модуля \(p\) составляет не менее 2048 бит (по состоянию на 2025 год). Для эллиптических кривых — не менее 256 бит. Атаки на DLP могут быть:

• Общими: перебор, \(\rho\)-метод — имеют экспоненциальную сложность.
• Специализированными: для групп с малым порядком, с гладким порядком (атака Полига-Хеллмана), для полей малой характеристики (алгоритмы, использующие решето).
• Квантовыми: алгоритм Шора — полиномиальная сложность.

В 2014 году группа исследователей (Клейньюнг, Шварц и др.) продемонстрировала возможность решения DLP для полей характеристики 2 с помощью алгоритма, основанного на решете, для полей размером до 923 бит. Это привело к отказу от использования полей малой характеристики в криптографии.

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

• Задача дискретного логарифмирования является обратной к задаче возведения в степень, которая в конечных группах выполняется быстро (полиномиально от размера). Эта асимметрия и лежит в основе криптографии с открытым ключом.
• В 2010 году группа математиков под руководством Жана-Франсуа Бийо решила DLP для мультипликативной группы поля \(\mathbb{F}_{2^{613}}\) (размер поля 613 бит) с использованием кластерных вычислений.
• Существует гипотеза, что для некоторых групп (например, групп точек эллиптических кривых) DLP не может быть решена субэкспоненциальными алгоритмами, что делает их особенно привлекательными для криптографии.

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

Основным ограничением криптосистем на основе DLP является уязвимость перед квантовыми вычислениями. Кроме того, для мультипликативных групп простых полей существуют субэкспоненциальные атаки, требующие увеличения размера ключей. В связи с этим в 2020-х годах активно развиваются постквантовые стандарты, такие как CRYSTALS-Kyber (для шифрования) и CRYSTALS-Dilithium (для подписей), не основанные на DLP. В России также разрабатываются постквантовые алгоритмы (например, на основе кодов Мак-Элиса).