Алгоритм Шенкса

Алгоритм Шенкса (англ. Baby-step giant-step; также называемый алгоритм больших и малых шагов) — в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным. Задача дискретного логарифмирования представляет большой интерес в области криптосистем с открытым ключом. Большинство существующих алгоритмов нахождения дискретного логарифма основаны на предположении о чрезвычайно высокой вычислительной сложности (вопрос о решении задачи дискретного логарифма за полиномиальное время на персональном компьютере остается открытым до сих пор); чем сложнее её решить, тем более криптобезопасной является пересылка информации. Таким образом, одним из способов повысить сложность задачи дискретного логарифмирования является создание криптосистемы, основанной на группе с большим порядком.

Научная основа

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали работу «Новые направления в современной криптографии»^[1], в которой были положены принципы обмена информацией без обмена секретным ключом. Принцип основывается на существовании односторонних функций $f(x)$, таких, что $f(x)$ может быть легко и быстро посчитана для любого заданного $x$, когда как восстановление $x$ из $f(x)$ является вычислительно сложной задачей. Если кодировать сообщения по этому принципу, то встает вопрос о декодировании зашифрованных сообщений. Предполагается, что получателю зашифрованного сообщения будет существенно проще дешифровать его, если он будет знать некоторую информацию, называемую «секретом», которая облегчит ему задачу по восстановлению $x$ по $f(x)$. Претендентами на односторонние криптостойкие функции являются^[2]:

• Умножение. $f(p, q) = y = pq$, где $p$ и $q$ — простые числа. Обратная функция должна находить $p$ и $q$ по заданному $y$.
• Возведение в квадрат по модулю. $f(x, N) = y = x^2 \mod N$, где $x$ и $N$ — целые числа и N — произведение простых чисел $p$ и $q$. Обратная функция должна находить $x$ по заданным $y$ и $N$.
• Дискретное экспоненцирование. $f(x, a, p) = y = a^x \mod p$. Обратная функция должна находить $x$ по $a$, $y$ и $p$.
• Криптографические хеш-функции. Существует множество различных криптографических хеш-функций.

Гаусс, Карл Фридрих, «Disquisitiones Arithmeticae», 329 глава (1801)^[3]:

Проблема распознавания простых чисел из составных и разложения составных чисел на простые множители является одной из самых важных и полезных среди всех арифметических задач. … Высокое призвание науки в том, кажется, и состоит, чтобы любой вклад в решение такой элегантной и знаменитой проблемы усердно культивировался.

Оригинальный текст  (лат.)  

Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere, et geometrarum tum veterum tum recentiorum industriam ac sagacitatem occupavisse, tam notum est, ut de hac re copiose loqui superfluum foret.

В данной статье приводится один из алгоритмов эффективного решения задачи нахождения функции, обратной дискретному экспоненцированию. Алгоритм был предложен Дэниэлем Шенксом в 1972 году.^[4]

Формулировка проблемы

Дэниэль Шенкс — автор опубликованного в 1972 году алгоритма больших и малых шагов

Пусть задана циклическая группа $G$ с генератором $g$. $x$ называется дискретным логарифмом $h$ над этой группой, если он удовлетворяет следующему условию:

$g^x = h \in G$

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

Можно привести следующее простое объяснение. Циклическая группа $G$ с генератором $g$ означает, что все последовательные степени $g$ (то есть $g^0, g^1, g^2, g^3, ..., g^{n-1}$) будут генерировать различные элементы группы. В какой-то момент, будет найден некоторый элемент $g^n$, который будет равен первому элементу (то есть $g^n = g^0$). Это выполняется в силу «конечности» группы. Порядком группы в данном случае называется число элементов в группе. Простым примером конечной циклической группы является такая группа, которая состоит из последовательных натуральных чисел, ограничивающиеся некоторым простым числом p(строго говоря, число может быть и составное). Обычно такие группы обозначаются $\mathbb{Z}^*_p$, где p — простое число и порядок группы p-1.

В качестве примера рассмотрим $\mathbb{Z}^*_7$. Для этой группы элементами будут числа

$1,2,3,4,5,6$

так как это все натуральные числа меньше 7. Возьмем генератор $g=3$. Увидим, что последовательным возведением генератора в степень мы получим последовательность

$1, 3, 2, 6, 4, 5, 1$

Очевидно, что $g^{6 \cdot k + i} \equiv g^i$ (mod 7). Мы имеем дело с циклической группой порядка $p-1=6$.

В случае с обычным логарифмом, поставленная задача решается просто. Обычный логарифм — непрерывная и монотонная функция, где $\log x > \log y$, если $x > y$. Отсюда следует, что если $y$ «достаточно близок» к $x$, то $\log y$ будет «достаточно близок» к $\log x$.

Поведение дискретного логарифма существенно отличается от обычного логарифма непредсказуемостью. Можно видеть, что $g^3 \equiv 6$ (mod 7), однако $g^4 \equiv 4$ (mod 7). Экстраполируя данную задачу на большие числа, оказывается, что предсказывание поведения данной функции — нетривиальная задача.^[5][6]

На графике представлена функция $2^x$ (mod 37). Красной линией разделяются подгруппы с максимальным периодом 37. Как видно, значения функции носят непредсказуемый характер, следовательно, данная функция хорошо подходит в качестве кандидата на криптостойкую функцию.

Формально задача дискретного логарифмирования ставится следующим образом^[7]:

$\left.\begin{align} \text{Input:} \quad & g, h, p \in \mathbb{N} \\ \text{Ouput:} \quad & x \in \mathbb{N}: \ g^x \equiv h\ (\bmod\ p ) \\ \end{align}\right\}$

при условии, что $x$ может не существовать, а также $n$ может быть как простым числом, так и составным.

Теория

Идея алгоритма в выборе оптимального соотношения время-память. Основная идея состоит в усовершенствованном последовательном переборе возможных показателей степеней — простейший метод решения задачи дискретного логарифма.

Пусть задана циклическая группа $G$ порядка $n$, генератор группы $\alpha$ и некоторый элемент группы $\beta$. Задача сводится к нахождению целого числа $x$, для которого выполняется

$\alpha^x = \beta\,.$

Алгоритм Шенкса основан на переборе $x$, таких, что $x = im - j$, где $m = \left\lfloor \sqrt{n} \right\rfloor + 1$ и $1 \leq i \leq m$ и $0 \leq j < m$. Ограничение на $i$ и $j$ следует из того, что порядок группы не превосходит $m$, а значит достаточно перебрать все $x$ в диапазоне $\left[0; m\right)$. Отсюда следует, что

$\alpha^{im} = \beta \alpha^j\,.$

(1)

Алгоритм предварительно вычисляет $\alpha^{im}$ для некоторых значений $i$ при фиксированном $m$. Затем следует перебрать всевозможные значения $j$ в правой части равенства для того, чтобы равенство (1) выполнялось. Таким образом проводятся испытания на выполнение равенства для каких-либо значений $j$, предварительно вычислив $\alpha^{im}$.

Алгоритм

Вход: Циклическая группа G порядка n, генератор α и некоторый элемент β.

Выход: Число x, удовлетворяющее $\alpha^{x}=\beta$.

1. m ← Пол(√n)+1
2. Вычислить γ ← α^m.
3. Для i от 0 до m:
   1. Записать в таблицу (i, γ). (см. раздел «Реализация»)
   2. γ ← γ • α^m
4. Для любого j где 0 ≤ j < m:
   1. Вычислить α^j.
   2. Проверить, содержится ли βα^j в таблице.
   3. Если да, вернуть im — j.
   4. Если нет, продолжить выполнение цикла.

Оценка сложности алгоритма

Нерешённые проблемы Computer Science: Может ли задача о дискретном логарифме решаться за полиномиальное время на современном компьютере?[1] (англ.)

Допустим, что необходимо решить $h = ng$, где $h$ и $g$ — целые положительные числа меньше 100. Один из способов — проитерировать последовательно $n$ от 1 до 100, сравнивая величину $n \cdot g$ с $h$. В худшем случае нам потребуется 100 шагов (когда $n=99$). В среднем это займет 50 шагов. В другом случае, мы можем представить $n$ как $n=10a-b$. Таким образом, задача сводится к нахождению $a$ и $b$ . В этом случае можно переписать задачу как $h=(10a-b)g$ или $h+bg=10ag$. Теперь мы можем перебрать все возможные значения $a$ в правой части выражения. В данном случае это все числа от 1 до 10. Это, так называемемые, большие шаги. Известно, что одно из полученных значение для $a$ — искомое. Мы можем записать все значения правой части выражения в таблице. Затем мы можем посчитать возможные значения для левой части для различных значений $b$. Такими являются все числа от 0 до 9 из которых одно является искомым, и вместе с правильным значением правой части дает искомый результат для $n$. Таким образом, задача сводится к перебору различных значений левой части и поиск их в таблице. Если нужное значение в таблице найдено, то мы нашли $b$, и, следовательно, соответствующее $n=10a+b$. Данная иллюстрация демонстрирует скорость работы алгоритма. В среднем выполняется 1.5$\sqrt{n}$ операций. В худшем случае требуется 2$\sqrt{n}$ операций.

Пример

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

Пусть требуется найти $x$, при условии, что $2^x=28$ (mod 37). Основная идея: в начале требуется составить таблицу для «больших». Мы выберем $m=7$ ($\sqrt{36}$ + 1). $i$ пробегает все значения от 1 до 7.

i	1	2	3	4	5	6	7
2im = 17·2i	17	30	29	12	19	27	15

Далее будем подбирать $j$ такое, что $\beta\alpha^j$ (mod 37) уже находится в таблице («маленькие шаги»).

j	0	1
βαj=28·2j	28	19

Видно, что выражение для $j=1$ уже находится в первой таблице. Отсюда находим, что $j=1, i=5$. Соответсвующее значение x=mi-j=7·5-2=34. Среднее число шагов — 1.5$\sqrt{37}$≈9. Нам понадобилось ровно 9 шагов.

Другой пример. Пусть задано $6^x=7531$ (mod 8101). Необходимо вычислить x. В начале создадим и заполним таблицу для «больших шагов». Выберем $m$=91 ($\sqrt{8101} + 1$). Затем мы просто проитерируем $i$ от 1 до 91.

i	1	2	3	4	5	6	…	73	74	…	91
6im = 7477·2i	7477	528	2669	3350	7759	2782	…	3789	1156	…	88

Найдем подходящее значение j для $7531 \cdot 6^j$ (mod 8101).

j	…	44	45
βαj=7531·6j	…	2893	1156

Видно, что во второй таблице для i=45, соответствующее значение уже находится в первой таблице. Отсюда находим x=mi-j=91·74-45=6689. В среднем необходимо 1.5$\sqrt{8101}$≈135 шагов. Нам понадобилось 136 шагов.

Реализация

Существует способ улучшить производительность алгоритма Шенкса. Он заключается в использовании эффективной схемы доступа к таблице. Лучший способ — использование хеш-таблицы. Следует производить хеширование по второй компоненте, а затем выполнять поиск по хешу в таблице в основном цикле по γ. Так как доступ и добавление элементов в хеш-таблицу работает за время O(1) (константа), то асимптотически это не замедляет алгоритм.

Время работы алгоритма оценивается как O($\sqrt n$), что намного лучше, чем время работы O($n$) алгоритма перебора показателей степени брутфорсом.^[8]

Особенности

• Алгоритм Шенкса работает для произвольной конечной цикличной группы.
• Нет необходимости знать порядок группы $G$ заранее. Алгоритм также работает, если $n$ — верхняя граница порядка группы.
• Обычно алгоритм Шенкса используется для групп, у которых порядок — простое число. Если порядком является составное число, то рекомендуется использование алгоритма Полига — Хеллмана.
• Алгоритму Шенкса требуется O($n$) памяти. Возможно выбрать меньшее $m$ на первом шаге алгоритма. Это увеличивает время работы программы до O($n/m$). Также возможно использование ρ-метода Полларда для дискретного логарифмирования, который работает за то же самое время, но требует малое количество памяти.

См. также

• Алгоритм Полига — Хеллмана
• Ρ-алгоритм Полларда

Ссылки

• Дискретное логарифмирование алгоритмом Шэнкса — описание и реализация алгоритма Шенкса на языке программирования C.

Примечания

1. ↑ W. Diffie and M. E. Hellman.D. New Directions in Cryptography. — IEEE Transactions on Information Theory, 1976. — Т. IT-22. — С. pp. 644-654..
2. ↑ Alfred Menezes, Paul van Oorschot, Scott Vanstone Handbook of Applied Cryptography. — CRC Press. — Yale University Press, 1996. — С. 284. — 816 с. — ISBN 0-8493-8523-7.
3. ↑ Carl Friedrich Gauss Disquisitiones Arithmeticae. — Yale University Press, 1965. — ISBN 0-300-09473-6.
4. ↑ D. Shanks. The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference. — University of Colorado, Boulder,, 1972. — С. pp. 217-224..
5. ↑ Serge Vaudenay A Classical Introduction to Cryptography - Applications for Communications Security. — Springer, 2006. — С. 204-205. — 335 с. — ISBN 978-0-387-25464-7.
6. ↑ Henri Cohen A Course in Computational Algebraic Number Theory. — 1. — Springer, 1993. — С. 241-243. — 550 с. — ISBN 978-0-387-25464-7.
7. ↑ Yan, Song Y. Primality testing and integer factorization in public-key cryptography. — 2. — Springer, 2009. — С. 257-260. — 374 с. — ISBN 978-0-387-77267-7.
8. ↑ D. C. Terr A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation. — 2000. — Т. Mathematics of Computation. Volume 69. — С. 767–773..