Алгоритм RSA

RSA — это криптографический алгоритм с открытым ключом, обеспечивающий шифрование и цифровую подпись данных. Относится к классу асимметричных шифров, в которых используются два различных ключа: открытый (public key) для шифрования и закрытый (private key) для расшифрования. Назван по первым буквам фамилий создателей — Рональда Ривеста, Ади Шамира и Леонарда Адлемана (Rivest–Shamir–Adleman). Безопасность RSA основана на практической сложности разложения большого целого числа (модуля) на простые множители — задаче, которая не имеет эффективного алгоритма решения для чисел длиной от 2048 бит и более.

История

Предпосылки создания

До середины 1970-х годов вся криптография была симметричной: для шифрования и расшифрования использовался один и тот же секретный ключ, что требовало надёжного канала передачи ключа между сторонами. В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали концепцию криптографии с открытым ключом, однако практической реализации асимметричного алгоритма шифрования тогда не существовало.

Разработка алгоритма

В 1977 году сотрудники Массачусетского технологического института Рональд Ривест, Ади Шамир и Леонард Адлеман предложили алгоритм, описанный в статье «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems». Авторы опирались на идеи Клода Шеннона и теоретическую работу Диффи — Хеллмана. Первая версия алгоритма была представлена в апреле 1977 года, а доработанная — в сентябре того же года. В 1983 году на алгоритм был получен патент США (номер 4 405 829), действовавший до 2000 года.

Распространение

После истечения срока патента RSA стал свободно доступным и вошёл в стандарты ANSI X9.31, PKCS#1, ISO/IEC 9796 и RFC 3447. Алгоритм широко применяется в протоколах SSL/TLS, PGP, S/MIME, а также в официальных криптографических стандартах США (FIPS 186-4) и России (после соответствующих доработок — в ГОСТ Р 34.10-2012).

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

Теоретическая база

RSA опирается на свойства односторонних функций с потайным ходом. В его основе лежат:

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

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

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

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

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

Криптографические операции

Шифрование

Сообщение M, представленное в виде числа, меньшего n, шифруется по формуле: C = M^e mod n. Полученный шифротекст C имеет размер, близкий к длине модуля n. Если сообщение длиннее n, оно предварительно разбивается на блоки.

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

Владелец закрытого ключа восстанавливает исходное сообщение: M = C^d mod n. Корректность расшифрования гарантируется теоремой Эйлера: (M^e)^d ≡ M (mod n) для всех M, взаимно простых с n (и для остальных — также, с небольшими исключениями).

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

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

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

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

Надёжность RSA зависит от длины модуля n. Практические рекомендации по длине ключа со временем возрастают из-за прогресса в алгоритмах факторизации и вычислительной технике:

• 1024 бита — минимальная длина, признаваемая недостаточной для долгосрочной защиты (по оценкам Национального института стандартов и технологий США, 2023).
• 2048 бита — стандартная длина, рекомендуемая для большинства применений (обеспечивает защиту ориентировочно до 2030 года).
• 3072 бита и более — для систем, требующих долговременной стойкости.

Согласно оценкам экспертов, факторизация 2048-битного модуля на современном оборудовании (2025 год) потребует эксафлопсных вычислений в течение десятилетий. С развитием квантовых вычислений ожидается, что алгоритм Шора позволит решить задачу факторизации за полиномиальное время, что сделает RSA уязвимым. Поэтому ведутся активные исследования алгоритмов, устойчивых к квантовому взлому (постквантовая криптография).

Атаки на RSA

Основные известные уязвимости и атаки:

• Атака по времени (timing attack) — вычисление закрытого ключа через анализ времени расшифрования (предотвращается использованием алгоритмов с константным временем).
• Атака на основании выбранного шифротекста — злоумышленник может получить расшифровку случайных данных (защищается добавлением случайных данных перед шифрованием — OAEP, Optimal Asymmetric Encryption Padding).
• Атака с использованием общего модуля — если один и тот же модуль n используется несколькими пользователями, то любой из них может вычислить закрытый ключ другого.
• Атака с малым показателем e — при малом e (например, 3) может быть использована атака Копперсмита для восстановления сообщения.
• Квантовая атака — алгоритм Шора позволяет разложить n за полиномиальное время, что теоретически делает RSA полностью уязвимым при наличии мощного квантового компьютера.

Применение

В протоколах

RSA является основой многих широко используемых протоколов:

• SSL/TLS — для установления защищённого соединения при передаче данных через интернет (особенно на этапе рукопожатия, когда клиент шифрует временный ключ симметричного шифрования).
• SSH (Secure Shell) — для аутентификации по открытому ключу.
• PGP/GPG (Pretty Good Privacy) — для шифрования электронных писем и цифровых подписей.
• X.509 — для создания и проверки цифровых сертификатов, используемых в инфраструктуре открытых ключей (PKI).
• S/MIME — для защиты электронной почты (шифрование и подпись).

В финансовой сфере

RSA применяется в системах электронных платежей и банковских карт (например, в стандартах EMV для микропроцессорных карт второго поколения). Алгоритм также используется в системах предоставления цифровых подписей для финансовых документов и электронных накладных.

В стандартах

Алгоритм RSA включён в:

• ANSI X9.31 (американский стандарт для цифровых подписей в финансовой индустрии).
• PKCS#1 (стандарт компании RSA Laboratories — описание заполнения и математических деталей).
• IEEE P1363.
• Российские стандарты не используют RSA напрямую, но отдельные протоколы (например, для межведомственного электронного документооборота) допускают его применение при зарубежных контрагентах.

Достоинства и недостатки

Преимущества

• Простота концепции и математической реализации.
• Высокая скорость проверки цифровой подписи (при малых e).
• Возможность использования для шифрования и подписи в одной системе.
• Широкая распространённость и поддержка во всех современных библиотеках.

Недостатки

• Низкая скорость шифрования и расшифрования (примерно в 100–1000 раз медленнее симметричных алгоритмов, таких как AES).
• Необходимость заполнения (padding) сообщений для устойчивости к некоторым атакам (наиболее распространённый — OAEP).
• Уязвимость к квантовым вычислениям в долгосрочной перспективе.
• Большие ключи (до 4096 бит) требуют значительных ресурсов памяти и процессора.

Пример реализации (учебный)

Для демонстрации принципа работы приводятся минимальные значения. Пусть p = 61, q = 53. Тогда:

• n = 61 × 53 = 3233.
• φ(n) = (61-1)(53-1) = 60 × 52 = 3120.
• Выбирается e = 17 (взаимно простое с 3120).
• Вычисляется d = 2753 (обратное к 17 по модулю 3120).
• Открытый ключ: (3233, 17). Закрытый ключ: (3233, 2753).
• Шифрование сообщения M = 123: C = 123¹⁷ mod 3233 = 855.
• Расшифрование: M = 855²⁷⁵³ mod 3233 = 123.

В реальных системах p и q выбираются длиной от 1024 бит, а сообщение перед шифрованием проходит процедуру заполнения OAEP.

Перспективы

По состоянию на 2025 год RSA остаётся наиболее распространённым асимметричным алгоритмом в мире. Однако его использование постепенно сокращается в пользу алгоритмов, основанных на эллиптических кривых (ECDSA, Ed25519), которые обеспечивают равный уровень безопасности при меньшей длине ключа (256 бит против 3072 бит). В связи с развитием квантовых вычислений Национальный институт стандартов и технологий США (NIST) проводит конкурс на постквантовые стандарты, и ожидается, что в течение 2020–2030 годов многие системы мигрируют на алгоритмы, устойчивые к квантовому взлому, такие как CRYSTALS-Kyber (для шифрования) и CRYSTALS-Dilithium (для подписи).

Источники

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.
• Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography.
• Ferguson, N., Schneier, B., & Kohno, T. (2010). Cryptography Engineering.
• Национальный институт стандартов и технологий США (NIST). FIPS 186-4: Digital Signature Standard (DSS).
• RFC 3447 — Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1.