Разработка и исследование параллельных алгоритмов анализа криптосистем, основанных на задаче дискретного логарифмирования

• Автор: Сидоров, Игорь Дмитриевич
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Таганрог
• Количество страниц: 194 с. : ил.

Введение.

1. Анализ известных методов дискретного логарифмирования

1.1. Появление асимметричной криптографии.

1.2. Асимметричные схемы, основанные на дискретном логарифмировании

1.2.1. Алгоритм обмена ключами ДиффиХеллмана.

1.2.2. Бесюиочевое шифрование МессиОмуры.

1.2.3. Алгоритм шифрования и подписи ЭльГамаля.

1.3. Задача дискретного логарифмирования

1.3.1. Задача ДЛ в общем виде.

1.3.2. Задача ДЛ в мультипликативной группе вычетов по модулю р.

1.3.3. Задача ДЛ в группе точек эллиптической кривой

1.4. Анализ методов дискретного логарифмирования
1.4.1. Полный перебор.
1.4.2. Метод Гельфонда
1.4.3. Встреча посредине
1.4.4. Метод Шенкса i
1.4.5. Метод Полларда.
1.4.5. Встреча на случайном дереве
1.4.6. Метод базы разложения
1.4.7. Метод решета числового поля
1.4.8. Выводы.
1.5. Используемые вычислительные средства.
1.5.1. Классификация параллельных архитектур
1.5.2. Интерфейс передачи сообщений I.
1.6. Оценка эффективности параллельных программ
1.6.1. Закон Амдала
1.6.2. Сетевой закон Амдала
1.7. Выводы
2. Разработка алгоритмов решения задачи дискретного логарифмирования в мультипликативной группе вычетов по модулю р.
2.1. Построение задачи дискретного логарифмирования заданной размерности.
2.2. Анализ методов базы разложения и решета числового поля
2.3. Разработка алгоритма параллельного просеивания
2.4. Разработка алгоритма параллельного гауссова исключения
2.5. Алгоритм решения сравнений по составному модулю.
2.6 Применение метода решета числового поля для произвольных основания и экспоненты.
2.7. Реализация метода базы разложения с помощью разработанных алгоритмов
2.8 Реализация метода решета числового поля с помощью разработанных алгоритмов.
2.9. Ускорение решения задачи дискретного логарифмирования с помощью нредвычислений.
2 Выводы.
3. Решение задачи дискретного логарифмирования в группе точек эллиптической кривой.
3.1. Построение задачи дискретного логарифмирования заданной размерности.
3.2. Анализ методов дискретного логарифмирования на эллиптической кривой.
3.3. Распределение базы точек между процессами.
3.4. Планирование взаимодействия процессов в топологии полносвязный граф
3.5. Разработка абстрактного типа данных и выбор структур данных для хранения точек эллиптической кривой.
3.6. Разработка параллельного алгоритма дискретного логарифмирования методом встречи посередине.
3.7. Разработка параллельного алгоритма дискретного логарифмирования методом встречи на случайном дереве
3.8 Возможность предвычислений.
3.9. Выводы.
4. Теоретическая и экспериментальная оценка эффективности разработанных алгоритмов
4.1. Теоретические оценки сложности субэкспоненциальных методов.
4.1.1. Оценка сложности метода базы разложения
4.1.2. Оценка сложности метода решета числового ноля
4.2. Теоретические оценки сложности экспоненциальных алгоритмов.
4.2.1. Оценка сложности метода встречи посередине.
4.2.2. Оценка сложности метода встречи на.случайном дереве
4.3. Аппаратные и программные средства, используемые в вычислительных экспериментах
4.3.1. Аппаратные средства.
4.3.2. Программные средства
4.4. Эффективность алгоритмов, используемых в библиотеках
4.4.1. Умножение целых чисел.
4.4.2. Возведение в степень
4.4.3. Нахождение НОД
4.4.4. Нахождение мультипликативного обратного элемента
4.5. Экспериментальные оценки эффективности субэкспоненциал ьных методов.
4.5.1. Определение эффективности распараллеливания.
4.5.2. Влияние размера задачи1 на время вычислений.
4.5.3. Определение влияния параметров алгоритмов на время вычислений.
4.6. Экспериментальные оценки эффективности экспоненциальных методов
4.6.1. Определение эффективности.распараллеливания.
4.6.2. Влияние размера задачи на время вычислений.
4.6.3. Влияние параметров алгоритмов на время вычислений.
4.7. Методики применения разработанных алгоритмов и программных реализаций .
4.7.1. Методика применения субэкспоненциальных алгоритмов
4.7.2. Методика применения экспоненциальных алгоритмов.
4.8. Оценки стойкости криптографических схем, основанных на задаче ДЛ
4.9. Выводы
Заключение.
Список использованных источников


В данной главе приводится постановка задачи дискретного логарифмирования, показывается важность этой задачи для современной асимметирочной криптографии, анализируются известные методы дискретного логарифмирования с точки зрения времени выполнения и возможности распараллеливания. Традиционная, симметричная криптография похожа на сейф с одним ключом. Только тот, кто запер сейф, может его отпереть. Если он хочет, чтобы сейф смог открыть ктото другой, необходимо решить проблему передачи ключа. Фактически, симметричная криптография подменяет большой секрет открытый текст малым ключом 3. В Уитфилд Диффи и Мартин Хеллман изменили эту парадигму криптографии 1. Они ввели понятие асимметричной криптографии криптографии с двумя ключами. Один из ключей называется открытым, и используется для шифрования сообщения. Этот ключ доступен всем желающим. Второй из ключей называется секретным, и должен храниться в тайне. Этот ключ используется для расшифрования сообщений. Криптография с открытым ключом больше похожа на конверт. Любой может положить письмо в конверт и опустить в почтовый ящик зашифровать с помощью открытого ключа. Прочитать же письмо может только владелец ключа от ящика секретного криптографического ключа3. Важность асимметричной криптографии состоит не только в том, что она решает проблему передачи ключей, остро стоящую для симметричной криптографии. С помощью средств асимметричной криптографии можно создавать и проверять электронные цифровые подписи ЭЦП. При этом обеспечивается аутентификация отправителя, проверка целостностиинеотрицание авторства . Стойкость асимметричных криптосистем, основана на. Рассмотрим некоторые израспространенных криптосхем,, основанных на задаче дискретного логарифмирования. Покажем, что стойкость этих схем напрямую определяется. Г,г. Г. Алгоритмобмена ключами ДиффиХсллмана . Алгоритм ДиффиХеллмана. Алиса и Боб выбирают два числа ,, называемые образующей и модулем При этом числа р и р1 2 должны быть простыми, образующей по модулю п. Эти условия нужны для обеспечения, корректности и . Хранить числа , в секрете не нужно. Xx р. Алиса вычисляет, общий. Легко видеть, что x р. Для взлома алгоритма Еве необходимо решить задачу дискретного логарифмирования, и по известным данным найти х или у. Строго говоря, задача восстановления х,у но известным X,,, носит название задачи ДиффиХеллмана, но иного способа решить е, кроме как произвести дискретное логарифмирование, не известно . Перед началом использования Алиса и Боб договариваются об использовании чисел ,. На эти числа накладываются те же ограничения, что и в алгоритме ДиффиХеллмана. На практике, для этого выбирается число еа, взаимно простое с р1, затем с помощью расширенного алгоритма Евклида находится . Аналогично пару , вырабатывает Боб. Боб вычисляет 2i р и отправляет Алисе. Боб вычисляет р. Корректность алгоритма доказать несложно. Для получения т4 исходное т возводится в степень р1. По малой теореме Ферма, 4. Для взлома алгоритма Еве необходимо решить задачу дискретного логарифмирования. Алгоритм ЭльГамаля был представлен в работах ,. Его можно использовать как для шифрования, так и для цифровой подписи. Для использования схемы выбирается число р так, чтори р1 2 простые числа. Далее выбирается образующая , и число х р1. Вычисляется x р. Числа ,, являются открытым ключом, х секретным ключом. При подписи сообщения алгоритмом ЭльГамаля случайным образом выбирается к и вычисляется р. Далее вычисляется Ъ, такое чтоОМхакЬ р1. Числа а,Ь являются подписью, к же должно храниться в секрете. Дняподписи различных сообщений необходимоиспользовать разные к. Для проверки подписи проверяется выполнение равенства р Если равенство выполняется, подпись верна. При шифровании с помощью алгоритма ЭльГамаля аналогично, случайным образом выбирается к, и вычисляются р, р. При. Принимающая сторона вычисляет р. Для взлома алгоритма, необходимо найти х дискретный логарифм у по основаниюи модулю. Для математической постановки задачи дискретного логарифмирования необходимо воспользоваться аппаратом одного из разделов дискретной математики теории групп. Определим, некоторые понятия, которые будут активно использоваться в дальнейшем ,. Существование единичного элемента. В множестве существует единичный элемент е такой, что еа ае адля любого а е .