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

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

Математические основы

Определение и свойства

Пусть \(G\) — конечная циклическая группа порядка \(n\) с операцией, обозначаемой мультипликативно. Если \(g\) — образующий элемент (генератор), то любой элемент \(h \in G\) может быть единственным образом представлен как \(g^x\) для некоторого \(x \in \{0, 1, \dots, n-1\}\). Число \(x\) и есть дискретный логарифм \(h\) по основанию \(g\). Свойства дискретного логарифма аналогичны свойствам обычного логарифма:

• \(\log_g (ab) = \log_g a + \log_g b \pmod{n}\)
• \(\log_g (a^k) = k \cdot \log_g a \pmod{n}\)

Однако эти свойства выполняются только в рамках модульной арифметики по порядку группы.

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

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

• Мультипликативная группа поля вычетов по модулю простого числа \(p\) (\(\mathbb{Z}_p^*\)): состоит из чисел \(\{1, 2, \dots, p-1\}\) с операцией умножения по модулю \(p\). Порядок группы равен \(p-1\).
• Группа точек эллиптической кривой (\(E(\mathbb{F}_q)\)): абелева группа, образованная точками эллиптической кривой над конечным полем. Операция — сложение точек (геометрически определённое). Дискретный логарифм в такой группе называется задачей эллиптической кривой (ECDLP).
• Мультипликативная группа поля Галуа (\(\mathbb{F}_{q}^*\)): обобщение для поля из \(q = p^m\) элементов.

Вычислительная сложность

Трудность задачи

Задача дискретного логарифмирования считается вычислительно трудной для правильно выбранных групп. Точнее, для групп большого порядка (например, \(p\) — простое число длиной 2048 бит или эллиптическая кривая с порядком около 256 бит) не известно алгоритмов, решающих её за полиномиальное время на классическом компьютере. Сложность лучших известных алгоритмов для мультипликативной группы поля вычетов — субэкспоненциальная (например, решето числового поля), а для эллиптических кривых — экспоненциальная (полный перебор или алгоритм Pollard’s rho). Это различие в сложности делает эллиптическую криптографию более эффективной при том же уровне безопасности.

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

• Полный перебор: проверка всех \(x\) от 0 до \(n-1\). Сложность \(O(n)\) — неприменим для больших \(n\).
• Алгоритм «шаг младенца — шаг великана» (Baby-step giant-step): работает за \(O(\sqrt{n})\) времени и памяти. Основан на принципе «разделяй и властвуй».
• Алгоритм Полига — Хеллмана: эффективен, если порядок группы \(n\) раскладывается на малые простые множители. Сводит задачу к решению в подгруппах простого порядка.
• Алгоритм Pollard’s rho: вероятностный алгоритм со сложностью \(O(\sqrt{n})\), не требующий большого объёма памяти.
• Решето числового поля (Number Field Sieve, NFS): субэкспоненциальный алгоритм, применяемый для мультипликативных групп полей вычетов. Сложность \(L_p[1/3, c]\), где \(c \approx 1.923\).
• Квантовый алгоритм Шора: решает задачу дискретного логарифмирования за полиномиальное время на квантовом компьютере, что делает все современные криптосистемы на его основе уязвимыми при появлении достаточно мощного квантового компьютера.

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

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

Один из первых и наиболее известных протоколов обмена ключами, основанный на трудности дискретного логарифмирования. Два участника (Алиса и Боб) выбирают открытые параметры: простое число \(p\) и генератор \(g\). Каждый генерирует свой секретный ключ (\(a\) и \(b\)), вычисляет открытые значения \(g^a \mod p\) и \(g^b \mod p\), обменивается ими, после чего каждый может вычислить общий секрет \(g^{ab} \mod p\). Без знания \(a\) или \(b\) злоумышленник не может получить общий ключ, так как для этого нужно решить задачу дискретного логарифмирования.

Алгоритм Эль-Гамаля (ElGamal)

Криптосистема с открытым ключом, предложенная Тахиром Эль-Гамалем в 1985 году. Основана на трудности дискретного логарифмирования. Открытый ключ состоит из тройки \((p, g, y)\), где \(y = g^x \mod p\), а секретный ключ — \(x\). Шифрование выполняется путём выбора случайного числа \(k\) и вычисления пары \((c_1 = g^k, c_2 = m \cdot y^k)\). Расшифровка требует вычисления \(c_2 \cdot (c_1^x)^{-1}\). Без знания \(x\) восстановить сообщение \(m\) невозможно без решения задачи дискретного логарифмирования.

Цифровая подпись

Схемы цифровой подписи, такие как DSA (Digital Signature Algorithm) и ECDSA (Elliptic Curve Digital Signature Algorithm), также опираются на дискретное логарифмирование. Подпись создаётся с использованием секретного ключа, а проверка — с использованием открытого ключа. Подделка подписи эквивалентна решению задачи дискретного логарифмирования.

Эллиптическая криптография (ECC)

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

Криптоанализ и атаки

Атаки на основе малого порядка

Если порядок группы \(n\) имеет малые простые делители, то с помощью алгоритма Полига — Хеллмана можно эффективно вычислить дискретный логарифм. Поэтому на практике выбирают группы, порядок которых является простым числом или имеет большой простой делитель.

Атаки на основе квантовых компьютеров

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

Атаки по сторонним каналам

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

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

• Задача дискретного логарифмирования является обратной к задаче возведения в степень в конечной группе, которая, в отличие от неё, выполняется быстро (с помощью алгоритма быстрого возведения в степень).
• В 2016 году группа исследователей под руководством Александра Маслова опубликовала работу, в которой утверждалось, что задача дискретного логарифмирования в мультипликативной группе поля вычетов может быть решена за полиномиальное время на классическом компьютере, однако эта работа была опровергнута научным сообществом.
• Дискретное логарифмирование лежит в основе протокола «доказательства с нулевым разглашением» (zero-knowledge proof), например, протокола Шнорра.
• В России для государственных информационных систем используются криптографические стандарты, основанные на дискретном логарифмировании: ГОСТ Р 34.10-2012 (цифровая подпись на эллиптических кривых) и ГОСТ Р 34.11-2012 (хэш-функция).

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

Основным ограничением криптосистем на основе дискретного логарифмирования является их уязвимость перед квантовыми компьютерами. Кроме того, выбор неподходящих параметров (например, слишком малого простого числа \(p\) или группы с малым порядком) может сделать систему уязвимой для атак. Также существует проблема «доверенного центра» при генерации параметров: если генератор \(g\) или модуль \(p\) выбраны неслучайно, это может создать скрытые лазейки (backdoor). Например, в 2013 году в стандарте NIST SP 800-90A была обнаружена потенциальная уязвимость, связанная с генератором случайных чисел, основанным на дискретном логарифмировании.

Источники

• М. А. Черепнёв, «Дискретное логарифмирование и криптография», учебное пособие, МГУ, 2010.
• А. В. Болотов, С. Б. Гашков, А. Б. Фролов, «Элементарное введение в эллиптическую криптографию», КомКнига, 2006.
• Н. Коблиц, «Курс теории чисел и криптографии», Springer, 2004 (русский перевод: М., 2007).
• Д. Шор, «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer», SIAM Journal on Computing, 1997.
• ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».
• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, «Handbook of Applied Cryptography», CRC Press, 1996.