Введение 3
Глава 1. Анализ предметной области 5
1.1. Методы криптографии 5
1.2. Ассиметричные системы шифрования 5
1.3. Алгоритм Диффи-Хеллмана обмена ключами [16] 6
1.4. Система шифрования Эль-Гамаля [12] 8
1.5. Алгоритм RSA [24] 9
1.6. Задачи вычисления закрытого ключа при наличии открытого [11] 11
1.6.1. Дискретное логарифмирование в конечной группе [13] 12
1.6.2. Дискретное логарифмирование в группе точек эллиптической кривой 12
1.6.3. Факторизация чисел 12
Глава 2. Субэкспоненциальные алгоритмы 14
2.1. Метод Диксона 14
2.2. Метод квадратичного решета [1] 17
2.3. Метод Ленстры [4,5] 19
Глава 3. Реализация алгоритмов 22
Глава 4. Сравнение и анализ полученных результатов 26
Заключение 29
Список литературы 31
Приложение 1. Таблицы результатов 34
Приложение 2. Листинг
В современном мире в условиях глобальной информатизации компьютерные технологии имеют широкое распространение практически во всех сферах жизни человечества. В связи с этим одной из опасных угроз является угроза несанкционированного доступа к информации [25], и для противодействия этому применяются разные методы и средства, в частности, криптографическая защита данных.
Имеется два вида криптографических алгоритмов: симметричные [15], в которых один ключевой элемент довольно легко вычисляется при наличии второго, помимо этого быстро происходит преобразование данных, и несимметричные [10]. Их особенность - наличие двух ключей, при этом вычисление одного, если имеется другой, является вычислительно сложной задачей.
В качестве этих задач выступают:
1. задача дискретного логарифмирования [3,6] в группе точек эллиптической кривой;
2. задача дискретного логарифмирования в конечной группе (алгоритм Диффи-Хеллмана);
3. факторизация натуральных чисел (алгоритм шифрования RSA).
В настоящее время активно ведутся исследования в области алгоритмов факторизации. Факторизация натурального числа [2,4] - это его разложение на множители. Постоянно проводятся различные конференции по данной тематике, достигаются новые рекорды в поисках множителей, находятся решения текущих проблем теории чисел и ставятся новые. В двухтысячных годах было разложено 512-битное число. Прошло почти 10 лет (2009г.), и был установлен рекорд по разложению числа размером 768 бит с помощью метода
Дипломная работа посвящена сравнительному анализу методов факторизации натуральных чисел. Задача факторизации актуальна тем, что выступает основой ряда алгоритмов безопасности, использующих открытые ключи шифрования (RSA [27] и некоторые других). Криптостойкость шифров базируется на предположении, что не существует быстрых алгоритмов факторизации, которые за короткое время позволили бы взломать код, а если это и получится сделать через некоторое время, то данные потеряют актуальность.
В ходе работы были поставлены следующие задачи:
• рассмотреть алгоритмы факторизации натуральных чисел, имеющих
субэкспоненциальную сложность: алгоритм Диксона, метод
квадратичного решета, метод Ленстры [14];
• разработать программный комплекс, осуществляющий разложение чисел на простые множители данными алгоритмами;
• провести общую оценку методов;
• на основе полученных результатов выявить их преимущества и
недостатки.
В ходе дипломной работы были рассмотрены основные методы криптографии. Были изучены основные ассиметричные алгоритмы шифрования, такие как протокол Диффи-Хеллмана, схема шифрования Эль¬Гамаля и криптосистема RSA. Разобраны атаки, основанные на факторизации чисел. В частности, реализованы и проанализированы алгоритмы факторизации натуральных чисел, имеющих субэкспоненциальную сложность: алгоритм Диксона, метод квадратичного решета, метод Ленстры.
Проведены вычислительные эксперименты на числах разной размерности, на основе которых были выявлены преимущества и недостатки данных методов. Все три метода довольно быстро, за доли секунды, раскладывают числа малой размерности (до 32 бит). При этом каждый метод имеет свои особенности. Метод Ленстры при увеличении факторизуемого числа дольше вычисляет множители. Однако, если один из множителей сравнительно небольшой, разложение происходит быстрее. Метод квадратичного решета показывает хорошие результаты, близкие к методу Ленстры. Алгоритм Диксона требует гораздо больше времени на вычисления и сильно зависит от выбора матрицы, составленной из соответствующих векторов.
Существует немало различных методов факторизации, однако при определенной длине ключ имеет высокую стойкость к факторизации. Таким образом задача модификации текущих алгоритмов факторизации вполне актуальна. Кроме этого не менее актуальной стоит задача создания новых алгоритмов. Основные направления модификации - распараллеливание вычислительных задач (актуально к факторизации на эллиптических кривых), использование быстрых вычислений, оптимизация процесса вычислений, применение новых алгоритмов и другие. Из графиков и полученных выше результатов видно, что наиболее лучшими кандидатами для модификации являются метод Ленстры и метод квадратичного решета.
Исследование существующих в настоящее время методов факторизации позволит изучить, проанализировать и найти недостатки и вероятные пути улучшения существующих алгоритмов факторизации. При исследовании алгоритмов важно выделить особые блоки алгоритма и их модифицировать.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
