Шаг младенца шаг великана алгоритм

Шаг младенца шаг великана алгоритм

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

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

Содержание

Область применения [ править | править код ]

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

В открытой литературе этот метод впервые был описан Шенксом (Daniel Shanks), ссылки на него известны с 1973 года. Это был один из первых методов, более быстрый чем метод прямого перебора.

Общая схема алгоритма такова:

Берем два целых числа m и k, таких что mk>p (как правило, m=k= ). Затем вычисляются два ряда чисел:

(все вычисления произведены по модулю p).

Найдем такие i и j, для которых g i a=g jm . Тогда x=jm—i.

Справедливость последнего равенства подтверждается следующей цепочкой, все вычисления в которой произведены по модулю p:

g x =g jm-i =g jm (g i ) -1 =g jm a(g i a) -1 =g jm a(g jm ) -1 =a.

Читайте также:  Как подключить компрессор напрямую

Заметим, что числа i и j непременно будут найдены, поскольку при i= , j= выполняется jm—i= , причем km>p. То есть среди всех чисел вида jm—i обязательно содержится 0 m .

Ш.3. Вычислить последовательности ui=b i , vj=ag j Для i,j= .

Одна из трудоемких частей этого алгоритма – это поиск на Шаге 4. Он может быть осуществлен несколькими способами:

1) Сначала построить таблицу (i, ui), отсортировать ее по второй компоненте а затем произволить сравнения по мере нахождения компонент vj.

2) Построить две таблицы (i, ui) и (j, vj), отсортировать каждую из них, а затем произвести поиск совпадений.

3) Объединить u, v в одну таблицу, снабдив их номером в соответствующей последовательности и битом принадлежности к одной из двух последовательностей, а затем применить совместную сортировку. И т. п.

Сложность данного алгоритма составляет O( ) умножений по модулю и O( log n) операций сравнения.

Пусть n=229 (простое число), g=6, a=12.

Ш.2. b=g a mod n =6 12 mod 229 = 183.

Ш.3. В этом примере вычислим сначала ряд ui, а затем будем вычислять компоненты vj до тех пор, пока не найдется совпадение.

i, j
ui
vj 196

i=16, j=6. x=mi—j mod n = 250 mod 228 = 22.

Проверка: 6 22 mod 229= 12.

Ответ: log612 mod 228 = 22.

Дата добавления: 2018-11-26 ; просмотров: 1133 ;

3.2. Шаг младенца – шаг великана.

В открытой литературе этот метод впервые был описан Шенксом (Daniel Shanks), ссылки на него известны с 1973 года. Это был один из первых методов, более быстрый чем метод прямого перебора.

Общая схема алгоритма такова:

Берем два целых числа m и k , таких что mk > p (как правило, m = k =). Затем вычисляются два ряда чисел:

a , ga , g 2 a , … , g m — 1 a (mod p )

g m , g 2 m , g 3 m , … , g km (mod p )

(все вычисления произведены по модулю p ).

Найдем такие i и j , для которых g i a = g jm . Тогда x = jm — i .

Справедливость последнего равенства подтверждается следующей цепочкой, все вычисления в которой произведены по модулю p :

g x =g jm-i =g jm ( g i ) -1 =g jm a ( g i a ) -1 =g jm a ( g jm ) -1 =a .

Заметим, что числа i и j непременно будут найдены, поскольку при i = , j = выполняется jm — i = , причем km > p . То есть среди всех чисел вида jm — i обязательно содержится 0 x ≤ p .

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

Читайте также:  Перевести изображение из png в jpg

Приведем этот метод в форме алгоритма.

Алгоритм «Шаг младенца-шаг великана»:

Вход: g — порождающий элемент конечной группы G порядка n ; a G.

Ш.1. Вычислить m =.

Ш.2. Вычислить b = g m .

Ш.3. Вычислить последовательности u i = b i , v j = ag j Для i , j = .

Ш.4. Найти i , j такие что u i = v j . x = mi — j mod n . Идти на Выход.

Выход: log g a = x .

Одна из трудоемких частей этого алгоритма – это поиск на Шаге 4. Он может быть осуществлен несколькими способами:

Сначала построить таблицу ( i , u i ), отсортировать ее по второй компоненте а затем произволить сравнения по мере нахождения компонент v j .

Построить две таблицы ( i , u i ) и ( j , v j ), отсортировать каждую из них, а затем произвести поиск совпадений.

Объединить u , v в одну таблицу, снабдив их номером в соответствующей последовательности и битом принадлежности к одной из двух последовательностей, а затем применить совместную сортировку. И т. п.

Сложность данного алгоритма составляет O() умножений по модулю и O(log n ) операций сравнения.

Пусть n = 229 (простое число), g = 6, a = 12.

Ш.2. b=g a mod n = 6 12 mod 229 = 183.

Ш.3. В этом примере вычислим сначала ряд u i , а затем будем вычислять компоненты v j до тех пор, пока не найдется совпадение.

i= 16, j= 6. x=mi—j mod n = 250 mod 228 = 22.

Проверка: 6 22 mod 229= 12.

Ответ: log 6 12 mod 228 = 22.

3.3. Ро-метод Полларда для дискретного логарифмирования.

Этот алгоритм осуществляет случайный поиск дискретных логарифмов, как и метод «шаг ребенка – шаг великана», но он требует меньшего объема памяти для хранения данных, поэтому предпочтительней для практических целей. В основе данного метода лежит та же идея, что и в основе ро-метода для факторизации – строится псевдослучайная последовательность, в которой находятся совпадающие элементы при помощи метода Флойда, а затем на основании полученной величины вычисляется искомый дискретный логарифм.

Пусть требуется вычислить log g a в конечной группе G порядка n .

Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S 1 US 2 US 3 , так чтобы 1S 2 . Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой.

Например, если G=Z p , где p – простое число, то можно задать разбиение S 1 =<1,…,>, S 2 =<,…,>, S 3 =<, … , p —1>, или разбиение может быть таким: если x mod 3=1, то xS 1 , если x mod 3=2, то xS 2 , если x mod 3=0, то x S 3 .

Далее на G задается последовательность x 0 , x 1 , x 2 , … , где x 0 =1, x i +1 вычисляется по x i посредством функции f для i ≥0:

Читайте также:  Как настроить сглаживание в крите

x i +1 = f ( x i )=

Вычисления проводятся в группе G, то есть если G=Z m , то вычисления следует производить по модулю m .

Такая последовательность групповых элементов может быть представлена двумя последовательностями u 0 , u 1 , u 2 ,… и v 0 , v 1 , v 2 ,… такими, что x i = , u 0 = v 0 =0,

u i +1 =, v i +1 =

Вычисления в последовательностях u и v производятся по модулю n .

В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие x i и x 2 i , что x i = x 2 i . Тогда =. Логарифмируя по основанию g обе части данного уравнения, получим

( v i — v 2 i )log g a ≡( u 2 i — u i ) (mod n )

Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z * m , то n = φ( m )).

Сложность данного метода составляет O() , где n – порядок группы G.

Замечание. Метод может дать отказ в том случае, когда v i = v 2 i . Тогда следует назначить случайные значения от 0 до n—1 переменным u 0 , v 0 , вычислить x 0 = и повторить все шаги алгоритма.

Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x , u и v до того, как x i = x j и дискретный логарифм находится из сравнения ( v i — v j )log g a ≡( u j — u i ) (mod n ).

G=Z * 19 , a =8, g =2.

Тогда n = φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда.

Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то x S 1 , если x mod 3=2, то x S 2 , если x mod 3=0, то x S 3 .

Вычисления будут производиться по формулам:

x i +1 = f ( x i )=

u i +1 =, v i +1 =

Затем вычисляются два ряда чисел:

y, y*a, y*a^2, … , y*a^(m-1) (mod p)
a^m, a^(2*m), a^(3*m), … , a^(k*m) (mod p)

47 mod 107 = 47
47*88 mod 107 = 70
47*88^2 mod 107 = 18
47*88^3 mod 107 = 18
47*88^4 mod 107 = 86
47*88^5 mod 107 = 78
47*88^6 mod 107 = 16
47*88^7 mod 107 = 17
47*88^8 mod 107 = 105
47*88^9 mod 107 = 38

88^10 mod 107 = 37
88^20 mod 107 = 85
88^30 mod 107 = 42
88^40 mod 107 = 56
88^50 mod 107 = 39
88^60 mod 107 = 52
88^70 mod 107 = 105
88^80 mod 107 = 33
88^90 mod 107 = 44
88^100 mod 107 = 23

Найдем такие i и j, для которых y*a^i=a^(j*m) . Тогда x=j*m-i.

47*88^8 mod 107 = 88^70 mod 107 = 105
i = 8, j = 7
x = 62

Проверка: a^x mod p = 88^62 mod 107 = 47 = y

Ссылка на основную публикацию
Adblock detector