Криптосистема RSA. 
Обзор современных средств криптографии

Криптосистема RSA, предложенная в 1977 году Ривестом, Шамиром и Адлеманом, предназначена для шифрования и цифровой подписи. В настоящее время RSA является наиболее распространенной криптосистемой — стандартом де-факто для многих кирптографических приложений. Статус де-факто послужил причиной включения криптосистемы RSA в принятые ранее криптографические стандарты.

Так, финансовый стандарт США ANSI X9.30 предусматривал использование федерального стандарта цифровой подписи DSS. Выпущенная позднее версия стандарта ANSI X9.31 была дополнена криптосистемой RSA. Последний является так же частью многих официальных стандартов, в частности международных стандартов ISO 9796 и ITU-T X.509, SWIFT, французского финансового стандарта ETABAC 5, австралийского стандарта управления ключами AS2805.6.5.3.

Криптосистема RSA широко применяется в составе различных стандартов и протоколов Internet, включая PEM, S/TIME, PEM-MIME, S-HTTP и SSL.

Возможно ли использование RSA в России? С точки зрения правовых норм это исключено — RSA не входит ни в один из действующих на территории России кирптографических стандартов. Отметим, что стандарты двухключевого шифрования и управления ключами в России также пока не приняты. Таким образом, разработчик криптографических приложений поставлен перед выбором: построить схему управления ключами по методу полной матрицы, экспоненциального ключевого обмена Диффи-Хеллмана или воспользоваться методом цифрового конверта (шифрование сеансового ключа при помощи двухключевого криптоалгоритма).

Недостатки существующего не одно десятилетие метода полной матрицы хорошо известны. Протокол Диффи-Хеллмана предполагает двусторонний обмен открытыми ключами и наличие сертификатов у отправителя и получателя сообщений. В случае односторонней аутентификации (сертификат имеется только у одной из сторон) предпочтение отдается последнему методу. В этой ситуации выбор RSA вполне оправдан — метод цифрового конверта на базе криптоалгоритма RSA описан в стандарте PKCS и применяется в протоколе SSL и других стандартах Internet (PEM, PEM-MIME и т. д.).

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

Для генерации парных ключей используеться два больших случайных простых числа, p и q. В целях максимальной криптостойкости p и q выбираються равной длины. Затем вычисляется произведение:

n=pq.

Далее случайным образом выбираеться ключ шифрования e, такой, что e и ц (n)=(p-1)(q-1).

являются взаимно простыми числами. Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что.

ed=1 mod ц (n).

Другими словами,.

d=e^-1 mod ц (n).

Заметим, что d и n — так же взаимно простые числа. Числа e и n — открытый ключ, а d — секретный. Два простых числа p и q хранятся в секрете. Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q — 100-разрядные простые числа, то n будет содержать около 200 разрядов. И каждый блок сообщения m_i должен иметь такое же число разрядов. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n.) Зашифрованное сообщение c будет состоять из блоков c_i той же самой длины. Шифрование сводиться к вычислению.

c_i=m_i^e mod n.

При дешифровании для каждого зашифрованного блока c_i вычисляется.

m_i=c_i^d mod n.

Последнее справедливо, так как.

C_i^d=(m_i^e)^e=m_i^ed=m_i^{kц (n)+1}=m_i*m_i ^{kц (n)}=m_i*1=m_i.

Все вычисления выполняются по модулю n.

Отметим, что сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.

Рассмотрим короткий пример. Если.

p=47 и q=71, то n=pq=3337.

Ключ e не должен иметь общих множителей с ц (n)=46*70=3220.