Криптография в CTF: ломаем RSA и классические шифры

За три сезона Jeopardy-CTF я собрал статистику по своей команде: четыре из пяти crypto-тасков ниже 500 баллов решаются одним из пяти шаблонов. Шифр Виженера сдаётся индексу совпадений за пару минут, RSA с публичной экспонентой e=3 ломается одной функцией gmpy2.iroot — а команды-новички проходят мимо, потому что видят слово «криптография» и представляют себе эллиптические кривые над полями Галуа. Зря. Криптография в CTF — это прежде всего умение читать параметры задачи и сопоставлять их с каталогом известных атак. Ниже — приёмы, которые закрывают crypto-категорию на турнирах среднего уровня: от криптоанализа классических шифров до факторизации RSA и атаки Хастада.

Классические шифры: криптоанализ в crypto CTF задачах

Почти каждый Jeopardy-CTF включает пару задач на классические подстановочные шифры. Смысл — отсеять тех, кто не знает базовых инструментов. Тратить на них больше пяти минут — воровать время у тасков, которые дают реальные баллы.

Подстановочные шифры и частотный анализ

Моноалфавитная подстановка — шифр Цезаря (фиксированный сдвиг), Атбаш (зеркальный алфавит), ROT13 — ломается перебором 25 вариантов. CyberChef для CTF закрывает задачу за секунды: загружаете шифротекст, применяете ROT13 Brute Force, видите все варианты разом. Если перед вами не простой сдвиг, а произвольная подстановка (каждая буква заменена фиксированной другой) — потребуется частотный анализ.

Принцип прост до неприличия: в естественном языке буквы появляются с предсказуемой частотой. В английском самая частая — «e» (~12.7%), за ней «t» (~9.1%) и «a» (~8.2%). Для русского — «о» (~10.9%), «е/ё» (~8.5%), «а» (~8.0%). Когда в шифротексте символ «X» занимает ~12% всех позиций — он почти наверняка соответствует «e». Решатели quipqiup.com и dcode.fr комбинируют частотный анализ с поиском по словарю и возвращают ответ за секунды, даже на коротком тексте.

На CTF главный навык при работе с подстановочными шифрами — скорость распознавания типа. Равномерно искажённый текст без пробелов и знаков → пробуйте Base64/hex через CyberChef. Пробелы сохранены, длина слов правдоподобна → моноалфавитная подстановка, quipqiup. Набор чисел → проверяйте ASCII-коды, десятичные или восьмеричные.

Шифр Виженера — от частотного анализа к взлому

Шифр Виженера — полиалфавитный шифр, где каждая буква открытого текста сдвигается на величину соответствующего символа ключа. Ключевое слово «KEY» задаёт циклическую последовательность сдвигов: 10, 4, 24 (позиции K, E, Y в алфавите). Первая буква сдвигается на 10, вторая на 4, третья на 24, четвёртая снова на 10. Прямой частотный анализ бессилен — одна и та же буква шифруется по-разному в зависимости от позиции.

Но криптоанализ классических шифров этого типа отработан ещё в XIX веке. Атака в два этапа.

Этап 1 — определение длины ключа. Метод Касиски ищет повторяющиеся триграммы в шифротексте. Если «QXR» встречается на позициях 7 и 37, расстояние — 30. Длина ключа с высокой вероятностью — делитель 30 (2, 3, 5, 6, 10, 15 или 30). Собрав расстояния для нескольких повторов и вычислив НОД, получаем кандидата.

Альтернатива — индекс совпадений (Index of Coincidence, IC). Для каждой предполагаемой длины k разбиваем шифротекст на k подпоследовательностей (символы на позициях 0, k, 2k, 3k… — первая; 1, k+1, 2k+1… — вторая). Считаем IC каждой: если он близок к 0.065 (английский) или 0.055 (русский) — длина угадана, потому что подпоследовательность превращается в обычный моноалфавитный шифр с предсказуемым распределением.

Этап 2 — определение каждой буквы ключа. Зная длину, обрабатываем каждую подпоследовательность отдельно: самый частый символ сопоставляем с «e» (или «о» для русского), вычисляем сдвиг — вот вам и буква ключа.

На CTF для шифра Виженера есть автоматические решатели: dcode.fr/vigenere-cipher выполняет оба этапа и возвращает ключ с открытым текстом. Но когда организаторы используют нестандартный алфавит (кириллица, Base64-символы, расширенный ASCII) — автоматика ломается, и нужен свой скрипт. В Python базовая реализация через collections.Counter с перебором длин ключа от 2 до 30 и подсчётом IC укладывается в 20-25 строк. Этого хватает за глаза.

Уязвимости RSA в CTF: малый экспонент e=3

RSA — безоговорочный лидер по количеству crypto CTF задач средней и высокой сложности. Ключевые параметры: два простых числа p и q, модуль N = p*q, публичная экспонента e, приватная экспонента d (мультипликативно обратная к e по модулю λ(N)). Шифрование: c = m^e mod N. Расшифрование: m = c^d mod N. Публичный ключ — пара (N, e), приватный — (N, d).

В эталонной реализации — ключ 2048+ бит, паддинг OAEP, e = 65537 — криптосистема устойчива. Но CTF-задачи (и, к сожалению, реальный production-код) систематически отступают от стандарта. Trail of Bits формулирует прямо: «RSA is an intrinsically fragile cryptosystem containing countless foot-guns which the average software engineer cannot be expected to avoid». Разработчики выбирают e = 3 ради экономии на шифровании и проверке подписей — и открывают целый класс атак. Именно низкая публичная экспонента e=3 порождает самые частые уязвимости RSA на CTF.

Взлом RSA CTF: извлечение кубического корня

Самый элементарный случай: e = 3, паддинг отсутствует, сообщение m достаточно мало, чтобы m^3 < N. Операция mod N тут ничего не делает — шифротекст c буквально равен m^3. Расшифровка — извлечение целочисленного кубического корня:

from gmpy2 import iroot

c = 10648  # шифротекст (пример для демонстрации)
e = 3
m, exact = iroot(c, e)
if exact:
    flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
    print(flag.decode())
# iroot(10648, 3) → (22, True)

gmpy2 выполняет целочисленное извлечение корня произвольной точности — стандартная math.isqrt для кубических корней не годится. Функция iroot(c, e) возвращает кортеж: результат и флаг точности. Если exact == True — задача закрыта.

Вариация: m^3 чуть больше N. Тогда c = m^3 mod N, и m^3 = c + k*N для небольшого k. Перебираем k от 0 до нескольких тысяч, проверяя iroot(c + k*N, 3) на точность. Для CTF-задач k обычно не превышает 10^4 — перебор занимает доли секунды.

Как распознать на CTF: в условии дано (N, e, c), экспонента e равна 3 (или 5, 7, иногда 17). Первое действие — попробовать корень e-й степени. Не сработало напрямую — перебрать k. Это 15 секунд работы, и именно с этого шага стоит начинать любой RSA-таск с малым e.

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

Атака Хастада — расширение предыдущей идеи на случай, когда одно и то же сообщение m зашифровано несколькими получателями с разными модулями, но одинаковым малым e. Допустим, e = 3, есть три пары (Ni, ci):

• c1 = m^3 mod N1
• c2 = m^3 mod N2
• c3 = m^3 mod N3

Китайская теорема об остатках (CRT) восстанавливает m^3 mod (N1 * N2 * N3). Поскольку m < min(Ni), верно m^3 < N1N2N3 — CRT даёт точное значение m^3 без модулярной обёртки. Дальше — кубический корень:

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

moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
m_cubed, _ = crt(moduli, remainders)
m, exact = iroot(int(m_cubed), 3)
if exact:
    print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))

На CTF атаку Хастада маскируют: задание подаётся как «перехваченные сообщения от трёх серверов» или «три публичных сертификата для одного домена». Опознавательный признак — одинаковый e, разные N, один открытый текст. Формально атака требует e шифротекстов: для e=3 нужно три, для e=17 — семнадцать. На практике e=17 с 17 серверами — экзотика, так что Хастад чаще всего встречается при e=3 или e=5.

Родственная атака — Franklin-Reiter: если два сообщения связаны известным линейным соотношением (m2 = a*m1 + b для известных a и b), то при e=3 оба восстанавливаются из шифротекстов. В CTF-контексте это две версии флага с минимальным отличием — например, инкрементированный счётчик в конце строки. Trail of Bits описывает эту атаку в своём обзоре слабостей RSA.

Факторизация RSA и атака Винера

Второй крупный класс уязвимостей RSA на CTF связан не с экспонентой, а с модулем N или приватным ключом d.

Когда факторизация RSA тривиальна

Малый множитель. Если один из простых q < 10^20, его найдёт yafu или даже перебор делителей. Обязательный первый шаг — проверить N на factordb.com. База хранит факторизации миллионов чисел: модуль из CTF-задачи нередко уже разложен кем-то до вас. На picoCTF это срабатывает удивительно часто (я перестал удивляться после третьего раза).

Близкие p и q. Если |p - q| мало, работает метод Ферма. Начинаем с a = ceil(sqrt(N)), перебираем a, пока a^2 - N не станет точным квадратом b^2. Тогда p = a + b, q = a - b. На Python — пять строк с gmpy2.isqrt.

Общий множитель между модулями (common modulus attack RSA). Два RSA-таска с разными модулями N1 и N2, но общим простым множителем p? GCD(N1, N2) = p. Одна строка: math.gcd(n1, n2). Организаторы маскируют задачи как «независимые» — ключ в том, чтобы всегда пробовать GCD для каждой пары модулей в наборе.

В 2012 году около 1% TLS-трафика использовало RSA-модули с общими множителями из-за дефектных генераторов случайных чисел (данные Trail of Bits). Не абстрактная угроза: в терминах MITRE ATT&CK ослабление криптографии через некорректные параметры — техника Weaken Encryption (T1600, Defense Evasion), подтехника Reduce Key Space (T1600.001).

Атака Винера — малый приватный экспонент d

Иногда разработчики выбирают маленький d для ускорения расшифрования — особенно на смарт-картах и IoT. Винер доказал: если d < N^(1/4) / 3, приватный ключ полностью восстанавливается.

Метод — разложение дроби e/N в цепную дробь (continued fraction). Подходящие дроби (convergents) содержат пару k/d. Атакующий перебирает convergents и для каждого кандидата d проверяет, факторизуется ли N на два простых с нужными свойствами.

Как опознать на CTF: аномально большой e, сопоставимый по битам с N. Если e = 65537 — атака Винера RSA не применима. Если e занимает почти столько же бит, сколько N — пробуйте немедленно.

Инструменты: модуль owiener на Python или встроенная атака в RsaCtfTool (--attack wiener). Бонех и Дёрфи расширили границу до d < N^0.292, но их метод требует решётчатых алгоритмов (LLL) — это уровень SageMath. На большинстве CTF стандартного Винера хватает.

Инструменты для crypto CTF: RsaCtfTool и SageMath

RsaCtfTool — автоматический взлом RSA

RsaCtfTool прогоняет десятки атак на переданные RSA-параметры. Из документации (список атак на ctf101.org): факторизация слабых ключей, атака Винера, атака Хастада, малый q (q < 100 000), общий множитель, метод Ферма для близких p и q, метод Бонеха-Дёрфи, метод Полларда p-1, метод эллиптических кривых и SIQS через yafu.

Типовые вызовы: python3 RsaCtfTool.py -n <N> -e <e> --uncipher <c> для расшифровки, python3 RsaCtfTool.py --publickey pub.pem --private для извлечения приватного ключа, python3 RsaCtfTool.py -n <N> -e <e> --attack wiener для конкретной атаки.

Инструмент не универсален — кастомные протоколы и нестандартную математику он не осилит. Но как первый автоматический проход по любому RSA-таску — экономит критические минуты. Совет: запускайте RsaCtfTool параллельно с ручным анализом. Пока скрипт перебирает атаки, вы уже изучаете параметры и думаете, что может сработать. Два процесса — один мозг, один CPU.

SageMath и вспомогательный арсенал

SageMath незаменим там, где нужна работа с решётками, эллиптическими кривыми и конечными полями. Главное применение — атака Копперсмита через small_roots(): при частично известном открытом тексте и малом e SageMath находит корни полинома по модулю N. Продвинутый уровень, но на серьёзных CTF (Google CTF, hxp, DEF CON Quals) такие задачи — регулярные гости.

CyberChef для CTF полезен на этапе разведки: определить кодировку (Base64, hex, URL-encoding), попробовать XOR с перебором ключа, применить ROT13/ROT47. Для серьёзной математики его мощности не хватит.

openssl из командной строки пригодится для работы с PEM-ключами: openssl rsa -pubin -in pub.pem -text -noout покажет параметры публичного ключа (N и e в читаемом виде), а openssl rsautl -decrypt -inkey priv.pem -in ct.bin расшифрует файл приватным ключом. Иногда openssl — единственное, что есть на сервере CTF-задачи.

Криптографические ошибки за пределами CTF

Уязвимости RSA из CTF-тасков — не учебная абстракция. ROCA-уязвимость 2017 года затронула смарт-карты, TPM-модули и ключи Yubikey: простые числа генерировались в специальной форме для ускорения, что позволяло факторизовать модуль через метод Копперсмита (описано в исследовании Trail of Bits). OWASP относит такие ошибки к категории A02:2021 — Cryptographic Failures, второй по критичности в актуальном OWASP Top 10.

Техника MITRE ATT&CK T1552.004 (Private Keys, Credential Access) описывает реальный сценарий: атакующий получает приватные ключи из-за слабой генерации или небезопасного хранения. На CTF вы восстанавливаете d через Винера или факторизуете N — в продуктивной системе последствия те же: компрометация всего зашифрованного канала. Trail of Bits прямо указывает: «developers who implement their own RSA fail to use padding at an alarmingly high rate» — и это касается не только CTF, но и коммерческого ПО.

Наблюдение, которое не даёт покоя после нескольких сезонов: русскоязычных материалов по криптографии два типа — пересказ учебника или разбор одного конкретного таска. Между «RSA — это p, q, N, e, d» и «вот мой writeup задачи с Google CTF» зияет методологическая пустота. Никто не объясняет самый ценный навык — как за 30 секунд определить, какая атака подходит к конкретному заданию.

А ведь алгоритм прост. Получили RSA-таск — первым делом N в FactorDB. Не нашлось — смотрим размер e. Маленький (3, 5, 17) → кубический корень, Хастад, Franklin-Reiter. Большой, сопоставим с N по битам → Винер. Дали несколько модулей → GCD всех пар. Параллельно запускаем RsaCtfTool на автомате. И только когда весь чеклист отработан — открываем SageMath и начинаем думать. По моим наблюдениям, большинство команд поступают ровно наоборот: час пытаются что-то придумать с нуля, потом случайно обнаруживают, что N лежал в FactorDB с 2019 года.

Прогноз на пару лет: задачи на чистый textbook RSA с голым e=3 уходят с серьёзных турниров. Организаторы уровня hxp и DEF CON давно перешли к решёткам, эллиптическим кривым и кастомным протоколам. Но на CTF для новичков и среднего уровня стандартные атаки будут работать ещё долго. Кто впитает чеклист из этой статьи, закроет crypto-категорию на подобных турнирах за первый час — а освободившееся время вложит в задачи, которые действительно требуют думать. На WAPT в Codeby School связку «классика + RSA» разбирают с лабами — если хочется не просто прочитать, а руками пощупать каждую атаку.

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