📄Работа №45740
Тема: Исследование алгоритмов дискретного логарифмирования
Тип работы
Дипломные работы, ВКР
Предмет
информационная безопасность
Объем:
81 листов
Год:
2018
Просмотров:
499
4355
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 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
ПРИЛОЖЕНИЕ
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, а, следовательно, и о более стойких криптосистемах, основанных на этой задаче.
В случае алгоритмов решения DLP в мультипликативной группе вычетов по простому модулю, алгоритм baby - step giant - step находит дискретный логарифм медленнее, чем р - метод Полларда и алгоритм Index Calculus, однако является простым в реализации. Другой алгоритм, р - метод Полларда, для простых модулей, битовая длина которых не превосходила 40 бит, находил дискретный логарифм стабильно быстрее, чем алгоритм Index Calculus. Однако, после 40 бит, начался быстрый рост времени выполнения р - метода Полларда. В результате, для простых модулей с битовой длиной более 40 бит, лучшее время показывал алгоритм Index Calculus. Также время выполнения алгоритма Index Calculus росло не так резко, как у двух других. Кроме этого, были даны рекомендации об оптимальном выборе размера факторной базы и количества гладких чисел для данного алгоритма.
В случае решения ECDLP, алгоритм baby-step giant-step превзошел р - метод Полларда по скорости выполнения, что свидетельствует о вероятностном характере и нестабильности р - метода Полларда. Однако основной вывод заключается в том, что данные алгоритмы работают медленнее, чем их аналоги в мультипликативной группе вычетов по простому модулю. Это говорит о более стойкой задаче ECDLP, а, следовательно, и о более стойких криптосистемах, основанных на этой задаче.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.