Крипто CTF для начинающих: от Цезаря до RSA

На picoCTF задача Mini RSA — три числа в файле и подсказка «What happens if you have a small exponent?». Формально достаточно извлечь кубический корень из шифротекста. Звучит просто? По writeup'у с dev.to, автор убил 45 минут на три неработающих подхода — float-арифметика Python, модуль decimal с точностью 2000 знаков и ручной метод Ньютона — прежде чем получил флаг в восьми строках кода с gmpy2. Вот этот разрыв между «понимаю идею атаки» и «получаю флаг» — типичная боль крипто CTF для начинающих. Его и разберём: от классических шифров до полного цикла атаки на RSA с малым показателем степени.

Классические шифры CTF: Цезарь, Виженер и XOR

Категория crypto на CTF начинается не с RSA и эллиптических кривых. Задачи уровня easy — подстановочные шифры, кодировки и XOR с коротким ключом. На picoCTF задачи с тегами Caesar и ROT13 решаются за минуту, а первый флаг по криптографии реально получить вообще без навыков программирования. Но именно на этих «детских» задачах отрабатывается навык, который потом определяет скорость на любом соревновании: распознавание типа шифра по виду шифротекста. Научился с ходу отличать base64 от hex, а Цезаря от Виженера — дальше всё пойдёт быстрее. Подробнее — в нашем статье о создание ctf заданий.

Шифр Цезаря и Виженера в CTF-задачах

Шифр Цезаря — сдвиг каждой буквы алфавита на фиксированное число позиций. ROT13 — частный случай со сдвигом 13. Всего 25 вариантов сдвига, перебор занимает секунды.

Где новички застревают: путают Цезаря с Виженером. Разница фундаментальна. У Цезаря один сдвиг на весь текст. У Виженера каждая буква сдвигается на свою величину, определяемую ключевым словом. Ключ CODEBY длиной 6 символов означает, что первая буква текста сдвигается на 2 (C = третья буква, индекс 2), вторая на 14 (O), третья на 3 (D) — и так по кругу. После шестой буквы ключ повторяется. Перебрали все 25 сдвигов Цезаря и не получили читаемый текст? Скорее всего перед вами Виженер или что-то сложнее.

Виженер ломается частотным криптоанализом. Принцип: определить длину ключа (тест Касиски или индекс совпадений), разбить шифротекст на группы букв, зашифрованных одним и тем же сдвигом, и для каждой группы найти сдвиг по частотам букв. В английском тексте самая частая буква — E (~12.7%), в русском — О (~10.9%). На CTF длина ключа обычно 3–8 символов, и автоматические инструменты справляются без ручного анализа. Ресурс dcode.fr/vigenere-cipher с автоопределением ключа решает большинство задач этого типа — тупо вставляете шифротекст и забираете ключ.

В терминале ROT13 решается одной командой: echo "PvoreOl{synt}" | tr 'A-Za-z' 'N-ZA-Mn-za-m'. Для произвольного сдвига Цезаря таблицу подстановки в tr нужно рассчитать под конкретный сдвиг, либо использовать CyberChef/dcode.fr с перебором всех 25 вариантов.

Навык распознавания кодировок и подстановочных шифров — не абстрактная CTF-гимнастика. В MITRE ATT&CK деобфускация данных описана как Deobfuscate/Decode Files or Information (T1140), а злоумышленники систематически кодируют вредоносные файлы через base64 и XOR для обхода детекта — техника Encrypted/Encoded File (T1027.013). Тот же certutil -decode, который встречается в Sigma-правилах для обнаружения подозрительной активности на Windows, в CTF-задачах появляется регулярно. По сути CRT-задачи — это тренажёр для навыка, который пригодится при анализе реального малваря.

CyberChef для начинающих: главный инструмент криптоанализа

CyberChef — веб-приложение, которое заменяет десяток скриптов для работы с классическими шифрами. Одна вкладка в браузере покрывает ROT13, Vigenère Decode, XOR, From Hex, From Base64 и сотни других операций. Я на каждом CTF начинаю именно с него.

Ключевая функция — Magic (автоопределение кодировки). Загружаете строку, Magic пробует популярные преобразования и показывает вероятные варианты. Для задач уровня easy этого часто хватает для полного решения без единой строки кода. Закинул шифротекст — забрал флаг.

XOR с коротким ключом — отдельная категория задач, и CyberChef справляется с ней отлично. Если ключ — один байт (256 вариантов), операция XOR Brute Force перебирает их мгновенно. Если ключ длиннее, но известен формат флага (например, CTF{), XOR этих известных байт с началом шифротекста выдаёт начало ключа. Конкретный пример: шифротекст в hex 1a0a001f084e, XOR 1a0a001f с 43544647 (hex-представление CTF{) даёт 595e4658 — это начало ключа. Подставляете ключ в CyberChef и расшифровываете полностью.

Среди open source инструментов криптоанализа CyberChef — стандарт для уровня easy-medium. На уровне hard без Python и специализированных библиотек уже не обойтись.

Основы криптографии RSA для CTF

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

Параметры RSA: - p, q — два больших простых числа (секрет) - n = p * q — модуль (публичный) - e — публичная экспонента (стандартное значение 65537, но в CTF бывает 3, 5, 17) - d — приватная экспонента (секрет), вычисляется как модульное обратное e по модулю phi(n) - phi(n) = (p-1)(q-1) — функция Эйлера

Шифрование: c = m^e mod n, где m — открытый текст, представленный как число. Дешифрование: m = c^d mod n.

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

Модульная арифметика — единственная концепция, которую нужно усвоить прочно. Для тех кто в танке: операция m^e mod n означает — возвести m в степень e, разделить результат на n и взять остаток. А вот критический момент для атак: если значение m^e оказывается меньше n, операция mod ничего не делает. Остаток от деления числа на большее число — само это число. Значит c = m^e в чистом виде, без модульной редукции. Именно это эксплуатируется при малой экспоненте.

RSA e=3 уязвимость: почему малая экспонента опасна

Публичная экспонента e=3 означает, что при шифровании сообщение возводится всего в третью степень. Если сообщение m достаточно короткое (флаг на CTF — обычно 30–50 байт), то m^3 может оказаться меньше модуля n (типично 2048 бит, ~617 десятичных цифр). Условие m^3 < n выполняется, модульная редукция не срабатывает, и для дешифрования достаточно извлечь точный целочисленный кубический корень из шифротекста. По сути — арифметическая задача для девятого класса, только числа побольше.

Стандарт RSA-OAEP существует именно для противодействия этой атаке: он добавляет к сообщению случайный паддинг перед шифрованием, увеличивая m до размера, при котором m^e гарантированно превышает n. Как отмечается в обсуждении на crypto.stackexchange.com, RSA-шифрование обязано дополнять сообщение случайными данными, уникальными для каждого получателя. Без паддинга RSA с e=3 — не криптографическая защита, а задачка на извлечение корня.

Разбор задания crypto CTF: атака на RSA с малой экспонентой

Разберём задачу в стиле picoCTF Mini RSA. Условие: даны модуль n (число длиной ~600 цифр), публичная экспонента e=3 и шифротекст c. Паддинг не применяется. Нужно получить открытый текст.

Три ошибки при извлечении корня

Вот тут начинается самое интересное — грабли, на которые наступает почти каждый новичок.

Ошибка 1: Python float. Выражение c ** (1/3) использует IEEE 754 double precision — 64 бита, примерно 15 значащих цифр. Для числа длиной 300+ цифр точности катастрофически не хватает. long_to_bytes() от такого «корня» возвращает мусор из нулевых байтов.

Ошибка 2: модуль decimal с высокой точностью. Конструкция Decimal(c) ** (Decimal(1)/Decimal(3)) с параметром prec=500 даёт частичный результат. По writeup'у Mini RSA с dev.to, первые 22 символа флага оказались корректными (picoCTF{e_sh0u1d_b3_lA), остальные — нули. Увеличение точности до 2000 знаков добавило ещё пару символов, но полного ответа не будет никогда: decimal работает с вещественной арифметикой расширенной точности, а нужна точная целочисленная. Близко, но мимо.

Ошибка 3: метод Ньютона с плохим стартом. Итерация x = (2*x + n // x**2) // 3 — корректный алгоритм для целочисленного кубического корня. Но начальное приближение через int(round(c ** (1/3))) для 300-значного числа настолько далеко от истины, что алгоритм сходится к неверному значению. Метод Ньютона гарантирует сходимость при достаточно хорошем старте — float-приближение таковым не является.

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

Рабочее решение через gmpy2

Библиотека gmpy2 — Python-обёртка над GNU Multiple Precision Arithmetic. Функция iroot(n, e) возвращает целочисленный корень и булев флаг точности результата. Восемь строк — и флаг в кармане:

import gmpy2
from Crypto.Util.number import long_to_bytes

c = ...  # шифротекст из задания
e = 3
m, exact = gmpy2.iroot(c, e)
if exact:
    print(long_to_bytes(int(m)))
else:
    print("m^3 > N, нужна итерация")

Если exact == True — сообщение m найдено, конвертируем в байты через long_to_bytes из pycryptodome и читаем флаг. Но организаторы часто подкидывают нюанс: делают m чуть длиннее, чтобы m^3 немного превысило n. Тогда модульная редукция срабатывает один-два раза, и c = m^3 mod n, то есть m^3 = c + k*n для небольшого целого k. Перебираем k:

import gmpy2
from Crypto.Util.number import long_to_bytes

e, N, c = 3, ..., ...  # параметры из задания
for k in range(10000):
    m, exact = gmpy2.iroot(c + k * N, e)
    if exact:
        pt = long_to_bytes(int(m))
        if b'{' in pt:
            print(f"k={k}: {pt}"); break

Скрипт перебирает k от 0 до 9999 и для каждого проверяет, является ли c + k*N точным кубом. Условие b'{' in pt — фильтр по формату флага. На picoCTF Mini RSA корректное k находится в пределах нескольких тысяч итераций, выполнение занимает секунды.

Установка зависимостей: pip install gmpy2 pycryptodome. На Linux предварительно sudo apt install libgmp-dev libmpfr-dev libmpc-dev — без системных библиотек GMP установка gmpy2 завершится ошибкой. На это тоже можно потратить полчаса, если не знать заранее.

Атака Хастада RSA: один текст и три получателя

Атака Хастада — развитие идеи малой экспоненты на сценарий с несколькими получателями. Допустим, одно сообщение m зашифровано с e=3 для трёх адресатов с разными модулями n1, n2, n3. Атакующий перехватывает три шифротекста:

• 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) и e=3, значение m^3 < n1 * n2 * n3. Модульная редукция снова не срабатывает, и мы получаем m^3 в чистом виде. Дальше — gmpy2.iroot, как в предыдущем разделе.

В общем виде: для экспоненты e нужно ровно e шифротекстов одного и того же сообщения с разными модулями. На CTF атака Хастада появляется в задачах уровня medium-hard, где условие содержит набор пар (n_i, c_i) с одинаковым e.

В SageMath CRT решается одной строкой: CRT_list([c1, c2, c3], [n1, n2, n3]). В чистом Python — через functools.reduce и расширенный алгоритм Евклида. На CryptoHack есть отдельный блок задач именно на CRT — рекомендую пройти его до того, как столкнётесь с Хастадом на реальном CTF. Потренироваться на кошках, так сказать.

Факторизация RSA: чек-лист перед написанием кода

Не каждая RSA-задача на CTF связана с малой экспонентой. Часто модуль n просто слабый — и разложить его на множители проще, чем искать алгебраические уязвимости. Перед тем как писать скрипт, пройдитесь по чек-листу:

factordb.com — база известных факторизаций. Если модуль n уже разложен кем-то ранее, результат хранится в базе. На архивных CTF-платформах (picoCTF, Root Me) срабатывает удивительно часто — задачи решались тысячами участников, и кто-то уже закинул ваш n в базу.

Малый n (до 512 бит) — факторизуется напрямую. В SageMath команда Integer(n).factor() для n < 1000 бит отрабатывает за секунды или минуты в зависимости от структуры числа. По сборнику RSA-атак с jia.je, для задач с «маленьким n» встроенных средств SageMath достаточно.

Близкие p и q — ошибка генерации ключей, при которой p и q различаются на несколько бит. Метод Ферма: начинаем с a = isqrt(n) + 1, проверяем a^2 - n на полный квадрат. Если p и q близки, метод сходится за несколько итераций. Красивая атака — буквально три строки кода.

Малый d (атака Винера) — если приватная экспонента d < n^0.25, цепные дроби разложения e/n восстанавливают d напрямую. По разбору jia.je, проверка подходящих дробей (convergents) на корректность позволяет однозначно определить d. На L3AK-CTF 2025 задача Lowkey RSA использовала модификацию атаки Винера для нестандартной функции Эйлера phi = (p^4-1)(q^4-1), где e*d ≡ -1 (mod phi) — и всё равно решалась через цепные дроби с приближением phi ≈ (N^2-1)^2.

RsaCtfTool — автоматизирует десятки известных атак. Запуск: python3 RsaCtfTool.py --publickey key.pub --uncipherfile cipher.txt. Инструмент последовательно пробует Wiener, Hastad, Fermat, Boneh-Durfee и другие методы. Не заменяет понимание механики атак, но экономит критические минуты на CTF с ограниченным таймером. Я обычно запускаю его в фоне, пока сам ковыряю параметры вручную.

Инструменты для разбора заданий crypto CTF

Минимальный набор, который покрывает 95% задач от easy до medium:

Инструмент	Применение	Когда нужен
CyberChef	Кодировки, классические шифры, XOR	Easy — каждый раз
gmpy2	Точный iroot, gcd, модульное обратное	Любая RSA-задача
SageMath	Coppersmith, цепные дроби, факторизация	Medium-hard RSA
RsaCtfTool	Автоматический перебор RSA-атак	Когда тип атаки неочевиден
pycryptodome	long_to_bytes, AES, работа с ключами	Конвертация результатов
dcode.fr	Виженер, подстановочные шифры, коды	Классические шифры

Практический совет: на CTF с таймером запускайте RsaCtfTool в фоне, пока сами анализируете параметры вручную. Если инструмент найдёт ответ раньше — сэкономите время. Если нет — у вас уже будет понимание задачи для ручного подхода. Двойная страховка.

Установка: pip install gmpy2 pycryptodome. SageMath ставится отдельно через пакетный менеджер (на Ubuntu — sudo apt install sagemath) или используется онлайн через CoCalc. RsaCtfTool клонируется с GitHub и требует Python 3 с набором криптографических библиотек.

Маршрут для новичка: что решать первым

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

Неделя 1–2: CryptoHack (cryptohack.org). Платформа, посвящённая исключительно криптографии. Задачи выстроены по нарастающей: кодировки и XOR → модульная арифметика → RSA → эллиптические кривые. Каждый блок — 5–10 задач с теоретическими подсказками и встроенной проверкой. Лучший структурированный ресурс для построения базы. За глаза хватит на первые две недели.

Неделя 3: picoCTF (picoctf.org). Фильтр по категории Cryptography, решать от easy к medium. Mini RSA — обязательная задача для закрепления атаки на малую экспоненту. После неё стоит взять задачи с тегами RSA, XOR и Vigenère.

Неделя 4: архивы CTFtime (ctftime.org). Искать writeup'ы прошедших CTF по тегу crypto и повторять чужие решения в своём терминале. Один разбор задания crypto CTF, выполненный руками, даёт больше понимания, чем десять прочитанных статей. Обращайте внимание на writeup'ы с тегом RSA — они чаще всего содержат переиспользуемые паттерны атак.

На CryptoPals (cryptopals.com) задачи ближе к реальной криптографии и криптоинженерии, чем к CTF-формату, но Sets 1–3 дают фундамент (блочные шифры, потоковые шифры, атаки на CBC), который пригодится на любом соревновании уровня medium и выше.

Crypto — самая недооценённая категория у русскоязычных CTF-игроков. На каждом соревновании вижу одну и ту же картину: web-задачи решают десятки команд, pwn берут продвинутые, а крипто пропускают из страха перед «высшей математикой». При этом команды, у которых есть хотя бы один человек с базовым крипто-навыком, стабильно набирают на 15–20% больше очков — не из-за повышенной стоимости задач, а из-за низкой конкуренции в категории. Реальная математика, которая нужна для 90% задач уровня easy-medium — наибольший общий делитель, модульная арифметика и понятие простого числа. Это даже не первый курс университета, это девятый класс. Сложность крипто начинается на hard (Coppersmith, lattice reduction, атаки на эллиптические кривые), и до этого уровня можно дорасти за полгода регулярной практики. Порог входа — не мифическая «математическая одарённость», а привычка разбирать writeup после каждого нерешённого таска и воспроизводить чужое решение руками. Если хочешь от отдельных crypto-задач перейти к полному пентест-стеку и подготовке к OSCP — на WAPT разбирают веб-часть с прогрессией от базовых инъекций до сложных цепочек, с лабами и ментором.

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