Размещено на http://www.allbest.ru/

Оглавление

• Введение
• 1. Детерминированные методы дискретного логарифмирования
• 2. С-метод Полларда для дискретного логарифмирования
• 3. Дискретное логарифмирование в простых полях
• 4. Алгоритм исчисления порядка (index-calculus algorithm)
• 5. Реализация метода с-метод Полларда
• Заключение
• Библиографический список

Задача дискретного логарифмирования применяется во многих алгоритмах криптографии с открытым ключом. Предложенная в 1976 году У. Диффи (W. Diffie) и М. Хеллманом (М. Hellman) для установления сеансового ключа, эта задача послужила основой для создания протоколов шифрования и цифровой подписи, доказательств с нулевым разглашением и других криптографических протоколов.

Следует отметить, что в криптографии эта задача возникла еще в 1950-х годах, когда вместо роторных машин стали использоваться регистры сдвига, и нужно было определить место конкретного элемента в данной последовательности сдвигов.

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

Ее решение х называется дискретным логарифмом элемента b по основанию а и обозначается , если основание фиксировано и если решение существует;

, если .

Рассмотрим уравнение:

(1)

в группе , где р - простое число. Пусть порядок равен . Тогда уравнение (1) разрешимо, и решение х является элементом . Безопасность соответствующих криптосистем основана на том, что, зная числа а, х, р вычислить легко (например, алгоритмом В-арного возведения в степень), а решить задачу дискретного логарифмирования трудно.

Рассмотрим некоторые методы решения этой задачи.

Методом перебора можно решить поставленное уравнение за арифметических операций.

Решение уравнения можно находить по формуле:

Однако сложность вычисления по этой формуле хуже, чем для метода перебора.

Алгоритм согласования имеет сложность:

.

1 этап. Присваиваем:

.

2 этап. Находим:

.

3 этап. Составляем и упорядочиваем таблицу значений:

,

4 этап. Составляем и упорядочиваем таблицу значений:

,

5 этап. Находим совпавшие элементы из полученных таблиц, для которых:

,

.

6 этап.

.

Предположим, что известно разложение на простые множители:

Тогда решение уравнения можно найти за:

арифметических операций с помощью алгоритма Полига-Хеллмана:

1 этап. Для каждого простого числа , составляем таблицу чисел:

.

2 этап. Для каждого простого , находим . Пусть:

,

где .

Тогда из (1) следует, что:

.

С помощью таблицы, полученной на первом шаге, находим .

Тогда выполнено сравнение:

.

По таблице находим , и т.д.. Значение находится из сравнения:

.

3 этап. Найдя , находим по китайской теореме об остатках.

Рассмотрим три числовые последовательности . определенные следующим образом:

;

Под понимаем наименьший неотрицательный вычет в данном классе вычетов. дискретное логарифмирование метод криптография

Далее рассматриваются наборы и ищем номер i, для которого . Из последнего равенства:

Если , то получим:

.

Откуда искомый х равен:

.

Эвристическая оценка сложности метода составляет операций.

Дано:

Тогда .

Разбиение на подмножества произведем следующим образом: если , то , если , то , если , то .

. Логарифм найдем из сравнения:

.

.

.

.

.

Действительно, .

Ответ: .

В данном параграфе мы рассмотрим алгоритмы решения уравнения:

.

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

Первый такой алгоритм предложил Адлеман.

1 этап. Сформировать факторную базу, состоящую из всех простых чисел:

.

2 этап. С помощью некоторого перебора найти натуральные числа - такие, что:

.

Отсюда следует, что:

. (2)

3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных - дискретных логарифмов элементов факторной базы.

4 этап. С помощью некоторого перебора найти одно значение , для которого:

где - простые числа "средней" величины, т. е. ,

где - также некоторая субэкспоненциальная граница,

5 этап. С помощью вычислений, аналогичных 2 и 3 этапам алгоритма, найти дискретные логарифмы для фиксированных простых чисел средней величины из 4 этапа.

6 этап. Определить искомый:

.

4. Алгоритм исчисления порядка (index-calculus algorithm)

Основные идеи алгоритма исчисления порядка были известны с 20-х годов XX века, но лишь в 1979 году Адлерман указал на этот алгоритм как на средство вычисления дискретного логарифма и исследовал его трудоемкость. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах, в частности, в группе Zp*.

Этот алгоритм в отличие от алгоритмов прямого поиска и ро-метода подходит не для всех циклических групп.

Алгоритм исчисления порядка.

Вход: - порождающий элемент циклической группы порядка - параметр надежности.

1 этап. Выбирается факторная база . (Если, то состоит из первых простых чисел.)

2 этап. Выбрать случайное и вычислить .

3 этап. Попытаться разложить по факторной базе:

.

Если это не удалось, вернуться на 2 этап.

4 этап. Логарифмируя обе части получившегося выражения, получаем:

. (3)

Это сравнение с неизвестными следует запомнить.

5 этап. Если сравнений вида (3), полученных на 4 этапе, меньше, чем , то вернуться на этап 2.

6 этап. Решить систему сравнений с неизвестными вида (3), составленную на этапах 2-5.

7 этап. Выбрать случайное и вычислить .

8 этап. Попытаться разложить по факторной базе:

.

Если это не удалось, вернуться на 7 этап.

9 этап. Логарифмируя обе части последнего равенства, получаем:

.

где вычислены на этапе 6 как решение системы сравнений.

Выход:

.

В том случае, когда , в качестве факторной базы берут первых простых чисел. Такой выбор оправдан следующим наблюдением. Число, наугад выбранное из множества целых чисел, с вероятностью 1/2 делится на 2, с вероятностью 1/3 - на 3, с вероятностью 1/5 - на 5 и т.д. Поэтому можно ожидать, что в промежутке от 1 до найдется достаточно много чисел, в разложении которых участвуют только маленькие простые делители из множества . Именно такие числа отыскиваются на шагах 2 и 7.

Параметр c вводится для того, чтобы система сравнений, решаемая на 6 этапе, имела единственное решение. Дело в том, что полученная система может содержать линейно зависимые сравнения. Считается, что при значении с порядка 10 и большом p система сравнений имеет единственное решение с высокой вероятностью.

def pollard(g,a,p):

# g^x = a mod p

n = EulerPhi(p) # функция Эйлера дает возможность работать не только с простыми р

while(x1!= x2 or start):

u = mod(a1 - a2, n)

v = mod(b2 - b1, n)

while(i!= (d + 1)):

g^(u*nu) = a^(v*nu) = a^(d - n*nu) = a^(d) = g(x*d) mod p

x = ((u * nu + w * n)/d) %n

if ((g**x - a) % p == 0):

print 'x=', x.

def mod(a,b):

Функция добавлена для наглядности кода. Возвращает остаток от деления а на b

return a % b

Нахождение наибольшего общего делителя (НОД) алгоритмом Евклида (рекурентной формулой).

х и y полезны для нахождения обратных элементов в кольце вычетов

return a, 1, 0

d1, x1, y1 = ExtenedGCD(b, mod(a, b))

d, x, y = d1, y1, x1 - (a/b)*y1

Функция Эйлера, возвращает количество натуральных чисел, небольших n и взаимно простых с ним

while(input % i == 0):

if (p!= 0):

n = input - 1

return n * res.

Дискретный логарифм составляет основу целого ряда алгоритмов криптографии. Дискретный логарифм широко применяется в:

1) криптосистеме с открытым ключом по Диффи-Хеллману;

1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2003. - 328 с.

2. Маховенко Е.Б. Теоретико-числовые методы в криптографии: учебное пособие /Е.Б. Маховенко. - М: Гелиос АРВ, 2006. 320 с., ил.

3. Алгоритмы. Построение и анализ. (Т. Кормен, Ч. Лейзер, Р. Ривест, К. Штайн). 2006 г. 2 издание.

4. http://ru.wikiversity.org/wiki/Программирование_и_научные_вычисления_на_языке_Python.