Криптография CTF для начинающих: атаки на RSA

На прошлогоднем Jeopardy-CTF мне попался RSA-таск: публичная экспонента e=3, модуль n на 2048 бит, шифртекст c примерно в шесть раз короче n. Три строки Python, сорок секунд — флаг. Рядом в Discord команда из четырёх человек билась над той же задачей полчаса, пытаясь факторизовать n. Разница — не в знании теории чисел, а в умении прочитать параметры и сразу выбрать правильную атаку. По сути crypto на CTF — это паттерн-матчинг: видишь набор параметров, узнаёшь атаку, пишешь скрипт. Здесь разберём те самые паттерны — от шифра Цезаря до трёх атак на RSA с малой экспонентой — которые покрывают большинство тасков начального и среднего уровня.

Классические шифры в crypto-тасках CTF

Crypto-категория на соревнованиях начинается не с RSA. Первые задачи — подстановочные и полиалфавитные шифры, где флаг спрятан за алгоритмом, которому несколько сотен лет. Три паттерна, которые встречаются чаще всего. Подробнее — в нашем обзоре создание ctf заданий.

Шифр Цезаря: расшифровка перебором 25 сдвигов

Шифр Цезаря — сдвиг каждой буквы алфавита на фиксированное число позиций. В латинском алфавите 26 букв, возможных ключей всего 25. На CTF задача со сдвиговым шифром решается тривиально: перебрать все варианты и найти осмысленный текст.

Частный случай — ROT13, сдвиг на 13 позиций. Фишка в том, что повторное применение ROT13 возвращает исходный текст (26 / 2 = 13). В crypto CTF задачах ROT13 часто маскируют под «неизвестную кодировку». Видишь строку из латинских букв без видимой структуры — попробуй ROT13 первым, не прогадаешь.

Распознать шифр Цезаря в условии просто: текст состоит только из букв одного алфавита, длина сохраняется, пробелы и знаки препинания на месте. На практике достаточно закинуть текст в CyberChef с рецептом ROT13 Brute Force — все 25 вариантов одним кликом.

Шифр Виженера: частотный анализ вместо перебора

Шифр Виженера — полиалфавитная подстановка, где каждая буква сдвигается на величину, определяемую соответствующей буквой ключевого слова. Ключ повторяется циклически. В отличие от Цезаря, прямой перебор тут не катит — пространство ключей растёт экспоненциально от длины ключа.

Классический подход к криптоанализу для начинающих на CTF:

1. Определить длину ключа — метод Касиски (поиск повторяющихся триграмм и вычисление НОД расстояний между ними) или индекс совпадений. Если IC для подстроки близок к 0.065 (английский текст) — длина ключа угадана верно.
2. Разбить шифртекст на блоки — по одному на каждую позицию ключа. Каждый блок зашифрован обычным Цезарем.
3. Частотный анализ каждого блока — сравнить частоты букв с эталонным распределением языка и найти сдвиг.

Для английских текстов с коротким ключом (3–8 символов) весь процесс автоматизируется. dcode.fr справляется за секунды. Для русскоязычных текстов эталонные частоты другие (буква «о» — самая частая, около 11%), но принцип тот же.

CyberChef для криптографии: швейцарский нож

CyberChef (gchq.github.io/CyberChef) — браузерный инструмент с drag-and-drop интерфейсом, который покрывает большинство задач на классические шифры криптографии. Рецепты, которые реально экономят время:

• Magic — автоматическое определение кодировки и шифра. Загружаешь шифртекст — CyberChef пробует десятки преобразований и показывает наиболее вероятные.
• From Base64 / From Hex / From Binary — конвертация между форматами. Часто флаг закодирован в несколько слоёв: base64 → hex → ASCII. Такая матрёшка встречается на каждом втором CTF.
• XOR / XOR Brute Force — перебор однобайтового XOR-ключа. Если шифртекст XOR'ен с одним байтом, CyberChef найдёт ключ по частотному анализу.
• ROT13 / ROT47 — мгновенная проверка ротационных шифров.

Типичная ошибка новичка — бросаться писать Python-скрипт, когда задача решается в CyberChef за 30 секунд. Правило простое: сначала попробуй Magic, потом открывай редактор кода.

RSA для CTF: математика без боли

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

Ключевые формулы RSA

Для решения crypto тасков CTF достаточно держать в голове пять формул:

• n = p × q — модуль, произведение двух больших простых чисел
• φ(n) = (p − 1)(q − 1) — функция Эйлера (в некоторых реализациях используют λ(n) = lcm(p−1, q−1), но для CTF разница несущественна)
• e × d ≡ 1 (mod φ(n)) — связь публичной экспоненты e и приватной экспоненты d
• c = m^e mod n — шифрование: открытый текст m возводится в степень e по модулю n
• m = c^d mod n — расшифрование: шифртекст c возводится в степень d по модулю n

Публичный ключ — пара (n, e). Приватный ключ — d (или, что эквивалентно, знание p и q, из которых d вычисляется). Вся безопасность RSA держится на одном допущении: факторизовать n на p и q вычислительно невозможно при достаточной длине ключа. На CTF авторы это допущение ломают — намеренно.

Что ломается в CTF-задачах

В реальных системах параметры RSA выбираются строго: n ≥ 2048 бит, e = 65537, p и q — случайные простые одинаковой длины. В CTF авторы намеренно ослабляют один или несколько параметров. Задача участника — найти слабость и эксплуатировать её.

Основные паттерны ослабления RSA на соревнованиях:

Что ослаблено	Признак в условии	Тип атаки
Малая экспонента e (e=3)	e=3, c значительно меньше n	Извлечение корня
Одно сообщение, e получателей	e пар (n_i, c_i), одинаковый m	Атака Хастада (CRT)
Слишком большая e	e близка к n по длине	Атака Винера
Малые простые p или q	n < 512 бит или имеет паттерн	Факторизация (yafu, FactorDB)
Общий делитель у нескольких n	Два модуля n_1 и n_2	GCD(n_1, n_2)

Эта таблица — чит-шит для crypto тасков CTF. По параметрам в условии сразу видно, какую атаку применять.

Атака на RSA с малой экспонентой

Самая частая RSA-атака для начинающих на CTF. Если публичная экспонента e маленькая (обычно e=3) и открытый текст m достаточно короткий, шифрование фактически не задействует модульную арифметику криптографии. И это подарок.

Почему e=3 — подарок для атакующего

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

Когда m^e всё-таки превышает n, но ненамного, шифртекст «обернулся» через модуль лишь несколько раз. Тогда перебираем k в формуле m = (c + k × n)^(1/e) для k = 0, 1, 2, ... пока не получим целый корень. Как описано на jorianwoltjer.com, хороший индикатор атаки — c значительно меньше n: обёрток мало или не было вовсе.

Ключевой признак в условии задачи: c заметно короче n (на порядки), e = 3 (реже 5 или 7). Видишь такую комбинацию — это почти гарантированно атака извлечением корня.

Решение: Python-код

from gmpy2 import iroot

def small_e_attack(c, e, n):
    # Перебираем "обороты" модуля — для e=3 обычно k=0
    for k in range(e):
        m, exact = iroot(c + k * n, e)
        if exact:
            return int(m)

# e=3, c и n из условия задачи
m = small_e_attack(c, 3, n)
print(bytes.fromhex(hex(m)[2:]))

iroot из gmpy2 вычисляет целочисленный корень и возвращает флаг exact — является ли результат точным. Цикл по k перебирает «обороты» модуля. Теоретически k < e (поскольку m < n, то m^e < n^e, и число оборотов не превышает e − 1). На практике для e=3 k почти всегда равно 0, 1 или 2. Альтернатива без gmpy2 — from sympy import integer_nthroot, работает аналогично. Для конвертации числа в читаемый текст вместо ручного hex-жонглирования удобнее from Crypto.Util.number import long_to_bytes.

Атака Хастада RSA: китайская теорема об остатках

Атака Хастада — усиление предыдущего подхода для случая, когда m^e > n и прямое извлечение корня не работает. Условие: одно и то же сообщение m зашифровано с той же экспонентой e, но разными модулями n_1, n_2, ..., n_e.

Когда одно сообщение — несколько шифртекстов

Типичный сценарий в crypto CTF задачах: сервер отправляет один флаг нескольким получателям, каждый со своим публичным ключом (n_i, e). Если e=3 и у нас есть три пары (n_1, c_1), (n_2, c_2), (n_3, c_3) — атака гарантированно работает.

Математика модульной арифметики криптографии:

• c_1 ≡ m^3 (mod n_1)
• c_2 ≡ m^3 (mod n_2)
• c_3 ≡ m^3 (mod n_3)

По китайской теореме об остатках (CRT), если модули попарно взаимно просты, можно найти единственное значение x ≡ m^3 (mod n_1 × n_2 × n_3). Поскольку m < каждого n_i, то m^3 < n_1 × n_2 × n_3. Значит, x = m^3 без остатка — извлекаем кубический корень и получаем открытый текст. Красиво, правда?

Пошаговый разбор с кодом

from sympy.ntheory.modular import crt
from gmpy2 import iroot

moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
# CRT: находим x = m^3 (mod n1*n2*n3)
result = crt(moduli, remainders)
if result is None:
    raise ValueError('moduli not coprime')
x, N = result
m, exact = iroot(x, 3)
if exact:
    print(bytes.fromhex(hex(int(m))[2:]))

crt из sympy.ntheory.modular принимает список модулей и остатков, возвращает общий модуль N и значение x. После — стандартное извлечение корня третьей степени.

Нюанс: атака Хастада работает для любого e, не только для 3. Но для e=65537 потребуется 65537 пар (n_i, c_i) — на CTF такого не бывает. По данным jorianwoltjer.com, для e=257 и 1024-битных ключей скрипт отрабатывает примерно за 40 секунд. На соревнованиях обычно дают e=3, 5 или 7, чтобы участники уложились в тайминг.

Атака Винера RSA: непрерывные дроби против малого d

Атака Винера эксплуатирует случай, когда приватная экспонента d слишком мала. Формально: классическая атака (Wiener, 1990) работает при d < (1/3) × n^(1/4); условие q < p < 2q (сбалансированные простые) используется в более поздних уточнениях границы. На CTF это проявляется как необычно большая публичная экспонента e — близкая по длине к самому модулю n.

Почему большая e означает малую d

Из соотношения e × d ≡ 1 (mod φ(n)) следует, что e и d — мультипликативные обратные по модулю φ(n). Если d мало, то e ≈ φ(n) / d, что делает e огромной. В условии задачи это выглядит как e с сотнями или тысячами цифр — сопоставимая по длине с n.

Нормальное значение e в RSA — 65537 (0x10001). Видишь e длиной в 256+ байт — это сигнал к атаке Винера. Прямо красный флаг.

Как работает непрерывная дробь в криптоанализе

Винер доказал, что разложение дроби e/n в непрерывную дробь содержит d среди подходящих дробей (convergents). Алгоритм восстановления:

1. Вычислить непрерывную дробь для e/n.
2. Перебрать подходящие дроби k/d.
3. Для каждой проверить: вычислить φ(n) = (e × d − 1) / k, затем убедиться, что n раскладывается на два простых множителя с полученным φ(n).
4. Если проверка пройдена — d найдено, задача решена.

На Python непрерывные дроби вычисляются через sympy и функцию continued_fraction_periodic. Готовая реализация атаки Винера есть в пакете owiener — после pip install owiener достаточно вызвать d = owiener.attack(e, n). Функция вернёт d или None, если d выходит за границу Винера. Для автоматизации подойдёт и RsaCtfTool с флагом --attack wiener.

Но понимание механизма важнее инструмента. На соревнованиях задача может быть модифицирована — автор слегка увеличит d за порог классической атаки Винера, и тогда потребуется расширенная версия (атака Бонэ-Дурфи через LLL-редукцию решёток в SageMath). Готовый тул просто скажет «attack failed», а ручной скрипт можно адаптировать.

Как распознать тип атаки по условию crypto CTF задачи

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

Признак в условии	Атака	Первое действие
e=3 (или 5, 7), c намного меньше n	Малая экспонента	iroot(c, e)
e=3, несколько пар (n_i, c_i)	Хастад (CRT)	crt() + iroot()
e огромная, сопоставима с n	Винер	owiener.attack(e, n)
n < 512 бит	Факторизация	FactorDB или yafu
Два разных n в одной задаче	GCD	math.gcd(n1, n2)
Известна часть открытого текста	Копперсмит	SageMath small_roots()
e=1	Тривиально	c = m, декодируй
Дано всё кроме d	Стандартная расшифровка	pow(c, d, n)

Алгоритм действий при встрече с RSA-таском:

1. Прочитать все данные — что дано: n, e, c, p, q, d? Чего не хватает?
2. Оценить размеры — e маленькая? e огромная? n короткий? c значительно меньше n?
3. Проверить FactorDB — возможно, факторизация модуля RSA уже проведена кем-то ранее.
4. Попробовать GCD, если дано несколько модулей.
5. Применить атаку из таблицы.

Этот алгоритм покрывает около 80% RSA-задач на соревнованиях начального и среднего уровня. Оставшиеся 20% — атака Копперсмита (требует SageMath), partial key recovery (на jorianwoltjer.com описана как анализ частично редактированного PEM-ключа через ASN.1-заголовки) и нестандартные авторские задачи.

Инструменты для решения crypto CTF задач

RsaCtfTool: автоматизация взлома RSA CTF

RsaCtfTool (github.com/RsaCtfTool/RsaCtfTool) — Python-утилита с десятками встроенных атак. Инструмент автоматически перебирает уязвимости в генерации ключей. Ключевые флаги:

• --publickey FILE — загрузить публичный ключ из PEM-файла
• -n N -e E — задать модуль и экспоненту вручную (целое число или 0xhex)
• --uncipher C — расшифровать шифртекст
• --private — вывести приватный ключ при успехе
• --attack ATTACK — указать конкретную атаку: wiener, hastads, smallq, small_e и другие

Пример: python3 RsaCtfTool.py -n 12345... -e 3 --uncipher 6789... --private — перебирает атаки и выводит открытый текст. Запуск с --attack all прогоняет весь арсенал.

Ограничение (и оно серьёзное): на нормальных соревнованиях задачи конструируются так, чтобы автоматические солверы не справлялись. Авторы добавляют нестандартные модификации — собственный padding, кастомные параметры, комбинации нескольких слабостей. Тут нужен ручной скрипт.

PyCryptodome, gmpy2 и SageMath

Три библиотеки для ручного криптоанализа:

PyCryptodome (pip install pycryptodome>=3.21.0 — более ранние версии содержат известные уязвимости, включая integer overflow (GHSA-hgg3-g7gr-66r7, исправлена в 3.19.1) и side-channel leakage при OAEP-дешифровании (GHSA-j225-cvw7-qrx7, исправлена в 3.21.0)) — модуль Crypto.PublicKey.RSA парсит PEM-ключи и вытаскивает n, e, d. Модуль Crypto.Util.number содержит long_to_bytes и bytes_to_long для конвертации между числами и байтами — без них вычисление ключа RSA превращается в ручное hex-жонглирование.

gmpy2 (pip install gmpy2) — быстрая арифметика больших чисел. iroot(x, n) для целочисленного корня и gcd(a, b) для НОД работают на порядки быстрее стандартного Python при работе с числами в 2048+ бит.

SageMath (sagemath.org) — математическая система для продвинутых атак. Метод small_roots() для атаки Копперсмита, LLL-редукция решёток для расширенной атаки Винера — всё из коробки. Настройка — боль (особенно на Windows), но альтернативы для решёточных атак нет.

Типичный рабочий процесс на соревнованиях: парсинг ключей через PyCryptodome → вычисления через gmpy2 → если стандартные атаки не сработали, переход в SageMath. CyberChef для классических шифров, Python-стек для RSA — такое разделение экономит время на каждом CTF.

---

Девять из десяти новичков, которых я встречаю на соревнованиях, подходят к crypto-таскам с одним из двух настроений: «RSA не ломается — пропускаю» или «запущу RsaCtfTool с --attack all и пойду пить кофе». Оба подхода гарантированно сливают баллы на задачах среднего уровня. RsaCtfTool — инструмент, а не решение. Он не объяснит, почему атака сработала, и не поможет, когда автор задачи добавил нестандартный twist.

Crypto в CTF — это паттерн-матчинг. Реальных атак на RSA, которые встречаются на соревнованиях, не больше десяти, и каждая привязана к конкретному набору параметров в условии. Научиться распознавать эти параметры — вопрос двух-трёх десятков решённых задач. Но большинство останавливается после первой нерешённой и уходит в web или forensics, где «хотя бы понятно, что делать».

Через год этот подход аукнется. CTF-площадки всё чаще делают задачи межкатегорийными: web-таск с JWT на кастомном RSA, forensics с зашифрованным трафиком, pwn с протоколом на эллиптических кривых. Crypto перестаёт быть отдельной категорией и превращается в базовый навык — как умение читать hex-дамп или пользоваться Burp. Те, кто вложился в понимание RSA сейчас, через полгода будут решать задачи, которые остальные даже не откроют. Если хочешь не просто writeup, а пройти всю цепочку от шифра Цезаря до Копперсмита с лабами на каждый кейс — WAPT покрывает это с прогрессией и ментором.

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