Центральный Дом Знаний - Алгоритм Шенкса

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

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

  • Умножение. f(p,q) = y = pq, где p и q — простые числа. Обратная функция должна находить p и q по заданному y.

  • Возведение в квадрат по модулю. f(x,N) = y = x2 mod N, где x и N — целые числа и N — произведение простых чисел p и q. Обратная функция должна находить x по заданным y и N.

  • Дискретное экспоненцирование. f(x,a,p) = y = ax mod p. Обратная функция должна находить x по a, y и p.

  • Криптографические хеш-функции. Существует множество различных криптографических хеш-функций.

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

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

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

g^x = h \in G

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

Можно привести следующее простое объяснение. Циклическая группа G с генератором g означает, что все последовательные степени g (т.е.g0,g1,g2,g3,...,gn − 1) будут генерировать различные элементы группы. В какой-то момент, будет найден некоторый элемент gn, который будет равен первому элементу (т.е. gn = g0). Это выполняется в силу "конечности" группы. Порядком группы в данном случае называется число элементов в группе. Простым примером конечной циклической группы является такая группа, которая состоит из последовательных натуральных чисел, ограничивающиеся некоторым простым числом 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.

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


График функции f(x) = 2x mod 37. Красной линией разделяются подгруппы с максимальным периодом 37

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

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

\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, генератор группы α и некоторый элементы группы β. Задача сводится к нахождению целого числа 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). Отсюда следует, что

 

 

 

 

(1)

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

Алгоритм:

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

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

  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: Может ли задача о дискретном логарифме решаться заполиномиальное время на современном компьютере?

Допустим, что необходимо решить 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, при условии, что 2x = 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 такое, что βα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 шагов.


Другой пример. Пусть задано 6x = 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]

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24