ВВЕДЕНИЕ 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, а, следовательно, и о более стойких криптосистемах, основанных на этой задаче.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
