Каким образом хозяин ключей отвечает корреспондентам?

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

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

Задача 13.1

Существует вероятность, что при шифровании по системе RSA строка перейдет сама в себя. Наиболее очевидными случаями для двухзначных строк из вышеприведенного примера являются строки AA и AB, численные представления которых равны соответственно 0000 и 0001. Поскольку эти числа при возведении в любую степень не изменяются, то они при шифровании переходят сами в себя независимо от значений ключа зашифрования и модуля. Существуют и другие случаи: проверьте, что

для значения модуля 3127 и ключа зашифрования 17 числа 0530 и 0531 при зашифровании по алгоритму RSA оба переходят в себя.

(Могут возразить, что числам 0530 и 0531 не отвечают никакие пары букв; однако, заметим, что числа 0825 и 2302 - числовые представления пар IZ и XC - также переходят сами в себя.)

Тем не менее, необходимо сказать, что для "реального" приложения системы RSA вероятность того, что блок текста перейдет при шифровании сам в себя, будет пренебрежимо мала