ВВЕДЕНИЕ 3
Глава 1. Исследование предметной области 5
1.1. Основные определения и понятия 5
1.2. RSA 7
1.2.1. Тест Миллера-Рабина 9
1.2.2. Уязвимости 11
1.3. Частотный анализ 13
1.4. Квадратичное решето 16
1.5. Атака Хастада 18
1.6. Атака Винера 19
Глава 2. Разработка программы 20
2.1. Средства реализации 20
2.2. Класс RSA и MR 22
2.3. Класс FrequencyAnalysis 24
2.4. Класс QuadraticSieve 26
2.5. Создаваемые файлы в ходе работы. 27
2.6. Класс Hastad 29
2.7. Класс Wiener 29
Глава 3. Результаты исследования 30
3.1. Частотный анализ 30
3.2. Факторизация методом квадратичного решета 32
3.3. Атака Хастада 36
3.4. Атака Винера 40
ЗАКЛЮЧЕНИЕ 43
СПИСОК ЛИТЕРАТУРЫ 44
ПРИЛОЖЕНИЕ
Учитывая то, что в криптографические методы защиты информации играют важную роль, а развитие математики и технологий в целом приносит, как новые способы шифрования, так и новые способы взломы этих шифров. При разработке любой системы шифрования следует детально изучать любую возможность взлома.
В 1977 году благодаря трем ученым: Рональду Ривесту, Ади Шамиру и Леонарду Адлеману появился метод RSA — самый известный представитель криптографических алгоритмов, так как является основоположником систем шифрования с открытым ключом и применяется в различных криптографических приложениях. Для любого алгоритма шифрования является закономерным вопрос о его надежности, целесообразности использования и формировании требований к нему.
Что очевидно, со временем требования к криптографическим алгоритмам не становятся мягче, поскольку вычислительные мощности растут, а это значит, что появляется возможность решать те задачи, на которые раньше не хватало ресурсов. На одной из таких задач и построена надежность алгоритма RSA, а именно, на факторизации чисел. То есть на разложении составного полупростого числа на его множители. В основе алгоритма лежит генерация простых чисел р и q и вычисление их произведения п. Число п будет называться полупростым числом, так как имеет представление в виде произведения двух простых чисел.
На данный момент существует ряд требований для алгоритма:
1. Простые числа p и q должны состоять более, чем из 512 бит.
2. Простые числа p и q не должны быть близкими.
3. Недопустимо использование посимвольного шифрования.
Шифруются блоки.
Среди множества алгоритмов факторизации натуральных чисел, таких как перебор делителей, метод Ферма, алгоритм Полларда, алгоритм Диксона и.т.д. особое место занимает метод квадратичного решета, так как он долгое время считался самым лучшим субэкспоненциальным методом факторизации.
Целью данной выпускной квалификационной работы является проверка актуальных требований к алгоритму шифрования RSA, где для подтверждения целесообразности использования блочного шифрования будет применен частотный криптоанализ, а для требований к генерации полупростых чисел будет применен алгоритм квадратичного решета. Объектом исследования является алгоритм шифрования RSA.
Для достижения указанной цели, решаются следующие задачи:
1. Изучение материалов, относящихся к объекту исследования.
2. Реализация алгоритма RSA с возможностью настройки соответствующих параметров для тестирования атак.
3. Изучение материалов связанных с частотным криптоанализом.
4. Реализация и применение частотного анализа.
5. Изучение материалов, связанных с методами факторизации.
6. Реализация и применение квадратичного решета.
7. Изучение материалов, связанных с атакой Хастада и Винера.
8. Реализация и применения этих атак.
Актуальность работы связана с тем, что существуют такие системы, где RSA активно применяется, а соответственно при несоблюдении современных требований и своевременном адаптировании под них появляется риск снижения надежности данного способа шифрования.
В ходе изучения и реализации частотного анализа были получены результаты, как для сгенерированного текста, так и для текста реального человека.
Применение частотного анализа для первого случая показало неудовлетворительные результаты, т.к. распределение символов для такого текста далеко от того, что занесено в частотную таблицу алфавита.
В случае с настоящим текстом результаты иные. Несмотря на то, что график не является строго возрастающим при шаге в 200 символов, начиная с 5800 символов, количество правильно определенных не опускается ниже 11. Таким образом, можно сказать, что с увеличением размерности текста при применении частотного анализа мы будем получать лучшие результаты.
В ходе изучения и реализации квадратичного решета были получены такие параметры для формирования факторной базы, при которых достигается максимальная скорость на рассматриваемом нами отрезке.
При использовании атаки Хастада мы выяснили, что недопустимо использование малых значений открытой экспоненты. А для больших значений процесс атаки вообще может быть невозможен.
При рассмотрении атаки Винера были получены достаточно хорошие результаты для атакующей стороны, что означает соблюдения условия d > 1 1
- П4 должно всегда выполняться для безопасного использования шифрования RSA.
Что касается вопроса об актуальности текущих требований шифрования, то при правильной реализации на сегодняшний день не стоит беспокоиться о безопасности данных. При факторизации числа размерностью более 100 бит процесс становится ресурсоемким, а текущие требования основываются на числах, состоящих из 1024 бит.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
