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

Скачать 0.51 Mb.

страница	1/5
Дата	22.12.2012
Размер	0.51 Mb.
Тип	Задача

1 2 3 4 5

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

Надежность большинства криптографических методов зависит от сложности задачи дискретного логарифмирования. В число таких задач входят соглашение о ключах Диффи-Хеллмана и его производных (§12.6), шифрование Эль-Гамаля (§8.4) и схема подписи типа Эль-Гамаля и ее варианты (§11.5). Этот раздел обобщает современные знания об алгоритмах решения задач дискретного логарифмирования.
Пока явно не указано противное, алгоритмы в этом разделе описаны в основных понятиях (мультипликативно записанной) конечной циклической группы G порядка n с порождающим элементом α (см. Определение 2.167). Для большей точности читателю может быть удобно представлять G, как мультипликативную группу Z*p порядка p  1, где групповая операция - есть умножение по модулю p.
3.48 Определение Пусть G - конечная циклическая группа порядка n. Пусть α - порождающий элемент группы G, и пусть βG. Дискретный логарифм β с основанием α, обозначенный log_α β, это единственное целое число x, 0  x  n  1, такое, что  = ^x.
3.49 Пример Пусть p = 97. Тогда Z*₉₇ циклическая группа порядка n = 96. α = 5 - порождающий элемент группы Z*₉₇. Так как 5³²  35 (mod 97), log ₅ 35 = 32 в Z*₉₇.
Ниже приведены некоторые простые сведения, касающиеся логарифмов.
3.50 Утверждение Пусть α порождающий элемент циклической группы G порядка n, и пусть β, γG. Пусть s целое число. Тогда log _α(βγ ) = (log _α β + log _α γ) mod n и log α (β^s ) = s log _α β mod n.

Наиболее важными в криптографии являются мультипликативная группа F*_qконечного поля F_q (§2.6), включая частные случаи мультипликативной группы Z*_pцелых чисел по модулю простого p, и мультипликативная группа F*₂^m конечного поля F₂^m второй характеристики. Также интересны группа отдельно взятых Z*_n, где n представляет собой составное целое, группа точек эллиптической кривой, определенной на конечном поле, и якобиан гиперэллиптической кривой, определенной на конечном поле.
3.
51 Определение Задача дискретного логарифмирования (DLP): дано простое p, порождающий элемент α группы Z*p , и элемент β  Z*p , требуется найти целое x, 0  x  p  2, такое, что ^x  (mod p).
3.52 Определение Обобщенная задача дискретного логарифмирования (GDLP): дана конечная циклическая группа G порядка n, ее порождающий элемент α, и элемент β  G, требуется найти целое x, 0  x  n  1, такое, что ^x =.

Задачи дискретного логарифмирования в группах эллиптической кривой и в якобианах гиперэллиптических кривых в этом разделе подробно не рассматриваются. Задача дискретного логарифмирования в Z*_n описана далее в §3.8.
3.53 Замечание (сложность GDLP не зависит от порождающего элемента) Пусть  и γ два порождающих элемента из циклической группы G порядка n, и пусть β  G. Пусть x = log _α β, y = log_γβ, и z = log _α γ. Тогда ^x =  = γ^y= (^z )^y. Следовательно, x = zy mod n, и log _γβ = (log _α β ) (log _α γ)^-¹ mod n.

Это означает, что любой алгоритм, вычисляющий логарифмы по основанию , может быть использован для вычисления логарифмов с любым другим основанием γ, являющимся порождающим элементом для G.
3.54 Замечание (обобщение GDLP) Более общая формулировка GDLP: даны конечная группа G и элементы , β  G, требуется найти целое x, такое, что ^x = , при условии, что такое целое существует. В такой формулировке не требуется, чтобы G была циклической группой, и, даже если это так,  не обязательно должен быть порождающим элементом для G. В общем случае, решение этой задачи сложнее, чем у задачи GDLP. Однако, если G циклическая группа (например, если G мультипликативная группа на конечное поле), и известна степень , то можно легко определить, существует ли целое x, отвечающее равенству ^x = . Это основывается на следующем факте: если G циклическая группа,  элемент порядка n из G, и   G, то целое x таково, что ^x = , существует тогда и только тогда, когда β ⁿ = 1.
3.55 Замечание (в сущности, решение DLP в циклической группе G порядка n - вычисление изоморфизма между G и Z_n) Даже если любые две циклические группы одного порядка изоморфны (то есть у них одинаковая структура несмотря на то, что элементы могут быть записаны по-разному), эффективность алгоритма для вычисления логарифмов в одной группе не обязательно означает его эффективность для другой группы. Чтобы это представить, заметим, что любая циклическая группа порядка n изоморфна аддитивной циклической группе Z_n, т.е. множеству целых чисел {0, 1, 2,… , n-1}, где групповые операции аддитивны по модулю n. Более того, задача дискретного логарифмирования в последней группе, а именно, задача нахождения целого x, такого, что ax  b (mod n) при заданных a, b  Z_n, проста, как показано ниже. Первое замечание: решение x не существует, если d = НОД(a, n) не делит b (утверждение 2.119).

Иначе, если d делит b, то для нахождения целых s и t таких, что as + nt = d может быть использован расширенный алгоритм Евклида (Алгоритм 2.107). Умножив обе части уравнения на целое b/d, получим a(sb/d) +n(tb/d) = b. Сокращение этого уравнения по модулю n дает a(sb/d)  b (mod n), и, следовательно, x = (sb/d) mod n искомое (и легко получаемое) решение.

Известные алгоритмы решения DLP могут быть сгруппированы следующим образом:

1. алгоритмы, работающие в произвольных группах, например, исчерпывающий поиск (§3.6.1), алгоритм маленьких и больших шагов (§3.6.2), Rho-алгоритм Полларда (§3.6.3);

2. алгоритмы, работающие в произвольных группах, но наиболее эффективны в группах с порядком, имеющим только маленькие простые коэффициенты, например, алгоритм Полига-Хеллмана (§3.6.4); и

3. алгоритмы с вычислением индексов (§3.6.5), которые эффективны только в определенных группах.
3.6.1 Исчерпывающий поиск

Наиболее очевидный алгоритм для GDLP (Определение 3.52) заключается в последовательном вычислении ⁰, ¹, ², … , пока не будет получено . Этот метод требует O(n) умножений, где n - порядок , и, следовательно, не эффективен при больших (т.е. представляющих интерес для криптографии) n.
3.6.2 Алгоритм маленьких и больших шагов

Пусть m = 

, где n - порядок . Алгоритм маленьких и больших шагов - это компромиссный по соотношению “память-время” вариант метода исчерпывающего поиска, он основан на следующем наблюдении. Если  = ^x, тогда можно записать x = im+j, где 0  i, j < m. Отсюда ^x = ^im^j, что означает  (^-^m)ⁱ = ^j. Предлагается следующий алгоритм для вычисления x.
3.56 Алгоритм Алгоритм маленьких и больших шагов для вычисления дискретных логарифмов

ВХОД: порождающий элемент  циклической группы G порядка n, и элемент   G.

ВЫХОД: дискретный логарифм x = log _α β.

Присвоить значение m  .

2. Построить таблицу с входами (j,  ^j) для 0  j <m. Упорядочить эту таблицу по второй компоненте. (Или, как вариант, использовать обычное хэширование по второй компоненте, чтобы сохранить входы в хэш-таблице; размещение входа и поиск его в таблице занимает постоянное время.)

3. Вычислить ^-^m и присвоить значение  .

4. По i от 0 до m - 1 выполнить следующее:

4.1 Проверить, не является ли оно второй компонентой какого-нибудь входа в таблице.

4.2 Если  =  ^j, то вернуть (x = im + j).

4.3 Присвоить    ^-^m.
Алгоритм 3.56 требует хранение O(

) элементов группы. Таблица требует O(

) умножений при создании, и O(

 lg n) сравнений для сортировки. При уже созданной таблице, шаг 4 требует O(

) умножений и O(

) обращений к таблице. Исходя из предположения, что умножение в группе занимает времени больше, чем lg n сравнений, время выполнения Алгоритма 3.56 можно указать более точно, как показано ниже.
3.57 Утверждение Время выполнения алгоритма маленьких и больших шагов (Алгоритм 3.56) - O(

) умножений в группе.
3.58 Пример (Алгоритм маленьких и больших шагов для логарифмов в Z*₁₁₃) Пусть p = 113. Элемент  = 3 порождающий элемент группы Z*₁₁₃ порядка n = 112. Положим  = 57. Тогда log₃ 57 вычисляется так.

1. Присвоить значение m  

 = 11.

2.Построить таблицу с входами (j;  ^j mod p) по 0  j <11:

j	0	1	2	3	4	5	6	7	8	9	10
3^jmod 113	1	3	9	27	81	17	51	40	7	21	63

и упорядочить таблицу по второй компоненте:

j	0	1	8	2	5	9	3	7	6	10	4
3^jmod 113	1	3	7	9	17	21	27	40	51	63	81

3. Используя алгоритм 2.142, вычислить  ^-1 = 3^-1 mod 113 = 38 и затем вычислить ^-^m = 38¹¹ mod 113 = 58.

4. Далее, вычисляется  =  ^-^mi mod 113 для i = 0, 1, 2, …, пока не получится значение во второй строке. Получаем:

I	0	1	2	3	4	5	6	7	8	9
 = 57 58ⁱmod 113	57	29	100	37	112	55	26	39	2	3

И, наконец, так как  ^-9^m = 3 = ¹,  =  ¹⁰⁰ , то log ₃ 57 = 100. □
3.59 Замечание (ограниченные экспоненты (restricted exponents)) Для увеличения эффективности некоторые криптографические протоколы, использующие возведение в степень в Z*_p, выбирают экспоненты определенного вида, например, с маленькой весовой функцией Хемминга. (Весовая функция Хемминга целого числа – число единиц в его двоичном представлении.) Если представить p, как k-битовое простое число, и использовать только экспоненты весовой функции Хемминга t. Число таких экспонент будет

. Алгоритм 3.56 может быть изменен для поиска экспоненты за время примерно равное

шагам. Алгоритм так же применим для экспонент, имеющих другие ограничения, и распространяется на все конечные группы.

1 2 3 4 5

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

Похожие: