Стандарты безопасности применяющие RSA

Криптосистема RSA — часть многих стандартов. Стандарт ISO 9796 описывает RSA как совместимый криптографический алгоритм, соответствующий стандарту безопасности ITU-T X.509. Кроме этого криптосистема RSA является частью стандартов SWIFT, ANSI X9.31 rDSA и проекта стандарта X9.44 для американских банков. Австралийский стандарт управления ключами AS2805.6.5.3 также включает систему RSA.

Алгоритм RSA используется в Internet, в частности он входит в такие протоколы как S/MIME, IPSEC (Internet Protocol Security) и TLS (которым предполагается заменить SSL), а также в стандарт PKCS, применяемый в важных приложениях.

Для разработчиков приложений с применением PKCS организация OSI Implementers Workshop (OIW) выпустила соглашение, которое в частности посвящено алгоритму RSA.

Множество других разрабатываемых в настоящее время стандартов включают в себя либо сам алгоритм RSA или его поддержку либо рекомендуют криптосистему RSA для обеспечения секретности и/или установления подлинности (аутентификации). Например, включают в себя систему RSA рекомендации IEEE P1363 и WAP WTLS.

Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире и это количество имеет явную тенденцию к увеличению по мере роста Internet.

Описание криптосистемы RSA.

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

Для генерации парных ключей берутся два больших случайных простых числа p и q. В целях максимальной криптостойкости p и q выбираются равной длины. Затем вычисляется их произведение n=pq (n называется модулем). Далее случайным образом выбирается число e (ключ шифрования), удовлетворяющее условию: 1< e < (p — 1)*(q — 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом ?(n)=(p-1)*(q-1).

Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что ed=1 mod ?(n). Число d такое, что (ed — 1) делится на (p — 1)(q-1).

Числа d и n — также взаимно простые числа.

Числа e и n — открытый ключ, а d — секретный.

Два простых числа p и q хранятся в секрете.

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

c_i =m_i^e mod n.

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

m_i = c_i^d mod n

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

c_i^d = (m_i^e)^d = m_i^ed = m_i^k?(n)+1 = m_i?1 = m_i

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