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

Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.

История

Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.

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

Для заданного простого числа [math]\displaystyle{ p }[/math] и двух целых чисел [math]\displaystyle{ g }[/math] и [math]\displaystyle{ c }[/math] требуется найти целое число [math]\displaystyle{ x }[/math], удовлетворяющее сравнению:

[math]\displaystyle{ g^x\equiv c\;\pmod{p}, }[/math]

где [math]\displaystyle{ c }[/math] является элементом циклической группы [math]\displaystyle{ G }[/math], порожденной элементом [math]\displaystyle{ g }[/math].

Алгоритм

Вход: g — генератор циклической группы порядка n, a — из циклической подгруппы, p — простое число, c — параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).

Задача: найти x такое, что [math]\displaystyle{ g^x \equiv c }[/math].

Выбираем факторную базу S = {p₁, p₂, p₃, …, p_t} (Если G = Z^*_p, то база состоит из t первых простых чисел).
Возводим g в случайную степень k, где k такое, что [math]\displaystyle{ 0 \leqslant k \lt n }[/math]. Получаем [math]\displaystyle{ g^k }[/math].
Представляем g^k следующим образом:
[math]\displaystyle{ g^k = \prod_{i=1}^{t} p^{a_i}_i, }[/math]

где [math]\displaystyle{ a_i \geqslant 0 }[/math] (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
Из пункта 3 следует выражение
[math]\displaystyle{ k \equiv \sum_{i=1}^t a_i \log_g p_i \mod n, }[/math]

полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а [math]\displaystyle{ g^n \equiv 1 }[/math] в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
Выбираем случайное число k такое, что [math]\displaystyle{ 0 \leqslant k \lt n }[/math]. Вычисляем [math]\displaystyle{ cg^k }[/math].
Повторяем пункт 3, только для числа [math]\displaystyle{ cg^k }[/math]. Если не получается, то возвращаемся к 6-му пункту.
Аналогично пункту 4, получаем:
[math]\displaystyle{ x = \log_gc = \sum_{i=1}^t a_i \log_g p_i - k \mod n }[/math], где [math]\displaystyle{ \log_g p_i }[/math] ([math]\displaystyle{ 1 \leqslant i \leqslant t }[/math]), где [math]\displaystyle{ k = \log _g g^k \mod n }[/math]. В этом пункте мы и решили задачу дискретного логарифма, отыскав [math]\displaystyle{ x = \log_g c }[/math].

Выход: [math]\displaystyle{ x = \log_g c }[/math].

Пример

Решить уравнение: [math]\displaystyle{ 17 \equiv 10^x\;(mod47) }[/math]

Выбираем факторную базу [math]\displaystyle{ S = \{2,3,5\} }[/math] Пусть k = 7 Вычисляем [math]\displaystyle{ g^k }[/math]

[math]\displaystyle{ k = 1 \;\;\;\; 10^1 mod 47 = 10 = 2 * 5 }[/math]

[math]\displaystyle{ k = 2 \;\;\;\; 10^2 mod 47 \equiv 6 = 2 * 3 }[/math]

[math]\displaystyle{ k = 3 \;\;\;\; 10^3 mod 47 \equiv 13 }[/math]

[math]\displaystyle{ k = 4 \;\;\;\; 10^4 mod 47 \equiv 36 = 2 * 2 * 3 * 3 }[/math]

[math]\displaystyle{ k = 5 \;\;\;\; 10^5 mod 47 \equiv 31 }[/math]

[math]\displaystyle{ k = 6 \;\;\;\; 10^6 mod 47 \equiv 28 = 2 * 2* 7 }[/math]

[math]\displaystyle{ k = 7 \;\;\;\; 10^7 mod 47 \equiv 45 = 3 * 3 * 5 }[/math]

Логарифмируем и обозначаем [math]\displaystyle{ U_i = log_gp_i }[/math] И получаем систему уравнений [math]\displaystyle{ \left\{\begin{matrix}U_1+U_3 = 1 \\ U_1 + U_2 = 2 \\ 2U_1 + 2U_2 = 4 \\ 2U_2 + U_3 = 7\end{matrix}\right. }[/math]

Решаем её

[math]\displaystyle{ u_2 = \frac{8}{3} (mod46) = 8*3^{-1}(mod46) = \{\varphi(46) = \varphi(2*23)\} = 22 = 8*3^{22}(mod46)\equiv 18 }[/math]

Действительно, [math]\displaystyle{ 10^{18} mod47 \equiv 3 }[/math], следовательно [math]\displaystyle{ U_1 = 30 }[/math], [math]\displaystyle{ U_2 = 18 }[/math], [math]\displaystyle{ U_3 = 17 }[/math]

Находим k такое, чтобы [math]\displaystyle{ cg^k = {\displaystyle\prod_{i=1}^{t} p^{a_i}_i} }[/math]

[math]\displaystyle{ 17 * 10^1 (mod47) = 29 }[/math]

[math]\displaystyle{ 17 * 10 ^2 (mod47) = 8 = 2 * 2 * 2 }[/math]

Следовательно [math]\displaystyle{ k = 2 }[/math]

Логарифмируем данное выражение и получаем

[math]\displaystyle{ log_a17 = [(log_a2 + log_a2 + log_a2) -2] mod46 = (3*30 - 2)mod 46 \equiv 42 }[/math]

Ответ: [math]\displaystyle{ x = 42 }[/math]

Сложность

В данном алгоритме, количество итераций зависит, как от размера p, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: [math]\displaystyle{ O(c_1*2^{(c_2 + o(1))\sqrt{logp\;loglogp}}) }[/math] , где [math]\displaystyle{ c_1 }[/math],[math]\displaystyle{ c_2 }[/math] — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.

Усовершенствования

Ускоренный алгоритм исчисления порядка, суть которого состоит в том, чтобы использовать таблицу индексов.

Сложность

Вычислительная сложность снижена до [math]\displaystyle{ O(2log_2(p)) }[/math], по сравнению с оригинальном алгоритмом.

См. также

Ссылки