Криптография CTF для новичков: Цезарь, XOR, RSA

На picoCTF в прошлом году я наблюдал, как новичок из нашей команды 40 минут пытался «расшифровать» строку cGljb0NURntiYXNlNjRfaXNfbm90X2VuY3J5cHRpb259, перебирая подстановки и Виженера. Это был обычный Base64. Два клика в CyberChef — флаг на экране. Самая частая ошибка в crypto CTF задачах — не незнание алгоритмов, а неумение определить, с чем именно ты имеешь дело. Эта статья — маршрут от распознавания шифра до написания эксплойта для RSA с маленькой экспонентой. Без теории чисел на 50 страниц, с рабочим кодом на Python.

Как распознать тип шифра в crypto CTF задачах

Как решать crypto таски CTF, если не понимаешь, на что смотришь? Никак. Распознавание кодирования или шифра — навык, который экономит часы на соревнованиях. Автор блога CharCharBloggles прямо пишет: «In my opinion, that's the hardest part of solving CTF crypto challenges» — и каждый турнир это подтверждает. Подробнее — в нашем обзоре создание ctf заданий.

Таблица визуальных маркеров, закрывающая 90% случаев на начальном уровне:

Что видишь	Что это скорее всего	Пример
Только буквы A-Z, текст «почти читается»	Шифр Цезаря / ROT13	Gur synt vf: PGS{ebg13}
Буквы + цифры, заканчивается на = или ==	Base64	Q1RGe2Jhc2U2NH0=
Только символы 0-9 и a-f	Hex (шестнадцатеричное)	4354467b6865787d
Только 0 и 1, длина кратна 8	Двоичное (binary)	01000011 01010100 01000110
Буквы разного регистра, без явного паттерна	Шифр подстановки или Виженер	Wkh iodj lv: FWI{yljhqhuh}
Большие числа (100+ цифр), метки n, e, c	RSA	n = 2519590847...
Символы . и -	Азбука Морзе	.-. ... .-

Три правила, которые работают всегда:

1. Попробуй Base64 первым — на начальных уровнях половина «зашифрованных» строк оказывается просто закодированной.
2. Если строка выглядит как текст, но нечитаема — начни с Цезаря (ROT-сдвиг).
3. Даны большие числа с метками n, e, c или p, q — это RSA. Без вариантов.

Тут принципиально понимать разницу: кодирование (Base64, hex) обратимо без ключа — это не шифрование. Шифр Цезаря и XOR — симметричное шифрование с ключом, пусть и примитивным. RSA — асимметричное шифрование с парой ключей. Путаница между ними — ловушка для каждого второго новичка, и организаторы CTF активно на ней играют, подсовывая закодированные строки в категорию crypto.

Шифр Цезаря: взлом простейшего подстановочного шифра

Шифр Цезаря — подстановочный шифр, где каждая буква алфавита сдвигается на фиксированное число позиций. Сдвиг на 13 позиций (ROT13) — частный случай, который встречается в CTF чаще остальных: повторное применение ROT13 даёт исходный текст, что делает его любимцем авторов «лёгких» задач.

Взлом шифра Цезаря тривиален: всего 25 возможных сдвигов. Перебираешь все — читаешь результат глазами. В writeup'е Crypto CTF 2019 автор описывает задачу «Decode Me», где строка оказалась перевёрнутой и зашифрованной Цезарем со сдвигом 7 — CyberChef позволил выстроить цепочку операций Reverse → ROT13 Brute Force и вытащить промежуточный результат за минуту. Но сначала автор не проверил простые варианты и потратил лишнее время на гипотезу о Виженере. Знакомая история.

Брутфорс шифра Цезаря на Python

ciphertext = "Wkh iodj lv: FWI{fdhvdu_flskhu}"
for shift in range(26):
    result = ""
    for ch in ciphertext:
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            result += chr((ord(ch) - base - shift) % 26 + base)
        else:
            result += ch
    if "CTF" in result or "flag" in result.lower():
        print(f"Сдвиг {shift}: {result}")

Фильтрация по формату флага — приём, который стоит запомнить. На реальном CTF организаторы заранее сообщают формат (например, flag{...} или CTF{...}). Подставляешь в условие — из 25 вариантов видишь только нужный. При сдвиге 3 строка выше превращается в The flag is: CTF{caesar_cipher}.

CyberChef для CTF: расшифровка без единой строки кода

CyberChef (gchq.github.io/CyberChef) — браузерный инструмент от GCHQ, ставший стандартом де-факто на CTF. Для Цезаря: вставляешь шифротекст, добавляешь операцию ROT13 Brute Force — получаешь все 25 вариантов мгновенно. Но настоящая сила — цепочки рецептов. Операция From Base64 → ROT13 решает задачи, где кодирование наложено поверх шифрования. From Hex → XOR → From Base64 — три слоя за один проход.

Типичная ошибка новичка — бросаться на сложные шифры, не проверив простые. Если текст выглядит как «Gur synt vf» — это ROT13, не Виженер и не AES. Правило «сначала самое простое» спасает на каждом турнире.

XOR шифрование: расшифровка через частотный анализ шифротекста

XOR (исключающее ИЛИ) — рабочая лошадка и CTF-криптографии, и реальных атак. В MITRE ATT&CK техника Obfuscated Files or Information (T1027) описывает использование XOR-кодирования для сокрытия вредоносной нагрузки — та же механика, что и в CTF-задачах. Техника Encrypted/Encoded File (T1027.013) уточняет: XOR с коротким ключом — один из самых распространённых методов обфускации шеллкодов. То есть ломая XOR на CTF, ты тренируешь навык, который SOC-аналитик применяет при разборе реального малваря.

Ключевое свойство XOR для дешифровки шифротекста: A XOR K = C и C XOR K = A. Шифрование и дешифровка — одна и та же операция. Если ключ — один байт (значение от 0 до 255), перебор занимает доли секунды.

Однобайтовый XOR-ключ

Перебор 256 вариантов — не единственный подход. Частотный анализ шифротекста работает быстрее. В английском тексте самый частый символ — пробел (0x20), за ним буква «e» (0x65). XOR-ишь самый частый байт шифротекста с 0x20 — с высокой вероятностью получаешь ключ.

from collections import Counter

ciphertext = bytes.fromhex("1b37373331363f78151b7f2b783431333d")
freq = Counter(ciphertext).most_common(1)[0][0]
likely_key = freq ^ 0x20
plaintext = bytes([b ^ likely_key for b in ciphertext])
print(f"Key: 0x{likely_key:02x}")
print(f"Text: {plaintext.decode('ascii', errors='replace')}")

Стопроцентной гарантии приём не даёт, но на CTF с короткими текстами срабатывает в большинстве случаев. Проверка: если в результате читаемый ASCII с пробелами и знаками препинания — ключ верный. Мусор — пробуй XOR с 0x65 или переходи к полному перебору всех 256 значений.

Многобайтовый XOR и known-plaintext атака

Когда ключ длиннее одного байта, есть два рабочих подхода.

Первый — known-plaintext. Формат флага известен (допустим, CTF{). XOR-ишь первые четыре байта шифротекста с CTF{ — получаешь первые четыре байта ключа. Если ключ повторяется (repeating-key XOR), этого хватит для полного восстановления.

Второй — индекс совпадений (Index of Coincidence). Разбиваешь шифротекст на группы по предполагаемой длине ключа. Группа с наиболее «неравномерным» частотным распределением (близким к естественному языку) указывает на правильную длину. Дальше каждый байт ключа находится отдельно через частотный анализ.

На CryptoPals (cryptopals.com) первые шесть задач Challenge Set 1 построены именно на этой прогрессии: от конвертации hex → base64 через single-byte XOR к repeating-key XOR и детектированию AES-ECB. Пройти эти шесть задач — значит выстроить фундамент для всех XOR-задач на CTF. Рекомендую начинать с них.

Base64 и hex кодирование — ловушка для новичков

Повторю в третий раз, потому что это принципиально: кодирование — НЕ шифрование. Base64 и hex обратимы без ключа. Но на CTF начального уровня именно они составляют заметную долю задач в категории crypto — организаторы проверяют способность отличать одно от другого.

Base64 использует 64 символа (A-Z, a-z, 0-9, +, /) и padding-символ =. Строка Q1RGe2Jhc2U2NH0= декодируется в CTF{base64} мгновенно — без ключа, без алгоритма. Hex — то же, но с основанием 16: 4354467b6865787d — это CTF{hex}. В CyberChef для CTF операции From Base64 и From Hex делают это за один клик.

Частый приём в задачах — многослойное кодирование, по типу матрёшки. Строка закодирована в Base64, результат — в hex, результат — снова в Base64. CyberChef позволяет строить цепочку From Base64 → From Hex → From Base64 и применять её одной кнопкой. На CyberChef-жаргоне это называется «рецепт», и опытные CTF-игроки держат библиотеку готовых рецептов для типичных комбинаций.

Почему распознавание кодировок критично за пределами CTF: техника Data Encoding (T1132, тактика Command and Control по MITRE ATT&CK) описывает использование Base64 для маскировки C2-трафика. Подтехника Standard Encoding (T1132.001) — именно Base64 и URL-encoding в связке с C2-каналами. Техника Deobfuscate/Decode Files or Information (T1140) — обратный процесс на стороне аналитика. Когда ты на CTF мгновенно определяешь Base64 по паддингу ==, тренируется тот же навык, который SOC-аналитик использует при разборе подозрительного PowerShell-скрипта с вызовом [Convert]::FromBase64String(...).

RSA маленькая экспонента: атака без приватного ключа

RSA — асимметричный алгоритм, основа половины crypto CTF задач среднего уровня и выше. Вот минимум математики, без которого не обойтись:

• Выбираются два простых числа p и q, вычисляется n = p * q
• Публичная экспонента e — часто 65537, но на CTF бывает 3
• Приватная экспонента d вычисляется так, чтобы e * d mod φ(n) = 1
• Шифрование: c = m^e mod n, где m — открытый текст как число
• Дешифровка: m = c^d mod n

Безопасность RSA держится на сложности факторизации n. Но если параметры выбраны криво — факторизация не нужна.

Почему e=3 ломает RSA

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

На бумаге: m = c^(1/3). Но стандартные вычисления с плавающей точкой теряют точность на больших числах (а в RSA числа — сотни цифр). Нужна целочисленная арифметика произвольной точности. В Python для этого есть gmpy2.

RSA low exponent attack: эксплойт на Python

import gmpy2
from Crypto.Util.number import long_to_bytes

# m^3, где m — короткий ASCII-текст
e = 3
c = 1879080904452

root, is_exact = gmpy2.iroot(c, e)
if is_exact:
    print(f"Флаг: {long_to_bytes(int(root)).decode()}")
else:
    print("Cube root не точный — нужна атака Хастада")

gmpy2.iroot(c, e) возвращает пару: целочисленный корень и флаг точности. Если is_exact == True — задача решена. long_to_bytes из pycryptodome конвертирует число обратно в текстовую строку. Восемь строк кода — и RSA с e=3 сломан.

Когда кубический корень не работает: атака Хастада

Что если m^3 > n и простой кубический корень не даёт целого числа? Тогда нужна атака Хастада (Hastad's broadcast attack). Условие: одно и то же сообщение m зашифровано с e=3 для трёх разных получателей с разными модулями n1, n2, n3. На CTF это выглядит как три набора (n_i, c_i) в условии задачи.

Алгоритм по шагам:

1. Собрать три пары (c_i, n_i) из условия
2. Применить Китайскую теорему об остатках (CRT) для вычисления C = m^3 mod (n1 * n2 * n3)
3. Извлечь gmpy2.iroot(C, 3) — теперь корень будет точным, потому что m^3 < n1 * n2 * n3
4. Применить long_to_bytes(m) для получения флага

CRT реализован в sympy через crt() или вручную через расширенный алгоритм Евклида. На CryptoHack (cryptohack.org) — платформе, целиком посвящённой криптографическим задачам, — раздел RSA начинается именно с low exponent и ведёт к Wiener's attack и padding oracle. Формула на бумаге понятна, но по-настоящему RSA low exponent attack ощущается только когда сам прогоняешь варианты. На HackerLab.pro есть крипто-таски разного уровня сложности — категория Crypto, подходит для отработки именно таких атак на стендовых данных.

Атака Винера: слишком маленькая приватная экспонента

Ещё один частый CTF-сценарий атаки на RSA — атака Винера (Wiener's attack). Работает, когда приватная экспонента d слишком мала — меньше n^(1/4) / 3. В этом случае d восстанавливается через разложение дроби e/n в цепную дробь (continued fraction). Алгоритм перебирает подходящие дроби и проверяет, даёт ли кандидат на d корректную дешифровку тестового сообщения.

На Python цепную дробь строит sympy — модуль continued_fraction_periodic. Но концептуально атака Винера — следующий уровень после low exponent. К ней стоит переходить, когда базовые RSA-задачи решаются уверенно.

Ещё один лайфхак: проверяй n через factordb.com — базу уже факторизованных чисел. На CTF организаторы иногда используют известные n, и факторизация находится за секунду без всяких атак. Для автоматизации есть RsaCtfTool на GitHub — утилита последовательно пробует десятки атак (Wiener, Fermat, Boneh-Durfee и другие) и выдаёт результат. Ленивый подход? Может быть. Но на CTF время — ресурс, и тратить его на ручную факторизацию, когда инструмент делает то же за секунды, — не героизм, а глупость.

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

Минимальный набор, покрывающий абсолютное большинство задач начального и среднего уровня:

Инструмент	Назначение	Когда использовать
CyberChef	Кодировки, классические шифры, цепочки	Первая попытка на любой задаче
Python + pycryptodome	RSA, AES, кастомные алгоритмы	Когда нужна автоматизация
gmpy2	Целочисленные корни, факторизация	RSA с большими числами
dcode.fr	Автоопределение типа шифра	Когда не можешь распознать
factordb.com	Поиск факторизации известных чисел	RSA: проверка, не факторизовано ли n
RsaCtfTool	Автоматические атаки на RSA	Когда знаешь RSA, не знаешь атаку

Рабочий процесс: получил шифротекст — вставил в dcode.fr для автоопределения — если не помогло, проверил по таблице маркеров — применил инструмент — для сложных задач написал скрипт на Python.

Для систематической тренировки основ криптографии для CTF три платформы закрывают разные потребности. CryptoPals (cryptopals.com) — 48 задач с нарастающей сложностью. Подсказок нет, автопроверки нет — пишешь код и проверяешь сам. Формирует глубокое понимание, но будет больно. CryptoHack (cryptohack.org) — интерактивная платформа с категориями от Introduction до Lattices. Есть проверка флагов и writeup'ы после решения — порог входа ниже. picoCTF (picoctf.org) — CTF-платформа от Carnegie Mellon University с задачами всех категорий, включая crypto, — идеальна как первый CTF.

Навыки из crypto CTF задач переносятся в реальную работу напрямую. Распознавание Base64 и hex — основа анализа обфусцированных скриптов и C2-трафика (MITRE ATT&CK: Standard Encoding T1132.001, Non-Standard Encoding T1132.002). XOR-дешифровка — анализ обфусцированных загрузчиков (Encrypted/Encoded File T1027.013). RSA-атаки — аудит криптографических реализаций и оценка стойкости ключей (Weaken Encryption T1600, Private Keys T1552.004). SOC-аналитик, который видит подозрительную строку в логах, применяет те же шаги, что CTF-игрок на турнире.

По опыту ведения команды на университетских CTF — главная проблема новичков в crypto не сложность задач, а паралич выбора. Человек видит строку из 200 символов, не знает с чего начать и переключается на веб или OSINT. Таблица маркеров из начала статьи и привычка «сначала Base64» решают эту проблему за один турнир.

Вторая беда — перфекционизм. Новичок хочет «понять RSA полностью», открывает учебник по теории чисел и выгорает к третьей главе. Не надо так. Возьми задачу с e=3, запусти эксплойт из 8 строк, увидь флаг — математику доберёшь, когда лёгкие задачи закончатся. Подход «от работающего эксплойта к пониманию, почему он работает» даёт результат быстрее академического маршрута «сначала три семестра алгебры». Большинство CTF-игроков, которых я знаю, никогда не доказывали теорему Эйлера — но стабильно решают RSA-задачи, потому что понимают паттерны: маленькая e — бери корень, маленькая d — бери Винера, знакомый n — проверяй factordb. Если хочешь не просто один writeup, а пройти криптовекторы с лабой на каждый кейс — на WAPT такая прогрессия выстроена модулями с ментором в чате при затыке.

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