Алгоритмы разложения чисел на множители для построения системы RSA

В связи со схемой RSA возникает ряд алгоритмических задач. 1. Для генерации ключей нам надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа. 2. Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна.
...

Оглавление
Введение
RSA
Выделение полного квадрата (Алгоритм Ферма)
Квадратичное решето
Поиск необходимого множества делителей
Алгоритмы факторизации Полларда (методы Монте-Карло)
Метод Монте-Карло 1: поиск цикла в рекуррентной последовательности
Метод Монте-Карло 2: (p-1)–алгоритм Полларда
Заключение
Список литературы

?

Асимметричные криптосистемы устроены таким образом, что ключ, используемый для зашифрования , отличается от ключа расшифрования . Более того, ключ расшифрования не может быть (по крайней мере, в течение разумного периода) вычислен из ключа зашифрования . Такие алгоритмы называют алгоритмами с открытым ключом, поскольку ключ зашифрования может быть открытым: кто угодно может воспользоваться этим ключом для зашифрования сообщения, однако расшифровать сообщение может только конкретный человек, знающий ключ расшифрования . В таких системах ключ зашифрования часто называют открытым ключом, а ключ расшифрования - закрытым ключом. Закрытый ключ нередко называют секретным ключом, однако во избежание путаницы с симметричными алгоритмами, здесь этот термин не используется. Т .е у пользователя есть два ключа - секретный и открытый. Открытый ключ публикуется в общедоступном месте, и каждый, кто захочет послать сообщение этому пользователю - зашифровывает текст открытым ключом. Расшифровать сможет только упомянутый пользователь с секретным ключом. Таким образом, пропадает проблема передачи секретного ключа (как у симметричных систем). В некоторых случаях сообщения следует зашифровывать закрытым ключом, а расшифровывать — открытым ключом. Такой метод используют в цифровых подписях. Стойкость асимметричных криптосистем базируется, в основном, на алгоритмической трудности решить за приемлемое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредитирована будет вся система и все сообщения, зашифрованные с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Примеры - системы о.ш . RSA , система о.ш . Рабина и т.д. Однако, несмотря на все свои преимущества, эти криптосистемы достаточно трудоемки и медлительны. Существует несколько хорошо известных асимметричных криптосистем: RSA , Эль Гамаля ( El Gamal ), Рабина ( Rabin ). Поскольку в этих криптосистемах вид преобразования определяется ключом, публикуют только открытый ключ с указанием, для какой криптосистемы он используется. Секретный и открытый ключ как правило взаимосвязаны между собой, но то, как конкретно они связаны - известно только их владельцу и получить секретный ключ по соответствующему открытому ключу вычислительно невозможно.