13)Алгоритм rsa

Рассмотрим математические факты, положенные в основу этого алгоритма.

Теорема 1. (Малая теорема Ферма)

Если Р - простое число, то хр-1 сравнимо с х(моdp) (это значит, что эти два числа при делении на этот модуль имеют один и тот де остаток). Для любого х и хр сравнимо с х(мodp).

Функция Эйлера

Теорема 2.

Если n=p*q, где р и q - отличные друг от друга простые числа, то

Пимер

Теорема 3

Если , где р и q - отличные друг от друга простые числа и х простое относительно p и q, то

Если, где , и е- простое число, относительно Фи(n), то отображение хRxe(modn) является взаимно однозначным на Zn.

Именно на этих математических фактах основан алгоритм RSA.

Пользователь i выбирает пару простых различных чисел pi и qi и рассчитывает пару простых чисел ( ei, di), которые являются простыми относительно

Приведем справочную таблицу публичных корней

Пользователь I зашифровывает текст при передаче пользователю g, применяя к n отображение Edi,ni. Пользователь g производит дешифрование n, применяет отображение E ei,in. Чтобы найти инверсиюEdi,in по отношению Eei,in, необходимо знание множителей ni= pi*qi. На сегодняшний день для осуществления наиболее известных алгоритмов такого разложения необходимо время, которое выходит за пределы современных технологических возможностей.

В реальных системах алгоритм RSA реализуется следующим образом:

Каждый пользователь выбирает два больших простых числа, например р и q, и на основании вышеописанного алгоритма выбирает еще два числа е и d. n устанавливается в результате унижения р и q. (e,n) образует открытый ключ, а (d,n) закрытый, или наоборот. Открытый ключ публикуется и доступен каждому желающему, закрытый зашифровываются по указанному алгоритму. После шифрования текст невозможно расшифровать с помощью открытого ключа, но получатель текста без труда может расшифровать полученное сообщение.

Практическая реализация RSA . В настоящее время алгоритм RSA применяется и как самостоятельная криптосистема, и в виде встроенного средства популярных приложений. Наиболее важная проблема практической реализации алгоритма - это генерация больших простых чисел. То есть решение задачи в лоб - генерация большого простого, нечетного числа n и проверка его делимости на множители от 3 и выше, в случае неудачи необходимо взять число n +2 и повторить проверку. Но если в алгоритме RSA использовать не простые, а составные числа, то его криптостойкость резко падает. Возможно использовать почти простые числа, те числа, вероятность которых, что они простые, стремится к единице. Еще одна проблема алгоритма RSA - ключи какой длины необходимо использовать. Для практической реализации алгоритма необходимо знать оценки трудоемкости разложения простых чисел различной длины, которые выполнены Шроппелем.

В 1995 году удалось практически реализовать раскрытие шифра RSA для 500 знатного ключа, для чего в сети интернет был задействован 1600 компьютеров. Создатели алгоритма RSA рекомендуют использовать следующие размеры моd n

1. 768 Бит для частных

2. 1024 бит для коммерческой информации

3. 2048 бит для особо секретной информации

3 й аспект реализации RSA - вычислительный, так как приходится использовать аппарат длиной арифметики.

Если используется , то по открытому к в квадрате, по закрытому - к в кубе, а для генерации новых ключей - к в четвертой. По сравнению с алгоритмом dES RSA требует в 1000 и в десятки тысяч раз больше времени. Например криптографический пакет RSA DS на компьютере Пентиум 90 осуществляет шифрование со скоростью 21,6 КБ/сек для 512 битого ключам со скоростью 7,4 КБ/сек для 1024 битого ключа. Самая быстрая аппаратная реализация обеспечивает скорость в 60 раз больше