Схема RSA

RSA (аббревиатура от фамилий Rivest, Shamir, Adleman) — это криптографический алгоритм с открытым ключом, используемый для шифрования данных и создания цифровых подписей. RSA относится к классу асимметричных криптосистем, в которых для шифрования и расшифрования применяются разные ключи: открытый (публичный) и закрытый (секретный). Безопасность алгоритма основана на практической сложности задачи факторизации больших целых чисел, а именно на трудности разложения произведения двух больших простых чисел на множители.

История

Алгоритм RSA был разработан в 1977 году тремя американскими математиками и криптографами — Роном Ривестом, Ади Шамиром и Леонардом Адлеманом — в Массачусетском технологическом институте (MIT). Название алгоритма составлено из первых букв их фамилий. Публикация описания алгоритма состоялась в 1978 году в журнале «Communications of the ACM».

Созданию RSA предшествовали работы Уитфилда Диффи и Мартина Хеллмана, которые в 1976 году предложили концепцию криптографии с открытым ключом. Однако Диффи и Хеллман не смогли найти практическую одностороннюю функцию с потайным ходом. Ривест, Шамир и Адлеман, после года безуспешных попыток, предложили решение, основанное на модульной арифметике и свойствах простых чисел.

В 1983 году на алгоритм RSA был получен патент США (№ 4,405,829), который действовал до 2000 года. В 1997 году британский математик Клиффорд Кокс из Центра правительственной связи (GCHQ) заявил, что его ведомство разработало аналогичный алгоритм ещё в 1973 году, но эта информация была засекречена.

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

Безопасность RSA опирается на несколько математических концепций:

• Теория простых чисел: в основе лежат большие простые числа (обычно от 1024 до 4096 бит).
• Функция Эйлера: φ(n) = (p-1)(q-1), где p и q — простые числа.
• Модульная арифметика: все операции выполняются по модулю n.
• Малая теорема Ферма: используется для доказательства корректности расшифрования.
• Задача факторизации: на данный момент не существует эффективного алгоритма для разложения произведения двух больших простых чисел на множители за полиномиальное время.

Принцип работы

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

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

1. Выбираются два больших случайных простых числа p и q.
2. Вычисляется их произведение n = p × q. Длина n в битах определяет криптостойкость алгоритма.
3. Вычисляется значение функции Эйлера: φ(n) = (p - 1) × (q - 1).
4. Выбирается целое число e (открытая экспонента), удовлетворяющее условиям: 1 < e < φ(n) и e взаимно просто с φ(n). Обычно выбирают e = 65537 (2¹⁶ + 1) как компромисс между скоростью и безопасностью.
5. Вычисляется число d (секретная экспонента), мультипликативно обратное к e по модулю φ(n): d × e ≡ 1 (mod φ(n)).
6. Открытый ключ: пара (e, n). Закрытый ключ: пара (d, n). Числа p, q и φ(n) держатся в секрете или уничтожаются.

Шифрование

Для шифрования сообщения m (представленного в виде числа, меньшего n) с использованием открытого ключа (e, n) выполняется операция:

c = mᵉ mod n

где c — шифротекст.

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

Для расшифрования шифротекста c с использованием закрытого ключа (d, n) выполняется операция:

m = cᵈ mod n

Корректность расшифрования гарантируется тем, что для любого m < n выполняется равенство (mᵉ)ᵈ ≡ m (mod n).

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

RSA также используется для создания цифровых подписей. Процесс обратный шифрованию:

1. Создание подписи: отправитель вычисляет хеш сообщения H, затем возводит его в степень d по модулю n: s = Hᵈ mod n. Подпись s прикладывается к сообщению.
2. Проверка подписи: получатель, зная открытый ключ (e, n), вычисляет H' = sᵉ mod n и сравнивает с хешем исходного сообщения. Если значения совпадают, подпись считается подлинной.

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

Размер ключа

Стойкость RSA напрямую зависит от длины ключа n. По состоянию на 2024 год рекомендуемые размеры ключей:

Угрозы и атаки

Основные известные атаки на RSA:

• Атака на основе подобранного шифротекста: злоумышленник может расшифровать сообщение, если система позволяет многократно расшифровывать произвольные данные.
• Атака по времени: измерение времени выполнения операций позволяет восстановить закрытый ключ.
• Атака по энергопотреблению: анализ энергопотребления устройства при выполнении криптографических операций.
• Атака с использованием общего модуля: если два пользователя используют одинаковое n, но разные e, третья сторона может расшифровать сообщение.
• Квантовая угроза: алгоритм Шора теоретически позволяет разложить большие числа на множители за полиномиальное время на квантовом компьютере. Однако для взлома RSA-2048 потребуется квантовый компьютер с несколькими тысячами логических кубитов, что пока недостижимо.

Практические рекомендации

Для обеспечения безопасности при использовании RSA необходимо:

• Использовать ключи длиной не менее 2048 бит.
• Применять криптостойкие генераторы случайных чисел.
• Использовать схемы дополнения (padding), такие как OAEP (Optimal Asymmetric Encryption Padding) для шифрования и PSS (Probabilistic Signature Scheme) для подписей.
• Регулярно обновлять ключи.
• Избегать использования общего модуля n.

Применение

RSA широко применяется в различных областях информационной безопасности:

• Протокол HTTPS: используется для установления защищённого соединения в веб-браузерах (в составе TLS/SSL).
• Электронная почта: стандарты S/MIME и OpenPGP используют RSA для шифрования и подписи писем.
• Цифровые сертификаты: инфраструктура открытых ключей (PKI) базируется на RSA для удостоверяющих центров.
• Электронная подпись: в России RSA используется в некоторых системах электронного документооборота наряду с ГОСТ-алгоритмами.
• VPN-соединения: протоколы IPsec и OpenVPN поддерживают RSA для аутентификации.
• Криптовалюты: некоторые ранние криптовалюты использовали RSA для подписи транзакций.
• Смарт-карты и банковские карты: RSA применяется для аутентификации чипов EMV.

Критика и альтернативы

Недостатки RSA

• Низкая скорость: операции с большими числами требуют значительных вычислительных ресурсов, особенно для шифрования и расшифрования.
• Размер ключа: ключи RSA значительно больше, чем ключи симметричных алгоритмов (например, AES) при сопоставимом уровне безопасности.
• Уязвимость к квантовым атакам: в перспективе RSA может быть полностью скомпрометирован квантовыми компьютерами.
• Сложность генерации простых чисел: требуется надёжный источник случайности и проверка чисел на простоту.

Альтернативные алгоритмы

• Эллиптическая криптография (ECC): обеспечивает аналогичный уровень безопасности при значительно меньших размерах ключей (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA).
• Криптосистема Эль-Гамаля: основана на сложности дискретного логарифмирования.
• Постквантовые алгоритмы: разрабатываются алгоритмы, устойчивые к квантовым атакам (например, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon).

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

• В 1994 году RSA-129 (129-значное число, 426 бит) был разложен на множители группой учёных с использованием 1600 компьютеров в течение 8 месяцев.
• В 2009 году был взломан RSA-768 (768 бит) — на это потребовалось около 2 лет вычислений на кластере из сотен машин.
• RSA Laboratories регулярно проводила конкурсы по факторизации чисел RSA, стимулируя развитие методов факторизации.
• Алгоритм RSA используется в технологии блокчейн и некоторых криптовалютах, хотя большинство современных систем перешли на ECC.

Источники

1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
2. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
3. Ferguson, N., Schneier, B., & Kohno, T. (2010). Cryptography Engineering: Design Principles and Practical Applications. Wiley.
4. Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2), 203-213.
5. NIST Special Publication 800-57. Recommendation for Key Management.