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


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

Работа №77606

Тип работы

Дипломные работы, ВКР

Предмет

информационная безопасность

Объем работы48
Год сдачи2017
Стоимость4325 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
189
Не подходит работа?

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


Введение
ПРИМЕНЕНИЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ В КРИПТОГРАФИИ 4
2. ИДЕЯ АЛГОРИТМА ЛЕНСТРЫ 9
3. ОСНОВНЫЕ ЭТАПЫ АЛГОРИТМА 11
4. МОДИФИКАЦИЯ АЛГОРИТМА 13
5. РЕАЛИЗАЦИЯ АЛГОРИТМА 15
5.1. РЕАЛИЗАЦИЯ ПРИЛОЖЕНИЯ 15
5.2. РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ 16
5.3. РЕАЛИЗАЦИЯ РАСШИРЕННОГО АЛГОРИТМА ЕВКЛИДА 18
5.4. РЕАЛИЗАЦИЯ ТЕСТА НА ПРОСТОТУ 20
5.5. РЕАЛИЗАЦИЯ ПОИСКА ФАКТОРА 21
6. АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМА 25
7. ВРЕМЯ РАБОТЫ АЛГОРИТМА 30
8. СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ 32
8.1. КВАДРАТИЧНОЕ РЕШЕТО 32
8.2. РЕШЕТО ЧИСЛОВОГО ПОЛЯ 33
8.3. МЕТОДИКА СРАВНЕНИЯ 34
ЗАКЛЮЧЕНИЕ 38
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 40
ПРИЛОЖЕНИЯ

В настоящее время вопрос защиты информации становится все более актуальным. Меняются способы обеспечения защиты, меняются и способы атаки злоумышленников. Поэтому крайне важно иметь алгоритм шифрования, который был бы устойчив к взлому, но при этом позволял бы истинному получателю безошибочно определять исходное сообщение. Целью всех систем шифрования является создание последовательности символов, недоступной для чтения. В таком случае, даже если злоумышленник и получит зашифрованную информацию, то не сможет использовать ее по назначению. Существуют системы шифрования с закрытым и открытым ключом. Наиболее популярными являются вторые. Это естественно, т.к. открытый ключ можно передавать по незащищенному каналу, не беспокоясь о том, что он будет перехвачен. А для расшифровывания используется закрытый ключ, который всегда хранится у получателя и не подвергается риску кражи. Достаточно популярной среди криптосистем с открытым ключом является RSA. Основывается она на сложности задачи факторизации, т.е. разложении числа на множители. В криптографии вопрос факторизации имеет очень большое значение. Множество алгоритмов шифрования используют предположение, что факторизация целого числа - вычислительно сложная задача. Иными словами, если злоумышленнику удастся факторизовать число, то он сможет вычислить закрытый ключ, не похищая его, и расшифровать сообщение, а значит, получит доступ к конфиденциальной информации. Эта задача приобрела огромную популярность после создания алгоритма RSA, и в настоящее время известны такие алгоритмы факторизации, как метод квадратичного решета, алгоритм Диксона, ро-алгоритм Полларда, (р-1)-метод Полларда и многие другие. Однако ни один из данных методов за короткое время не может справиться с такими размерами ключей, которые используются в современных криптосистемах. Поэтому задача разложения длинных чисел на множители является крайне важной.

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

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

Помощь в написании работ!


По быстродействию данный метод факторизации среди всех прочих алгоритмов проигрывает только методу решета числового поля и методу квадратичного решета. Но при этом, у него есть одно важное преимущество. В отличие от них, алгоритм Ленстры зависит от размера делителя, а не самого факторизуемого числа. Поэтому, если известно, что число, которое нужно разложить на множители, имеет такой размер, с которым ни одно решето не справится рациональнее использовать именно алгоритм Ленстры. Поскольку в данном случае остается вероятность, что у него есть небольшой множитель, который будет найден методом эллиптических кривых за разумное время. Тот факт, что ни одно решето не справится с числом, как правило, мы можем предположить сразу.
К настоящему моменту самое большое число было факторизовано в конце 2009 года. Группа ученых, куда входили Ленстра, Монтгомери, Циммерманн и другие, факторизовала число RSA-768, состоящее из 232 десятичных знаков, были найдены 2 множителя длиной 116 символов.
Из-за высокой сложности одного шага в алгоритме Ленстры, всегда отдается предпочтение решету числового поля для «неудобного» случая, когда факторизуемое число состоит из примерно одинаковых чисел, поэтому теряется то преимущество «наименьшего существующего множителя» в нашем алгоритме. Однако мы не всегда можем предугадать, «удобный» этот случай, или нет, поэтому Померанц в своей работе рекомендует сначала протестировать метод Ленстры, и только после того, как будет потрачено достаточно времени и желаемый результат не будет получен, следует запустить какое-либо решето [12].
Но если число п настолько велико, что мы заранее знаем, что о решете не может быть и речи, то остается надеяться только на эллиптические кривые. Здесь нам может повезти в двух случаях: либо у рассматриваемого числа действительно может быть небольшой множитель
В результате выполнения данной работы был успешно программно реализован данный алгоритм факторизации. Также было выявлено, что он является третьим по быстроте после решета числового поля и квадратичного решета. Проанализировав результаты работы алгоритма, можем сделать вывод, что лучше всего его использовать для поиска простых чисел длиной от 60 до 84 бит, - не самая большая ниша, но этот факт никак не умаляет важности данного метода. В настоящее время он является одним из лидеров существующих алгоритмов факторизации, которые могут сыграть немаловажную роль в развитии современной криптографии.



1. Ш.Т. Ишмухаметов Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов // Казань: Казан. ун. - 2011
2. Ш.Т. Ишмухаметов Математические основы защиты информации / Ш.Т. Ишмухаметов, Р.Г. Рубцова // Казань: Казан. ун. - 2012
3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии/ О.Н. Василенко. - МЦНМО, 2003
4. А. А. Болотов Элементарное введение в эллиптическую криптографию / А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских // М.: КомКнига - 2006
5. Коблиц Н. Курс теории чисел и криптографии / Н. Коблиц. - М.: ТВП, 2001 - второе издание
6. Черемушкин А.В. Лекции по арифметическим функциям в криптографии / А.В. Черемушкин.- М.: МЦНМО, 2002
7. Crandall R. The prime numbers: a computational perspertive / R. Crandall, C. Pomerance // Springer-Verlag, Berlin - 2005 - sec.ed.
8. Lenstra H.W. Factoring integers with elliptic curves / H.W. Lenstra // Ann.Math - 1987
9. Lenstra H.W., JR Elliptic Curves and Number-Theoretic Algorithms / H.W. Lenstra // Proceedings of the International Congress of Mathematicians Berkeley, California, USA, 1986.
10. Lenstra H. JR A hyperelliptic smoothness test. / H. Lenstra, Jr., J. Pila, and C. Pomerance // I. Philos. Trans. Roy. Soc. London Ser. A, 345:397-408, 1993.
11. Washington L. Elliptic Curves Number Theory and Cryptography /L. Washington. - Series Discrete Mathematics and Its Applications, Chapman & Hall // CRC,second ed. 2008
12. Pomerance C. Smooth Numbers and the Quadratic Sieve / C. Pomerance. // - MSRI publications- 2008
13. Montgomery P.L. Speeding the Pollard and Elliptic Curve Methods of Factorization./P.L. Montgomery.- // Mathematics of Computation, v.48, iss.177, 1987
14. R. Schoof. Counting points on elliptic curves over finite fields. / R. Schoof. // Les Dix-huit'emes Journ'ees Arithm'etiques , Bordeaux, 1993
15. M. Morrison A method of factoring and the factorization of F7. / M. Morrison and J. Brillhart //Math. Comp., 29:183-205, 1975


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



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


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