RSA (шифрование RSA) — один из первых и самых распространённых алгоритмов с открытым ключом, названный по фамилиям Рона Ривеста, Ади Шамира и Леонарда Адлемана; применяется для шифрования и цифровой подписи.
Как работает RSA
RSA был опубликован в MIT в 1977 году. Его стойкость основана на сложности разложения очень большого числа на два простых множителя:
- Владелец ключа выбирает два больших случайных простых числа и перемножает их; произведение (модуль) становится частью открытого ключа.
- При шифровании сообщение возводится в степень открытой экспоненты по этому модулю; обратить операцию может лишь тот, кто знает простые множители и может вычислить закрытую экспоненту.
- Подпись работает наоборот: закрытый ключ создаёт цифровую подпись, которую любой может проверить открытым ключом.
На практике RSA шифрует только небольшие значения, например сеансовые ключи, и всегда используется со схемами дополнения: OAEP для шифрования и PSS для подписей.
Почему RSA важен
Как ключевой алгоритм криптографии с открытым ключом, RSA подписывает большинство TLS-сертификатов, сертификаты подписи кода и обновления ПО, а также защищает SSH-ключи и шифрование почты. Его слабости хорошо изучены:
- Короткие ключи — 829-битное число RSA-250 было разложено в 2020 году; 1024-битные ключи считаются устаревшими, рекомендуется не менее 2048 бит.
- Оракулы дополнения — атака Блейхенбахера 1998 года на дополнение PKCS #1 v1.5 вернулась в 2017 году как уязвимость ROBOT во многих TLS-серверах.
- Слабая генерация ключей — уязвимость ROCA (2017) в библиотеке Infineon позволяла факторизовать ключи смарт-карт, включая эстонские ID-карты.
В TLS 1.3 передача ключей через RSA полностью исключена в пользу эфемерного протокола Диффи — Хеллмана, обеспечивающего прямую секретность.
RSA и квантовые вычисления
Алгоритм Шора на достаточно мощном квантовом компьютере сможет эффективно факторизовать модули RSA. Поэтому NIST предложил объявить RSA и другие классические алгоритмы с открытым ключом устаревшими к 2030 году и запретить их после 2035 года, перейдя на постквантовую криптографию. Организациям стоит уже сейчас выяснить, где используется RSA, и спланировать миграцию.
