Благодарю автора за ответственное отношение к выполнению заказа.
Информация о работе
Подробнее о работе
Криптоанализ. Алгоритмы факторизации
- 26 страниц
- 2021 год
- 5 просмотров
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Содержание
Введение 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 – Результат разложения
Программа показала правильный ответ.
Реализуем алгоритм Лемана.
...
Список использованных источников
1. А. Е. Ваулин «Факторизация числа, проблемы ее теории» - 2014. - [Электронный ресурс] https://habr.com/ru/post/226395/
2. А.А. Сериков «Методы криптоанализа» - 2015 – [Электронный ресурсы] https://intuit.ru/studies/courses/940/456/lecture/10198
3. В.С. Головин «Факторизация чисел и методы решета» - 2020. – [Электронный ресурс] https://se7en.ws/faktorizaciya-chisel-i-metody-resheta-chast
4. «Сравнительный анализ методов факторизации натуральных чисел» - 2013. – [Интернет ресурс] https://www.bibliofond.ru/view.aspx?id=656994
5. Интернет ресурс profy48.ru.
6. Приказ ФСБ РФ от 9.02.2005 N 66 "Об утверждении Положения о разработке, производстве, реализации и эксплуатации шифровальных (криптографических) средств защиты информации (Положение ПКЗ-2005)"
7. Об утверждении Положения о лицензировании деятельности по раз-работке, производству, распространению шифровальных (криптографических) средств, информационных систем и телеком-муникационных систем, защищенных с использованием шифровальных (криптографических) средств, выполнению работ, оказанию услуг в об-ласти шифрования информации, техническому обслуживанию шифро-вальных (криптографических) средств, информационных систем и теле-коммуникационных систем, защищенных с использованием шифро-вальных (криптографических) средств (за исключением случая, если техническое обслуживание шифровальных (криптографических) средств, ин-формационных систем и телекоммуникационных систем, защищенных с ис-пользованием шифровальных (криптографических) средств, осуществляется для обеспечения собственных нужд юридического лица или индивидуального предпринимателя) [Электронный ресурс].: постановление Правительства Рос. Федерации от 16.04.2012 № 313 // КонсультантПлюс : справочная правовая система / разраб. НПО «Вычисл. математика и информатика». – Москва : Кон-сультант Плюс, 1997-2020. – Режим доступа : http://www.consultant.ru. – 01.12.2020.
8. Интернет СУБД [Электронный ресурс]. – Математика криптографи и теория шифрования - Режим доступа: https://intuit.ru/studies/courses/552/408/lecture/9368?page=6
9. Интернет СУБД [Электронный ресурс]. – Метод Лемана- Режим доступа:http://wp.wiki wiki.ru/wp/index.php/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9B%D0%B5%D0%BC%D0%B0%D0%BD%D0%B0
10. Интернет СУБД [Электронный ресурс]. – Python- Режим доступа: https://pythonworld.ru/moduli/modul-math.html
11. Интернет СУБД [Электронный ресурс]. – Python docymentation- Режим доступа: https://andreyex.ru/yazyk-programmirovaniya-python/python-3-chislovaya-funkciya-sqrt/
12. Интернет СУБД [Электронный ресурс]. – Python docymentation- Режим доступа: https://docs.microsoft.com/ru-ru/cpp/c-runtime-library/reference/ceil-ceilf-ceill?view=msvc-160&viewFallbackFrom=vs-2019
13. Интернет СУБД [Электронный ресурс]. – Разложение чисел - Режим доступа: https://brestprog.by/topics/factorization/
14. С. Авдошин, А.Савельев «Криптоанализ: вчера, сегодня, завтра » - 2009. - [Электронный ресурс] https://www.osp.ru/os/2009/03/8120956
15. Л. Инфельд, Т.Е. Халл «Метод факторизации» - 2009. -[Электронный ресурс] http://ega-math.narod.ru/Nquant/Infeld.htm
16. Интернет СУБД [Электронный ресурс]. Алгоритмы факторизации натуральных чисел Режим доступа: https://studbooks.net/2321890/informatika/algoritmy_faktorizatsii_naturalnyh_chisel
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
