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



страница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*97 циклическая группа порядка n = 96. α = 5 - порождающий элемент группы Z*97. Так как 532  35 (mod 97), log 5 35 = 32 в Z*97.
Ниже приведены некоторые простые сведения, касающиеся логарифмов.
3.50 Утверждение Пусть α порождающий элемент циклической группы G порядка n, и пусть β, γG. Пусть s целое число. Тогда log α (βγ ) = (log α β + log α γ) mod n и log α (βs ) = s log α β mod n.

Наиболее важными в криптографии являются мультипликативная группа F*q конечного поля Fq (§2.6), включая частные случаи мультипликативной группы Z*p целых чисел по модулю простого p, и мультипликативная группа F*2m конечного поля F2m второй характеристики. Также интересны группа отдельно взятых 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  xn  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 α γ)-1 mod n.

Это означает, что любой алгоритм, вычисляющий логарифмы по основанию , может быть использован для вычисления логарифмов с любым другим основанием γ, являющимся порождающим элементом для G.
3.54 Замечание (обобщение GDLP) Более общая формулировка GDLP: даны конечная группа G и элементы , β G, требуется найти целое x, такое, что x = , при условии, что такое целое существует. В такой формулировке не требуется, чтобы G была циклической группой, и, даже если это так,  не обязательно должен быть порождающим элементом для G. В общем случае, решение этой задачи сложнее, чем у задачи GDLP. Однако, если G циклическая группа (например, если G мультипликативная группа на конечное поле), и известна степень , то можно легко определить, существует ли целое x, отвечающее равенству x = . Это основывается на следующем факте: если G циклическая группа,  элемент порядка n из G, и G, то целое x таково, что x = , существует тогда и только тогда, когда β n = 1.
3.55 Замечание (в сущности, решение DLP в циклической группе G порядка n - вычисление изоморфизма между G и Zn) Даже если любые две циклические группы одного порядка изоморфны (то есть у них одинаковая структура несмотря на то, что элементы могут быть записаны по-разному), эффективность алгоритма для вычисления логарифмов в одной группе не обязательно означает его эффективность для другой группы. Чтобы это представить, заметим, что любая циклическая группа порядка n изоморфна аддитивной циклической группе Zn, т.е. множеству целых чисел {0, 1, 2,… , n-1}, где групповые операции аддитивны по модулю n. Более того, задача дискретного логарифмирования в последней группе, а именно, задача нахождения целого x, такого, что ax b (mod n) при заданных a, bZn, проста, как показано ниже. Первое замечание: решение 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) заключается в последовательном вычислении 0, 1, 2, … , пока не будет получено . Этот метод требует O(n) умножений, где n - порядок , и, следовательно, не эффективен при больших (т.е. представляющих интерес для криптографии) n.
3.6.2 Алгоритм маленьких и больших шагов

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

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

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

  1. Присвоить значение 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*113) Пусть p = 113. Элемент  = 3 порождающий элемент группы Z*113 порядка n = 112. Положим = 57. Тогда log3 57 вычисляется так.

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

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


j

0

1

2

3

4

5

6

7

8

9

10

3j mod 113

1

3

9

27

81

17

51

40

7

21

63


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


j

0

1

8

2

5

9

3

7

6

10

4

3j mod 113

1

3

7

9

17

21

27

40

51

63

81


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

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


I

0

1

2

3

4

5

6

7

8

9

 = 57 58i mod 113

57

29

100

37

112

55

26

39

2

3


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

Похожие:

Задача дискретного логарифмирования iconМетоды факторизации и дискретного логарифмирования
Учебный курс предназначен для студентов специальности 1-31 03 01-01 «математика (научно-производственная деятельность)». Для понимания...
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛабораторная работа №2 Транспортная задача
Транспортная задача (Задача Монжа — Канторовича) — задача об оптимальном плане перевозок продуктов из пунктов отправления в пункты...
Задача дискретного логарифмирования iconЗадача 1 Задача 2 Медицина. Задача 3 Основные понятия моделирования
Модель — это некоторое упрощенное подобие реального объекта, явления или процесса
Задача дискретного логарифмирования iconЭкзаменационные вопросы Понятие математической модели. Инструментальные переменные и параметры математической модели. Критерий оптимизации и целевая функция
Математические модели простейших экономических задач: задача использования сырья, задача о диете; задача планирования товарооборота;...
Задача дискретного логарифмирования iconКомплексный анализ
Автор: д-р физ мат наук, профессор, зав кафедрой дискретного анализа Бондаренко В. А
Задача дискретного логарифмирования iconЗадача на границах периодической системы 3 Задача кот шредингера и химия 4
Задача 22. Необычные пути окисления жирных кислот: омега- и (омега-1)-окисление 42
Задача дискретного логарифмирования iconЗадача №1. Вычислить определитель четвертого порядка Задача №2. Даны матрицы А, В, с и числа  и 
Задача № Для данной матрицы найти обратную и убедиться, что обратная матрица найдена правильно
Задача дискретного логарифмирования iconЗадача №1: получение данных 6 Задача №2 модели и программное обеспечение управления добычей 7
Задача №3 Переход к технологиям облачных вычислений в задачах связанных с «интеллектуальным месторождением». Высокопроизводительные...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org