RSA алгоритм

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

История

Идея асимметричной криптографии была впервые публично предложена Уитфилдом Диффи и Мартином Хеллманом в 1976 году. В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман, работавшие в Массачусетском технологическом институте, разработали практическую реализацию такой системы, основанную на математической задаче разложения числа на простые множители. В 1978 году алгоритм был опубликован в статье «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems».

В 1983 году компания RSA Security (изначально — RSA Data Security) получила патент на алгоритм, который действовал до 2000 года в США и до 2003 года в некоторых других странах. После истечения срока патента RSA стал общедоступным. В 1990-х годах алгоритм стал основой для стандартов цифровой подписи и шифрования, включая PKCS#1 и часть протокола SSL/TLS.

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

RSA основан на свойствах модульной арифметики и теореме Эйлера. Ключевым математическим понятием является функция Эйлера φ(n), которая для числа n = p·q (где p и q — простые числа) равна (p-1)(q-1). Безопасность алгоритма опирается на предположение, что для достаточно больших чисел (сотни десятичных знаков) задача факторизации n на простые множители p и q является вычислительно неразрешимой за приемлемое время.

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

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

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

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

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

Шифрование сообщения M (представленного в виде числа, меньшего n) выполняется по формуле: C = M^e mod n

Расшифрование шифротекста C: M = C^d mod n

Корректность расшифрования обеспечивается тем, что M^(e·d) ≡ M (mod n) для всех M, меньших n, благодаря теореме Эйлера.

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

RSA также используется для создания цифровых подписей. Подпись S создаётся с помощью закрытого ключа: S = M^d mod n

Проверка подписи выполняется с помощью открытого ключа: M' = S^e mod n

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

Размеры ключей и безопасность

Безопасность RSA напрямую зависит от длины ключа. Рекомендуемые минимальные размеры модуля n:

Современные оценки показывают, что для взлома 2048-битного RSA с помощью классических компьютеров потребуется более 10¹² лет. Однако квантовые компьютеры, использующие алгоритм Шора, теоретически способны взломать RSA за полиномиальное время, что делает алгоритм уязвимым перед квантовыми атаками.

Практические реализации

RSA используется в различных протоколах и стандартах:

• SSL/TLS — для защиты веб-трафика (рукопожатие и обмен ключами).
• PGP/GPG — для шифрования электронной почты и файлов.
• SSH — для аутентификации и шифрования удалённых подключений.
• PKCS#1 — стандарт RSA Laboratories, определяющий форматы ключей и схемы шифрования/подписи.
• X.509 — для цифровых сертификатов, используемых в HTTPS и электронной подписи.

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

RSA имеет несколько недостатков:

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

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

Среди асимметричных алгоритмов, используемых вместо RSA, выделяются:

• ECC (эллиптическая криптография) — обеспечивает аналогичный уровень безопасности при меньшей длине ключа (например, 256-битный ключ ECC эквивалентен 3072-битному RSA).
• DSA (Digital Signature Algorithm) — алгоритм цифровой подписи, основанный на задаче дискретного логарифмирования.
• Постквантовые алгоритмы — например, CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, которые устойчивы к квантовым атакам.

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

• В 2009 году был взломан 768-битный RSA (232 десятичных знака) с использованием кластера из сотен компьютеров за два года.
• В 2023 году китайские исследователи сообщили о факторизации 2048-битного числа с помощью квантового компьютера D-Wave, но это утверждение оспаривается научным сообществом.
• RSA является частью стандарта ГОСТ Р 34.10-2012 в России, хотя для цифровой подпизи в РФ официально используется алгоритм на эллиптических кривых (ГОСТ Р 34.10-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., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• Ferguson, N., Schneier, B., Kohno, T. (2010). «Cryptography Engineering». Wiley.
• NIST Special Publication 800-57 Part 1 Rev. 5 (2020). «Recommendation for Key Management».
• ГОСТ Р 34.10-2012. «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».