Криптография
RSA на практике
DROWN (2016): 33% HTTPS-серверов уязвимы из-за поддержки SSLv2 с PKCS#1 v1.5 RSA. Атака Блейхенбахера - оракул расшифровки за ~2^17 запросов. Одна уязвимость в протоколе 1995 года ломала TLS 2016 года. Правильное дополнение RSA - не опциональная деталь.
- **DROWN (2016)**: атака Блейхенбахера на PKCS#1 v1.5. Серверы с SSLv2 стали оракулом для расшифровки TLS 1.2 трафика. Патчи вышли за 48 часов, затронуты OpenSSL, Microsoft, IBM.
- **Ataque ROCA (2017)**: уязвимость в библиотеке Infineon (используется в смарт-картах, паспортах, YubiKey 4): генерация RSA-ключей с предсказуемой структурой. Миллионы ключей заменены.
- **TLS 1.3**: RSA-PSS обязателен для подписи сертификатов. PKCS#1 v1.5 запрещён в новых TLS 1.3 соединениях.
- **PGP**: RSA-2048 с OAEP используется для шифрования сессионного ключа. Переход на Curve25519 (Ed25519 + X25519) в GnuPG 2.1+.
OAEP: безопасное дополнение RSA
Textbook RSA детерминирован: M всегда -> C. Атака: если атакующий знает набор возможных M (например, 'yes'/'no'), он шифрует их и сравнивает с перехваченным C. OAEP (Optimal Asymmetric Encryption Padding) добавляет случайность и делает шифрование вероятностным.
PKCS#1 v1.5 (более старая схема дополнения) уязвима к атаке Блейхенбахера (1998): CBC-MAC oracle позволяет расшифровать любой ciphertext за 2^20 запросов. Атака была реализована против DROWN (SSL) в 2016. Никогда не использовать PKCS#1 v1.5 в новых системах.
Почему textbook RSA (без дополнения) уязвим к chosen-plaintext атаке?
RSA-PSS: подписи с вероятностным дополнением
RSA подпись - 'шифрование' приватным ключом: S = H(M)^d mod n. Проверка: S^e mod n == H(M). RSA-PSS (Probabilistic Signature Scheme) добавляет случайность в подпись, что даёт доказуемую безопасность в random oracle model.
RSA-PKCS1-v1.5 подписи детерминированы и широко используются в legacy системах (TLS 1.2 сертификаты). RSA-PSS вероятностен и доказуемо безопасен. TLS 1.3 требует RSA-PSS для новых сертификатов. CA/Browser Forum запрещает RSA-PKCS1-v1.5 для TLS-сертификатов с 2021 года.
Подписывается ли сообщение M напрямую в RSA или хэш H(M)?
Атака малой экспоненты
Если e мало (e=3) и одно сообщение M шифруется для трёх получателей с разными n1, n2, n3, то по Китайской теореме об остатках (CRT) атакующий восстанавливает M^3 без факторизации, а затем берёт кубический корень.
Атака Хастада полностью устраняется использованием OAEP: случайный padding делает M_padded уникальным для каждого шифрования, даже при одном исходном M. Это ещё одна причина, почему textbook RSA недопустим в production.
Почему атака Хастада работает при e=3 и трёх получателях, но не работает при использовании OAEP?
Атака Винера: малое d
Атака Винера (1990): если d < n^(1/4)/3, приватный ключ d восстанавливается из публичного ключа (n, e) через цепные дроби. Мотивация для малого d - ускорение расшифровки. Цена - полная компрометация.
Современное расширение - атака Бонэ-Дурфи (1999): восстанавливает d < n^0.292. Для RSA-2048 это ~178-битные d - всё ещё намного меньше безопасного d. Все стандартные библиотеки (OpenSSL, BouncyCastle) генерируют d близким к размеру n.
RSA-1024 достаточно безопасен для внутренних систем, не требующих долгосрочной защиты
RSA-1024 взламывается специализированным железом. NIST вывел RSA-1024 из одобренных алгоритмов в 2010 году. Минимум - RSA-2048, для долгосрочной защиты - RSA-3072 или переход на ECDSA P-256
В 2009 году RSA-768 был факторизован за 2 CPU-года. RSA-1024 оценивается в ~2^80 операций - достижимо для государственных акторов. RSA-2048 ~ 2^112 - безопасен до ~2030 по NIST SP 800-57.
Почему 'оптимизация' RSA через малое d опасна?
Ключевые идеи
- **OAEP обязателен**: textbook RSA детерминирован - атаки через CPA. OAEP добавляет случайный seed, делая шифрование вероятностным. PKCS#1 v1.5 уязвим к Блейхенбахеру.
- **RSA-PSS для подписей**: PSS вероятностен и доказуемо безопасен. PKCS#1 v1.5 подписи детерминированы. TLS 1.3 требует PSS.
- **Атака Хастада**: малое e + многократное шифрование одного M разным получателям = CRT-восстановление M^e. Защита: OAEP.
- **Атака Винера**: малое d (< n^(1/4)/3) = восстановление d через цепные дроби из публичного ключа. Никогда не оптимизировать d.
Связанные темы
RSA на практике связан с протоколами и атаками:
- RSA математика — Генерация ключей, теорема Эйлера, корректность - математическая основа для понимания практических уязвимостей.
- Атаки на асимметричные системы — Атаки Блейхенбахера, Копперсмита - класс атак на RSA с оракулом или слабыми параметрами.
- PKI и сертификаты — RSA-2048 или ECDSA P-256 - ключи в X.509 сертификатах. CA подписывает PSS или ECDSA.
Вопросы для размышления
- Если PKCS#1 v1.5 уязвим, почему он всё ещё встречается в legacy системах и что это означает для их безопасности?
- При RSA шифровании email для 100 получателей с одним публичным ключом каждого - как атака Хастада применяется здесь если e=3?
- Смарт-карта с RSA-2048 выполняет подпись за 300ms. Разработчик хочет ускорить до 50ms через малое d. Какова максимальная безопасная длина d?