Алгоритм Гельфонда — Шенкса

Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов; также очень часто можно встретить название алгоритм согласования, например в книге Василенко "Теоретико-числовые алгоритмы криптографии") — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниелом Шенксом в 1972 году^[1][2][3].

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

Задача дискретного логарифмирования представляет большой интерес для построения криптосистем с открытым ключом. На предположении о чрезвычайно высокой вычислительной сложности решения этой задачи основаны такие криптоалгоритмы как, например, RSA, DSA, Elgamal, Diffie-Hellman, ECDSA, ГОСТ Р 34.10-2001, Rabin и другие. В них криптоаналитик может получить закрытый ключ путём взятия дискретного логарифма от открытого ключа (известного всем), и с его помощью преобразовать шифротекст в текст сообщения. Однако чем сложнее его найти (чем большее количество операций нужно проделать для нахождения дискретного логарифма), тем более стойкой является криптосистема. Одним из способов повысить сложность задачи дискретного логарифмирования является создание криптосистемы, основанной на группе с большим порядком (где логарифмирование будет происходить по модулю большого простого числа). В общем случае такая задача решается полным перебором, данный же алгоритм позволяет в некоторых случаях упростить нахождения показателя степени (уменьшить количество шагов) при вычислении по модулю простого числа, в самом благоприятном случае в квадратный корень раз^[4], но этого сокращения всё равно недостаточно для решения задачи на электронно-вычислительной машине за разумное время (вопрос о решении задачи дискретного логарифма за полиномиальное время на персональном компьютере остаётся открытым до сих пор)^[5].

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

${\displaystyle g^{x}=h.}$

Задача дискретного логарифмирования — по заданным ${\displaystyle h}$, ${\displaystyle g}$ определить ${\displaystyle x}$.

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

${\displaystyle {\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Output:}}\quad &x\in \mathbb {N} :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}}$

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

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

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

${\displaystyle \alpha ^{x}=\beta \,.}$

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

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

(1)

Алгоритм предварительно вычисляет ${\displaystyle \alpha ^{im}}$ для разных значений ${\displaystyle i}$ и сохраняет их в структуре данных, позволяющей эффективный поиск, а затем перебирает всевозможные значения ${\displaystyle j}$ и проверяет, если ${\displaystyle \beta \alpha ^{j}}$ соответствует какому-то значению ${\displaystyle i}$. Таким образом находятся индексы ${\displaystyle i}$ и ${\displaystyle j}$, которые удовлетворяют соотношению (1) и позволяют вычислить значение ${\displaystyle x=i\cdot m-j}$^[7].

Вход: Циклическая группа ${\displaystyle G}$ порядка ${\displaystyle n}$, генератор ${\displaystyle \alpha }$ и некоторый элемент ${\displaystyle \beta }$.

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

1. ${\displaystyle m}$ ← ${\displaystyle \left\lfloor {\sqrt {n}}\right\rfloor +1}$
2. Вычислить ${\displaystyle \gamma }$ ← ${\displaystyle \alpha ^{m}}$.
3. Для любого ${\displaystyle i}$ где ${\displaystyle 1}$ ≤ ${\displaystyle i}$ ≤ ${\displaystyle m}$:
   1. Записать в таблицу (${\displaystyle i}$, ${\displaystyle \gamma }$). (см. раздел «Реализация»)
   2. ${\displaystyle \gamma }$ ← ${\displaystyle \gamma }$ • ${\displaystyle \alpha ^{m}}$
4. Для любого ${\displaystyle j}$ где ${\displaystyle 0}$ ≤ ${\displaystyle j}$ ≤ ${\displaystyle m-1}$:
   1. Вычислить ${\displaystyle \beta \alpha ^{j}}$.
   2. Проверить, содержится ли ${\displaystyle \beta \alpha ^{j}}$ в таблице.
   3. Если да, вернуть ${\displaystyle im}$ — ${\displaystyle j}$.
   4. Если нет, продолжить выполнение цикла^[1][2][7].

Нужно доказать, что одинаковые элементы в таблицах обязательно существуют, то есть найдутся такие ${\displaystyle i}$ и ${\displaystyle j}$, что ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j}}$. Это равенство имеет место в случае ${\displaystyle mi=x+j{\pmod {n}}}$, или ${\displaystyle x=mi-j{\pmod {n}}}$. При ${\displaystyle 1\leq i\leq m}$, ${\displaystyle 1\leq j\leq m}$ выполнено неравенство ${\displaystyle 0\leq mi-j\leq m^{2}-1}$. Для различных пар ${\displaystyle (i_{1},j_{1})}$ и ${\displaystyle (i_{2},j_{2})}$ имеем ${\displaystyle mi_{1}-j_{1}\neq mi_{2}-j_{2}}$, так как в противном случае получилось бы ${\displaystyle m(i_{1}-i_{2})=(j_{1}-j_{2})}$, что при указанном выборе ${\displaystyle i_{1},i_{2}}$ возможно только в случае ${\displaystyle i_{1}=i_{2}}$, и, следовательно, ${\displaystyle j_{1}=j_{2}}$. Таким образом, выражения ${\displaystyle mi-j}$ принимают все значения в диапазоне от ${\displaystyle 0}$ до ${\displaystyle m^{2}-1}$, который, в силу того, что ${\displaystyle m^{2}>n}$, содержит все возможные значения ${\displaystyle x}$ от ${\displaystyle 0}$ до ${\displaystyle n-1}$. Значит, для некоторых ${\displaystyle i}$ и ${\displaystyle j}$ имеет место равенство ${\displaystyle x=mi-j{\pmod {n}}}$^[2].

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

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

Пусть известно ${\displaystyle 5^{x}\equiv 3{\pmod {23}}}$. В начале создадим и заполним таблицу для «больших шагов». Выберем ${\displaystyle m=5}$ ← (${\displaystyle {\sqrt {16}}+1}$). Затем ${\displaystyle i}$ пройдёт от ${\displaystyle 1}$ до ${\displaystyle 5}$.

${\displaystyle i}$	1	2	3	4	5
${\displaystyle 5^{im}=20^{i}}$	20	9	19	12	10

Найдем подходящее значение ${\displaystyle j}$ для ${\displaystyle 3\cdot 5^{j}\ {\bmod {\ }}23}$, чтобы значения в обеих таблицах совпали

${\displaystyle j}$	1	2	3	4
${\displaystyle \beta \alpha ^{j}=3}$·${\displaystyle 5^{j}}$	15	6	7	12

Видно, что во второй таблице для ${\displaystyle j=4}$, такое значение уже находится в первой таблице. Находим ${\displaystyle x=mi-j=5\cdot 4-4=16}$^[2].

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

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

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

• А.О. Гельфонд, Ю.В. Линник. Элементарные методы в аналитической теории чисел. — М.: Физматгиз, 1962. — 272 с.