Криптография
Атаки на асимметричные системы
RSA-2048 математически стойкий - но 33% HTTPS-сайтов были уязвимы к DROWN-атаке через SSLv2, без единой математической слабости RSA.
- DROWN 2016: 33% HTTPS-сайтов уязвимы через SSLv2 оракул - включая facebook.com, yahoo.com
- ROBOT 2017: Bleichenbacher-атака переоткрыта в продуктах F5, Citrix, Cisco - 27% из топ-100 HTTPS сайтов уязвимы
- Факторизация RSA-768 (2009) заняла 2.5 года на сотнях машин - именно поэтому RSA-768 устарел
- Heartbleed косвенно: утечка приватного ключа через переполнение буфера обнулила всю математическую стойкость RSA
Атаки на RSA
RSA-2048 надёжен при правильном использовании, но история знает десятки реальных взломов через ошибки реализации. Атака Bleichenbacher 1998 года эксплуатировала padding PKCS#1 v1.5: сервер возвращал разные ошибки в зависимости от корректности padding, что давало оракул для расшифровки любого ciphertext за ~1 млн запросов. DROWN-атака 2016 года взломала TLS серверы через SSLv2 оракул - пострадали 33% HTTPS-сайтов.
Факторизация - центральная проблема RSA. Метод Полларда p-1 работает если p-1 имеет только малые простые делители: если все простые делители p-1 не превышают B, то факторизация за O(B log B) шагов. Атака Ферма эффективна если p и q близки: разложение n = a^2 - b^2 = (a+b)(a-b). При p-q < n^{0.25} факторизация тривиальна.
ROBOT (Return Of Bleichenbacher's Oracle Threat) 2017: переоткрытие оригинальной атаки. Исследователи нашли уязвимость в 7 ключевых продуктах включая F5, Citrix, Cisco. Facebook использовал уязвимый сертификат - атакующий мог подписывать данные от имени facebook.com. Единственная защита - OAEP вместо PKCS#1 v1.5 и constant-time сравнения.
Почему атака Bleichenbacher работает против PKCS#1 v1.5 RSA, но не против OAEP?
Алгоритм Полига-Хеллмана
Задача дискретного логарифма (DLP): дано g, h, p - найти x такое что g^x ≡ h (mod p). Алгоритм Полига-Хеллмана 1978 решает DLP за O(sum(e_i * (log n + sqrt(p_i)))) где p_i - простые делители порядка группы. Ключевой вывод: если порядок группы имеет только малые простые делители, DLP решается быстро.
Практическое следствие: простые числа для DH должны быть safe primes - вида p = 2q+1 где q тоже простое. Тогда порядок подгруппы = (p-1)/2 = q - большое простое, Полиг-Хеллман неприменим. RFC 3526 определяет стандартные safe prime группы для IKE. Кривые в ECC проектируются с порядком, равным большому простому, по той же причине.
Почему для DH нужны safe primes p = 2q+1?
Метод индексного исчисления
Index Calculus - субэкспоненциальный алгоритм решения DLP в мультипликативных группах Z_p*. Работает за L_p[1/2, c] = exp(c * sqrt(ln p * ln ln p)), что субэкспоненциально. Поэтому DH на конечных полях требует ключи 2048+ бит, тогда как ECDLP не имеет субэкспоненциального алгоритма и 256 бит достаточно.
GNFS (General Number Field Sieve) - лучший известный алгоритм факторизации и DLP в Z_p*. В 2019 RSA-240 (795 бит) был факторизован за ~900 CPU-лет. В 2022 DLP в 795-битной группе решён аналогичным усилием. NIST рекомендует минимум 2048 бит для RSA/DH до 2030 года, 3072 бит - для долгосрочной защиты.
Почему ECC с 256-битным ключом считается эквивалентным RSA-3072?
Метод Копперсмита и решёточные атаки
Метод Копперсмита 1996 находит малые корни многочленов по модулю N за полиномиальное время. Теорема: если f(x) - многочлен степени d и существует x_0 < N^{1/d} такой что f(x_0) ≡ 0 (mod N), то x_0 находится за полиномиальное время через LLL-алгоритм на решётках. Практически: атака на RSA с малой экспонентой шифрования e=3 и незначительным рандомизированием.
LLL-алгоритм (Lenstra-Lenstra-Lovász) 1982 находит 'короткий' вектор в решётке за полиномиальное время. Стал основой десятков атак на криптосистемы. Сегодня LLL - стандартный инструмент криптоаналитика: атаки на DSA с частичной утечкой nonce, атаки на ECC, декодирование кодов исправления ошибок. Библиотека fpylll (Python) и SageMath предоставляют готовые реализации.
При каком условии метод Копперсмита находит малый корень многочлена степени d по модулю N?
Математика атак
- Атаки Bleichenbacher и ROBOT: padding oracle через информационную утечку ошибок PKCS#1 v1.5
- Полиг-Хеллман: DLP решается быстро если порядок группы имеет малые простые делители - защита: safe primes
- Index Calculus (GNFS): субэкспоненциальный алгоритм для DLP/факторизации - отсюда RSA/DH требуют 2048+ бит
- Метод Копперсмита: находит малые корни многочленов через LLL - атакует RSA с малой экспонентой и частичным знанием
Связанные темы
Атаки на асимметричные системы требуют понимания математических основ RSA, ECC и дискретного логарифма
- RSA на практике — OAEP и PSS защищают от атак Bleichenbacher и Hastad
- Постквантовая криптография — Шор сломает RSA/DH/ECC - переход на решёточные схемы
- Атаки по побочным каналам — Timing-атаки на RSA дополняют математические атаки
Вопросы для размышления
- Если математически RSA-2048 не взломан, почему NIST рекомендует переходить на post-quantum криптографию уже сейчас, а не когда квантовые компьютеры станут реальностью?