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

(перенаправлено с «Алгоритм Шенкса»)

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

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

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

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

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

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

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

 

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

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

 

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

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

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

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

 

Алгоритм Гельфонда — Шенкса основан на представлении   в виде  , где  , и переборе   и  . Ограничение на   и   следует из того, что порядок группы не превосходит  , а значит указанные диапазоны достаточны для получения всех возможных   из полуинтервала  . Такое представление равносильно равенству

 

 

 

 

 

(1)

Алгоритм предварительно вычисляет   для разных значений   и сохраняет их в структуре данных, позволяющей эффективный поиск, а затем перебирает всевозможные значения   и проверяет, если   соответствует какому-то значению  . Таким образом находятся индексы   и  , которые удовлетворяют соотношению (1) и позволяют вычислить значение   [7].

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

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

Выход: Число  , удовлетворяющее  .

  1.   
  2. Вычислить   .
  3. Для любого   где    :
    1. Записать в таблицу ( ,  ). (см. раздел «Реализация»)
    2.    
  4. Для любого   где    :
    1. Вычислить  .
    2. Проверить, содержится ли   в таблице.
    3. Если да, вернуть   —  .
    4. Если нет, продолжить выполнение цикла[1][2][7].

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

Нужно доказать, что одинаковые элементы в таблицах обязательно существуют, то есть найдутся такие   и  , что  . Это равенство имеет место в случае  , или  . При  ,   выполнено неравенство  . Для различных пар   и   имеем  , так как в противном случае получилось бы  , что при указанном выборе   возможно только в случае  , и, следовательно,  . Таким образом, выражения   принимают все значения в диапазоне от   до  , который, в силу того, что  , содержит все возможные значения   от   до  . Значит, для некоторых   и   имеет место равенство  [2].

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

Допустим, что необходимо решить  , где   и   — целые положительные числа меньше  . Один из способов — перебрать последовательно   от   до  , сравнивая величину   с  . В худшем случае нам потребуется   шагов (когда  ). В среднем это займет   шагов. В другом случае, мы можем представить   как  . Таким образом, задача сводится к нахождению   и   . В этом случае можно переписать задачу как   или  . Теперь мы можем перебрать все возможные значения   в правой части выражения. В данном случае это все числа от   до  . Это, так называемые, большие шаги. Известно, что одно из полученных значение для   — искомое. Мы можем записать все значения правой части выражения в таблице. Затем мы можем посчитать возможные значения для левой части для различных значений  . Такими являются все числа от   до   из которых одно является искомым, и вместе с правильным значением правой части дает искомый результат для  . Таким образом, задача сводится к перебору различных значений левой части и поиск их в таблице. Если нужное значение в таблице найдено, то мы нашли  , и, следовательно, соответствующее  . Данная иллюстрация демонстрирует скорость работы алгоритма. В среднем выполняется   операций. В худшем случае требуется   операций [3].

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

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

Пусть известно  . В начале создадим и заполним таблицу для «больших шагов». Выберем   ← ( ). Затем   пройдёт от   до  .

  1 2 3 4 5
  20 9 19 12 10

Найдем подходящее значение   для  , чтобы значения в обеих таблицах совпали

  1 2 3 4
 ·  15 6 7 12

Видно, что во второй таблице для  , такое значение уже находится в первой таблице. Находим  [2].

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

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

Время работы алгоритма оценивается как  , что намного лучше, чем время работы   полного перебора показателей степени[4].

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

Примечания править

  1. 1 2 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..
  2. 1 2 3 4 И. А. Панкратова. Теоретико-числовые методы в криптографии: Учебное пособие. — Томск: ТГУ, 2009. — С. 90-98. — 120 с..
  3. 1 2 3 В.И. Нечаев. Элементы криптографии. Основы теории защиты информации. — М.: Высшая школа, 1999. — С. 61-67. — 109 с. — ISBN 5-06-003644-8..
  4. 1 2 D. C. Terr. A modification of Shanks’ baby-step giant-step algorithm. — Mathematics of Computation. — 2000. — Т. 69. — С. 767–773. Архивировано 27 сентября 2011 года..
  5. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦНМО, 2003. — С. 163-185. — 328 с. — ISBN 5-94057-103-4. Архивировано 27 января 2007 года. Архивированная копия. Дата обращения: 23 ноября 2016. Архивировано из оригинала 27 января 2007 года..
  6. Yan, Song Y. Primality testing and integer factorization in public-key cryptography. — 2. — Springer, 2009. — С. 257-260. — 374 с. — ISBN 978-0-387-77267-7. Архивировано 17 января 2013 года..
  7. 1 2 3 4 5 6 Глухов М. М, Круглов И. А., Пичкур А. Б., Черемушкин А. В. Введение в теоретико- числовые методы криптографии. — 1 изд.. — СПб.: Лань, 2010. — С. 279-298. — 400 с. с. — ISBN 978-5-8114-1116-0..

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

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