Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

Алгоритм Гельфонда — Шенкса ( также называемыйалгоритмом больших и малых шагов) — в теории группдетерминированный алгоритм дискретного логарифмирования вмульпликативной группе кольца вычетов по модулю простого числа. Былпредложен советским математиком Александром Гельфондом в 1962 году иДэниэлем Шенксом в 1972 году.
 Метод теоретически упрощает решение задачи дискретного логарифмирования,на вычислительной сложности которой построены многие криптосистемы соткрытым ключом. Относится к методам встречи посередине.

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


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

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


 Пусть задана циклическая группа G с образующим g, содержащая nэлементов. Целое число x (в диапазоне от 0 до n1) называетсядискретным логарифмом элемента hG по основанию g, есливыполняется соотношение:

gx=h.
 Задача дискретного логарифмирования — по заданным h, g определитьx.
 Формально задача дискретного логарифмирования ставится следующимобразом:


 \{begin\{cases\}
 \texttt       \{text\{Input:\} \{quad \& g, h, n \{in \{mathbb\{N\} \{\{\\\texttt       \{text\{Output:\} \{quad \& x \{in \{mathbb\{N\}: \{ g\^x \{equiv h\{pmod n\{\{
 \{end\{cases\} при условии, что x может не существовать,а также n может быть как простым числом, так и составным.

Теория


 Идея алгоритма состоит в выборе оптимального соотношения времени ипамяти, а именно в усовершенствованном поиске показателя степени.
 Пусть задана циклическая группа G порядка n, генератор группыα и некоторый элемент группы β. Задача сводится кнахождению целого числа x, для которого выполняется

αx=β.
 Алгоритм Гельфонда — Шенкса основан на представлении x в видеx=imj, где m=n+1, ипереборе 1im и 0j<m. Ограничение на i и jследует из того, что порядок группы не превосходит m, а значитуказанные диапазоны достаточны для получения всех возможных x изполуинтервала [0;m). Такое представление равносильноравенству


 Алгоритм предварительно вычисляет αim для разных значений iи сохраняет их в структуре данных, позволяющей эффективный поиск, азатем перебирает всевозможные значения j и проверяет, еслиβαj соответствует какому-то значению i. Таким образомнаходятся индексы i и j, которые удовлетворяют соотношению(1) и позволяют вычислить значение x=imj .

Алгоритм


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

  1. m[n]+1
  2. Вычислить γαm.
  3. Для i от 0 до m:
    1. Записать в таблицу (i, γ). (см. раздел «Реализация»)
    2. γγαm

  4. Для любого j где 0j \textless m:
    1. Вычислить α.
    2. Проверить, содержится ли βαj в таблице.
    3. Если да, вернуть im — j.
    4. Если нет, продолжить выполнение цикла.

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


 Нужно доказать, что одинаковые элементы в таблицах обязательносуществуют, то есть найдутся такие i и j, чтоgmi=βgj=gx+j. Это равенство имеет место вслучае mi=x+j(modn), или x=mij(modn). При1im, 1jm выполнено неравенство0mijm21. Для различных пар (i1,j1) и (i2,j2)имеем mi1j1mi2j2, так как в противном случаеполучилось бы m(i1i2)=(j1j2), что при указанном выбореi1,i2 возможно только в случае i1=i2, и, следовательно,j1=j2. Таким образом, выражения mij принимают все значения вдиапазоне от 0 до m21, который, в силу того, что m2>n,содержит все возможные значения x от 0 до n1. Значит, длянекоторых i и j имеет место равенство x=mij(modn).

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


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

Пример


 Ниже приведен пример решения задачи дискретного логарифмирования смаленьким порядком группы. На практике в криптосистемах используютсягруппы с большим порядком для повышения криптостойкости.
 Пусть известно 5x3(mod23). В начале создадим и заполнимтаблицу для «больших шагов». Выберем m=5 ← (16+1). Затемi пройдёт от 1 до 5.
j1234
βαj=3·5j156712

 Видно, что во второй таблице для j=4, такое значение уже находится впервой таблице. Находим x=mij=544=16.

Реализация


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

Особенности



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