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

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

На челлендже Weak RSA с Hack The Box весь путь от скачивания файлов до флага занимает одну команду: RsaCtfTool.py --publickey ./key.pub --uncipherfile ./flag.enc. Два файла на входе — публичный ключ и шифротекст — один plaintext-флаг на выходе. Красота. Но на следующей задаче, где слабость другого типа, новичок снова застревает на часы и тупо перебирает атаки наугад. Разница между «угадал» и «системно решаю RSA CTF задания» — в понимании семи типовых слабостей ключей и умении за минуту определить, какая из них перед тобой. Дальше — пошаговый разбор каждой атаки: минимальная математика, диагностика по параметрам, рабочий код на Python и практика с RsaCtfTool. Криптография CTF для новичков без академического балласта.

RSA математика объяснение: минимум для решения CTF-задач

RSA работает с целыми числами, не с файлами и не со строками. Сообщение m превращают в число, возводят в степень и берут остаток от деления. Всё шифрование — одна формула: c = m^e mod n. Расшифровка — обратная операция: m = c^d mod n. Никакой высшей математики, серьёзно.

Публичный ключ (n, e) — то, что дают в условии задачи. Модуль n — произведение двух больших простых чисел p и q. Публичная экспонента e — чаще всего 65537, но в CTF-задачах автор намеренно выбирает «сломанные» значения: 3, 5, 17 или наоборот — аномально большие. Увидел нестандартный e — уже подсказка.

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

Пример на маленьких числах (аналогичный приводит ctf101.org): p=61, q=53, n=3233, e=17. Считаем φ(n)=lcm(60,52)=780, находим d=413. Шифруем m=65: c = 65^17 mod 3233 = 2790. Расшифровываем: m = 2790^413 mod 3233 = 65. Круг замкнулся.

Вся безопасность RSA стоит на одном факте: факторизация большого n на p и q — вычислительно сложная задача. В RSA CTF заданиях автор намеренно делает один из параметров слабым. Твоя задача — определить какой и применить соответствующую атаку.

Диагностика слабых RSA ключей: чек-лист перед первой строкой кода

Прежде чем открывать IDE, пройди по этому дереву решений. Оно покрывает порядка 80% криптографических задач CTF уровня easy-medium:

1. e маленькое (3, 5, 17)? → Small e атака RSA: извлечение корня. Если в условии несколько шифротекстов с разными n — атака Хастада через CRT.
2. e огромное (сопоставимо с n или больше)? → Wiener attack RSA на малую секретную экспоненту d.
3. Два шифротекста, одинаковый n, разные e? → Common modulus attack RSA.
4. n маленький (менее 512 бит)? → Прямая факторизация модуля RSA через factordb, yafu или msieve.
5. Даны два разных n из разных заданий? → Проверь gcd(n1, n2). Результат больше 1 — общий простой множитель найден, задача решена.
6. Ничего из перечисленного? → Запускай RsaCtfTool с флагом --attack all.

Чтобы извлечь параметры из файла .pub: python3 RsaCtfTool.py --dumpkey --key ./key.pub или openssl rsa -pubin -in key.pub -text -noout. Оба варианта покажут n и e.

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

Все примеры воспроизводимы на Linux/macOS/Windows с Python 3.9+. RAM: 1-2 ГБ хватит за глаза — вычисления не ресурсоёмкие. Зависимости: pip install gmpy2 sympy pycryptodome. Для RsaCtfTool: git clone https://github.com/RsaCtfTool/RsaCtfTool.git, затем pip install -r requirements.txt. На Ubuntu/Kali предварительно: sudo apt-get install libgmp3-dev libmpc-dev. SageMath опционален, но расширяет набор доступных атак (Boneh-Durfee, Coppersmith). Работа полностью offline, интернет нужен только для запросов к factordb.

Small e атака RSA: корень вместо расшифровки

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

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

import gmpy2
from Crypto.Util.number import long_to_bytes

# n, e, c — из условия задачи; типично e = 3
m, exact = gmpy2.iroot(c, e)
if exact:
    print(long_to_bytes(int(m)))
else:  # m^e чуть больше n: перебираем c + k*n
    for k in range(1, 10000):
        m, exact = gmpy2.iroot(c + k * n, e)
        if exact:
            print(long_to_bytes(int(m)))
            break

gmpy2.iroot(c, e) возвращает целочисленный корень и флаг точности. Если exact == True — сообщение восстановлено, long_to_bytes из pycryptodome переводит число обратно в строку. Когда m^e слегка превысил n (m^e = c + k*n для небольшого k), перебирай k — на практике он редко выходит за несколько тысяч.

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

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

Атака Хастада: CRT против broadcast-шифрования

Сценарий: одно и то же сообщение m зашифровано экспонентой e = 3 для трёх разных получателей с модулями n1, n2, n3. В условии даны три пары (n_i, c_i). Файлы обычно называются output1.txt, output2.txt, output3.txt — прямой маркер.

Математика: 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 ничего не отсекает. Дальше — стандартное извлечение кубического корня через gmpy2.iroot, как в предыдущей атаке.

В Python используется crt из sympy.ntheory.modular: передаёшь списки модулей и остатков, получаешь m^3, извлекаешь корень. Предварительно проверь gcd(n_i, n_j) для всех пар — если результат больше 1, перед тобой атака общего множителя (ещё проще, и скрипт даже не нужен).

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

Факторизация модуля RSA: три подхода к разложению n

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

factordb факторизация: проверяем базу первым делом

factordb.com — коллективная база факторизованных чисел. Авторы CTF-задач нередко берут «учебные» числа или генерируют ключи без достаточной энтропии, и модули попадают в базу. Вставь n на сайте или используй CLI-обёртку factordb-pycli. Статус FF (fully factored) — p и q известны, задача решена. RsaCtfTool проверяет factordb автоматически через --attack factordb.

Ориентиры по размеру модуля: до 256 бит — факторизация мгновенная. 512 бит — часы-сутки утилитами msieve или yafu на одной машине. 768-битный RSA был факторизован ещё в 2009 году (Kleinjung et al., CRYPTO 2010), но потребовалось около 2000 core-years вычислений. В RSA CTF заданиях модуль до 512 бит — прямой сигнал «факторизуй меня».

Метод Ферма для близких множителей

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

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

Поллард p-1 и гладкие числа

Если p - 1 состоит только из малых простых делителей (гладкое число), срабатывает алгоритм Полларда p-1. В CTF гладкие простые — нарочная подсказка автора. Запусти --attack pollard_p_1 — если результат получен за секунды, значит автор именно этого и ожидал.

Когда факторизация НЕ работает: при модулях от 1024 бит и выше с правильно сгенерированными strong primes (простые, у которых p-1 и p+1 содержат большие простые делители). Тут ищи слабость не в n, а в других параметрах.

Wiener attack RSA: когда секретная экспонента слишком мала

Wiener attack эксплуатирует ситуацию, когда d маленькое относительно n: конкретнее, d < n^0.25. Маркер в условии: e аномально большое, сопоставимо с n или превышает его. Видишь публичную экспоненту RSA из сотен цифр — это кандидат на Wiener, почти наверняка.

Идея строится на разложении e/n в цепную дробь. Подходящие дроби (convergents) перебираются, и одна из них даёт пару (k, d), где d — искомая секретная экспонента. Проверка: если (e*d - 1) % k == 0, то φ(n) = (e*d - 1)/k, далее p и q восстанавливаются из φ(n) через решение квадратного уравнения x^2 - (n - φ(n) + 1)x + n = 0.

Писать атаку вручную не нужно. RsaCtfTool реализует её через --attack wiener. Команда: python3 RsaCtfTool.py --publickey key.pub --private --attack wiener. Если d действительно мал, приватный ключ восстанавливается мгновенно.

Расширение этой идеи — метод Боне-Дурфи (Boneh-Durfee), который работает при d < n^0.292. Он опирается на решётчные методы (lattice reduction) и требует SageMath. RsaCtfTool поддерживает его через --attack boneh_durfee.

Когда атака НЕ работает: при стандартном e = 65537 секретная экспонента d имеет размер, сопоставимый с n, и цепные дроби не дают результата. Атака бессильна и если автор задачи подобрал d > n^0.25 — формально «маленькое» в человеческих терминах, но за пределами досягаемости Wiener.

Common modulus attack RSA: один модуль, две экспоненты

Этот вектор взлома RSA CTF задач не покрыт большинством русскоязычных гайдов, хотя встречается регулярно. Сценарий: одно сообщение m зашифровано дважды с одним модулем n, но разными публичными экспонентами e1 и e2. В условии — n, e1, e2, c1, c2.

Условие работоспособности: gcd(e1, e2) = 1 (экспоненты взаимно просты). Расширенный алгоритм Евклида находит коэффициенты s1 и s2 такие, что s1*e1 + s2*e2 = 1. Из этого следует: c1^s1 * c2^s2 mod n = m^(s1*e1 + s2*e2) mod n = m^1 mod n = m.

from Crypto.Util.number import long_to_bytes

def egcd(a, b):
    if a == 0: return b, 0, 1
    g, x, y = egcd(b % a, a)
    return g, y - (b // a) * x, x

# n, e1, e2, c1, c2 — из условия задачи
_, s1, s2 = egcd(e1, e2)
# Отрицательный показатель = модулярный обратный
v1 = pow(c1, s1, n) if s1 > 0 else pow(pow(c1, -1, n), -s1, n)
v2 = pow(c2, s2, n) if s2 > 0 else pow(pow(c2, -1, n), -s2, n)
print(long_to_bytes(v1 * v2 % n))

Один из коэффициентов s1 или s2 будет отрицательным. Отрицательная степень в модулярной арифметике — возведение в степень модулярного обратного. В Python 3.8+ pow(c, -1, n) вычисляет обратный элемент нативно. Факторизация модуля RSA здесь вообще не нужна — за это и люблю эту атаку, она элегантная.

Когда атака НЕ работает: если gcd(e1, e2) > 1, прямое восстановление m невозможно — получаешь только m^gcd(e1,e2). Не работает и при разных открытых текстах или при наличии padding, отличающегося между шифрованиями.

RsaCtfTool использование: от файла до расшифровки флага

RsaCtfTool (github.com/RsaCtfTool/RsaCtfTool, активно поддерживается — коммиты в 2024-2025 годах) объединяет все перечисленные атаки на RSA шифрование в одном инструменте. По данным README проекта, поддерживается более 20 атак: Wiener, Hastad, Fermat, Boneh-Durfee, factordb, Pollard p-1, Pollard Rho, ECM, past CTF primes, Mersenne primes, common factors и другие.

Пошаговый workflow решения

Типичная задача даёт два файла: публичный ключ (key.pub) и шифротекст (flag.enc). Цепочка действий:

Шаг 1. Извлеки параметры: python3 RsaCtfTool.py --dumpkey --key ./key.pub. На выходе — n, e, размер ключа в битах. Оцени e и битность n по чек-листу выше.

Шаг 2. Запусти автоматический перебор: python3 RsaCtfTool.py --publickey ./key.pub --uncipherfile ./flag.enc. Инструмент последовательно пробует все реализованные атаки и выводит расшифрованный текст при успехе.

Шаг 3. Если автоматика не справилась — запусти конкретную атаку: --attack wiener, --attack fermat, --attack factordb.

Когда n и e даны числами, а не файлом: python3 RsaCtfTool.py -n <модуль> -e <экспонента> --uncipher <шифротекст>.

Для нескольких публичных ключей (проверка общего множителя между модулями): python3 RsaCtfTool.py --publickey "*.pub" --private. Инструмент автоматически проверит gcd для всех пар.

Если RsaCtfTool не помог — следующий уровень: SageMath для решётчных атак (Coppersmith, partial key recovery) и специализированные утилиты yafu/msieve для тяжёлой факторизации.

Ограничения RsaCtfTool и когда переключаться на другой инструмент

Работает	Не работает
Textbook RSA без padding	RSA-OAEP с корректным padding
Semiprime модуль n = p*q	Multi-prime RSA (n = pqr) — ограничение upstream pycrypto
Модуль до 2048 бит при наличии слабости	2048+ бит с правильной генерацией ключей
Offline-атаки (кроме factordb)	Атаки с oracle (Bleichenbacher, padding oracle)
Автоматический подбор атаки	Задачи, требующие кастомного скрипта (Franklin-Reiter, Coppersmith)

Если задача уровня hard и RsaCtfTool молчит — переходи к SageMath и ручной реализации. Easy-medium в подавляющем большинстве покрываются автоматикой.

Атаки на RSA шифрование: зачем это за пределами CTF

RSA CTF задания эксплуатируют намеренно ослабленные параметры, но аналогичные алгоритм RSA уязвимости встречаются в продуктивных системах. Уязвимость ROCA (CVE-2017-15361) затронула RSA-ключи, сгенерированные аппаратными модулями Infineon Technologies. Из-за дефекта в генерации простых чисел ключи имели предсказуемую структуру, допускающую факторизацию. Скомпрометированы были TPM-чипы, YubiKey 4 (до версии 4.3.5) и национальные ID-карты Эстонии. EPSS score CVE-2017-15361 — 0.0983 (percentile 0.9497, топ-5% по вероятности эксплуатации в 30 дней).

В терминологии MITRE ATT&CK генерация слабых ключей относится к технике Reduce Key Space (T1600.001, Defense Impairment), а восстановление приватных ключей — к Private Keys (T1552.004, Credential Access). По данным IBM X-Force Threat Intelligence Index 2025, среднее время между публикацией CVE и устранением в организации — 29 месяцев. Слабые RSA ключи, сгенерированные уязвимым оборудованием, могут жить в инфраструктуре годами — пока кто-то не проверит их теми же методами, что и CTF-игрок.

Навык диагностики слабых параметров RSA, наработанный на CTF-задачах, напрямую переносится на аудит криптографических реализаций: проверку TLS-сертификатов на предмет малых ключей, анализ SSH-ключей в корпоративной среде, ревизию самодельных криптографических протоколов в приложениях.

Большинство новичков в криптографии CTF совершают одну и ту же ошибку: запускают RsaCtfTool с --attack all и считают это «решением задачи». Инструмент — ускоритель, не замена пониманию. На CTF уровня medium авторы намеренно создают задания, где автоматика буксует: модуль, который почти попадает под Ферма, но с достаточным зазором, чтобы метод не сходился за разумное время. Без понимания, чем одна факторизация отличается от другой, решатель ждёт бесконечно вместо того чтобы переключить атаку.

Настоящая ценность прорешанных RSA-задач — не в самих флагах, а в криптографической интуиции. После полусотни задач слабость видна по размеру параметров ещё до запуска скрипта: маленький e — кубический корень, огромный e — Wiener, два файла с одинаковым n — common modulus. Эта интуиция работает и в продуктивной среде: когда ревьюишь TLS-конфигурацию или проверяешь генерацию ключей в финтех-приложении, те же паттерны слабости проявляются в менее очевидной форме. Считаю, что любой ИБ-специалист, который занимается аудитом криптографии, должен пройти хотя бы базовый набор RSA-задач — не ради CTF-рейтинга, а ради калибровки глаза, который потом ловит CVE-2017-15361 в дикой природе. На HackerLab есть подборка задач с нарастающей сложностью — можно начать с textbook RSA и дойти до Coppersmith за вечер.

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