Дискретное логарифмирование — Википедия

Дискре́тное логарифми́рование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе .

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

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

Постановка задачи

[править | править код]

Пусть в некоторой конечной мультипликативной абелевой группе задано уравнение

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху — алгоритм полного перебора нашёл бы решение за число шагов не выше порядка данной группы.

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

Рассмотрим задачу дискретного логарифмирования в кольце вычетов по модулю простого числа. Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 33≡27 — остаток от деления на 17 равен 10).

31 ≡ 3 32 ≡ 9 33 ≡ 10 34 ≡ 13 35 ≡ 5 36 ≡ 15 37 ≡ 11 38 ≡ 16
39 ≡ 14 310 ≡ 8 311 ≡ 7 312 ≡ 4 313 ≡ 12 314 ≡ 2 315 ≡ 6 316 ≡ 1

Теперь легко увидеть, что решением рассматриваемого сравнения является x = 4, поскольку 34≡13.

На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.

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

[править | править код]

В произвольной мультипликативной группе

[править | править код]

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья J. Buchmann, M. J. Jacobson и E. Teske[1]. В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

В кольце вычетов по простому модулю

[править | править код]

Рассмотрим сравнение

где  — простое, не делится на без остатка. Если является образующим элементом группы , то уравнение (2) имеет решение при любых . Такие числа называются ещё первообразными корнями, и их количество равно , где  — функция Эйлера. Решение уравнения (2) можно находить по формуле:

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

Следующий алгоритм имеет сложность .

Алгоритм

  1. Присвоить
  2. Вычислить
  3. Составить таблицу значений для и отсортировать её.
  4. Составить таблицу значений для и отсортировать её.
  5. Найти общие элементы в таблицах. Для них откуда
  6. Выдать .

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

Алгоритмы с экспоненциальной сложностью

[править | править код]
  1. Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step)
  2. Алгоритм Полига — Хеллмана работает, если известно разложение числа на простые множители. Сложность: . Если множители, на которые раскладывается , достаточно маленькие, то алгоритм очень эффективен[2].
  3. ρ-Метод Полларда имеет эвристическую оценку сложности [3].

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

[править | править код]

В L-нотации вычислительная сложность данных алгоритмов оценивается как арифметических операций, где и  — некоторые константы. Эффективность алгоритма во многом зависит от близости величин и к 1 и 0, соответственно.

  1. Алгоритм Адлемана появился в 1979 году[4]. Это был первый субэкспоненциалный алгоритм дискретного логарифмирования. На практике он всё же недостаточно эффективен. В этом алгоритме .
  2. Алгоритм COS был предложен в 1986 году математиками Копперсмитом (Don Coppersmith), Одлыжко (Andrew Odlyzko) и Шреппелем (Richard Schroeppel)[5]. В этом алгоритме константа , . В 1991 году с помощью этого метода было проведено логарифмирование по модулю . В 1997 году Вебер провёл дискретное логарифмирование по модулю с помощью некоторой версии данного алгоритма. Экспериментально показано, что при алгоритм COS лучше решета числового поля.
  3. Дискретное логарифмирование при помощи решета числового поля было применено к дискретному логарифмированию позднее, чем к факторизации чисел. Первые идеи появились в 1990-х годах. Алгоритм, предложенный Д. Гордоном в 1993 году, имел эвристическую сложность [6], но оказался достаточно непрактичным. Позднее было предложено множество различных улучшений данного алгоритма. Было показано, что при решето числового поля быстрее, чем COS. Современные рекорды в дискретном логарифмировании получены именно с помощью этого метода.

Наилучшими параметрами в оценке сложности на данный момент является , [7].

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут , . За счёт того, что константа достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с .

В произвольном конечном поле

[править | править код]

Задача рассматривается в поле GF(q), где ,  — простое.

  1. Алгоритм исчисления индексов (index-calculus) эффективен, если невелико. В этом случае он имеет эвристическую оценку сложности .
  2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при и имеет сложность арифметических операций.
  3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой в оценке сложности . Данный алгоритм появился в 1984 году — до изобретения решета числового поля[8].

В группе точек на эллиптической кривой

[править | править код]

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

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Альфред Менезес, Тацуаки Окамото и Скотт Ванстоун предложили алгоритм, использующий спаривание Вейля[9]. Для эллиптической кривой, определённой над полем , данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле . Однако, данное сведение полезно, только если степень мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.

Вычислительная сложность и приложения в криптографии

[править | править код]

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана[10], схема электронной подписи Эль-Гамаля[11][12], криптосистема Мэсси-Омуры[13] для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции. Хотя сама показательная функция вычисляется достаточно эффективно, даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.

Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что с помощью алгоритма Шора дискретный логарифм можно вычислить за полиномиальное время[14][15][16]. В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе для долговременной защиты данных. Рассматривается ряд идей для создания новых алгоритмов с открытым ключом.

Примечания

[править | править код]
  1. Buchmann J., Jacobson M. J., Teske E. On some computational problems in finite abelian groups (англ.) // Mathematics of Computation[англ.] : journal. — 1997. — Vol. 66. — P. 1663—1687. — doi:10.1090/S0025-5718-97-00880-6. Архивировано 4 марта 2016 года.
  2. S. Pohlig, M. Hellman. An improved algorithm for computing logarithms over and its cryptographic significance (Corresp.) // IEEE Transactions on Information Theory. — 1978. — Январь (т. 24, вып. 1). — С. 106—110. — ISSN 0018-9448. — doi:10.1109/TIT.1978.1055817. Архивировано 21 июня 2018 года.
  3. Pollard J. M. Monte Carlo methods for index computation (mod p) (англ.) // Mathematics of Computation. — 1978. — Vol. 32, iss. 143. — P. 918—924. — doi:10.1090/S0025-5718-1978-0491431-9.
  4. Adleman L. A subexponential algorithm for the discrete logarithm problem with applications to cryptography (англ.) // 20th Annual Symposium on Foundations of Computer Science. — 1979. — P. 55—60. — doi:10.1109/SFCS.1979.2. Архивировано 10 мая 2017 года.
  5. Coppersmith D., Odlzyko A. M., Schroeppel R. Discrete logarithms inGF(p) (англ.) // Algorithmica. — 1986. — Vol. 1, iss. 1—4. — P. 1—15. — doi:10.1007/BF01840433. Архивировано 13 апреля 2018 года.
  6. Gordon D. M. Discrete Logarithms in GF(p) Using the Number Field Sieve (англ.) // SIAM Journal on Discrete Mathematics. — 1993. — Vol. 6, iss. 1. — P. 124—138. — doi:10.1137/0406010.
  7. Coppersmith D. Modifications to the Number Field Sieve (англ.) // Journal of Cryptology. — 1993. — Vol. 6, iss. 3. — P. 169—180. — doi:10.1007/BF00198464. Архивировано 19 июня 2018 года.
  8. Coppersmith D. Fast evaluation of logarithms in fields of characteristic two (англ.) // IEEE Transactions on Information Theory. — 1984. — Vol. 30, iss. 4. — P. 587—594. — ISSN 0018-9448. — doi:10.1109/TIT.1984.1056941.
  9. Menezes A. J., Okamoto T., Vanstone S. A. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Transactions on Information Theory. — 1993. — Т. 39, вып. 5. — С. 1639—1646. — ISSN 0018-9448. — doi:10.1109/18.259647. Архивировано 2 июля 2017 года.
  10. Diffie, Hellman, 1976.
  11. Elgamal, 1984.
  12. Elgamal, 1985.
  13. Massey J. L., Omura J. K. Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission (28 января 1986). Архивировано 20 октября 2016 года.
  14. Shor, 1994.
  15. Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science : Conference Publications. — 1997. — P. 1484–1509.
  16. CompuTerra Online #224 — Квантовые компьютеры и квантовые вычисления… Беседа с кандидатом физико-математических наук, специалистом по теории алгоритмов Михаилом Вялым (Вычислительный центр РАН)