Processing math: 100%

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

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

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


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

Пример


 Рассмотрим задачу дискретного логарифмирования в кольце вычетов помодулю простого числа. Пусть задано сравнение
 Будем решать задачу методом перебора. Выпишем таблицу всех степенейчисла 3. Каждый раз мы вычисляем остаток от деления на 17 (например,33≡27 — остаток от деления на 17 равен 10).
31 ≡ 332 ≡ 933 ≡ 1034 ≡ 1335 ≡ 536 ≡ 1537 ≡ 1138 ≡ 16
39 ≡ 14310 ≡ 8311 ≡ 7312 ≡ 4313 ≡ 12314 ≡ 2315 ≡ 6316 ≡ 1

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

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


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


 Разрешимости и решению задачи дискретного логарифмирования впроизвольной конечной абелевой группе посвящена статья J. Buchmann, M.J. Jacobson и E. Teske. В алгоритме используется таблица, состоящая из$O(\sqrt{|
 === В кольце вычетов по простому модулю ===Рассмотрим сравнение
 {{Формула |a^x\equiv b\pmod{p},$
 \texttt 2\\\texttt\}\}
 где p — простое, b не делится на p. Если a является образующимэлементом группы Z/pZ, то уравнение (2) имеетрешение при любых b. Такие числа a называются ещё первообразнымикорнями, и их количество равно ϕ(p)=p1, где ϕ — функцияЭйлера. Решение уравнения (2) можно находить по формуле:
 Однако, сложность вычисления по этой формуле хуже, чем сложностьперебора.
 Следующий алгоритм имеет сложность O(plogp).


Алгоритм 

  1. Присвоить H:=p+1
  2. Вычислить c=aHmodp
  3. Составить таблицу значений cumodp для 1uH и отсортировать её.
  4. Составить таблицу значений bavmodp для 0vH и отсортировать её.
  5. Найти общие элементы в таблицах. Для них cubav(modp), откуда aHuvb(modp).
  6. Выдать Huv.

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

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

  1. Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step)
  2. Алгоритм Полига-Хеллмана — работает, если известно разложение числа p1=si=1qαii на простые множители. Сложность: O(si=1αi(logp+qi)). Если множители, на которые раскладывается p1, достаточно маленькие, то алгоритм очень эффективен.
  3. ρ-метод Полларда имеет эвристическую оценку сложности O(p12).


agraphСубэкспоненциальныеалгоритмы
 В L-нотации вычислительная сложность данных алгоритмов оценивается какLp[d,c] арифметических операций, где c и 0d<1 — некоторыеконстанты. Эффективность алгоритма во многом зависит от близости величинc и d к 1 и 0, соответственно.

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

 Наилучшими параметрами в оценке сложности на данный момент являетсяc=(92+2613)13/31,902, d=13.
 Для чисел специального вида результат можно улучшить. В некоторыхслучаях можно построить алгоритм, для которого константы будутc1,00475, d=25. За счёт того, что константа cдостаточно близка к 1, подобные алгоритмы могут обогнать алгоритм сd=13.

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


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

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

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


 Рассматривается группа точек эллиптической кривой над конечным полем. Вданной группе определена операция сложения двух точек. Тогда mP —это $\underbrace{P+\ldots+P\limits_{m}.Решениемзадачидискретногологарифмированиянаэллиптическойкривойявляетсянахождениетакогонатуральногочислаm,чтоmP=AдлязаданныхточекPиA.До1990годанесуществовалоалгоритмовдискретногологарифмирования,учитывающихособенностейстроениягруппыточекэллиптическойкривой.Впоследствии,Менезес(AlfredJ.Menezes),Окамото(TatsuakiOkamoto)иВенстон(ScottA.Vanstone)предложилиалгоритм,использующийспариваниеВейля.Дляэллиптическойкривой,определённойнадполемGF(q),данныйалгоритмсводитзадачудискретногологарифмированияканалогичнойзадачевполеGF(q^k).Однако,данноесведениеполезно,толькоеслистепеньk$ мала. Это условие выполняется, в основном, для суперсингулярныхэллиптических кривых. В остальных случаях подобное сведение практическиникогда не приводит к субэкспоненциальным алгоритмам.

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


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