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