Стойкость алгоритма RSA.

В RSA стойкость определяется как сложность обращения односторонней функции F(x) = x^y (mod N), которая зависит от сложности разложения на множители модуля N (факторизация). При этом следует иметь в виду, что это утверждение является всего лишь предположением, поскольку строгих математических доказательств данного факта не существует. Стойкость алгоритма может быть существенно снижена за счёт некорректного выбора параметров алгоритма. Недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа Р и Q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Ривест полагал, что разложение на простые множители числа из почти что 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и Манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира. Выбранное число, называемое девятым числом Ферма, с 1983 года находилось в списке чисел, разложение которых считалось наиболее желательным. Это число взято потому, что оно считалось неразложимым при существующей вычислительной технике и достаточно большим для того, чтобы его можно считать безопасным для формирования N в RSA. Как заявил Ленстра, ведущий в Bellcore исследования по электронной защите информации и разложению больших чисел, их целью было показать разработчикам и пользователям криптографических систем, с какими угрозами они могут встретиться и насколько осторожными должны быть при выборе параметров алгоритмов шифрования.

Следует учесть, что работа по совершенствованию методов и техники разложения больших чисел только началась и будет продолжена. Те же Ленстра и Манасси в 1991 году нашли делитель тринадцатого числа Ферма, которое состоит примерно из 2500 десятичных разрядов. Теперь разработчикам криптографических алгоритмов с открытым ключом на базе RSA приходится избегать применения разложимых чисел длиной менее 200 десятичных разрядов. А так как для шифрования каждого блока информации приходится соответствующее число возводить в колоссально большую степень по модулю N, то для современных компьютеров это задача на грани возможного. Поэтому для практической реализации шифрования RSA начали разрабатывать специальные процессоры, которые позволили бы выполнять операции RSA достаточно быстро. Лучшими из серийно выпускаемых кристаллов являются процессоры фирмы CYLINK, которые позволяют выполнять возведение в степень целого числа из 307 десятичных знаков за доли секунды. Отметим, что чрезвычайно слабое быстродействие криптографических систем на основе RSA лишь ограничивает область их применения, но вовсе не перечеркивает их ценность.

Другим недостатком RSA является наличие так называемых нешифруемых блоков открытого сообщения, т.е. таких M, для которых выполняется равенство M^E (mod N)=M. Например, M = 0, 1, N-1 всегда являются нешифруемыми блоками сообщения. Точное количество нешифруемых блоков сообщения при выбранных параметрах алгоритма равно

(1 + НОД (E-1, P-1)) × (1 + НОД (E-1, Q-1)).

Данная особенность налагает определённые требования на выбор параметров алгоритма. Для вычисления простых чисел большой размерности можно использовать различные алгоритмы. Например, малая теорема Ферма: если взять простое число N и все числа, меньшие N, т.е. i = 1..N-1, то i^N-1 (mod N) = 1. Так, пусть N = 5. Тогда

при i = 4 ® 4 ^N-1 (mod N) = 4 ⁴ (mod 5) = 256 (mod 5) = 1;

при i = 3 ® 3 ^N-1 (mod N) = 3 ⁴ (mod 5) = 81 (mod 5) = 1;

при i = 2 ® 2 ^N-1 (mod N) = 2 ⁴ (mod 5) = 16 (mod 5) = 1;

при i = 1 ® 1 ^N-1 (mod N) = 1 ⁴ (mod 5) = 1 (mod 5) = 1.

Поскольку одной из основных проблем помимо обеспечения надлежащей стойкости алгоритма RSA путём выбора корректных параметров является низкая скорость проведения вычислений и операций зашифрования / расшифрования (RSA приблизительно в 1000 раз медленнее DES), то для длинных сообщений его использование оказывается неэффективным. Поэтому асимметричные алгоритмы используются в основном для решения задачи распределения сеансовых ключей по общедоступным каналам передачи данных. То есть симметричный ключ передаётся зашифрованным при помощи асимметричного алгоритма шифрования, и дальнейший обмен данными производится с использованием симметричных алгоритмов шифрования. Алгоритмы с открытым ключом (асимметричные) применяются также в процедурах генерации и проверки электронно-цифровой подписи.