🔍 Поиск готовых работ

🔍 Поиск работ

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

Работа №45740

Тип работы

Дипломные работы, ВКР

Предмет

информационная безопасность

Объем работы81
Год сдачи2018
Стоимость4355 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
484
Не подходит работа?

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


ВВЕДЕНИЕ 5
1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. Алгоритм Диффи - Хеллмана 6
1.2. Определение мультипликативной группы вычетов по модулюp ... 7
1.3. Определение задачи дискретного логарифмирования в
мультипликативной группе вычетов по модулю p 8
1.4. Алгоритмы для решения задачи дискретного логарифмирования в
мультипликативной группе вычетов по модулю p 8
1.5. Задача дискретного логарифмирования в группе точек
эллиптической кривой 9
1.6. Основы теории эллиптических кривых 10
1.7. Арифметика эллиптических кривых 12
1.8. Алгоритм Диффи - Хеллмана в группе точек эллиптической
кривой 15
1.9. Определение задачи дискретного логарифмирования в группе
точек эллиптической кривой 15
1.10. Алгоритмы для решения задачи дискретного логарифмирования
в группе точек эллиптической кривой 16
2. ПОСТАНОВКА ЗАДАЧИ 17
3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДИСКРЕТНОГОЛОГАРИФМИРОВАНИЯ В МУЛЬТИПЛИКАТИВНОЙ ГРУППЕ
ВЫЧЕТОВ ПО МОДУЛЮ p 18
3.1. Реализация вспомогательных структур данных и математических
функций 18
3.2. Baby-step giant-step 20
3.2.1. Реализация алгоритма 20
3.2.2. Обоснование алгоритма 21
3.2.3. Оценка сложности алгоритма 22
3.3. р - метод Полларда 22
3.3.1. Реализация алгоритма 22
3.3.2. Оценка сложности алгоритма 25
3.4. Index Calculus 25
3.4.1. Реализация алгоритма 25
3.4.2. Оценка сложности алгоритма 29
4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДИСКРЕТНОГО
ЛОГАРИФМИРОВАНИЯ В ГРУППЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ 31
4.1. Реализация вспомогательных структур данных и математических
функций 31
4.2. Baby-step giant-step 32
4.2.1. Реализация алгоритма 32
4.2.2. Обоснование алгоритма 33
4.2.3 Оценка сложности алгоритма 34
4.3. р - метод Полларда 34
4.3.1. Реализация алгоритма 34
4.3.2. Оценка сложности алгоритма 36
5. АНАЛИЗ РЕЗУЛЬТАТОВ 37
5.1. Baby - step giant - step DLP 38
5.2. р - метод Полларда DLP 39
5.3. Index Calculus DLP 41
5.4. Baby - step giant-step ECDLP 43
5.5. p - метод Полларда ECDLP 45
ЗАКЛЮЧЕНИЕ 48
СПИСОК ЛИТЕРАТУРЫ 49
ПРИЛОЖЕНИЕ

Впервые идею криптографии с открытым ключом предложили Уитфилд Диффи и Мартин Хеллман в 1976 году. До этого все секретные коммуникации совершались только на основе общего секретного ключа, который был заранее известен сторонам коммуникации и не передавался по каналу связи. Такие системы, в которых для шифрования сообщений используют общий секретный ключ, называются симметричными криптосистемами. Безопасность канала связи основывалась на том факте, что данный секретный ключ согласовывался между сторонами коммуникации в строжайшей секретности без передачи третьим лицам. Эти факторы привносили в данный подход практические сложности, например, когда коммуникация по закрытому каналу проходила между сторонами, находящимися на больших расстояниях. Криптография на основе открытого ключа, или асимметричная криптография, позволяет проводить секретную коммуникацию без предварительного обмена секретным ключом. В настоящее время криптосистемы с открытым ключом широко используются в современных алгоритмах и протоколах. Помимо генерации общего секретного ключа для обеспечения конфиденциального общения по открытому каналу связи, алгоритмы криптосистем с открытым ключом позволяют генерировать электронную подпись сообщений для подтверждения подлинности , а также шифровать данные. Асимметричные криптографические методы базируются на некоторой вычислительной задаче, трудноразрешимость которой гарантирует криптостойкость системы. В современной криптографии наиболее широко применяются две математические задачи: факторизация целого числа и задача дискретного логарифмирования (Discrete Logarithm Problem,далее - DLP). [6]

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В результате проделанной работы, были изучены и реализованы несколько алгоритмов дискретного логарифмирования в мультипликативной группе вычетов по простому модулю и в группе точек эллиптической кривой. Также был проведен сравнительный анализ, по результатам которого сформировался вывод о применимости различных алгоритмов на практике.
В случае алгоритмов решения DLP в мультипликативной группе вычетов по простому модулю, алгоритм baby - step giant - step находит дискретный логарифм медленнее, чем р - метод Полларда и алгоритм Index Calculus, однако является простым в реализации. Другой алгоритм, р - метод Полларда, для простых модулей, битовая длина которых не превосходила 40 бит, находил дискретный логарифм стабильно быстрее, чем алгоритм Index Calculus. Однако, после 40 бит, начался быстрый рост времени выполнения р - метода Полларда. В результате, для простых модулей с битовой длиной более 40 бит, лучшее время показывал алгоритм Index Calculus. Также время выполнения алгоритма Index Calculus росло не так резко, как у двух других. Кроме этого, были даны рекомендации об оптимальном выборе размера факторной базы и количества гладких чисел для данного алгоритма.
В случае решения ECDLP, алгоритм baby-step giant-step превзошел р - метод Полларда по скорости выполнения, что свидетельствует о вероятностном характере и нестабильности р - метода Полларда. Однако основной вывод заключается в том, что данные алгоритмы работают медленнее, чем их аналоги в мультипликативной группе вычетов по простому модулю. Это говорит о более стойкой задаче ECDLP, а, следовательно, и о более стойких криптосистемах, основанных на этой задаче.



1. England, Matthew. Elliptic curve cryptography [Текст] / Matthew England - Heriot-Watt University, 2006. - 175 c.
2. Galbraith, Steven. Mathematics of Public Key Cryptography [Текст] / Steven Galbraith - Cambridge University Press, 2012. - 608 c.
3. Hoffstein, Jeffrey. An Introduction to Mathematical Cryptography [Текст] / Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. - Springer, 2008. - 530 с.
4. Howell, Jason S. The Index Calculus Algorithm for Discrete Logarithms [Текст] / Jason S. Howell - Clemson University, 1998. - 99 c.
5. Mandy Zandra Seet. Elliptic curve cryptography. Improving the Pollard- Rho Algorithm [Текст] / Mandy Zandra Seet - The University of New South Wales, 2007. - 93 с.
6. Maurits, Luke. Public Key Cryptography Using Discrete Logarithms in Finite Fields: Algorithms, Efficient Implementation and Attacks [Текст] / Luke Maurits. - The University Of Adelaide, Australia, 2006. - 103 с.
7. Musson, Matthew. Attacking the Elliptic Curve Discrete Logarithm Problem [Текст] / Matthew Musson. - Acadia University, 2006. - 154 c.
8. Washington, C. Lawrence. Elliptic Curves. Number Theory and Cryptography. Second Edition [Текст] / Lawrence C. Washington. - University of Maryland, 2008. - 524 с.
9. Акритас, А. Основы компьютерной алгебры с приложениями [Текст] / А. Акритас; пер. с англ. Е.В. Панкратьев. - М.: изд-во “Мир”, 1994. - 544 c.
10. Болотов, А.А. Алгоритмические основы эллиптической криптографии [Текст] / А.А.Болотов и др. - Москва, Вильямс, 2004. - 499 c.
11. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии [Текст] / О.Н.Василенко. - М.: МЦНМО, 2003. - 328 с.
12. Винберг, Э.Б. Курс алгебры [Текст] / Э.Б. Винберг - М.: Изд-во “Факториал Пресс”, 2001. - 544 c.
13. Ишмухаметов, Ш.Т. Математические основы защиты информации [Текст] / Ш.Т. Ишмухаметов, Р.Г. Рубцова - Казань: Казанский государственный университет, 2012. - 138 с.
14. Крэндалл, Р. Простые числа. Криптографические и вычислительные аспекты [Текст]: Пер. с англ. / Под ред. и с предисл. В.Н. Чубарикова. Р. Крэндалл, К. Померанс. - М.:УРСС: Книжный дом “ЛИБРОКОМ”, 2011. - 664 с.
15. Панкратова И.А. Теоретико-числовые методы в криптографии [Текст] / И.А. Панкратова - Томск: Томский государственный университет, 2009. - 120 с.
16. Рябко.Б.Я. Криптографические методы защиты информации. Учебное пособие [Текст] / Б.Я. Рябко, А.Н. Фионов - М.: Горячая линия - Телеком, 2005. - 229 с.
17. Cryptography/ Prime Curve/ Standard Projective Coordinates
[Электронный ресурс]. - Режим доступа: URL:
https: //en.wikibooks. org/wiki/Cryptography/Prime_Curve/Standard_Proj ective_Co ordinates. (04.03.2011)
18. Discrete logarithm in GF(p) 768 bits [Электронный ресурс]. Режим доступа: URL: https: //listserv.nodak.edu/cgi- bin/wa.exe?A2=NMBRTHRY;a0c66b63.1606. (16.06.2016)
19. Elliptic Curve Cryptography: breaking security and a comparison with
RSA [Электронный ресурс]. - Режим доступа: URL:
http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/.(08.06.2015)
20. Алгоритм Гельфонда - Шенкса [Электронный ресурс]. - Режим
доступа: URL: ru.wikipedia.org/wiki/Алгоритм_Гельфонда_— Шенкса.
(04.03.2018)
21. Дискретное логарифмирование [Электронный ресурс]. - Режим
доступа: URL: ги.’№1к1реШа.огд/’№1к1/Дискретное_логарифмирование.
(0.05.2018)
22. Сравнение по модулю [Электронный ресурс]. - Режим доступа: URL: ги.’№1к1реШа.огд/’№1к1/Сравнение_по_модулю. (30.05.2018)
23. Хеш - таблица [Электронный ресурс]. - Режим доступа: URL: ru.wikipedia. org/wiki/Хеш-таблица. (17.02.2018)


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



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


©2025 Cервис помощи студентам в выполнении работ
.