Криптография для CTF: от Цезаря до RSA

Около 90% крипто-заданий на CTF строятся на полудюжине известных паттернов — к такому выводу приходят авторы солверских гайдов (cybersecurityelite.com), и опыт решения задач на CryptoCTF и PicoCTF это подтверждает. Барьер входа в crypto-категорию — не теория чисел и не абстрактная алгебра, а навык быстро классифицировать то, что перед тобой: подстановочный шифр, XOR с коротким ключом или текстбук-RSA с дырявыми параметрами. Дальше — дело техники.

Три направления криптографии для CTF, которые покрывают абсолютное большинство задач начального и среднего уровня: классические шифры с частотным анализом, XOR-шифрование и атаки на RSA с малой экспонентой. Рабочий код на Python, чек-листы и пошаговая логика решения — всё, чтобы начать закрывать крипто-таски.

Распознавание шифра: первые 30 секунд решают всё

Самая частая ошибка новичка — бросаться писать код, не определив тип задачи. На соревновании время ограничено, и правильная классификация на старте экономит часы. Смотрим на шифротекст или исходный код, определяем семейство, выбираем инструмент. Подробнее — в нашем обзоре создание ctf заданий.

Базовая таблица визуальных признаков:

Что видим в шифротексте	Вероятное семейство	Первый шаг
Латинский текст, читаемые слова, но бессмысленные	Caesar / ROT-N	Перебор 26 сдвигов
Латинский текст без повторяющихся паттернов, равномерное распределение букв	Vigenere / подстановка	Индекс совпадений, метод Касиски
Строка с символами =, +, / на конце	Base64 (кодировка, не шифр)	Декодировать, анализировать результат
Hex-строка с повторами блоков по 32 символа	AES-ECB	Поиск одинаковых блоков
Два-три больших числа (n, e, c)	RSA	Чек-лист уязвимостей
Непечатаемые символы или hex без выраженных паттернов	XOR с ключом	Brute-force по частоте букв
Числа через запятую, нестандартный формат	Кастомный шифр	Анализ исходного кода задачи

Не путать кодирование с шифрованием. Base64, hex, URL-encoding — это представление данных, а не криптография. На CTF начального уровня «крипто-задача» нередко оказывается матрёшкой из кодировок: Base64 → hex → ROT13. Прежде чем искать ключ шифрования, убедитесь, что перед вами действительно шифр, а не многослойная обёртка.

В CTF crypto заданиях почти всегда дают исходный код (source.py, encrypt.py, chall.py). Если код есть — анализируйте его до работы с шифротекстом. Код показывает точный алгоритм и дырявые места, а гадание по шифротексту после этого уже не нужно.

Для автоматической идентификации без исходного кода подходит dCode.fr: загружаете шифротекст, сервис выдаёт список вероятных алгоритмов с вариантами расшифровки. CyberChef для криптографии полезен через модуль Magic — он последовательно пробует распространённые преобразования и показывает наиболее вероятные результаты. Два инструмента покрывают 80% ситуаций, когда шифр нужно определить «вслепую».

Классические шифры: криптоанализ от Цезаря до Виженера

Классические шифры — стартовая точка основ криптографии для начинающих в CTF. Они появляются в задачах уровня Easy и иногда прячутся внутри задач посложнее как один из слоёв.

Взлом шифра Цезаря: перебор 26 ключей

Шифр Цезаря — моноалфавитная подстановка, где каждая буква сдвигается на фиксированное число позиций. Ключевое пространство — 26 вариантов для латиницы (33 для кириллицы). Атака тривиальна: перебираем все сдвиги, выбираем осмысленный результат.

На соревнованиях первым делом пробую ROT13 в CyberChef — один клик, потому что составители задач обожают именно этот сдвиг. Если не совпало — полный перебор занимает секунды:

ct = "GUVF VF N FRPERG ZRFFNTR"

for shift in range(26):
    pt = ""
    for ch in ct:
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            pt += chr((ord(ch) - base + shift) % 26 + base)
        else:
            pt += ch
    print(f"Сдвиг {shift:2d}: {pt}")

В выводе ищем строку, похожую на осмысленный текст или формат флага (CTF{...}, flag{...}, picoCTF{...}). Здесь сдвиг 13 даёт THIS IS A SECRET MESSAGE. CyberChef с операцией ROT13 Brute Force делает то же самое без написания кода, но скрипт на Python выручает при нестандартных алфавитах, кириллице или модифицированных вариантах Цезаря.

Лайфхак для распознавания: шифротекст содержит только латинские буквы и выглядит как слова с «неправильными» буквами — с высокой вероятностью Цезарь или ROT-N. Если распределение букв визуально равномерное (нет «частых» и «редких» символов) — скорее Виженер или другой полиалфавитный шифр.

Частотный анализ шифротекста и шифр Виженера

Когда моноалфавитный шифр сложнее Цезаря — произвольная подстановочная таблица — перебор невозможен: ключевое пространство 26! вариантов. Тут работает частотный анализ шифротекста. В естественном языке буквы встречаются с предсказуемой частотой. Для английского: E (~12.7%), T (~9.1%), A (~8.2%), O (~7.5%), I (~7.0%), N (~6.7%). Для русского: О (~10.9%), Е (~8.5%), А (~8.0%), И (~7.4%).

Если в шифротексте буква X встречается заметно чаще остальных — вероятно, она соответствует E (или О для русского текста). Сопоставив частоты всех букв с эталонными частотами языка, восстанавливаем таблицу подстановки. Чем длиннее текст, тем точнее результат — на текстах короче 200 символов частотный анализ ненадёжен, и тут уже начинается гадание на кофейной гуще.

Шифр Виженера усложняет картину: каждая буква сдвигается на величину, определяемую символом ключевого слова. Частотный анализ напрямую не работает, потому что одна и та же буква открытого текста шифруется разными сдвигами. Решение — двухшаговая атака:

1. Определить длину ключа. Метод Касиски: ищем повторяющиеся тройки или четвёрки букв в шифротексте. Расстояние между повторами кратно длине ключа. НОД всех найденных расстояний — вероятная длина. Альтернатива — индекс совпадений (Index of Coincidence, IoC). Для английского текста IoC ≈ 0.067, для случайного распределения — 0.038. Разбиваем шифротекст на подстроки с шагом k, считаем IoC каждой. Значение k, при котором IoC максимально близок к 0.067 — правильная длина ключа.

2. Частотный анализ каждой группы. Зная длину ключа (допустим, 5), берём каждую 1-ю, 6-ю, 11-ю букву — все они зашифрованы одним сдвигом. Применяем частотный анализ к каждой группе отдельно, восстанавливая ключ побуквенно.

На соревнованиях dCode.fr автоматизирует оба шага: загружаете шифротекст, сервис определяет длину ключа Виженера и выполняет дешифровку без ключа. Для ручного подхода — скрипт на Python с подсчётом IoC, десяток строк кода, которые стоит держать в персональном шаблоне для CTF.

XOR в CTF crypto заданиях

XOR-шифрование — рабочая лошадка CTF-криптографии. Операция обратима: plaintext XOR key = ciphertext и ciphertext XOR key = plaintext. Знаем любые два компонента из трёх — восстанавливаем третий. Просто и красиво.

Однобайтовый ключ. Весь текст XOR-ится с одним байтом из диапазона 0–255. Атака: перебираем 256 вариантов, каждый результат оцениваем по частоте английских букв — e, t, a, o, i, n. Осмысленный текст набирает высокий «балл читаемости». Подход описан в Cryptopals (Set 1, Challenge 3) — каноническое вводное задание по CTF crypto. В CyberChef операция XOR Brute Force с фильтрацией по ASCII решает это за один клик.

Повторяющийся ключ. Ключ длиной N байт циклически применяется к тексту. Атака: определяем длину ключа через расстояние Хэмминга (Hamming distance) между блоками шифротекста. Блоки, зашифрованные одним фрагментом ключа, дают меньшее расстояние. После определения длины разбиваем шифротекст на N групп и решаем каждую как однобайтовый XOR. Пошагово — Cryptopals Set 1, Challenge 6. Рекомендую пройти руками, прежде чем хвататься за готовые инструменты. Разница между «понял» и «прочитал writeup» — именно в этом задании.

Known-plaintext и crib-dragging. Если известна часть открытого текста (заголовок файла, формат флага flag{, HTTP-заголовок GET /), XOR-им её с соответствующим участком шифротекста — получаем фрагмент ключа. Дальше «протаскиваем» (crib-drag) этот фрагмент по всему шифротексту, расширяя известную часть ключа до полной длины.

Отдельный случай — CTR nonce reuse в AES. Если два сообщения зашифрованы с одним nonce, XOR двух шифротекстов даёт XOR двух открытых текстов. Дальше — crib-dragging. По OWASP A02:2021 (Cryptographic Failures), повторное использование nonce — типичная криптографическая ошибка в продакшне, и CTF-задачи регулярно моделируют именно этот сценарий.

Атака на RSA с малой экспонентой: разбор криптографических CTF задач

RSA — самый частый «босс» крипто-категории на CTF среднего уровня. Минимум, который нужно держать в голове: открытый ключ (n, e), шифротекст c = m^e mod n, цель — найти m. Безопасность RSA опирается на сложность факторизации n = p * q, где p и q — большие простые. В CTF параметры намеренно выбирают слабыми, и задача сводится к распознаванию конкретной дыры из ограниченного набора.

Чек-лист уязвимостей RSA для CTF задач

Получив задачу с RSA, проходите по чек-листу сверху вниз. Составлен по материалам разборов CTF-задач и гайда cybersecurityelite.com:

Признак	Атака	Инструмент
Маленький n (< 512 бит)	Прямая факторизация	FactorDB, yafu
e = 3 и короткое сообщение	Извлечение корня e-й степени	gmpy2.iroot
e = 1	Шифрования нет: c = m	—
p и q близки друг к другу	Факторизация Ферма	Python, SageMath
Общий n, два разных e	Атака общего модуля (extended GCD)	Python
Одно m, несколько (n_i, e) с малым e	Атака Хостада (CRT)	SageMath
Утечка части d или dp/dq	Метод Копперсмита	SageMath, small_roots()
Очень большой e / малый d	Атака Винера (continued fractions)	RsaCtfTool

Первый шаг — всегда проверить n через FactorDB (factordb.com). Составители CTF нередко берут n из учебных примеров, и модуль уже факторизован в базе. Занимает 5 секунд и решает задачу в неожиданно большом числе случаев. На одном соревновании я так закрыл три RSA-таска подряд — составители не удосужились сгенерировать свежие ключи.

RSA low exponent attack: извлечение корня при e=3

Если экспонента e мала (классика — e = 3) и сообщение m достаточно короткое, то m^e < n. Модулярная арифметика не «оборачивается»: c = m^3 mod n превращается в c = m^3 в обычных целых числах. Чтобы восстановить m, достаточно извлечь кубический корень из c:

import gmpy2

e = 3
c = 1030301  # пример: 101^3

m, exact = gmpy2.iroot(c, e)
if exact:
    print(f"m = {m}")
    # Конвертация: long_to_bytes(int(m))
else:
    print("Корень не точный — пробуйте Coppersmith")

gmpy2.iroot(c, e) возвращает целочисленный корень и флаг точности. Если exact = True — задача решена, осталось конвертировать число в байты через long_to_bytes из Crypto.Util.number (пакет pycryptodome). Если корень не точный — сообщение было достаточно длинным и произошло модулярное обёртывание. Тогда два варианта:

• Padding фиксированный и известный — метод Копперсмита (поиск малых корней полинома по модулю n). В SageMath это small_roots() для объекта PolynomialRing(Zmod(n)).
• Одно сообщение зашифровано для нескольких получателей с разными n, но одинаковым малым e — атака Хостада: собираем систему c_i = m^e mod n_i, решаем через CRT (Китайскую теорему об остатках), затем извлекаем корень.

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

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

from sympy import isqrt

def fermat_factor(n):
    a = isqrt(n) + 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

p, q = fermat_factor(n)

Если p и q отличаются менее чем на n^(1/4), факторизация завершается за доли секунды. При большей разнице цикл зависнет — переходим к yafu, cado-nfs или RsaCtfTool.

После нахождения p и q расшифровка стандартная: phi_n = (p - 1) * (q - 1), d = pow(e, -1, phi_n) (Python 3.8+), m = pow(c, d, n). Финал — long_to_bytes(m) для конвертации числа в текст флага.

RsaCtfTool автоматизирует весь процесс: передаёте n, e, c, он последовательно пробует FactorDB, Fermat, Wiener, Boneh-Durfee и десятки других атак. На соревнованиях экономит время, но без понимания механики каждой атаки нестандартную задачу, где автоматика буксует, не решить.

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

Набор инструментов для криптографических CTF задач компактен. Вот что реально используется на соревнованиях:

CyberChef (gchq.github.io/CyberChef) — браузерный мультитул для кодировок, шифров и хешей. Для крипто-задач: From Hex / Base64 / Base32, XOR, XOR Brute Force, ROT13 Brute Force, Magic (автоматическое определение кодировки). Собираете цепочку преобразований (Recipe) и видите результат в реальном времени. Для классических шифров и быстрой работы с кодировками — первый инструмент в арсенале.

SageMath — математическая система с нативной поддержкой колец, полей Галуа и полиномов. Для RSA-атак незаменима: small_roots() для Копперсмита, CRT для Хостада, LLL-редукция для решёточных атак. На CryptoHack большинство продвинутых writeup-ов написаны именно на SageMath — и не просто так.

Python + библиотеки. Ядро: pycryptodome — шифрование/дешифрование и модуль Crypto.Util.number с long_to_bytes, bytes_to_long, getPrime. gmpy2 — быстрая арифметика с большими числами (iroot, invert, gcd). Для факторизации и символьных вычислений — sympy с isqrt, factorint, isprime.

pwntools — для сетевых задач. Когда нужно подключиться к серверу по TCP и обменяться данными (как в разборе задачи Android-in-the-middle с HTB Cyber Apocalypse, описанном на Хабре), remote('host', port) открывает соединение, sendline() и recvline() управляют обменом.

RsaCtfTool — автоматизированный набор атак на RSA. Не заменяет понимание, но когда за 5 минут нужно проверить полтора десятка векторов — экономит нервы.

dCode.fr — онлайн-сервис с автоматическим распознаванием типа шифра. Особенно хорош для классики: Цезарь, Виженер, Полибий, Хилл, Playfair.

Площадки для тренировки. CryptoHack (cryptohack.org) — лучшая платформа для прокачки крипто-навыков: задачи от основ до эллиптических кривых и решёток с пошаговым прогрессом. Cryptopals (cryptopals.com) — канонический набор из 48 упражнений по криптоанализу. PicoCTF — CTF для начинающих с достойной крипто-категорией.

Практический совет: заведите шаблон-скрипт для RSA — подставляете n, e, c и последовательно прогоняете чек-лист уязвимостей. Быстрее, чем писать с нуля на каждом соревновании.

CTF-криптография напрямую связана с реальными уязвимостями: категория OWASP A02:2021 (Cryptographic Failures) описывает ровно те ошибки, которые моделируют в CTF — слабые ключи, повторное использование nonce, отсутствие проверки padding. В MITRE ATT&CK техника T1600 (Weaken Encryption) и подтехника T1600.001 (Reduce Key Space) покрывают сценарии намеренного ослабления криптографии — то, что заложено в каждую CTF-задачу на слабые RSA-параметры.

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

Ещё одно наблюдение из практики: крипто — единственная категория CTF, где чтение чужих writeup-ов по-настоящему работает как метод обучения. В pwn каждая задача требует уникального подхода к эксплуатации, а в crypto одни и те же атаки воспроизводятся десятки раз с разными числами. Прочитал 20 разборов RSA — на 21-й задаче паттерн узнаёшь за минуту. Но writeup-ы дают только чужую логику. Чтобы она стала своей — нужно решать самостоятельно, с пустым экраном и без подсказок. Крипто при этом лишь одна из шести базовых категорий CTF, и если хочешь закрыть остальные с тем же уровнем уверенности — на WAPT эту механику разбирают с лабами и прогрессом от простого к сложному.

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