ВВЕДЕНИЕ 4
1. Анализ предметной области 7
1.1. Определение задачи дискретного логарифмирования 7
1.2. Понятие мультипликативной группы кольца вычетов по модулю р.... 9
1.3. Задача дискретного логарифмирования в мультипликативной группе
кольца вычетов по модулю р 11
1.4. Алгоритмы дискретного логарифмирования в мультипликативной
группе кольца вычетов по модулю простого числа 12
1.5. Задача дискретного логарифмирования в группе точек эллиптической
кривой над конечным полем 13
1.6. Теория эллиптических кривых над конечными полями 14
1.7. Практические арифметические алгоритмы для эллиптических
кривых 18
1.8. Практическое значение ECDLP на примере алгоритма ECDSA 21
1.9. Алгоритмы дискретного логарифмирования в группе точек
эллиптической кривой над конечным полем 22
2. Алгоритмы дискретного логарифмирования мультипликативной группе
кольца вычетов по простому модулю 24
2.1. Алгоритм Гельфонда-Шенкса 24
2.2. p-метод Полларда 27
2.3. Алгоритм Полига-Хеллмана 30
2.4. Алгоритм исчисления порядка 33
3. Алгоритмы дискретного логарифмирования в группе точек
эллиптической кривой над конечным полем 40
3.1. Алгоритм Гельфонда-Шенкса для ECDLP 40
3.2. р —метод Полларда для ECDLP
3.3. Реализация алгоритмов для ECDLP 43
4. Экспериментальная часть и анализ полученных результатов 46
4.1. Модуль генерации простых чисел 46
4.2. Модуль тестирований 47
4.3. Алгоритм Гельфонда-Шенкса и р —метод Полларда 49
4.4. Алгоритм Полига-Хеллмана 51
4.5. Алгоритм исчисления порядка 53
4.6. Тестирование размеров потребляемой памяти алгоритмами DLP 57
4.7. Тестирование скорости работы алгоритмов ECDLP 59
4.8. Тестирование размеров потребляемой памяти алгоритмами ECDLP . 61
4.9. Модифицированные реализации алгоритмов дискретного
логарифмирования 62
ЗАКЛЮЧЕНИЕ 68
СПИСОК ЛИТЕРАТУРЫ 70
ПРИЛОЖЕНИЕ 73
Основы асимметричной криптографии были заложены в 1976 году Уитфилдом Диффи и Мартином Хеллманом в их работе «Новые направления в современной криптографии».
В асимметричных криптосистемах, в отличие от симметричных, применяются разные ключи для шифрования и дешифрования: открытый и закрытый. Открытый ключ передаётся по условно открытому незащищённому каналу и используется для шифрования сообщения, а для расшифровки сообщения используется закрытый ключ. В схемах электронной цифровой подписи (ЭЦП) с помощью закрытого ключа генерируется сама подпись, а открытый ключ необходим для проверки её подлинности. Открытый ключ находится в свободном доступе и может быть известен всем, закрытый же ключ должен быть известен только владельцу. При этом два отличающихся асимметричных ключа всегда связаны между собой математически. [20] В основе этой связи лежит предположение о существовании односторонних функций.
Односторонней или трудно обратимой функцией называется математическая функция /, для которой существует алгоритм, вычисляющий у = f (х) за полиномиальное время, однако задача нахождения прообраза х = /-1(у) является вычислительно сложной, т.е. не существует алгоритма значительно эффективнее полного перебора.
Существование трудно обратимых функций не доказано. Доказательство их существования подтвердит неравенство классов Р Ф N (что следует из определения односторонних функций). Стоит заметить, что обратное утверждение неверно: неизвестно, следует ли из РФ NP существование односторонних функций.
Одним из возможных кандидатов в односторонние функции является дискретное экспоненцирование. Несмотря на отсутствие доказательства труднообратимости данной функции, обширные исследования в данной области пока не привели к обнаружению эффективного обратного алгоритма.
Дискретное экспоненцирование - возведение некоторого а в степень х 6 [0, р — 1] и взятие остатка по модулю р, где р - простое число. [19]
Оно используется во многих схемах асимметричного шифрования и электронной цифровой подписи, в частности в таких как:
- протокол Диффи-Хеллмана;
- схема Эль-Гамаля;
- ECDSA;
- ГОСТ Р 34.10-2012;
- схема Шнорра;
- протокол Мэсси-Омуры.
Обращение функции дискретного экспоненцирования приводит нас к задаче дискретного логарифмирования (Discrete Logarithm Problem).
Современная асимметричная криптография базируется на высокой сложности дискретного логарифмирования. Для взлома многих
ассиметричных схем или подделки цифровой подписи необходимо решить данную задачу, что делает актуальным исследование алгоритмов дискретного логарифмирования. Их изучение и оценка эффективности с точки зрения скорости работы и затрат памяти способствует развитию этой области исследований и предоставляет сведения о возможных способах дополнительной защиты от взлома подобным образом.
Целью данной работы является исследование алгоритмов дискретного логарифмирования путём решения следующих задач:
-изучение задачи дискретного логарифмирования;
-изучение алгоритмов дискретного логарифмирования в мультипликативной группе кольца вычетов по простому модулю р (для краткости далее - алгоритмы DLP): алгоритм Гельфонда-Шенкса, р —метод Полларда, алгоритм Полига-Хеллмана, алгоритм исчисления порядка, а также их программная реализация;
- изучение алгоритмов дискретного логарифмирования в группе точек эллиптической кривой над конечным полем (для краткости далее - алгоритмы ECDLP): алгоритм Гельфонда-Шенкса, р —метод Полларда, а также их программная реализация;
-генерация наборов входных данных, удовлетворяющих требованиям алгоритмов, и проведение тестирования скорости работы и затрат памяти реализованных алгоритмов;
-проведение сравнительного анализа полученных на практике результатов, построение графиков;
-предложение возможной модификации изученных алгоритмов
В ходе данной работы были изучены различные алгоритмы для решения задачи дискретного логарифмирования в мультипликативной группе кольца вычетов по простому модулю и в группе точек эллиптической кривой над конечным полем, выполнена их программная реализация, было проведено тестирование скорости работы в зависимости от битовой длины модуля р, экспериментальное исследование потребляемых ими размеров памяти. В завершение был проведен сравнительный анализ результатов, полученных в ходе тестирования алгоритмов, и предложены варианты модификации нескольких алгоритмов.
Полученные результаты подтверждают теоретические оценки сложности алгоритмов. Однако, на практике, несмотря на одинаковую оценку, р —метод Полларда оказался быстрее алгоритма Гельфонда-Шенкса. Отчасти это можно объяснить тем, что все операции в оценке сложности р —метода являются простыми и сводятся к сложению, умножению, и сокращению по модулю, тогда как в алгоритме Гельфонда -Шенкса происходит построение большой структуры данных- хеш-таблицы, и поиск в ней по ключу. Конечно, ожидаемое время поиска в хеш-таблице 0(1), однако в худшем случае эта величина равна 0(п2).
Алгоритм Полига-Хеллмана оказался неэффективен для решения задачи DLP, если модуль р не удовлетворяет условию: р — 1 = nf=i 4iai, где все простые ^ достаточно малы (на практике выяснено: не превосходят 15- 20 бит в длину). Но при удовлетворении модуля данному условию алгоритм работает за полиномиальное время, что обязывает проверять отсутствие подобного разложения при генерации данных в криптографических схемах.
Вероятностный алгоритм исчисления порядка с субэкспоненциальной оценкой сложности оказался неэффективен при вычислениях по модулю малой битовой длины, однако при длине от 51-53 бит его использование будет целесообразнее экспоненциальных р —метода Полларда и алгоритма Гельфонда-Шенкса вследствие более медленного роста времени работы в зависимости от размера модуля мультипликативной группы кольца вычетов. В рамках проведенных вычислений были найдены наиболее универсальные значения задаваемых входных параметров алгоритма: размер факторной базы в 140 чисел, коэффициент надёжности равный 2.
Для задачи ECDLP алгоритм Гельфонда-Шенкса оказался эффективнее р —метода Полларда, в отличие от задачи DLP, а также была наглядно продемонстрирована разница в сложности этих двух задач (первая значительно сложнее) и приведено обоснование данной разницы.
С точки зрения памяти лишь один алгоритм можно считать неэффективным: алгоритм Гельфонда-Шенкса для DLP. Все остальные алгоритмы DLP и ECDLP имеют малые медленно растущие в зависимости от битовой длины модуля р затраты памяти, которые, учитывая возможности современных компьютеров, можно не учитывать, рассматривая возможность применения того или иного алгоритма. Кроме того, в ходе экспериментов в алгоритме Г ельфонда-Шенкса для ECDLP была обнаружена интересная зависимость размера хеш-таблицы baby steps от битовой длины модуля р, которую можно выразить следующей формулой: s = I — 2 + l(mod2), где I- длина в битах модуля р, s- число пар значений в хеш-таблице. Данный факт предоставляет возможность для дальнейших исследований. На его основе был предложен модифицированный вариант алгоритма Гельфонда-Шенкса для ECDLP с условием по вышеозначенной формуле на этапе построения хеш-таблицы, оказавшийся в среднем быстрее обычного на 19,5%. На всех измерениях дискретные логарифмы, выданные алгоритмами по завершении работы, совпадали.
Также были представлены распараллеленные версии алгоритмов Гельфонда-Шенкса и исчисления порядка для задачи DLP. Выигрыш по скорости для первого составил 20%, для второго- 29,5%.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
