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

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

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

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

Сложность задачи зависит от выбора группы. Наиболее распространённые группы, используемые в криптографии:

• Мультипликативная группа простого поля \( \mathbb{Z}_p^* \), где \( p \) — простое число.
• Группа точек эллиптической кривой над конечным полем.
• Мультипликативная группа поля характеристики 2 (используется реже из-за уязвимостей).

История

Первые упоминания задачи дискретного логарифмирования относятся к XIX веку в контексте теории чисел. В 1920-х годах Эмиль Артин сформулировал гипотезу о дискретных логарифмах в полях алгебраических чисел. Однако практический интерес к задаче возник в 1970-х годах с развитием криптографии с открытым ключом.

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

Классификация

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

По типу группы

• DLP в мультипликативной группе простого поля (\( \mathbb{Z}_p^* \)): классическая постановка, уязвимая для атак на основе решета числового поля (NFS) при достаточно малых \( p \).
• DLP в группе точек эллиптической кривой (ECDLP): считается более сложной; для неё не известны субэкспоненциальные алгоритмы общего вида, что позволяет использовать меньшие размеры ключей.
• DLP в мультипликативной группе поля характеристики 2 (\( GF(2^m)^* \)): ранее использовалась, но атаки с помощью функционального поля решета (FFS) снизили её стойкость.

По вычислительной сложности

• Общая задача: для произвольной циклической группы сложность оценивается как \( O(\sqrt{n}) \) с помощью алгоритмов «шаг младенец — шаг великан» или ρ-метода Полларда.
• Специализированная задача: для групп со специальной структурой (например, гладкий порядок) существуют более эффективные алгоритмы, такие как алгоритм Полига — Хеллмана.

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

Несмотря на сложность, для дискретного логарифмирования разработано несколько классов алгоритмов, различающихся по эффективности:

Алгоритмы общего назначения

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

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

• Алгоритм Адлемана — Померанса — Румели (1983): первый субэкспоненциальный алгоритм для DLP в \( \mathbb{Z}_p^* \), основанный на решете числового поля.
• Решето числового поля (NFS): наиболее эффективный алгоритм для DLP в простых полях; сложность \( L_p[1/3, c] \), где \( c \approx 1.923 \). Применяется для взлома ключей размером до 1024 бит.
• Решето функционального поля (FFS): аналог NFS для полей характеристики 2.

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

• Алгоритм Полига — Хеллмана (1978): эффективен, если порядок группы \( n \) имеет только малые простые делители (гладкое число). Сложность \( O(\sum \sqrt{p_i}) \), где \( p_i \) — простые делители \( n \).
• Алгоритм index calculus: использует факторную базу и линейную алгебру; применим к мультипликативным группам полей, но не к эллиптическим кривым.

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

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

Протокол Диффи — Хеллмана (1976)

Позволяет двум сторонам согласовать общий секретный ключ по незащищённому каналу. Стойкость основана на вычислительной сложности DLP. Используется в протоколах TLS, IPsec, SSH.

Криптосистема Эль-Гамаля (1985)

Асимметричная криптосистема, использующая DLP для шифрования и цифровой подписи. Легла в основу стандарта цифровой подписи DSA (Digital Signature Algorithm).

Криптография на эллиптических кривых (ECC)

Использует ECDLP, что позволяет достичь эквивалентной стойкости при меньших размерах ключей (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA). Применяется в современных протоколах (TLS 1.3, Bitcoin, Ethereum).

Схемы идентификации и подтверждения подлинности

Например, схема Шнорра (1989) и схема Окамото — Шираиши (1992) основаны на знании дискретного логарифма без его раскрытия.

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

Вычислительная сложность DLP определяет практическую стойкость криптосистем. Для мультипликативной группы \( \mathbb{Z}_p^* \) при размере модуля \( p \) в 1024 бита (около 309 десятичных цифр) сложность вскрытия оценивается как \( 2^{80} \) операций (эквивалент 80-битного симметричного ключа). Для 2048-битного \( p \) — около \( 2^{112} \) операций. Однако прогресс в алгоритмах (например, улучшение NFS) снижает эти оценки.

Для эллиптических кривых наилучший известный алгоритм — ρ-метод Полларда — имеет сложность \( O(\sqrt{n}) \), где \( n \) — порядок группы. Для 256-битной кривой это около \( 2^{128} \) операций, что считается стойким на современном уровне. В 2020 году группа исследователей под руководством Клауса Шнорра вычислила дискретный логарифм для 114-битной эллиптической кривой (около 34 десятичных цифр) за 10 дней на кластере из 256 процессоров, что иллюстрирует границы практической стойкости.

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

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

Дополнительная критика касается выбора групп: использование групп с гладким порядком или полей малой характеристики может сделать DLP разрешимой за полиномиальное время (атака Полига — Хеллмана). Также существуют атаки по побочным каналам (времени выполнения, энергопотреблению) на реализации алгоритмов.

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

• В 2014 году группа учёных из EPFL (Швейцария) вычислила дискретный логарифм в \( \mathbb{Z}_p^* \) для 596-битного простого числа (около 180 десятичных цифр) с помощью NFS, используя кластер из 2000 ядер за 6 месяцев.
• Для эллиптических кривых рекордным на 2023 год является вычисление логарифма для кривой над полем \( GF(2^{127}) \) (128-битная кривая), что потребовало около \( 2^{64} \) операций.
• Задача дискретного логарифмирования тесно связана с задачей факторизации целых чисел: обе принадлежат классу NP, но не доказано, что они NP-полны.
• В 2022 году Национальный институт стандартов и технологий США (NIST) рекомендовал переход на эллиптические кривые с размером ключа не менее 256 бит для обеспечения стойкости до 2030 года.

Источники

• Шнайер Б. «Прикладная криптография». — М.: Триумф, 2002.
• Менезес А., ван Орсхот П., Ванстон С. «Руководство по прикладной криптографии». — М.: Вильямс, 2006.
• Odlyzko A. M. «Discrete logarithms: The past and the future» // Designs, Codes and Cryptography. — 2000.
• Шор П. «Алгоритмы для квантовых компьютеров: дискретные логарифмы и факторизация» // SIAM Journal on Computing. — 1997.
• Национальный институт стандартов и технологий США (NIST). «Recommendation for Key Management» (SP 800-57). — 2020.