Криптосистема RSA

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

История

Алгоритм RSA был впервые опубликован в 1977 году в статье «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems» в журнале Communications of the ACM. Разработка велась в Массачусетском технологическом институте. В 1983 году авторы получили патент США (US 4405829), который действовал до 2000 года.

Идея асимметричного шифрования была предложена Уитфилдом Диффи и Мартином Хеллманом в 1976 году, но RSA стал первой практической реализацией, удовлетворяющей требованиям конфиденциальности и аутентификации. В 1997 году было рассекречено, что британский математик Клиффорд Кокс из Центра правительственной связи (GCHQ) разработал эквивалентную систему ещё в 1973 году, однако его работа не была опубликована и оставалась засекреченной до 1997 года.

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

RSA опирается на свойства модульной арифметики и теорему Эйлера. Ключевым понятием является функция Эйлера φ(n), которая для числа n = p × q, где p и q — простые числа, вычисляется как φ(n) = (p − 1)(q − 1).

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

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

Выбираются два больших простых числа p и q (обычно длиной не менее 512 бит каждое).
Вычисляется их произведение n = p × q. Длина n определяет криптостойкость системы.
Вычисляется значение функции Эйлера: φ(n) = (p − 1)(q − 1).
Выбирается целое число e (открытая экспонента), удовлетворяющее условиям: 1 < e < φ(n) и gcd(e, φ(n)) = 1 (взаимно простые числа). На практике часто используют e = 65537 (2¹⁶ + 1) как компромисс между скоростью и безопасностью.
Вычисляется число d (секретная экспонента) как мультипликативное обратное к e по модулю φ(n): d ≡ e⁻¹ (mod φ(n)). Это означает, что e × d ≡ 1 (mod φ(n)).

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

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

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

Шифротекст c = mᵉ mod n

Для дешифрования получатель применяет свой закрытый ключ:

Исходное сообщение m = cᵈ mod n

Корректность алгоритма обеспечивается теоремой Эйлера: для любого m, взаимно простого с n, выполняется mᵉᵈ ≡ m (mod n). Если m не взаимно просто с n (что маловероятно при больших p и q), равенство также выполняется благодаря китайской теореме об остатках.

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

RSA может использоваться для создания цифровой подписи. В этом случае отправитель подписывает сообщение своим закрытым ключом:

Подпись s = mᵈ mod n

Любой получатель может проверить подпись, используя открытый ключ отправителя:

m = sᵉ mod n

Если результат совпадает с исходным сообщением, подпись считается подлинной.

Криптостойкость

Безопасность RSA основана на предположении, что задача факторизации большого целого числа n на простые множители p и q является вычислительно сложной. Если злоумышленник сможет разложить n, он вычислит φ(n) и, зная открытую экспоненту e, найдёт секретную экспоненту d.

Угрозы

Основные угрозы для RSA включают:

Квантовые компьютеры: алгоритм Шора позволяет эффективно решать задачу факторизации на квантовом компьютере. При достаточном развитии квантовых технологий RSA станет небезопасным. В связи с этим активно разрабатываются постквантовые криптосистемы.
Атаки по побочным каналам: анализ времени выполнения операций, потребляемой мощности или электромагнитного излучения может позволить восстановить закрытый ключ. Для защиты применяются методы маскирования и постоянного времени выполнения.
Атаки на основе выбранного шифротекста: злоумышленник может дешифровать сообщение, запрашивая дешифрование специально подобранных шифротекстов. Защита обеспечивается использованием схем дополнения (padding), таких как OAEP (Optimal Asymmetric Encryption Padding).
Уязвимости реализации: ошибки в генерации простых чисел (например, использование предсказуемых генераторов случайных чисел) могут привести к компрометации ключей.

Применение

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

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

Реализации

RSA реализован во многих криптографических библиотеках и программных продуктах:

OpenSSL (широко используется в Linux и macOS)
GnuPG (GNU Privacy Guard)
Java Cryptography Extension (JCE)
.NET Framework (System.Security.Cryptography)
Crypto++ (C++ библиотека)
Bouncy Castle (Java, C#)

Критика и ограничения

RSA имеет ряд недостатков по сравнению с более современными алгоритмами:

Низкая скорость: операции шифрования и дешифрования с большими ключами (2048+ бит) выполняются значительно медленнее, чем операции в симметричных алгоритмах (AES) или алгоритмах на эллиптических кривых (ECDSA).
Размер шифротекста: шифротекст имеет тот же размер, что и модуль n (например, 256 байт для 2048-битного ключа), что может быть неэффективно для коротких сообщений.
Отсутствие прямой поддержки для шифрования длинных сообщений: RSA может шифровать только сообщения, длина которых меньше длины модуля. Для больших объёмов данных используется гибридная схема: RSA шифрует симметричный ключ, а сам ключ используется для шифрования данных.
Уязвимость к квантовым атакам: как упоминалось выше, появление достаточно мощных квантовых компьютеров сделает RSA небезопасным.

Альтернативы

Основными альтернативами RSA являются:

Криптосистемы на эллиптических кривых (ECC): обеспечивают аналогичный уровень безопасности при меньшей длине ключа (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA). Широко используются в современных протоколах (TLS 1.3, Bitcoin, Ethereum).
Криптосистема Эль-Гамаля: основана на сложности задачи дискретного логарифмирования.
Постквантовые алгоритмы: такие как CRYSTALS-Kyber (шифрование) и CRYSTALS-Dilithium (подпись), которые считаются устойчивыми к атакам квантовых компьютеров. В 2024 году Национальный институт стандартов и технологий США (NIST) опубликовал первые стандарты постквантовой криптографии.

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

В 1994 году число RSA-129 (129 цифр, около 426 бит) было факторизовано группой исследователей под руководством А. Ленстры с использованием добровольных вычислений на 1600 компьютерах. Это заняло 8 месяцев.
В 2009 году группа учёных из EPFL (Швейцария) успешно восстановила закрытый ключ RSA, анализируя звук, издаваемый процессором во время дешифрования (акустическая криптоатака).
Алгоритм RSA используется в системе электронных платежей Visa и Mastercard для защиты транзакций.
В России сертифицированные средства криптографической защиты информации (СКЗИ) могут использовать RSA, но предпочтение отдаётся национальным стандартам (ГОСТ Р 34.10-2012, ГОСТ Р 34.11-2012).

Источники

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.
Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
NIST Special Publication 800-56B Rev. 2: «Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography» (2019).
NIST Post-Quantum Cryptography Standardization Project (2024).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →