RSA

RSA — это криптографический алгоритм с открытым ключом, основанный на вычислительной сложности задачи факторизации больших целых чисел. RSA является одним из первых и наиболее распространённых асимметричных шифров, используемых для шифрования данных и создания цифровых подписей. Название алгоритма составлено из первых букв фамилий его авторов — Рональда Ривеста, Ади Шамира и Леонарда Адлемана, опубликовавших описание в 1977 году.

История

Предпосылки и разработка

Идея асимметричной криптографии была впервые предложена Уитфилдом Диффи и Мартином Хеллманом в 1976 году. Однако их протокол обмена ключами не позволял напрямую шифровать сообщения. В 1977 году трое исследователей из Массачусетского технологического института — Ривест, Шамир и Адлеман — разработали практическую реализацию асимметричного шифрования, основанную на модульной арифметике и задаче разложения числа на простые множители. Первая публикация алгоритма состоялась в 1978 году в журнале Communications of the ACM.

Патент и стандартизация

В 1983 году Массачусетский технологический институт получил патент США № 4405829 на алгоритм RSA, который действовал до 21 сентября 2000 года. В 1990-х годах RSA стал основой для стандартов электронной подписи (например, PKCS#1) и протоколов защиты данных (SSL/TLS). В настоящее время алгоритм включён в международные стандарты ISO/IEC 9796 и IEEE P1363.

Математические основы

Генерация ключей

Процесс создания пары ключей (открытого и закрытого) включает следующие шаги:

1. Выбираются два различных больших простых числа \( p \) и \( q \).
2. Вычисляется модуль \( n = p \times q \). Длина \( n \) определяет криптостойкость алгоритма (обычно 2048 или 4096 бит).
3. Вычисляется функция Эйлера \( \varphi(n) = (p-1)(q-1) \).
4. Выбирается открытая экспонента \( e \), такая что \( 1 < e < \varphi(n) \) и \( \gcd(e, \varphi(n)) = 1 \). Чаще всего используется \( e = 65537 \).
5. Вычисляется секретная экспонента \( d \) как мультипликативное обратное к \( e \) по модулю \( \varphi(n) \): \( d \equiv e^{-1} \pmod{\varphi(n)} \).

Открытый ключ — пара \( (e, n) \), закрытый ключ — \( (d, n) \). Числа \( p \), \( q \) и \( \varphi(n) \) должны храниться в секрете или уничтожаться.

Шифрование и расшифрование

Для шифрования сообщения \( m \) (представленного в виде числа, меньшего \( n \)) используется операция: \[ c = m^e \bmod n \] Расшифрование выполняется возведением шифротекста \( c \) в степень \( d \): \[ m = c^d \bmod n \] Корректность алгоритма следует из теоремы Эйлера: \( m^{ed} \equiv m \pmod{n} \).

Цифровая подпись

Для создания подписи владелец закрытого ключа вычисляет \( s = h^d \bmod n \), где \( h \) — хеш-значение сообщения. Проверка подписи осуществляется путём вычисления \( h' = s^e \bmod n \) и сравнения с исходным хешем.

Криптостойкость и безопасность

Факторизация

Безопасность RSA основана на предположении, что задача разложения числа \( n \) на простые множители \( p \) и \( q \) является вычислительно сложной для классических компьютеров. Наиболее эффективный известный алгоритм факторизации — общий метод решета числового поля (GNFS) — имеет субэкспоненциальную сложность. Для модуля длиной 2048 бит требуемое время факторизации оценивается в миллионы лет при современном уровне вычислительной техники.

Атаки и уязвимости

Известны несколько типов атак на RSA:

• Атака по времени — основана на измерении времени выполнения операций модульного возведения в степень. Защита реализуется через «постоянное время» (constant-time) или рандомизацию.
• Атака по энергопотреблению — анализ профиля питания устройства при вычислениях. Применяется в аппаратных реализациях.
• Атака с использованием подобранного шифротекста — злоумышленник может расшифровать сообщение, если система не проверяет корректность данных. Для защиты используется схема Optimal Asymmetric Encryption Padding (OAEP).
• Атака на основе малого показателя — при малом значении \( e \) (например, 3) возможно восстановление сообщения при определённых условиях. Стандарты требуют \( e \geq 65537 \).

Квантовая угроза

В 1994 году Питер Шор предложил квантовый алгоритм факторизации, который способен разложить число \( n \) за полиномиальное время. При появлении достаточно мощного квантового компьютера RSA станет небезопасным. В связи с этим ведутся работы по переходу на постквантовые криптосистемы (например, на основе решёток).

Применение

Протоколы защиты данных

RSA широко используется в протоколах:

• SSL/TLS — для аутентификации серверов и обмена симметричными ключами при установлении защищённого соединения (HTTPS).
• SSH — для аутентификации пользователей и хостов.
• IPsec — для защиты сетевого трафика.

Электронная подпись

Стандарты цифровой подписи, такие как RSA-PSS (Probabilistic Signature Scheme), применяются в электронном документообороте, банковских системах и государственных информационных системах. В России для подписи используется ГОСТ Р 34.10-2012, основанный на эллиптических кривых, но RSA остаётся распространённым в международных транзакциях.

Шифрование ключей

В гибридных криптосистемах RSA используется для шифрования сеансовых ключей симметричных алгоритмов (AES, ChaCha20). Это позволяет сочетать скорость симметричного шифрования с удобством асимметричного управления ключами.

Смарт-карты и аппаратные модули

Микропроцессорные смарт-карты и аппаратные модули безопасности (HSM) реализуют операции RSA для аутентификации и подписи. Ограниченные вычислительные ресурсы таких устройств требуют оптимизации алгоритма.

Размеры ключей и рекомендации

Современные стандарты (NIST, ETSI) рекомендуют минимальную длину модуля RSA:

• 2048 бит — для большинства приложений до 2030 года.
• 3072 бита — для долгосрочной защиты (до 2035 года).
• 4096 бит — для критически важных систем.

Ключи длиной 1024 бита считаются устаревшими и небезопасными; их факторизация возможна с использованием кластерных вычислений или облачных ресурсов.

Интересные факты

• В 2009 году группа исследователей успешно факторизовала 768-битное число RSA-768 за два года с использованием сотен компьютеров.
• Алгоритм RSA лежит в основе протокола PGP (Pretty Good Privacy), созданного Филом Циммерманом в 1991 году.
• В 2013 году Сноуден раскрыл информацию о том, что АНБ США могло влиять на стандарты генерации случайных чисел, что потенциально ослабляло реализацию RSA в некоторых продуктах.

Источники

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems». Communications of the ACM.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). «Handbook of Applied Cryptography». CRC Press.
• NIST Special Publication 800-57: «Recommendation for Key Management».
• Boneh, D. (1999). «Twenty Years of Attacks on the RSA Cryptosystem». Notices of the AMS.
• Шор, П. (1994). «Algorithms for Quantum Computation: Discrete Logarithms and Factoring». Proceedings of the 35th Annual Symposium on Foundations of Computer Science.