Тип работы:
Предмет:
Язык работы:


ИССЛЕДОВАНИЕ АЛГОРИТМОВ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ

Работа №39080
Тип работыДипломные работы, ВКР
Предметинформационные системы
Объем работы93
Год сдачи2019
Стоимость6500 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 211
Не подходит работа?

Узнай цену на написание

ВВЕДЕНИЕ 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%.



1. Diffie W. New Directions in Cryptography [Текст] / W. Diffie, M. Hellman // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644-654. — ISSN 0018-9448 — doi:10.1109/TIT.1976.1055638
2. Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms [Текст] / T. Elgamal // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469-472. — ISSN 00189448 — doi:10.1109/TIT.1985.1057074
3. Mandy Zandra Seet. Elliptic curve cryptography. Improving the Pollard-Rho Algorithm [Текст] / Mandy Zandra Seet. - The University of New South Wales, 2007. - 93 с.
4. Musson, Matthew. Attacking the Elliptic Curve Discrete Logarithm Problem [Текст] / Matthew Musson. - Acadia University, 2006. - 154 c.
5. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance^e^T] / A. M. Odlyzko // LNCS. — 1984. — Т. 209. — С. 224—316.
6. Pohlig S. C. An Improved Algorithm for Computing Logarithms Over GF(p) and its Cryptographic Significance [Текст] / S. C. Pohlig, M. E. Hellman // IEEE Transactions on Information Theory. — 1978. — Vol. 1, no. 24. — P. 106110.
7. Pollard J. M. Monte Carlo methods for index computation (mod p). [Текст] / J. M. Pollard // Mathematics of Computation— 32 (143), 1978.—P. 918-924. — JSTOR 2006496
8. Shanks D. The infrastructure of a real quadratic field and its applications. [Текст] / D. Shanks // Proceedings of the Number Theory Conference. — University of Colorado, Boulder, 1972. — С. pp. 217-224.
9. Sipser, Michael. Section 10.6.3: One-way functions // Introduction to the Theory of Computation [Текст] / Michael Sipser. — PWS Publishing, 1997. — P. 374—376. — ISBN 0-534-94728-X.
10. Болотов А. А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы [Текст] / А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских. — М. : КомКнига,
2006. — С. 328. — ISBN 5-484-00443-8.
11. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии [Текст] / О. Н. Василенко. — Москва: МЦНМО, 2003. — 328 с. — ISBN 594057-103-4.
12. Виноградов И. М. Основы теории чисел [Текст] / И. М. Виноградов. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
13. Ишмухаметов Ш.Т. Математические основы защиты информации
[Текст] / Ш.Т. Ишмухаметов, Р.Г. Рубцова. - Казань: Казанский
государственный университет, 2012. - 138 с.
14. Коблиц Н. Курс теории чисел и криптографии [Текст] Пер. с англ. / Н. Коблиц — Москва: ТВПб, 2001. — 254 с. — ISBN 5-85484-014-6.
15. Крэндалл Р. Простые числа. Криптографические и
вычислительные аспекты [Текст] Пер. с англ. / Под ред. и с предисл. В.Н. Чубарикова. Р.Крэндалл, К. Померанс. - М.:УРСС: Книжный дом “ЛИБРОКОМ”, 2011. - 664с.
16. Нестеренко Ю. В. Глава 7. Первообразные корни и индексы // Теория чисел [Текст] / Ю. В. Нестеренко. — М.: «Академия», 2008. — 464 с.
17. Осипов Н. Н. Теория чисел. Конспект лекций [Текст]. / Н. Н. Осипов. — Красноярск: СФУ , 2008. — 117 с.
18. Панкратова И. А. Теоретико-числовые методы в криптографии: Учебное пособие [Текст] / И. А. Панкратова. — Томск: ТГУ, 2009.— 120 с.
19. Смарт Н. Криптография [Текст] Пер. с англ. / Под ред. С.К. Ландо. Н. Смарт. — Москва, ЗАО РИЦ «Техносфера» 2005. — 185-192 с.
20. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. [Текст] Пер. с англ. / Б. Шнайер. — М.: Триумф, 2002. — 816 с. — ISBN 5-89392-055-4.
21. Discrete logarithm records [Электронный ресурс]. - Режим доступа: URL: https://en.wikipedia.org/wiki/Discrete_logarithm_records (Дата обращения: 16.02.2019)
22. Коржев В. 8.08.2002. Цифровая подпись. Эллиптические кривые.
«Открытые системы» [Электронный ресурс]. - Режим доступа: URL: http ://www.morepc.ru/security/crypt/ os200207010.html (Дата обращения: 24.02.2019)
23. Дискретное логарифмирование [Электронный ресурс]. - Режим
доступа: URL: https://ru.wikipedia.org/wiki/Дискретное_логарифмирование
(Дата обращения: 13.03.2019)


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ