Тип работы:
Предмет:
Язык работы:


ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ ТЕСТОВ ПРОСТОТЫ С ИСПОЛЬЗОВАНИЕМ ЭЛЛИПТИЧЕСКИХ КРИВЫХ

Работа №45591
Тип работыДипломные работы, ВКР
Предметинформационная безопасность
Объем работы81
Год сдачи2018
Стоимость4370 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 264
Не подходит работа?

Узнай цену на написание

ВВЕДЕНИЕ 3
1. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ 5
1.1 Операции на эллиптической кривой 7
1.1.1 Аффинные координаты 7
1.1.2 Проективные координаты 9
1.2 Использование эллиптических кривых 10
1.3 Тесты простоты на эллиптических кривых 11
2. ПОСТАНОВКА ЗАДАЧИ 13
3. ТЕСТ ПРОСТОТЫ АТКИНА-МОРЕЙНА 14
4. РЕАЛИЗАЦИЯ АЛГОРИТМА 16
4.1. Тест Аткина-Морейна 16
4.2. Организация проверки сертификата 21
5. ПРИМЕР ИСПОЛЬЗОВАНИЯ ПРОГРАММЫ 21
6. ИССЛЕДОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ ПРОГРАММЫ 23
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 35
ПРИЛОЖЕНИЕ

С развитием информационных технологий увеличивается значение криптографии. Если раньше достаточно было защищать лишь документы, то теперь в этом нуждается вся система, которая имеет доступ к информации.
Практически на всех уровнях сетевой модели OSI, благодаря которым происходит взаимодействие между пользователями, используются протоколы, включающие в себя шифрование передаваемых данных. Таким образом, обеспечивается защита при передаче информации между уровнями и при передаче информации в сети между пользователями. Большое внимание уделяется методам шифрования, что понятно. Их делят на симметричные и асимметричные. Первые используют один ключ, который необходимо держать в тайне между общающимися сторонами. Вторые используют два ключа, открытый, который находится в общем доступе, и закрытый, который хранится в тайне. Огромное количество разных подходов к тем или иным способам сокрытия информации, однако, у всех есть общие стороны, одной из которых является использование простых чисел в своей основе. Гарантированно, что, к примеру, системы, взлом которых требует решения задачи дискретного логарифмирования, более криптостойки, если используют большие простые числа в качестве модуля. То же самое касается и задач разложения на множители.
К сложным задачам современности относится задача о факторизации большого числа N. Она требует значительных вычислительных ресурсов и, как следствие, выполнение программы, которая находит простые делители числа N, может длиться годами. Однако обратная задача выполнима легко [28]. Это значит, что мы быстро генерируем два простых числа p, q и находим их произведение p*q =N, а оппонент, имея N, долго раскладывает его на множители p и q. [11]
Становится естественным, что ключи и алгоритмы программ, которые используют генерацию большого простого числа, одни из самых криптостойких на сегодняшнее время.
Переходя к элементарным определениям:
Основная теорема арифметики гласит, что каждое натуральное число n можно единственным образом представить в виде
n = рр-* р2 pk, где ру< р2<.< Рк - простые числа,
а±, а2 ,... , ак - некоторые натуральные числа [20]
Так, если условиться, что произведение пустого множества чисел равно 1, выходит, что:
• само число 1 не считается простым;
• для простого числа k= 1; [25]
Таким образом, основная теорема арифметики, идея которой упоминалась еще до н.э., возможно первая обозначила проблему разложения данного целого числа на простые множители.[16]
Итак, простое число - натуральное число больше единицы, которое делится на себя и на 1. Чем оно больше, тем сложнее взломать систему, которая использует его в качестве шифрования.
Существующие алгоритмы нахождения простого числа используют либо вероятностные тесты, либо детерминированные. Первые работают гораздо быстрее, чем вторые, но могут ошибаться, выдавая составное число простым. Последние совершенно точно срабатывают верно. К ним относится полный перебор всевозможных делителей числа.
Алгоритмы, основанные на эллиптических кривых, точно определяют простое число и конкурируют с вероятностными тестами по скорости выполнения. Они представляют собой математические вычисления, производящиеся над уравнениями третьего порядка, которые и называются эллиптическими. Построение кривой производится в поле предполагаемого простого числа. Происходит подсчет точек на заданной кривой и по некоторому списку критериев делают определенные выводы. Примерами такого теста являются тесты на простоту Гольдвассера-Килиана и Аткина- Морейна(ЕСРР), реализация и анализ последнего как раз и описывает данная работа.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Тест простоты Аткина-Морейна - теста простоты основанный на теореме Гольдвассера-Килиана. В нем при определенных условиях генерируется порядок и уже после идет поиск параметров кривой. Недостаток алгоритма в том, что подходящие порядки имеют неизвестное распределение, именно поэтому говорят, что алгоритм имеет вероятностную сложность. Так этот аспект можно наблюдать на графике максимумов времени выполнения теста. Таким образом, мы не можем угадать, где нам повезет и алгоритм закончит свое выполнение за приемлемое время. Однако график значений среднего времени выполнения не так безнадежен: рост уже можно предсказать и на наших значениях является экспоненциальным. Степень экспоненты 0.017x, а это говорит о том, что на проверенном интервале, до 400 бит, график достаточно пологий и проверки проходят быстро. Еще лучше обстоят дела с графиком минимумов: полученные значения можно примерно аппроксимировать логарифмической функцией. Последнее означает, что при помощи алгоритма Аткина-Морейна можно за малый промежуток времени сгенерировать большое простое число, просто игнорируя те случаи, когда мы предпринимаем больше усилий, чем задано. К примеру, 747-битное число алгоритм определил как простое за 1,5 минуты. К тому же генерируется сертификат, который еще за более короткий срок, путем подстановки ранее вычисленных параметров кривой и разложений, позволяет произвести проверку. Так именно этим тестом были проверены числа, имеющие более чем две тысячи разрядов.
Самой емкой частью алгоритма является этап факторизации порядка. В реализации сначала поиск тривиальных делителей, а после, если факторизовать все-таки не получилось, начинает работать po-метод Полларда. Для повышения эффективности на этом этапе было введено распараллеливание, так как алгоритм может генерировать до 6 разных порядков, и в ситуации, когда в их последовательном разложении удастся разложить только последний элемент, время работы заметно увеличивается.
Факторизация может производиться любым известным способом, главный критерий - эффективность метода, но это уже другая область исследования, вопросы которой решаются отдельно. Следующим емким шагом алгоритма является поиск параметров кривой. Дело в том, что в случае, когда дискриминант Э -3, -4, тогда начинается сложная математика, которая
включается в себя операции над многочленами такие, например, как деление полинома большой степени на полином в малой степени и пр.
Проверка сертификата, сгенерированного при помощи метода доказательства простоты, сразу проверяет условия теоремы Гольдвассера- Килиана, таким образом, затрачивает основное время выполнения на несложные операции над кривыми. В таком случае естественно, что проверка числа занимает очень малое время.
Метод Аткина-Морейна хорошо работает на практике и однозначно определяет простоту числа - казалось, что эти два пункта не могут употребляться как характеристики одного. Существует много вариантов реализации теста и скорость его работы может совершенствоваться в будущем благодаря применению новых быстрых алгоритмов факторизации, операций над многочленами и прочее. Выполнение программы на компьютерах больших мощностей позволяет генерировать сертификаты чисел. Таким образом, проверка очень большого числа на простоту может быть выполнена обычным пользователем за реальное время.



1. Francois M. Implementing the asymptotically fast version of the elliptic curve primality proving algorithm [Text]: Publication/ HAL Id: hal-00004136, https://hal.archives-ouvertes.fr/hal-00004136v2, Submitted on 4 Feb 2005.
2. Harald B. Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography [Text]: Dissertation/ 2002
3. Ian F. Blake. Goldwasser-Kilian Approach to Certificates for RSA modulii [Text]: Publications/ Department of computer science, Toronto, M5S 3G$, Canada.
4. Андреев Е.В. Исследование областей практического применения средств криптографической защиты информации, реализующих алгоритмы на эллиптических кривых [Электронный ресурс]: МИЭТ, 26.06.2015 - Режим доступа - http://jurnal.org/articles/2015/inf9.html(10.05.2018).
5. Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография: монография. / Киев: 1ВЦ «Видавництво «Полггехника»», 2017. -272с.
6. Болотов А.А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы [Текст]: А.А. Болотов, С.Б. Гашков, А.Б. Фролов, А.А. Часовских. - М.: КомКнига, 2006. - 328 с.
7. Вечтомов Е.М. Абстрактная алгебра. Базовый курс: учебное пособие / Е. М. Вечтомов, В. В. Сидоров. — Киров: Изд-во ООО «Радуга-ПРЕСС», 2014. — 260 с.
8. Вечтомов Е. М. Философия [Текст]: Монография - Киров, 2013.
9. Горбенко И. Тестирование чисел на простоту: теория и практика
[Текст]: статья/ Иван Горбенко, Виталий Вервейко - Харьковский
национальный университет радиоэлектроники, 2003 г
10. Гречников Е.А. Метод комплексного умножения для построения эллиптических кривых и его оптимизации [Текст]: Статья / Журнал «Прикладная математика», область наук «Алгебраическая теория чисел (поля алгебраических чисел)», Московский государственный университет им. М.В. Ломоносова, г. Москва, Россия, 2011.
11. Ишмухаметов Ш.Т. Математические основы информационной безопасности [Текст]: учебно-методическое пособие/ Ш.Т. Ишмухаметов, Р.Х. Латыпов, Р.Г. Рубцова. - Казань: Казан. ун. 2014 - 95 с.
12. Кнэпп Э. Эллиптические кривые [Текст]: Пер. с англ. Ф.Ю. Попеленского. - М.: Из-во «Факториал Пресс», 2004. - 488с
13. Коблиц Н. Курс теории чисел и криптографии [Текст] - Москва: Научное изд-во ТВП, 2001, х+254 с.
14. Ковтун В. Криптопреобразования в группах точек эллиптических кривых [Текст]: Курс лекций. NRJETIX 2000 - 2008.
15. Кошлак М. М. Использование преобразований в группах точек эллиптических кривых, как следующий шаг в развитии несимметричной криптографии [Электронный ресурс]: статья / Кошлак М. М., Мельников Ю. Н. // Защита информации в ВС, 2004, Номер 2(5)- Режим доступа - http: //network-j ournal .mpei.ac. ru/cgi-bin/main.pl?l=ru&n=5&pa=14&ar=1 (10.05.2018).
16. Крэндалл Р. Простые числа: криптографические и вычислительные аспекты [Текст]: Крэндалл Ричард, Померанс Карл. Пер. с англ. / Под ред. и с предисл. В. Н. Чубарикова. - М.: УРСС: Книжный дом <ЛИБРОКОМ», 2011. -664 с.
17. Куржеевский И.В. Применение эллиптических кривых и
«гаммирования» для защиты от несанкционированного доступа [Электронный ресурс]: статья - Куржеевский И.В., Бродовская В.В., Филимонова А.А. /VIII Международной научно-практической конференции «Физико-математические науки и информационные технологии: проблемы и тенденции развития» - 26.11.2012 - Режим доступа -
https: //sibac. info/conf/math/viii/30225 (10.05.2018)
18. Ростовцев А.Г. Теоретическая криптография - Ростовцев А.Г., Маховенко Е.Б. - НПО «Профессионал», Санкт-Петербург, 2004.
19. Рябко, Б.Я. Криптографические методы защиты информации [Текст]: учебное пособие/ Б.Я. Рябко, А.Н. Фионов - М., «Горячая линия - Телеком», 2005.
20. Серовайский, С. Я. Простые числа: от Пифагора до криптографии Математика. Республиканский научно-методический журнал. 2009, №№ 1-3
21. Скрипко, А.И. Оптимизационные задачи вычислений в
эллиптических кривых [Электронный ресурс]: статья /Александр Игоревич Скрипко, Александр Николаевич Велигура // Безопасность информационных технологий Том 24, № 3 (2017) - Режим доступа -
https: //bit.mephi .ru/index.php/bit/article/view/266 (09.05.2018).
22. Швейкин, В.В. Применение эллиптических кривых в криптографии [Текст]: статья / Швейкин В.В., Танаев И.В., Дмитриев Е.А., Завгородний С.Д. // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XLV междунар. студ. науч.-практ. конф. № 8(44), Сентябрь 2016г., издательство АНС «СибАК».
23. Дискретное логарифмирование [Электронный ресурс] Режим доступа - http://new.math.msu. su/department/number/dw/doku.php?id=dislog (10.05.2018)
24. Криптографические протоколы на эллиптических кривых
[Электронный ресурс] - 08.06.2012 - Режим доступа -
https://www.bibliofond.ru/view.aspx?id=550653(20.04.2018)
25. Основная теорема арифметики [Электронный ресурс] - 15 января
2018 - Режим доступа:
https://ru.wikipedia.org/wiki/Основная_теорема_арифметики#%D0%98%D1%8 1 %D 1 %82%D0%BE%D 1 %80%D0%B8%D 1 %8F (29.04.2018)
26. Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее? [Электронный ресурс] - 17 июля 2017 - Режим доступа: https://habrahabr.ru/company/neobit/blog/332942(10.05.2018)
Т1. Эллиптические кривые [Электронный ресурс] - 13.02.2016 - Режим доступа - http://helpiks.org/7-3799.html(3.05.2018)
28. Эллиптические кривые: новый этап развития современной
криптографии [Электронный ресурс]: статья - Каталог "Пожарная
безопасность"-2004 / Режим доступа -
http://www.secuteck.ru/articles2/Inf_security/elept_krivaya_nov_etap_razv_kripto/(11.05.2018)
29. Эллиптическая криптография: теория [Электронный ресурс] - 9.08.2013 - Режим доступа - https://habr.com/post/188958/(18.05.2018)
30. Cryptography/Prime Curve//Standard Projective Coordinates
[Электронный ресурс] - 4 March 2011 - Режим доступа:
https: //en.wikibooks. org/wiki/Cryptography/Prime_Curve/Standard_Proj ective_Co ordinates (15.05.2018).


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ