RSA CTF атаки на слабый ключ: от модуля до флага с RsaCtfTool и SageMath

RSA CTF атаки на слабый ключ: от модуля до флага с RsaCtfTool и SageMath

На NahamCon CTF 2024 задача Magic RSA решалась за две минуты — публичная экспонента e=3, и весь «взлом» свёлся к извлечению кубического корня из шифротекста. Ни факторизации модуля, ни перебора, ни продвинутой алгебры. Просто gmpy2.iroot(c, 3) — и флаг в консоли.

Большинство RSA-задач на CTF для начинающих строятся на одних и тех же ошибках в параметрах: слишком маленький модуль, предсказуемые простые, неудачный выбор экспоненты. Разница между решением за 90 секунд и зависанием на три часа — в знании того, что проверять первым и какой флаг передать RsaCtfTool. Тут не будет доказательств теоремы Эйлера — будет рабочий алгоритм: вот параметры, вот команда, вот флаг.

Как устроена RSA-задача на CTF и что с ней делать

Прежде чем разбирать конкретные атаки на слабый RSA ключ, зафиксируем контекст. В типичном CTF crypto-таске выдают набор параметров: модуль n (произведение двух простых p и q), публичную экспоненту e и шифротекст c. Параметры лежат либо в текстовом файле, либо в PEM-ключе, который парсится через openssl rsa -pubin -text -noout -in public.pem или через pycryptodome в Python.

Цель: восстановить секретный ключ d или сразу получить открытый текст m. Для этого нужно факторизовать n (получить p и q) либо найти способ обойти факторизацию через криптографические уязвимости RSA в выборе параметров. Шифрование — c = m^e mod n, расшифровка — m = c^d mod n, где d — модулярная инверсия e по модулю phi(n) = (p-1)(q-1).

В терминах MITRE ATT&CK восстановление закрытого ключа соответствует технике Private Keys (T1552.004, Credential Access), а сама ситуация слабого ключевого пространства — Reduce Key Space (T1600.001). По классификации OWASP — прямая иллюстрация A02:2021 (Cryptographic Failures): ошибка в криптографических параметрах делает защиту бессмысленной.

Цепочка решения: от задачи до флага

Каждая RSA-задача на CTF проходит через четыре этапа:

1. Извлечение параметров из файлов задания (n, e, c)
2. Диагностика типа слабости (маленький n? малая e? огромная e? общий модуль?)
3. Применение атаки — факторизация n или прямое восстановление m
4. Расшифровка, декодирование байтов, получение флага

Первый и четвёртый этапы одинаковы для всех задач. Вся работа — на втором и третьем.

Decision tree: что проверять и в каком порядке

Шаг	Что проверить	Как проверить	Если сработало
1	n уже в factordb	factordb.com или RsaCtfTool --attack factordb	p и q известны, задача решена
2	n маленький (< 512 бит)	python3 -c "print(n.bit_length())"	Прямая факторизация через SageMath или sympy
3	e = 3 (или 5, 7, 17)	Посмотреть значение e	Cube root: m = iroot(c, e)
4	e огромная (близка к n)	Сравнить bit_length(e) и bit_length(n)	Wiener attack: --attack wiener
5	Два шифротекста, один n	Описание задачи	Common modulus attack
6	p и q близки	Подозрение по контексту	Fermat: --attack fermat
7	Ничего не подошло	Интуиция	RsaCtfTool --attack all

В 80% задач начального уровня ответ находится на шагах 1–4. Каждый шаг занимает секунды.

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

Перед переходом к практике — минимальный набор:

• ОС: Kali Linux 2023.x+, Ubuntu 20.04+ или любой Linux с Python 3.8+; на Windows — через WSL2
• RAM: 4 ГБ минимум — RSA CTF задачи не требуют серьёзных ресурсов
• Python-зависимости: pip3 install gmpy2 pycryptodome sympy
• RsaCtfTool: git clone https://github.com/RsaCtfTool/RsaCtfTool.git && pip3 install -r requirements.txt (последнее обновление: 2024, активно поддерживается, 5.5k+ звёзд на GitHub)
• SageMath: sudo apt install sagemath или Docker: docker run -it sagemath/sagemath — версия 9.x+, занимает 2+ ГБ на диске
• factordb: онлайн-сервис factordb.com, требует интернета; для offline — pip3 install factordb-pycli
• Интернет: нужен для factordb и первоначальной установки; после установки всё работает автономно

RSA факторизация модуля в CTF: три рабочих метода

Факторизация n — центральная задача большинства RSA CTF задач. Когда p и q известны, всё остальное тривиально: phi = (p-1)*(q-1), d = pow(e, -1, phi), m = pow(c, d, n). Вся сложность — в получении множителей.

Factordb — первый шаг для любого n

Factordb.com — база известных факторизаций. Авторы CTF-задач для начинающих часто берут «учебные» числа, которые давно разложены и валяются в публичных базах. Проверка занимает секунду: вставляете n на сайте, смотрите статус. FF (Fully Factored) — p и q уже известны.

Автоматизация через RsaCtfTool: python3 RsaCtfTool.py -n <n> -e <e> --attack factordb --uncipher <c>. Инструмент обращается к базе, получает множители и сразу расшифровывает. Как отмечает bitsdeep.com: «The first thing to try is to see if n is known — it's a quick check that might save you a lot of time.» Для CTF буквально так: одна команда — и флаг в консоли.

Ограничение: работает только если n уже попадал в factordb. Генерированные на лету числа в базе отсутствуют. Но проверить — дело пяти секунд, пропускать этот шаг нет причин.

Прямая факторизация малого n

Если n меньше 512 бит (примерно 155 десятичных цифр), его можно факторизовать напрямую. В SageMath — одна строка: factor(n). На Python — sympy.factorint(n). На числах до 256 бит результат мгновенный, для 512 бит может потребоваться несколько минут.

RsaCtfTool пробует прямую факторизацию через --attack smallfraction или при запуске --attack all. Для чисел до 100 бит хватает даже наивного перебора делителей.

Ограничение: бесполезен для модулей стандартного размера (1024+ бит). В реальной криптографии используются 2048–4096 бит — факторизация таких чисел за разумное время невозможна. Но CTF-задачи для начинающих намеренно уменьшают n, чтобы факторизация была выполнимой.

Ферма: когда p и q подозрительно близки

Если автор задачи выбрал p и q близкими друг к другу — метод Ферма факторизует n за секунды. Идея: представляем n = a^2 - b^2 = (a+b)(a-b), начинаем с a = ceil(sqrt(n)) и увеличиваем, проверяя, является ли a^2 - n полным квадратом.

Запуск: --attack fermat. В SageMath можно написать руками, но зачем, если автоматизация справляется.

Ограничение: работает только при малой разнице |p - q|. Если p и q выбраны случайно и независимо (как положено), разница слишком велика. В CTF этот сценарий маркируется подсказками: «close primes», «twin primes», или p и q отличаются лишь в нескольких младших битах.

Атака малая экспонента RSA e=3: cube root и её границы

Атака на малую публичную экспоненту (small public exponent attack RSA) — одна из самых частых и самых простых для понимания. Если e = 3 и сообщение m достаточно мало, чтобы m^3 < n, операция mod n ничего не делает: c = m^3 mod n = m^3. Расшифровка — кубический корень из c. По сути CRC… нет, тут ещё проще — тупо арифметика.

Именно это произошло в задаче Magic RSA на NahamCon CTF 2024. По данным разбора с Medium, e=3, модуль n огромный, а сообщение — короткая строка. m^3 не дотягивает до n, и c равно m^3 без всякого модуля.

import gmpy2
from Crypto.Util.number import long_to_bytes

e = 3
c = 0x...  # шифротекст из задачи
m, is_exact = gmpy2.iroot(c, e)
if is_exact:
    print(long_to_bytes(int(m)))
else:
    print("m^e >= n, нужна другая атака")

Функция gmpy2.iroot(c, e) извлекает целочисленный корень степени e и возвращает флаг точности. is_exact == True — m^e строго меньше n и корень точен. long_to_bytes конвертирует число обратно в текст — и в консоли появляется флаг.

Ограничения техники:

• Работает только при m^e < n. Для стандартного e = 65537 сообщение должно быть астрономически коротким — на практике невозможно
• Если применён padding (OAEP, PKCS#1 v1.5), сообщение искусственно увеличивается, и m^e гарантированно больше n. В CTF обычно textbook RSA без padding — иначе не было бы задачи
• Если m^e немного превышает n (на 1–2 значения), пробуйте перебор: m = iroot(c + k*n, e) для малых k. RsaCtfTool делает это автоматически через --attack cube_root

Cube root attack — прямая иллюстрация low exponent RSA attack: ошибка одного параметра превращает шифрование в тривиальную арифметику.

Wiener attack RSA: большая e сигнализирует о малом d

Wiener attack — зеркальная ситуация: проблема не в малом e, а в малом d. Если секретный ключ d < n^{0.25} / 3, атака восстанавливает его через разложение дроби e/n в цепную дробь. На CTF распознаётся моментально: если e сопоставима с n по количеству бит — почти наверняка Wiener.

Математика: из соотношения ed ≡ 1 mod phi(n) следует, что e/n — хорошее приближение к k/d. Подходящие дроби (convergents) цепной дроби перебираются, и для каждого кандидата (k, d) проверяется корректность через квадратное уравнение. Реализация из jia.je использует continued_fraction(e/n) в SageMath, перебирает convergents, проверяет k != 0 и нечётность d, затем строит полином x^2 - (n - phi + 1)*x + n и ищет целые корни. Если корни есть и дают p * q == n — ключ восстановлен.

На практике — одна команда: python3 RsaCtfTool.py -n <n> -e <e> --attack wiener --uncipher <c>. RsaCtfTool реализует атаку Wiener из коробки, для CTF этого за глаза.

Ограничение: Wiener работает строго при d < n^{0.25}. Для стандартных ключей (2048+ бит, e = 65537) секретный ключ сопоставим с n по размеру — атака неприменима. В CTF Wiener-задача всегда маркирована аномально большим значением e. Есть усиление Boneh-Durfee, расширяющее границу до d < n^{0.292}, но оно требует решётчатых методов (lattice) и в RsaCtfTool доступно через --attack boneh_durfee.

RsaCtfTool использование: автоматизация расшифровки RSA флага

RsaCtfTool (GitHub, 5.5k+ звёзд, активные коммиты в 2024) — основной инструмент для RSA CTF задач. Реализует более 20 атак и автоматически подбирает подходящую. Для большинства задач начального и среднего уровня хватает одной команды. Я начинаю с него на каждом CTF — и в 70% случаев дальше идти не приходится.

Ключевые режимы

• Перебор всех атак: python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c> — последовательно пробует factordb, Wiener, Fermat, Hastad, cube root и десятки других. Если одна сработает — получаете расшифрованный текст
• Целевая атака: --attack wiener, --attack fermat, --attack cube_root, --attack smallfraction — когда тип слабости уже определён
• Работа с PEM: python3 RsaCtfTool.py --publickey public.pem --uncipher <c> — автоматическое извлечение n и e из ключа
• Расшифровка из файла: --uncipherfile flag.enc — для задач с бинарным шифротекстом

Когда что использовать: trade-off таблица

Инструмент	Преимущества	Ограничения	Когда использовать	Когда не использовать
RsaCtfTool	20+ атак из коробки, PEM-парсинг, автовыбор	Не покрывает кастомные сценарии, иногда тормозит на --attack all	Первый запуск на любой RSA-задаче	Нестандартная математика (lattice, CRT-нюансы)
SageMath	Coppersmith, lattice, полная гибкость, arbitrary precision	Нужно писать код, тяжёлая установка (2+ ГБ)	Partial key recovery, known MSB bits of p	Стандартные задачи — overkill
Python + gmpy2	Лёгкий, быстрый, минимальные зависимости	Нужно знать, какую атаку применять	Cube root, простая факторизация, конвертация результатов	Когда тип слабости не определён
factordb.com	Моментальный результат для известных n	Только если n уже в базе, нужен интернет	Первый шаг для любого n	Генерированные на лету числа

SageMath криптография: Coppersmith и нестандартные задачи

SageMath становится нужен, когда RsaCtfTool не справляется. Основной сценарий — атака Копперсмита: известна часть ключа (старшие 60–70% бит p), и нужно восстановить остальное.

По реализации из jia.je, метод small_roots() в SageMath находит малые корни полинома по модулю неизвестного делителя n. Параметр beta задаёт размер делителя относительно n (обычно 0.4–0.5 для RSA), epsilon — допустимый размер корня: чем меньше epsilon, тем больший корень можно найти, но дольше вычисление.

Типичное применение: дан n и верхние биты p. Строится полином f(x) = known_p_high * 2^shift + x, вызывается f.small_roots(X=2^shift, beta=0.4, epsilon=0.02). Если корень найден — p восстановлен, n факторизован.

Помимо Coppersmith, SageMath нужен для атак Hastad (одно сообщение, зашифрованное разными n при малом e) и Franklin-Reiter (два связанных сообщения, один n). На соревнованиях уровня CryptoHack и HTB Cyber Apocalypse эти атаки встречаются регулярно.

Ограничение: SageMath — тяжёлый зверь. Для быстрого старта используйте Docker-образ. На базовых CTF-задачах категории easy и medium он избыточен — RsaCtfTool и gmpy2 покрывают 90% случаев.

Расшифровка RSA флага CTF: полный воркфлоу

Задача открыта, файлы скачаны. Вот сценарий от начала до флага.

Шаг 1: извлечение параметров. Если дан PEM-файл — openssl rsa -pubin -text -noout -in key.pub. Получаете n (Modulus) и e (Exponent). Шифротекст c берёте из файла задачи. Параметры в текстовом файле — читаете напрямую.

Шаг 2: экспресс-диагностика. Три проверки за десять секунд. Размер n: python3 -c "print(int('...').bit_length())". Значение e: если 3 — cube root, если огромное — Wiener. Несколько шифротекстов с одним n — common modulus.

Шаг 3: автоматический прогон. python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c>. Если RsaCtfTool нашёл ответ — готово, переходите к шагу 5.

Шаг 4: ручные проверки. factordb.com вручную, gmpy2.iroot(c, e) для cube root, Ферма через --attack fermat. Если ничего — SageMath и Coppersmith.

Шаг 5: расшифровка. Когда p и q известны:

from Crypto.Util.number import long_to_bytes
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)   # Python 3.8+
m = pow(c, d, n)
print(long_to_bytes(m))

pow(e, -1, phi) в Python 3.8+ вычисляет модулярную инверсию — эквивалент расширенного алгоритма Евклида. long_to_bytes конвертирует числовой результат обратно в строку. В консоли появляется b'flag{...}'.

Частые ошибки при расшифровке

Шифротекст в hex, а передан как decimal. Если c выглядит как 0x4d7920..., нужно int(c_hex, 16) перед подачей в формулы. Классическая ошибка новичков — убивает полчаса на пустом месте.

gcd(e, phi) != 1. Если e делит (p-1) или (q-1), модулярная инверсия невозможна. Задача требует другого подхода — AMM-метод или Rabin decryption.

Результат — нечитаемые байты. Проверьте, не перепутаны ли параметры. Попробуйте m.to_bytes((m.bit_length() + 7) // 8, 'big') — иногда long_to_bytes обрезает ведущие нули.

Common modulus attack: два шифротекста — одно решение

Ещё один частый сценарий в CTF crypto задачах RSA: одно сообщение m зашифровано дважды с одним модулем n, но разными экспонентами e1 и e2. Перехвачены оба шифротекста c1 и c2.

Если gcd(e1, e2) = 1 (почти всегда), через расширенный алгоритм Евклида находятся u и v такие, что e1*u + e2*v = 1. Тогда m = c1^u * c2^v mod n — и никакой факторизации не нужно. Как описывает bitsdeep.com, достаточно перехватить оба шифротекста; факторизация n не требуется.

RsaCtfTool поддерживает эту атаку при передаче нескольких пар (e, c) для одного n.

Ограничение: нужен gcd(e1, e2) = 1. Если оба e чётные или имеют общий делитель больше единицы, прямой метод не работает — потребуется модификация с вычислением корня степени gcd(e1, e2).

Где практиковаться: от теории к задачам

Понимание атак без практики быстро выветривается. CryptoHack (cryptohack.org) — интерактивные задачи по криптографии с нарастающей сложностью, раздел RSA покрывает все описанные здесь атаки. PicoCTF (picoctf.org) — задачи категории crypto для начинающих с подсказками. Оба ресурса бесплатны и работают в браузере.

Для тех, кто хочет уровень сложнее — формула decay на бумаге понятна, но по-настоящему ощущается, когда сам прогоняешь сабмишены и упираешься в edge-case. На HackerLab.pro есть категория crypto с задачами разного уровня — российская CTF-платформа с 12 категориями (web, pwn, forensics, crypto и другие), нужна регистрация, после неё доступны таски всех уровней.

Половина навыка в CTF — быстро определить тип задачи. Решите 10–15 RSA-тасков на разных площадках — и decision tree из этой статьи станет автоматическим.

Есть мнение, что новичкам нужно сначала «глубоко понять математику RSA» и только потом переходить к решению задач. Три года участия в CTF убедили меня в обратном. Команды, которые стабильно закрывают RSA-таски за минуты, не рисуют на доске доказательство теоремы Эйлера — они знают пять типовых слабостей и гоняют RsaCtfTool с правильными флагами. Математика нужна ровно на уровне «e=3 означает cube root» и «огромная e означает Wiener». Для 80% задач начального и среднего уровня этого хватает за глаза. Глубокая теория понадобится позже — на задачах с lattice reduction и Coppersmith, которые встречаются на hard-уровне. Но тратить три недели на изучение цепных дробей, когда можно за вечер решить двадцать задач и усвоить паттерны через практику — неэффективная стратегия. В русскоязычном сегменте разборов RSA-задач с рабочим кодом практически нет: есть академические описания атак и новостные статьи о слабых ключах, но пошаговых гайдов «вот n, вот команда, вот флаг» до сих пор не хватает. Если интересна системная подготовка к OSCP-уровню с лабами — на WAPT эту цепочку проходят в модулях с практикой и ментором в чате при затыке.

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