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

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

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

Область примененияПравить

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

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

 

Дэниэль Шенкс — математик, предложивший алгоритм Гельфонда — Шенкса в 1972 году.

 

Александр Осипович Гельфонд — математик, предложивший алгоритм Гельфонда — Шенкса в 1962 году.

Основная статья: Дискретное логарифмирование

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

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

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

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

${\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}}$ 

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

ТеорияПравить

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

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

${\mathrm{\alpha <!--\; \alpha \; -->}}^x=\mathrm{\beta <!--\; \beta \; -->}.$$\alpha^x = \beta\,.$ 

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

${\mathrm{\alpha <!--\; \alpha \; -->}}^{im}=\mathrm{\beta <!--\; \beta \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}^j.$$\alpha^{im} = \beta \alpha^j\,.$

(1)

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

АлгоритмПравить

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

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

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

Обоснование алгоритмаПравить

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

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

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

ПримерПравить

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

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

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

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

$j$$j$	1	2	3	4
$\mathrm{\beta <!--\; \beta \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}^j=3$$\beta \alpha ^{j}=3$ ·$5^j$$5^{j}$	15	6	7	12

Видно, что во второй таблице для $j=4$$j=4$ , такое значение уже находится в первой таблице. Находим $x=mi-<!--\; -\; -->j=5\cdot <!--\; \cdot \; -->4-<!--\; -\; -->4=16$$x=mi-j=5\cdot 4-4=16$ .

РеализацияПравить

Основная статья: Хеш-таблица

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

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

ОсобенностиПравить

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

ЛитератураПравить

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