RSA атаки CTF: от чтения условия до флага за шесть стандартных приёмов

RSA атаки CTF: от чтения условия до флага за шесть стандартных приёмов

Первая RSA-задача на CTF выглядит одинаково: файл output.txt с тремя большими числами — n, e, c — и тишина. Из двухсот с лишним crypto-задач, которые я прорешал на CryptoHack, PicoCTF и HTB, больше половины сводились к одной из шести стандартных атак, каждая — 5-15 строк на Python. Разница между «застрял на два часа» и «сдал флаг за пять минут» не в знании высшей математики, а в умении быстро определить, какой параметр сломан. Это систематизация подходов к RSA атакам CTF: от диагностики условия до рабочего кода, превращающего шифротекст в открытый текст.

Анатомия RSA-задания в CTF: входные данные и алгоритм выбора атаки

В большинстве задач по RSA криптографии CTF задания сводятся к одному: вам дают открытый ключ (n, e) и шифротекст c, а вы должны восстановить сообщение m. Стандартная расшифровка требует секретной экспоненты d, которую можно вычислить только зная разложение n на простые множители p и q. Задача автора — сделать один из параметров «слабым». Ваша задача — определить, какой именно.

Чек-лист, который я прохожу при каждом новом задании, прежде чем писать хоть строчку кода:

1. Размер n — до 256 бит? Факторизуется мгновенно (msieve/yafu/ECM). 384–512 бит — факторизация возможна, но требует GNFS/CADO-NFS и часов работы. 768+ бит — прямая факторизация не поможет, ищите другую слабость.
2. Значение e — маленькое (3, 5, 7, 17)? Возможна атака малой экспоненты RSA или атака Хастада.
3. Значение e непропорционально большое (сопоставимо с n)? Вероятно, d маленькое — RSA Wiener attack CTF.
4. Несколько пар (n, e, c) с одинаковым e? — Broadcast-атака Хастада.
5. Несколько модулей? — Вычислить GCD попарно. Общий делитель больше единицы — мгновенная факторизация.
6. Один модуль, но два разных e? — Общий модуль RSA атака.
7. n присутствует в factordb? — Проверка занимает секунды, а задачу может решить мгновенно.

Этот алгоритм покрывает примерно 80% задач уровня easy-medium. Теперь разберём каждую атаку с кодом и ограничениями.

Требования к окружению

Все примеры воспроизводимы на любой ОС с Python 3.9+. Установка зависимостей: pip install gmpy2 sympy pycryptodome. Для автоматизации — RsaCtfTool (Python 3.9+, SageMath рекомендуется, но не обязателен). RAM: 1-2 ГБ достаточно для любых CTF-задач по RSA, вычисления не ресурсоёмкие.

Атака малой экспоненты RSA: когда e=3 превращает шифрование в формальность

Самая частая «первая» RSA-задача на любом CTF и самая простая RSA e=3 атака в принципе. Условие: дано n (большое), e = 3, c (шифротекст). Иногда e = 5 или 17, но принцип тот же.

Шифрование RSA — это c = m^e mod n. Если сообщение m настолько маленькое, что m^e < n, то mod не срабатывает. Шифротекст c — просто m^e в обычных целых числах. Расшифровка сводится к извлечению корня e-й степени. По сути, «шифрование» тут — красивый фантик, который ничего не прячет.

import gmpy2
from Crypto.Util.number import long_to_bytes

# Дано: n, e=3, c из условия задачи
m, is_exact = gmpy2.iroot(c, e)
if is_exact:
    print(long_to_bytes(int(m)))
# Если is_exact == False, перебираем: c + k*n для k=1,2,...

gmpy2.iroot(c, e) возвращает целочисленный корень и флаг точности. Если is_exact == True — сообщение восстановлено, long_to_bytes из pycryptodome переводит число обратно в читаемую строку — обычно это и есть флаг.

Если m^e чуть больше n (то есть m^e = c + k*n для небольшого k), перебирайте k: вычисляйте gmpy2.iroot(c + k*n, e) для k = 0, 1, 2, ... пока не получите точный корень. На практике k редко превышает несколько тысяч.

Когда атака НЕ работает: если автор задачи применил OAEP или PKCS#1 padding. Padding дополняет сообщение случайными байтами, и m^e гарантированно превышает n в разы. Отсутствие padding в условии — как раз маркер этой уязвимости. Атака бесполезна и при e = 65537 (стандартное значение) — m^65537 астрономически превышает n для любого сообщения длиннее нескольких байт.

Контекст за пределами CTF: слабые ключи RSA с малым e без padding попадают под категорию OWASP A02:2021 (Cryptographic Failures) — ошибки криптографической реализации, ведущие к раскрытию данных.

Атака Хастада: одно сообщение, три получателя, ноль секретов

Допустим, одно и то же сообщение m зашифровано экспонентой e = 3, но тремя разными модулями n1, n2, n3. Вы перехватили три шифротекста: c1, c2, c3. Именно такой сценарий разбирался в задании NeoQUEST-2016, writeup которого опубликован на Хабре — участники находили три файла .asn1 с парами (n_i, c_i) и одинаковым e = 3.

Математика тут прозрачная. Мы знаем: c1 = m^3 mod n1, c2 = m^3 mod n2, c3 = m^3 mod n3. Если модули попарно взаимно просты, Китайская теорема об остатках (CRT) восстанавливает m^3 mod (n1*n2*n3). Поскольку m < min(n_i), то m^3 < n1*n2*n3, и mod ничего не отсекает. Извлекаем кубический корень — получаем m.

from sympy.ntheory.modular import crt
import gmpy2
from Crypto.Util.number import long_to_bytes

# Дано: (n1,c1), (n2,c2), (n3,c3), e=3
moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
m_cubed, _ = crt(moduli, remainders)  # убедитесь, что gcd(n_i, n_j)==1 для всех пар, иначе это атака общего множителя
m, _ = gmpy2.iroot(int(m_cubed), 3)
print(long_to_bytes(int(m)))

crt из sympy принимает списки модулей и остатков, возвращает результат CRT. Дальше — стандартное извлечение корня, как в предыдущей атаке.

Когда атака НЕ работает: нужно минимум e шифротекстов с попарно взаимно простыми модулями и идентичным сообщением. Если сообщения хотя бы немного отличаются (разный padding для каждого получателя), прямая атака Хастада бессильна. Для связанных сообщений вида m_i = a_i*m + b_i существует обобщённая версия — атака Франклина-Рейтера, но она на порядок сложнее и встречается в задачах уровня hard. Как отмечено в статье на Вики по криптоанализу RSA, защитой от Хастада служит произвольная (не фиксированная) перестановка при формировании сообщений для каждого адресата.

Факторизация RSA модуля: от factordb до метода Ферма

Если ни малая экспонента, ни множественные шифротексты не применимы, следующий шаг — попытка факторизации модуля RSA. Это фундаментальный подход: зная p и q, вы вычисляете d через d = pow(e, -1, (p-1)*(q-1)) и расшифровываете напрямую. Весь вопрос — откуда взять p и q.

Factordb: факторизация модуля за секунды

factordb.com — коллективная база факторизованных чисел. Многие авторы CTF-задач берут «интересные» числа из учебников или генерируют ключи без достаточной энтропии, и модули попадают в базу. Вставьте n на сайте или используйте factordb-pycli (команда factordb <число>). Статус FF (fully factored) — задача решена: забираете p и q, вычисляете d, расшифровываете c. RsaCtfTool тоже проверяет factordb автоматически через --attack factordb, а опция --sendtofdb отправляет ваш модуль в базу для будущих поколений.

Маленький модуль: прямая факторизация слабых ключей RSA

Модуль до 256 бит факторизуется мгновенно. 512 бит — за часы-сутки утилитами msieve, yafu или CADO-NFS на одной машине (в облаке с распараллеливанием — несколько часов). 768-битный RSA был факторизован ещё в 2009 году группой учёных из Швейцарии, Японии и других стран (Kleinjung et al., «Factorization of a 768-bit RSA modulus», CRYPTO 2010) — правда, для этого потребовалось около 2000 core-years вычислений на множестве кластеров. В CTF модуль до 512 бит — прямой сигнал «факторизуй меня».

Метод Ферма: близкие простые числа

Если p и q выбраны слишком близко друг к другу (оба рядом с sqrt(n)), работает факторизация Ферма. Алгоритм начинает с a = ceil(sqrt(n)) и инкрементирует a, пока a^2 - n не станет полным квадратом b^2. Тогда n = (a+b)(a-b), множители найдены. Количество итераций пропорционально |p - q|: чем ближе множители, тем быстрее.

Böck (2023) показал, что эта атака актуальна и за пределами CTF: в работе «Fermat Factorization in the Wild» (IACR ePrint 2023/026) обнаружились RSA-ключи в принтерах Canon/Fujifilm, факторизуемые методом Ферма за одну итерацию. Одну. Причина — дефектные генераторы случайных чисел, производящие последовательные или почти последовательные простые. В CTF сценарий распространён: автор генерирует p и q в узком диапазоне, а RsaCtfTool --publickey key.pub --attack fermat находит множители за доли секунды.

Pollard p-1 и гладкие числа

Если p - 1 гладкое (все его простые делители малы), срабатывает алгоритм Полларда p-1. Аналогично, алгоритм Вильямса p+1 эксплуатирует гладкость p + 1. Как отмечает EN-2 (sjoerdlangkemper.nl), вероятность случайно получить гладкое p - 1 пренебрежимо мала, поэтому некоторые реализации специально генерируют «strong primes» с большими простыми делителями p - 1 и p + 1. В CTF гладкие простые — нарочная подсказка автора. Увидели, что Pollard отработал — значит, автор хотел, чтобы вы его запустили.

Реальный мир: ROCA и CVE-2017-15361

Уязвимость ROCA (Return of Coppersmith's Attack), зарегистрированная как CVE-2017-15361, затронула RSA-ключи, сгенерированные аппаратными модулями Infineon Technologies. Из-за дефекта в алгоритме генерации простых чисел ключи имели предсказуемую структуру, допускающую эффективную факторизацию. Скомпрометированы были более 750 000 эстонских национальных ID-карт, TPM-чипы в ноутбуках крупных производителей и токены безопасности. EPSS score CVE-2017-15361 — 0.0983 (≈9.8% вероятность эксплуатации в 30 дней), percentile 0.9494 — в топ-5% CVE по относительной вероятности. RsaCtfTool умеет проверять ключи на уязвимость ROCA: RsaCtfTool --isroca --publickey key.pub.

RSA Wiener attack CTF: большая экспонента как маркер уязвимости

Атака Винера — один из самых элегантных приёмов криптоанализа RSA и частый гость на CTF средней сложности. Распознать несложно: если открытая экспонента e аномально большая (по длине сопоставима с n), значит секретная экспонента d мала.

Почему? e * d ≡ 1 (mod φ(n)). Если d мало, e должно быть велико, чтобы произведение дало единицу по модулю lambda(n). Теорема Винера (1990) гарантирует восстановление d при d < N^(1/4) / 3. Бонех и Дурфе (Boneh-Durfee, 1999) эвристически улучшили границу до d < N^0.292 с помощью LLL-редукции решётки, согласно работе Boneh & Durfee (Eurocrypt 1999).

Механика: d восстанавливается через разложение дроби e/n в цепную дробь. Подходящие дроби (convergents) перебираются по порядку: для каждого кандидата проверяется, даёт ли он корректное разложение n на множители. Если да — d найдено. Красота в том, что вся атака — это по сути арифметика с дробями, никакой тяжёлой алгебры.

Реализация: библиотека owiener (pip install owiener, вызов owiener.attack(e, n) возвращает d или None). Либо RsaCtfTool --publickey key.pub --attack wiener. В SageMath цепные дроби доступны через continued_fraction(e/n).convergents() — каждую подходящую дробь проверяете как кандидата на d.

Когда атака НЕ работает: если d чуть превышает порог n^0.25, стандартная реализация Винера не справится. Порог Бонех-Дурфи (n^0.292) шире, но его реализация требует LLL-редукции решётки и SageMath. Если автор задачи намеренно установил d между этими порогами — задача переходит в категорию hard.

[Применимо: CTF задачи, где e по длине сопоставимо с n. Не работает при стандартном e=65537]

Общий модуль RSA атака и эксплуатация общего множителя

Две связанные, но разные атаки. Обе эксплуатируют ситуацию, когда несколько RSA-ключей связаны между собой.

Общий модуль: одно n, два e

Если одно сообщение зашифровано двумя разными экспонентами e1 и e2, но с одним и тем же модулем n, и gcd(e1, e2) = 1, сообщение восстанавливается без знания d. Находим a и b такие, что a*e1 + b*e2 = 1 (расширенный алгоритм Евклида), и вычисляем m = c1^a * c2^b mod n. Работает потому, что c1^a * c2^b = m^(a*e1) * m^(b*e2) = m^(a*e1 + b*e2) = m^1 mod n. Если a или b отрицательно, в Python 3.8+ pow(c, a, n) с отрицательным a работает напрямую (при gcd(c,n)==1), поэтому m = pow(c1, a, n) * pow(c2, b, n) % n корректно даже при отрицательных коэффициентах. На практике gcd(c, n) = 1 почти всегда; если же gcd(c, n) > 1 — поздравляю, вы уже факторизовали n через этот GCD и можете расшифровать напрямую.

В CTF сценарий общего модуля RSA обычно подаётся как два файла с одинаковым n и разными e. Решение через RsaCtfTool --publickey key1.pub key2.pub --attack same_n_huge_e или ручной скрипт через from Crypto.Util.number import inverse — 8-10 строк.

Общий множитель: GCD между модулями

Если два разных модуля n1 и n2 имеют общий простой множитель p (то есть n1 = p*q1, n2 = p*q2), то gcd(n1, n2) = p. Вычисление GCD занимает микросекунды.

from math import gcd
from Crypto.Util.number import long_to_bytes

# Дано: n1, n2 (два модуля), e, c1 (шифротекст)
p = gcd(n1, n2)
if p > 1:
    q = n1 // p
    d = pow(e, -1, (p - 1) * (q - 1))
    print(long_to_bytes(pow(c1, d, n1)))

Исследование Heninger et al. (2012) «Mining Your Ps and Qs» проанализировало миллионы TLS-сертификатов и обнаружило более 64 000 хостов с RSA-ключами, уязвимыми к GCD-атаке. 0.2% всех TLS-хостов оказались скомпрометированы. Причина — встроенные устройства (роутеры, VPN-шлюзы, файрволы) генерировали ключи сразу после загрузки, когда пул энтропии /dev/urandom ещё не заполнился, и одни и те же простые числа повторялись. Результат — получение Private Keys, что в MITRE ATT&CK соответствует технике T1552.004 (Private Keys).

В CTF задача с несколькими публичными ключами — почти всегда приглашение проверить GCD попарно. Если ключей до 20, хватит простого двойного цикла. Для массовых проверок (тысячи ключей) Heninger et al. разработали batch GCD алгоритм, обрабатывавший 11 миллионов ключей за 1.3 часа на облачных ресурсах стоимостью $5.

Автоматизация: RsaCtfTool и когда его недостаточно

RsaCtfTool (GitHub, MIT-лицензия, Python 3.9+, активно поддерживается) — основной инструмент автоматизации для взлома RSA без закрытого ключа на CTF. Инструмент последовательно пробует десятки атак и выдаёт результат.

Ключевые команды: - Извлечение приватного ключа: RsaCtfTool --publickey key.pub --private - Расшифровка файла: RsaCtfTool --publickey key.pub --decryptfile cipher.enc - Конкретная атака: RsaCtfTool --publickey key.pub --attack wiener - Дамп параметров: RsaCtfTool --dumpkey --key key.pub - Создание PEM из n и e: RsaCtfTool --createpub -n <число> -e 65537 - Несколько ключей: RsaCtfTool --publickey "*.pub" --private

Поддерживаемые атаки (из README): Wiener, Hastad, Boneh-Durfee, Fermat factorization, Pollard p-1, ECM, factordb lookup, common factor across multiple keys, small CRT exponent, partial d/q recovery, lattice reduction, noveltyprimes, past CTF primes.

Преимущество	Ограничение
Автоматический перебор десятков атак	Работает только с textbook RSA (semiprime, не multiprime)
Не требует глубоких знаний математики	Lattice-based атаки требуют SageMath
Интеграция с factordb	Нестандартные варианты (LSB oracle, partial key exposure) не покрыты
Активная разработка, MIT-лицензия	Может быть медленным на больших модулях без GPU

Для продвинутой факторизации авторы RsaCtfTool рекомендуют msieve, yafu или cado-nfs. Если задача включает pycryptodome RSA примеры с нестандартным padding или многораундовым шифрованием — ручной скрипт неизбежен.

Алгоритм решения: чек-лист для любой RSA-задачи

Шаг	Что проверить	Инструмент	Атака
1	Размер n ≤ 256 бит — мгновенно; 384–512 бит — часы (CADO-NFS)	RsaCtfTool --dumpkey, msieve, yafu	Прямая факторизация
2	e маленькое (3, 5, 7)	Условие задачи	Cube root / Hastad
3	e аномально большое	Сравнить длину e и n	Wiener / Boneh-Durfee
4	Несколько модулей	gcd(n1, n2) в Python	Общий множитель
5	Один n, два e	Сравнить модули	Common modulus
6	n в factordb	factordb.com	Lookup
7	p и q близки	--attack fermat	Fermat
8	Ничего не сработало	RsaCtfTool --private	Автоперебор

Каждый шаг — от секунд до минут. Если все восемь шагов не дали результата, задача уровня hard: LSB oracle, Coppersmith's short pad attack, partial key exposure, кастомный lattice на SageMath.

Паттерн, который я наблюдаю раз за разом: участники CTF знают названия атак — Хастад, Винер, Копперсмит — но не понимают, почему конкретная атака работает. Выучить RsaCtfTool --attack wiener занимает тридцать секунд. Понять, что цепная дробь аппроксимирует d/k из соотношения e*d = 1 + k*φ(n), и что convergents этой дроби дают кандидатов на d — это уже другой уровень. Именно этот уровень нужен, когда автор задачи добавляет twist: слегка модифицирует параметры, вводит нестандартный padding, комбинирует две слабости в одной задаче. RsaCtfTool молча вернёт None, а вы останетесь без флага.

Мой подход: каждую новую атаку сначала реализовать вручную на Python, убедиться, что понимаешь каждый шаг, и только потом автоматизировать. Автоматизация без понимания — это долг, который рано или поздно придётся отдать. Прорешайте хотя бы первые 20 челленджей на CryptoHack в категории RSA руками, без RsaCtfTool, с чистым Python и gmpy2. На HackerLab есть задачи, покрывающие и стандартные, и продвинутые атаки — полезно отрабатывать не только теорию, но и скорость прохождения чек-листа в условиях таймера.

🚀 Хочешь закрепить на практике? Реши задачи по теме на HackerLab — категория «pentest-machines».