Криптоанализ. Алгоритмы факторизации

Содержание

Введение 5
Цель и задачи работы 7
1 Алгоритмы факторизации 8
1.1 Обзор основных сведений по криптоанализу 8
1.2 Законодательство 15
2 Программный комплекс « Алгоритмы факторизации» 18
2.1 Функциональное назначение программы, область применения, её ограничения 18
2.2 Руководство программиста 18
2.3 Руководство пользователя 21
2.4 Тестовый пример 23
Заключение 25
Список использованных источников 26
Приложение А 28

2 Разработать программный комплекс, реализующий «Алгоритмы факторизации».
Объектом исследования является алгоритм работы методов факторизации.

Цель и задачи работы

Цель: Ознакомиться с алгоритмами факторизации.

Задачи:
1 Провести анализ теоретических сведений по выбранной теме;
2 Разработать программный комплекс, реализующий «Алгоритмы факторизации».

1 Алгоритмы факторизации

Разложение (факторизация) натуральных чисел на множители является трудной вычислительной задачей. Сложность решения этой задачи лежит в основе одного из наиболее известных методов криптографии - методе RSA. Существует большое количество алгоритмов факторизации, среди которых наиболее быстрыми на сегодняшний день методами являются метод квадратичного решета и метод решета числового поля.(аббревиатура от фамилий Rivest, Shamir и Adleman) - криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
...

1.1 Обзор основных сведений по криптоанализу

Криптоанализом (от греческого krypts - "скрытый" и analein - "ослаблять" или избавлять") называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Хотя история криптоанализа насчитывает многие века, особенно интенсивно эта область знаний начала развиваться с наступлением компьютерной эры.
Попытка криптоанализа называется атакой. Криптоанализ ставит своей задачей в разных условиях получить дополнительные сведения о ключе шифрования, чтобы значительно уменьшить диапазон вероятных ключей. Результаты криптоанализа могут варьироваться по степени практической применимости. Так, криптограф Ларс Кнудсен предлагает следующую классификацию успешных исходов криптоанализа блочных шифров в зависимости от объема и качества секретной информации, которую удалось получить:
Полный взлом - криптоаналитик извлекает секретный ключ.
...

1.2 Законодательство

При разработке, производстве, реализации и эксплуатации средств защиты информации с использованием алгоритмов факторизации, нужно руководствоваться следующими документами:
1)Приказ ФСБ РФ от 9 февраля 2005 г. "Об утверждении Положения о разработке, производстве, реализации и эксплуатации шифровальных (криптографических) средств защиты информации (Положение ПКЗ-2005)" [6].
Положение регулирует отношения, возникающие при разработке, производстве, реализации и эксплуатации шифровальных (криптографических) средств защиты информации с ограниченным доступом, не содержащей сведений, составляющих государственную тайну (далее - информация конфиденциального характера).
2) Постановление Правительства Российской Федерации от 16 апреля 2012 г. N 313 г.
...

2.1 Функциональное назначение программы, область применения, её ограничения
Программный комплекс предназначен для реализации алгоритмов факторизации.
Результатом работы данного решения является разложение натурального числа в произведение простых чисел, на основе алгоритмов факторизации.
Ограничения применения программного комплекса определяются произ-водительностью персонального компьютера (ПК).
Программа разработана на языке программирования python версии 3.8.
Программный комплекс предназначен для работы на ПК с системами Windows 7 с пакетом обновления 1 (SP1) (с последними обнов-лениями Windows) и выше.
Для корректной работы программного комплекса необходимо наличие ПК с процессором с тактовой частотой не ниже 1,8 ГГц. Рекомендуется как минимум двухъядерный процессор. Необходимый объем оперативной памяти составляет 1 ГБ ОЗУ. Рекомендуется 2 ГБ ОЗУ (минимум 2,5 ГБ при выполнении на виртуальной машине). Место на жестком диске: минимум 100 МБ свободного места.
...

2.2 Руководство программиста

Программное обеспечение включает в себя основное окно с кодом через которое осуществляется управление и доступ к отдельным методам.
Данное программное обеспечение использует следующие библиотеки:
- sys;
- match;
Match один из наиважнейших в Python. Этот модуль предоставляет обширный функционал для работы с числами. [10].
Основной код программы находится в классе GetLehmanFactor. Функции этого класса вызывают функции других классов.
Функция Trunc возвращает целочисленную часть числа с плавающей запятой. Она возвращает эту часть как Целочисленное значение.
Функция Sqrt возвращает квадратный корень числа (Number).Число должно быть вещественного типа.[11]
Функция Power возводит X в степень Y. Значение аргумента Х должно быть больше нуля, иначе возникнет исключение EInvalidOp. Данная функция аналогична функции IntPower за исключением того, что для Power значение показателя степени Y может превышать MaxInt и иметь нецелочисленный тип.
...

2.3 Руководство пользователя

Программ имеет одно основное окно, через которое происходит управление функциями.

Рисунок 3 - Окно программы

Разложение по алгоритму Ферма происходит при вводе в программу единицы. После чего выйдет новая подсказка, которая предложит ввести число. Ввод данных при алгоритме Ферма изображён на рисунке 4.

Рисунок 4 – Ввод данных при алгоритме Ферма

Вводим натуральное число и нажимаем на кнопку, чтобы ввести данное в программу. Дальше нам выйдет результат. Результат разложения по алгоритму Ферма изображён на рисунке 5.

Рисунок 5 – Результат разложения по алгоритму Ферма

Для того чтобы воспользоваться алгоритмом Лемана, возвращаемся к начальной подсказке где нас просят ввести 2 если хотим использовать этот алгоритм. После ввода двойки выходит новая подсказка, где нас просят ввести число. Ввод данных при алгоритме Лемана изображён на рисунке 6.
...

2.4 Тестовый пример

Реализуем алгоритм Ферма
Для примера возьмём большое число n=89755.
1)Найдём корень от числа n.
2)Если значение получилось не целое, ищем , x=300+0=300
3)Находим переменную , L=3002 - 89755=245
4)Находим Y1.
5) Округляем значение y1 и присваиваем полученное значение y.Y=16
6) Если Y1 не равен Y , то прибавляем и повторяем шаг 2, до тех пока они не станут равны. K=82, L=3822 - 89755=56169, Y1=237, Y1=Y
7)Находим a и b.,. A=382+237=619, B=382-237=145
8)Данное разложение является не конечным, так как, очевидно, что число 145 не является простым:  145=29*5
В итоге, конечное разложение исходного числа {\displaystyle n}n на произведение простых множителей  89755=29*5*619
Разложение получено, теперь посмотрим, какой результат даст программа.
Результат разложения показан на рисунке 8.

Рисунок 8 – Результат разложения

Программа показала правильный ответ.
Реализуем алгоритм Лемана.
...