Криптоанализ. Алгоритмы факторизации
Описание работы
Работа пользователя Beskonechno
Добрый день! Уважаемые студенты, Вашему вниманию представляется курсовая работа на тему: «Криптоанализ. Алгоритмы факторизации»
Аннотация
Курсовая работа посвящена исследованию криптоанализа и алгоритмов факторизации.
В ходе работы были рассмотрены существующие работы по теме «Криптоанализ. Алгоритмы факторизации». Теоретически описаны основные алгоритмы факторизации.
Разработано программное обеспечение, реализующее один из алгоритмов факторизации.
Работа содержит 9 рисунков.
Введение
Факторизацией целого числа называется его разложение в произведение простых сомножителей. Такое разложение, согласно основной теореме арифметики, всегда существует и является единственным (с точностью до порядка следования множителей). Все методы факторизации в зависимости от их производительности можно разбить на две группы: экспоненциальные методы и субэкспоненциальные методы. Все эти методы достаточно трудоемки, поэтому требуют значительных вычислительных ресурсов для чисел большой длины.
Предположение о том, что для больших чисел задача факторизации является вычислительно сложной, лежит в основе широко используемых алгоритмов (например, RSA). В настоящее время исследования в области построения быстрых алгоритмов факторизации интенсивно ведутся во всем мире. Ежегодно проводятся десятки конференций по этой тематике, достигаются новые рекорды факторизации длинных чисел, исследуются известные проблемы алгоритмической теории чисел и ставятся новые проблемы.
Актуальность использования алгоритмов факторизации растёт, с ростом вычислительных возможностей современных технологий, так как необходимы более сложные алгоритмы для криптографических шифров, которые злоумышленник не сможет взломать.
Исследуемая тема поднимается в различной литературе.
А.Е. Ваулин в своей статье рассматривает проблему факторизации и недо-статка операций для удобного шифрования и расшифрования. Проблема по его словам состоит в неопределённости современного шифра RSA, который в принципе может быть взломан без знания закрытого ключа. Важным аспектом проблемы автор считает – отсутствие операции обратной к умножению чисел. [1]
В статье Александра Серикова «Методы криптоанализа» подробно рас-смотрен термин криптоанализ, и рассмотрены основные методы: частотный анализ, полный перебор ключей, анализ ключевого генератора, факторизация, разностный анализ, линейный анализ, метод коллизий, анализ по побочным каналам, квантовый анализ. Термин “криптоанализ” служит как определение науки, занимающейся дешифрованием без доступа к ключу.[2]
Головин В.С. в своей работе пишет, что на данный момент всевозможные методы не решают проблему факторизации в принципе, так как почти все ме-тоды завязаны на жёсткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. При этом автор подмечает, что у чисел есть и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации. Факторизация чисел на данный момент зашла в тупик, математика необходимо пересмотреть подход к проблеме и создать новые модели. [3]
Целью исследования является ознакомление с алгоритмами факторизации.
Задачи исследования:
1 Провести анализ теоретических сведений по выбранной теме;
2 Разработать программный комплекс, реализующий «Алгоритмы факторизации».
Объектом исследования является алгоритм работы методов факторизации.
Содержание
Введение 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
Список использованных источников
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
Заключение
В ходе выполнения курсовой работы было произведено ознакомление с алгоритмами факторизации. Были реализованы в виде программы 2 алгоритма факторизации: Метод Ферма, метод Лемана. Была проведена проверка программы, в результате которой, было выявлено, что программа успешно справляется со своей задачей.
Аннотация
Курсовая работа посвящена исследованию криптоанализа и алгоритмов факторизации.
В ходе работы были рассмотрены существующие работы по теме «Криптоанализ. Алгоритмы факторизации». Теоретически описаны основные алгоритмы факторизации.
Разработано программное обеспечение, реализующее один из алгоритмов факторизации.
Работа содержит 9 рисунков.
Введение
Факторизацией целого числа называется его разложение в произведение простых сомножителей. Такое разложение, согласно основной теореме арифметики, всегда существует и является единственным (с точностью до порядка следования множителей). Все методы факторизации в зависимости от их производительности можно разбить на две группы: экспоненциальные методы и субэкспоненциальные методы. Все эти методы достаточно трудоемки, поэтому требуют значительных вычислительных ресурсов для чисел большой длины.
Предположение о том, что для больших чисел задача факторизации является вычислительно сложной, лежит в основе широко используемых алгоритмов (например, RSA). В настоящее время исследования в области построения быстрых алгоритмов факторизации интенсивно ведутся во всем мире. Ежегодно проводятся десятки конференций по этой тематике, достигаются новые рекорды факторизации длинных чисел, исследуются известные проблемы алгоритмической теории чисел и ставятся новые проблемы.
Актуальность использования алгоритмов факторизации растёт, с ростом вычислительных возможностей современных технологий, так как необходимы более сложные алгоритмы для криптографических шифров, которые злоумышленник не сможет взломать.
Исследуемая тема поднимается в различной литературе.
А.Е. Ваулин в своей статье рассматривает проблему факторизации и недо-статка операций для удобного шифрования и расшифрования. Проблема по его словам состоит в неопределённости современного шифра RSA, который в принципе может быть взломан без знания закрытого ключа. Важным аспектом проблемы автор считает – отсутствие операции обратной к умножению чисел. [1]
В статье Александра Серикова «Методы криптоанализа» подробно рас-смотрен термин криптоанализ, и рассмотрены основные методы: частотный анализ, полный перебор ключей, анализ ключевого генератора, факторизация, разностный анализ, линейный анализ, метод коллизий, анализ по побочным каналам, квантовый анализ. Термин “криптоанализ” служит как определение науки, занимающейся дешифрованием без доступа к ключу.[2]
Головин В.С. в своей работе пишет, что на данный момент всевозможные методы не решают проблему факторизации в принципе, так как почти все ме-тоды завязаны на жёсткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. При этом автор подмечает, что у чисел есть и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации. Факторизация чисел на данный момент зашла в тупик, математика необходимо пересмотреть подход к проблеме и создать новые модели. [3]
Целью исследования является ознакомление с алгоритмами факторизации.
Задачи исследования:
1 Провести анализ теоретических сведений по выбранной теме;
2 Разработать программный комплекс, реализующий «Алгоритмы факторизации».
Объектом исследования является алгоритм работы методов факторизации.
Содержание
Введение 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
Список использованных источников
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
Заключение
В ходе выполнения курсовой работы было произведено ознакомление с алгоритмами факторизации. Были реализованы в виде программы 2 алгоритма факторизации: Метод Ферма, метод Лемана. Была проведена проверка программы, в результате которой, было выявлено, что программа успешно справляется со своей задачей.
