Криптография
Асимметричная криптография (RSA)
Асимметричная криптография — это когда для шифрования и расшифровки используются два разных ключа: публичный (открытый) и приватный (секретный). RSA — самый известный алгоритм такого типа. В категории crypto на CTF RSA встречается в каждой третьей задаче: флаг зашифрован публичным ключом, а тебе нужно найти приватный или обойти шифрование. Новичку важно понять, как RSA работает и где он ломается, потому что это классика крипто-задач. Знание поможет тебе быстро распознавать слабые места в ключах и использовать стандартные атаки, чтобы достать флаг за 10–30 минут.
Словарь терминов
Асимметричная криптография
Шифрование с двумя ключами: публичным и приватным
RSA
Самый популярный алгоритм асимметричного шифрования
Публичный ключ
Ключ, который можно всем показывать для шифрования
Приватный ключ
Секретный ключ, только с ним можно расшифровать
Модуль n
Большое число — произведение двух простых p и q
Экспонента e
Маленькое число в публичном ключе (обычно 65537)
Экспонента d
Секретное число в приватном ключе
PKCS#1 v1.5
Старый способ добавления набивки к сообщению перед шифрованием
OAEP
Более безопасный способ набивки для RSA
Wiener attack
Атака, когда приватный ключ можно найти по публичному
Boneh-Durfee
Атака на маленькую экспоненту d
Hastad attack
Атака, когда одно сообщение зашифровано несколькими ключами
Coppersmith
Атака на маленькие корни уравнений
Franklin-Reiter
Атака на похожие сообщения с маленькой экспонентой
Common modulus
Атака, когда два человека используют один и тот же n
RSA basics, key generation, padding schemes (PKCS#1 v1.5, OAEP)
RSA работает так: берутся два больших простых числа p и q. Умножаем их — получаем n (это модуль, часть публичного ключа). Выбираем маленькое число e (обычно 65537) — это публичная экспонента. Вычисляем d так, чтобы d × e ≡ 1 (mod (p-1)(q-1)). Публичный ключ — (n, e), приватный — (n, d).
Чтобы зашифровать сообщение m, берём m^e mod n. Чтобы расшифровать — c^d mod n.
Сообщение перед шифрованием нужно "набить" (padding), чтобы оно было нужной длины и безопасно.
PKCS#1 v1.5 — старый padding: добавляют случайные байты и фиксированные 00 02. Очень уязвим к атакам.
OAEP — новый, более безопасный: добавляет случайность и хэш, чтобы одинаковые сообщения давали разный шифротекст.
В CTF RSA basics — основа всех задач. Если видишь два больших числа n и e — это почти всегда RSA. Смотришь, можно ли факторизовать n или подобрать d.
На практике: если n маленькое или p и q близкие — факторизуешь и находишь приватный ключ.
Common RSA attacks: Wiener, Boneh-Durfee, Hastad, Coppersmith, Franklin-Reiter, common modulus, small exponent, small prime factors
Wiener attack — когда приватный d маленький, его можно найти по публичному ключу с помощью непрерывных дробей.
Boneh-Durfee — улучшенная атака на маленькую d.
Hastad attack — если одно и то же сообщение зашифровано несколькими ключами с маленькой e — можно восстановить сообщение.
Coppersmith — мощная атака на маленькие корни уравнений, часто используется для поиска части ключа.
Franklin-Reiter — когда два похожих сообщения зашифрованы с маленькой e — можно восстановить оба.
Common modulus — два человека используют один и тот же n, но разные e — можно найти приватный ключ.
Small exponent — маленькая публичная e (3, 5, 17) делает атаку проще.
Small prime factors — если p и q маленькие или близкие — n легко факторизовать.
В CTF эти атаки — основа 60% RSA-задач. Если видишь маленький d, маленькую e или одинаковый n — это одна из этих атак.
На практике: если e маленькое — пробуешь Hastad или Franklin-Reiter; если n факторизуется за секунды — это small primes.
RSA with weak primes, multiprime RSA, CRT-RSA faults
Weak primes — когда p и q слишком маленькие, близкие или имеют общие делители с другими ключами. Тогда n легко разложить на множители.
Multiprime RSA — когда n — произведение не двух, а трёх или четырёх простых чисел. Это быстрее, но иногда даёт слабые ключи.
CRT-RSA faults — когда используют Chinese Remainder Theorem для ускорения, но при ошибке в вычислениях можно восстановить приватный ключ.
В CTF weak primes — самая частая причина, почему RSA ломается. Если n ≈ 10^100–10^200 и факторизуется за минуты — это weak primes.
На практике: вставляешь n в factordb.com или используешь yafu/ecm — если разложилось — получаешь приватный ключ.
Итог
Асимметричная криптография RSA — это когда публичный ключ шифрует, а приватный расшифровывает. В crypto CTF это основа 60–70% задач: флаг зашифрован RSA, и нужно найти приватный ключ или обойти шифрование.
Главное запомнить: RSA ломается, если n маленькое, p и q близкие, d маленькое, e маленькое, или одно сообщение зашифровано несколькими ключами. Всегда проверяй n на факторизацию и смотри на размер e и d.
Ключевые слова/термины выучить: RSA, публичный ключ, приватный ключ, модуль n, экспонента e, экспонента d, PKCS#1 v1.5, OAEP, Wiener attack, Boneh-Durfee, Hastad attack, Coppersmith, Franklin-Reiter, common modulus, small prime factors.
Эти знания помогут тебе сразу узнавать RSA по двум числам n и e. В задачах ты сможешь факторизовать слабое n, применить Wiener или Hastad, восстановить сообщение по нескольким шифротекстам — и достать флаг за минуты.
Атаки на протоколы шифрования
Протоколы шифрования — это правила, по которым компьютеры договариваются, как защищать данные при передаче по интернету. Самый известный — TLS (он же SSL в старых версиях). В категории crypto и web на CTF атаки на эти протоколы встречаются очень часто: флаг прячут в перехваченном трафике, сертификате или уязвимом соединении. Новичку важно понять, где TLS ломается, потому что это одна из самых реальных угроз в интернете и классика соревнований. Знание поможет тебе распознавать слабые версии TLS, ошибки в настройках и неправильное использование шифров, чтобы расшифровать данные или подделать соединение.
Словарь терминов
TLS
Современный протокол шифрования соединения (бывший SSL)
Padding oracle attack
Атака, когда ошибка расшифровки выдаёт информацию о тексте
POODLE
Атака на SSL 3.0 через padding в режиме CBC
Lucky Thirteen
Атака на TLS через время обработки padding
Bleichenbacher
Атака на RSA с PKCS#1 v1.5 padding
BEAST
Атака на TLS 1.0/1.1 в режиме CBC
CRIME
Атака через сжатие данных в TLS
BREACH
Атака через сжатие HTTP-ответов
DROWN
Атака на старые версии SSL через современный TLS
Logjam
Атака на слабые параметры Diffie-Hellman
FREAK
Атака на downgrade до слабого экспорта шифрования
Downgrade attack
Заставляем использовать старую слабую версию протокола
ECB
Режим шифра, где каждый блок независим (очень слабый)
CTR nonce reuse
Повтор одного и того же nonce в режиме CTR — шифр ломается
Padding oracle attacks (POODLE, Lucky Thirteen, Bleichenbacher)
Padding — это набивка в конце сообщения, чтобы длина была кратна размеру блока шифра (например 16 байт для AES). При расшифровке сервер проверяет padding и может выдать ошибку, если он неправильный.
Padding oracle — когда сервер разными ответами (или временем) выдаёт, правильный padding или нет. По этим ответам можно восстановить сообщение поблочно.
POODLE — атака на SSL 3.0: заставляешь браузер использовать SSL 3.0 и по padding ошибкам расшифровываешь куки или пароли.
Lucky Thirteen — атака на TLS 1.1/1.2: по времени обработки padding угадываешь биты сообщения.
Bleichenbacher — атака на RSA с PKCS#1 v1.5: сервер выдаёт разные ошибки при расшифровке — по ним восстанавливаешь сообщение.
В CTF padding oracle — классика для задач на TLS и RSA. Если сервер отвечает "bad padding" или меняет время — это oracle.
На практике: собираешь запросы, меняешь последний байт — по ответам сервера восстанавливаешь plaintext за 256 запросов на блок.
BEAST, CRIME, BREACH, DROWN, Logjam, FREAK
BEAST — атака на TLS 1.0/1.1 в режиме CBC: по предсказуемому IV угадываешь первые байты блока.
CRIME — атака через сжатие в TLS: сжимаешь куки с известным текстом — по размеру ответа угадываешь куки.
BREACH — похожая атака, но через сжатие HTTP-ответов: подмешиваешь текст в запрос и по размеру ответа угадываешь секрет.
DROWN — атака на старые версии SSL: если сервер поддерживает SSLv2 — можно взломать современный TLS.
Logjam — атака на слабые параметры Diffie-Hellman: заставляешь использовать слабый DH и факторизуешь ключ.
FREAK — downgrade до экспортного шифрования (слабые ключи 512 бит) и факторизация.
В CTF эти атаки дают в задачах на перехват трафика или downgrade. Если трафик в TLS 1.0/1.1 с CBC — это BEAST; если сжатие включено — CRIME/BREACH.
На практике: если видишь TLS 1.0 — пробуешь BEAST; если сжатие — подмешиваешь текст и смотришь размер ответа.
TLS handshake attacks, downgrade attacks
TLS handshake — "рукопожатие": клиент и сервер договариваются о версии TLS, шифрах, обмениваются ключами.
Downgrade attack — заставляешь использовать старую слабую версию TLS (например TLS 1.0 вместо 1.3).
Атаки на handshake: подмена шифров, подмена сертификатов, атака на Diffie-Hellman.
В CTF downgrade — частая тема: если сервер поддерживает старые версии — можно заставить использовать слабый шифр и взломать соединение.
На практике: если видишь, что сервер отвечает на TLS 1.0 — это шанс на downgrade и атаку типа BEAST или POODLE.
Protocol misuse (ECB for images, CTR nonce reuse)
ECB — режим шифра, где каждый блок независим. Если шифровать картинку в ECB — одинаковые блоки дают одинаковый шифротекст, и картинка видна как мозаика.
CTR nonce reuse — в режиме CTR nonce + счётчик должны быть уникальными. Если nonce повторяется — шифр становится XOR с одним потоком, и два сообщения можно XOR'ить, чтобы получить разницу.
В CTF protocol misuse — классика: картинка в ECB показывает флаг; два шифротекста с одним nonce — XOR'ишь и получаешь plaintext.
На практике: если видишь зашифрованную картинку с паттернами — это ECB, расшифровываешь по блокам; если два шифротекста — XOR'ишь и видишь разницу.
Итог
Атаки на протоколы шифрования — это ошибки в TLS и способах использования шифров. В crypto и web CTF это очень частая тема: флаг прячут в трафике, куках или зашифрованных данных с ошибкой.
Главное запомнить: старые версии TLS (1.0/1.1) и SSL 3.0 уязвимы; padding oracle ломает CBC и RSA; сжатие опасно; ECB показывает паттерны; повтор nonce в CTR ломает шифр.
Ключевые слова/термины выучить: TLS, padding oracle attack, POODLE, Lucky Thirteen, Bleichenbacher, BEAST, CRIME, BREACH, DROWN, Logjam, FREAK, downgrade attack, ECB, CTR nonce reuse.
Эти знания помогут тебе распознавать слабые версии TLS по заголовкам и пробовать downgrade. В задачах ты сможешь восстанавливать куки через padding oracle, ломать CTR повтором nonce или читать зашифрованные картинки в ECB — и доставать флаг из трафика или подменять данные.
Атаки на RNG и слабые генераторы случайных чисел
RNG — это генератор случайных чисел, который должен выдавать непредсказуемые значения для ключей, nonce и других важных вещей. Слабый RNG — когда числа предсказуемы или повторяются. В категории crypto на CTF это одна из самых частых тем: флаг прячут в "случайном" числе, которое на самом деле легко угадать. Новичку важно понять, почему блокчейн и программы не могут делать по-настоящему случайные числа и как это ломать. Знание поможет тебе предсказывать "случайные" значения, восстанавливать ключи и получать флаг там, где другие застревают.
Словарь терминов
RNG
Генератор случайных чисел
Predictable seed
Начальное значение, от которого зависят все числа
Linear congruential generator
Простой RNG, где каждое число считается по формуле
LCG
Сокращение от linear congruential generator
Mersenne Twister
Популярный RNG, который используется во многих языках
Dual_EC_DRBG
Генератор случайных чисел с встроенной лазейкой
Debian OpenSSL RNG bug
Ошибка в Debian, из-за которой ключи были очень предсказуемы
Weak keys in DSA/ECDSA
Слабые ключи подписи из-за плохого RNG
Nonce reuse
Когда одно и то же случайное число используется дважды
Predictable seeds, linear congruential generators
Seed — это начальное число, от которого стартует генератор. Если seed известен или предсказуем — все последующие числа тоже предсказуемы.
Linear congruential generator (LCG) — самый простой RNG. Формула выглядит так: next = (a × current + c) mod m. Где a, c, m — константы.
LCG очень слабый: зная несколько чисел — можно вычислить a, c, m и предсказать всё вперёд и назад.
В CTF LCG — классика для задач на предсказание. Часто дают несколько "случайных" чисел и просят следующее.
На практике: видишь последовательность чисел — пробуешь LCG, решаешь систему уравнений и предсказываешь флаг.
LCG cracking, Mersenne Twister reverse engineering
LCG cracking — это когда из 3–6 последовательных чисел находишь параметры и предсказываешь весь поток.
Mersenne Twister — более сложный RNG, используется в Python random, PHP mt_rand и многих других. Он генерирует очень длинную последовательность (2^19937 - 1).
Но он тоже ломается: зная 624 последовательных числа — можно восстановить внутреннее состояние и предсказать всё будущее.
В CTF Mersenne Twister — частая задача. Дают 624 числа или около того — просят следующее или восстановить seed.
На практике: собираешь 624 значения random() — вставляешь в скрипт для untempering — получаешь состояние и предсказываешь флаг.
Dual_EC_DRBG backdoor, Debian OpenSSL RNG bug
Dual_EC_DRBG — генератор случайных чисел от NSA. В нём заложена лазейка: если знать секретные параметры — можно предсказать все числа.
В 2007 году стало известно, что NSA могла читать трафик тех, кто использовал Dual_EC_DRBG.
Debian OpenSSL RNG bug — ошибка в 2006–2008 годах: в Debian убрали одну строчку кода, и RNG выдавал всего 32 767 возможных ключей вместо миллиардов.
В CTF эти исторические баги дают в задачах "найди приватный ключ" или "восстанови сессию".
На практике: если задача на старый Debian или Dual_EC — перебираешь 32k ключей или используешь backdoor параметры.
Weak keys in DSA/ECDSA, nonce reuse
DSA/ECDSA — алгоритмы подписи. Они используют случайное число nonce для каждой подписи.
Если nonce повторяется (reuse) — из двух подписей можно вычислить приватный ключ.
Weak keys — когда ключ сгенерирован слабым RNG, и его легко угадать или перебрать.
В CTF nonce reuse — одна из самых простых атак на ECDSA. Дают две подписи с одним nonce — решаешь уравнение и находишь ключ.
На практике: видишь две подписи с одинаковым r — это reuse, решаешь уравнение и подписываешь что угодно.
Итог
Атаки на RNG — это когда "случайные" числа предсказуемы из-за слабого генератора или ошибки. В crypto CTF это очень частая тема: флаг прячут в "случайном" числе, ключе или подписи.
Главное запомнить: seed и nonce должны быть уникальными и по-настоящему случайными; LCG и Mersenne Twister ломаются по нескольким значениям; nonce reuse в ECDSA даёт приватный ключ.
Ключевые слова/термины выучить: RNG, predictable seed, linear congruential generator, LCG, Mersenne Twister, Dual_EC_DRBG backdoor, Debian OpenSSL RNG bug, weak keys in DSA/ECDSA, nonce reuse.
Эти знания помогут тебе предсказывать "случайные" числа в лотереях, восстанавливать приватный ключ по двум подписям или перебирать слабые ключи. В задачах ты сможешь угадать seed LCG по нескольким числам, untemper Mersenne Twister или использовать nonce reuse для подписи от чужого имени — и достать флаг за минуты.
Эллиптические кривые (ECC)
Эллиптические кривые — это особый вид математики, который используется для создания очень надёжных ключей шифрования. Вместо больших чисел, как в RSA, здесь работают с точками на специальной кривой. В категории crypto на CTF ECC встречается всё чаще, особенно в задачах на подписи и обмен ключами. Новичку важно понять, как ECC работает и где оно ломается, потому что это один из самых современных и популярных способов защиты в блокчейне и протоколах. Знание поможет тебе находить слабые места в подписях и обмене ключами, чтобы восстановить приватный ключ или подделать подпись и достать флаг.
Словарь терминов
Эллиптическая кривая
Специальная математическая кривая, на которой лежат точки
ECC
Криптография на основе эллиптических кривых
ECDSA
Алгоритм цифровой подписи на основе ECC
Nonce
Случайное число в каждой подписи, должно быть уникальным
Nonce bias
Когда nonce не совсем случайное и можно его предсказать
Lattice attack
Математическая атака с помощью решёток для поиска nonce
Ladder leak
Утечка информации через время выполнения операций
Ladder reuse
Повторное использование одной и той же последовательности
ECDH
Способ обмена секретным ключом между двумя сторонами
Invalid curve attack
Атака, когда используют кривую с другими параметрами
Twist attack
Атака на "перевёрнутую" кривую с похожими свойствами
secp256k1
Кривая, которую использует Bitcoin и Ethereum
secp256r1
Кривая, которую используют многие протоколы (NIST P-256)
Small subgroup attack
Атака, когда точка лежит в маленькой подгруппе
Invalid point attack
Атака, когда точка не лежит на кривой
ECDSA (nonce bias, lattice attacks, ladder leak, ladder reuse)
ECDSA — это алгоритм подписи, который используется в Bitcoin, Ethereum и многих протоколах. Ты берёшь приватный ключ и случайное число (nonce), считаешь подпись, и любой может проверить её публичным ключом.
Nonce bias — когда nonce не совсем случайное. Например, оно всегда меньше какого-то числа или имеет предсказуемый паттерн. Тогда из нескольких подписей можно вычислить приватный ключ.
Lattice attacks — математический способ найти nonce, если он слабый. Ты собираешь несколько подписей и решаешь систему уравнений с помощью решёток.
Ladder leak — утечка информации через время выполнения. Если операция "подъём по лестнице" (scalar multiplication) занимает разное время в зависимости от битов ключа — можно угадать биты.
Ladder reuse — когда nonce повторяется в двух подписях. Тогда приватный ключ восстанавливается за секунды.
В CTF ECDSA — одна из самых частых тем. Если дают несколько подписей с одним ключом — это почти всегда nonce bias или reuse.
На практике: собираешь 2–100 подписей, проверяешь nonce на повтор или bias — если да, восстанавливаешь ключ и подписываешь что угодно.
ECDH, invalid curve attacks, twist attacks
ECDH — это способ двух людей получить общий секретный ключ без передачи его по сети. Каждый берёт свой приватный ключ, умножает на публичный ключ другого — получается один и тот же результат.
Invalid curve attack — когда атакующий отправляет точку, которая не лежит на кривой, но лежит на похожей кривой с маленьким порядком. Контракт считает, что это нормальная точка, и выдаёт слабый ключ.
Twist attack — похожая атака, но на "перевёрнутую" кривую (twist), которая имеет те же параметры, но другой порядок. Атакующий заставляет контракт работать с twist-кривой.
В CTF эти атаки дают в задачах на обмен ключами или протоколы. Если сервер принимает любую точку без проверки — это invalid curve или twist.
На практике: если видишь ECDH и сервер не проверяет, лежит ли точка на кривой — отправляешь invalid point и получаешь слабый общий секрет.
Curve parameters (secp256k1, secp256r1, Brainpool, Curve25519)
secp256k1 — кривая, которую использует Bitcoin и Ethereum. Она считается безопасной, но имеет особые параметры, которые иногда позволяют атаки.
secp256r1 (NIST P-256) — стандартная кривая от NIST, используется в TLS и многих протоколах.
Brainpool — европейские кривые, сделаны "честно", без подозрительных констант.
Curve25519 — кривая для ECDH, очень быстрая и безопасная, используется в Signal, WhatsApp, SSH.
В CTF часто дают задачу с нестандартной кривой или слабым параметром. Если параметры кривой подозрительные или маленькие — это шанс на атаку.
На практике: если видишь маленькую кривую или кривую с подозрительными константами — проверяешь на small subgroup или invalid curve.
Small subgroup attacks, invalid point attacks
Small subgroup attack — когда точка лежит в маленькой подгруппе кривой. Тогда порядок точки маленький, и можно перебрать все возможные значения.
Invalid point attack — когда точка вообще не лежит на кривой, но контракт её принимает и делает с ней вычисления. Это даёт слабый ключ или утечку информации.
В CTF эти атаки — классика для ECDH и ECDSA. Если сервер не проверяет точку на кривой — отправляешь invalid point и получаешь слабый результат.
На практике: генерируешь точку с маленьким порядком или вне кривой — отправляешь в ECDH или подпись — получаешь слабый ключ или утечку.
Итог
Эллиптические кривые (ECC) — современная замена RSA для подписей и обмена ключами. В crypto CTF это очень частая тема: флаг прячут в приватном ключе или общем секрете, который можно достать через слабый nonce или точку.
Главное запомнить: nonce в ECDSA должен быть уникальным и случайным; точка должна лежать на кривой; кривые secp256k1 и Curve25519 — самые популярные и безопасные, но слабые параметры ломаются.
Ключевые слова/термины выучить: ECC, ECDSA, nonce bias, lattice attack, ladder leak, ladder reuse, ECDH, invalid curve attack, twist attack, secp256k1, secp256r1, Brainpool, Curve25519, small subgroup attack, invalid point attack.
Эти знания помогут тебе распознавать ECDSA по подписям (r, s) и ECDH по точкам на кривой. В задачах ты сможешь найти приватный ключ через nonce bias или lattice, обмануть ECDH invalid point или twist, и достать флаг, восстановив секрет или подпись.
Хэш-функции и MAC
Хэш-функция — это как мясорубка для данных: берёт любой текст, файл или сообщение и выдаёт короткую строку фиксированной длины (хэш). Изменится хоть один бит — хэш будет совсем другой. В категории crypto на CTF хэши встречаются почти в каждой задаче: флаг прячут в хэше, используют для проверки целостности или подписи. Новичку важно понять, как хэши работают и где они ломаются, потому что это основа защиты паролей, подписей и блокчейна. Знание поможет тебе находить слабые хэши, подделывать сообщения или восстанавливать оригинал, чтобы достать флаг.
Словарь терминов
Хэш-функция
Превращает любые данные в короткую строку фиксированной длины
MD5
Старый хэш, 128 бит, сейчас легко ломается
SHA-1
Хэш 160 бит, тоже устарел и ломается на коллизиях
SHA-256
Современный хэш 256 бит, пока считается безопасным
SHA-3
Совсем новый хэш, другой принцип работы
Length extension attack
Атака, когда к хэшу можно добавить данные без знания оригинала
HMAC
Хэш с секретным ключом для проверки подлинности
Poly1305
Быстрый MAC на основе хэша, используется с ChaCha
CBC-MAC
MAC на основе блочного шифра в режиме CBC
Коллизия хэша
Два разных сообщения с одинаковым хэшем
Preimage attack
Найти сообщение по его хэшу
Second preimage attack
Найти другое сообщение с тем же хэшем
Merkle tree
Дерево хэшей для проверки больших данных
Hash-based signature
Подпись, которая использует только хэши (без RSA/ECC)
MD5, SHA-1, SHA-256/3, length extension attacks
MD5 — старый хэш, выдаёт 128-битную строку (32 символа в hex). Его использовали везде: пароли, чек-суммы, сертификаты. Сейчас MD5 легко ломается — можно найти два разных файла с одинаковым хэшем (коллизия) за секунды.
SHA-1 — чуть лучше, 160 бит. Но тоже сломан: в 2017 году нашли реальную коллизию, а сейчас это делается на обычном компьютере.
SHA-256 — современный стандарт, 256 бит. Пока считается безопасным, используется в Bitcoin, TLS, подписях.
SHA-3 — ещё новее, построен на другом принципе (Keccak). Самый устойчивый к атакам на коллизии.
Length extension attack — хитрая атака на MD5 и SHA-1/256. Если знаешь h(secret + message), можно вычислить h(secret + message + append) без знания secret. Это ломает многие системы, где хэш используется как подпись.
В CTF MD5 и SHA-1 — классика: флаг зашифрован в MD5, или нужно подделать сообщение с length extension.
На практике: если видишь MD5 или SHA-1 — ищи коллизию или length extension; если SHA-256 — проверяй, можно ли расширить хэш.
HMAC, poly1305, CBC-MAC
HMAC — это хэш с секретным ключом. Берёшь хэш-функцию (SHA-256), добавляешь ключ два раза и считаешь. Получается MAC — код аутентификации сообщения. Если ключ секретный, никто не может подделать HMAC.
Poly1305 — очень быстрый MAC, работает вместе с ChaCha20. Используется в современных протоколах (TLS 1.3, WireGuard).
CBC-MAC — MAC на основе блочного шифра (AES). Сообщение шифруется в режиме CBC, последний блок — это MAC.
В CTF HMAC часто ломается, если ключ слабый или длина сообщения не проверяется. Poly1305 и CBC-MAC дают в задачах на подделку сообщений.
На практике: если видишь HMAC-SHA256 — проверяй, можно ли подобрать ключ или использовать length extension; если CBC-MAC — ищи одинаковые блоки.
Hash collisions, preimage/second preimage attacks
Коллизия — два разных сообщения с одинаковым хэшем. Для MD5 и SHA-1 коллизии находят легко.
Preimage attack — по хэшу найти исходное сообщение. Для сильных хэшей (SHA-256) это почти невозможно.
Second preimage — по сообщению найти другое сообщение с тем же хэшем. Тоже очень сложно для хороших хэшей.
В CTF коллизии — классика для MD5/SHA-1: нужно подменить файл или сообщение, чтобы хэш остался тем же.
На практике: если задача требует одинаковый хэш для двух файлов — ищешь коллизию MD5 или SHA-1.
Merkle trees, hash-based signatures
Merkle tree — дерево хэшей. Листья — хэши данных, каждый узел — хэш от двух детей. Корень — один хэш всей структуры.
Используется в блокчейне (Bitcoin), git, доказательствах с нулевым разглашением.
Hash-based signatures — подписи, которые используют только хэши (без RSA или ECC). Пример: Lamport, XMSS, SPHINCS+.
В CTF Merkle tree дают в задачах на доказательства или подделку блоков. Hash-based signatures — в постквантовых задачах.
На практике: если видишь дерево хэшей — ищешь, можно ли подменить лист и обновить корень; в подписях — проверяешь, использован ли один и тот же хэш повторно.
Итог
Хэш-функции и MAC — это инструменты для проверки целостности и подлинности данных. В crypto CTF они встречаются везде: флаг в хэше, подпись, проверка файлов, блокчейн.
Главное запомнить: MD5 и SHA-1 сломаны на коллизии, SHA-256 пока держится, HMAC защищает от подделки, length extension ломает многие системы.
Ключевые слова/термины выучить: хэш-функция, MD5, SHA-1, SHA-256, SHA-3, length extension attack, HMAC, poly1305, CBC-MAC, коллизия, preimage attack, second preimage attack, Merkle tree, hash-based signature.
Эти знания помогут тебе распознавать слабые хэши (MD5/SHA-1) и подделывать сообщения через length extension. В задачах ты сможешь находить коллизии для подмены файлов, ломать HMAC без ключа или использовать Merkle tree для подделки доказательств — и доставать флаг через подмену данных или подпись.
Инструменты и библиотеки
Инструменты и библиотеки — это специальные программы и наборы готовых функций, которые помогают быстро решать криптографические задачи в CTF. Без них даже простые вычисления занимают часы, а с ними — минуты. В категории crypto эти инструменты встречаются практически в каждой задаче: они нужны для факторизации, расшифровки, подбора ключей и анализа подписей. Новичку важно знать хотя бы основные, потому что именно они позволяют переходить от теории к практике. Знание поможет тебе не тратить время на ручные расчёты, а сосредоточиться на поиске уязвимости и получении флага.
Словарь терминов
SageMath
Программа для математики, идеальна для крипто-расчётов
PwnTools
Библиотека Python для написания эксплойтов и крипто-скриптов
RsaCtfTool
Готовый инструмент для всех известных атак на RSA
CryptoAttacks
Набор скриптов для стандартных крипто-атак
CyberChef
Онлайн-инструмент для кодировок, шифров и анализа
factordb
Онлайн-база, где хранятся уже разложенные большие числа
OpenSSL
Программа для работы с сертификатами, ключами и шифрами
PyCryptodome
Библиотека Python для шифрования и крипто-алгоритмов
cryptography.io
Современная Python-библиотека для криптографии
Z3
Инструмент для решения логических и математических уравнений
angr
Фреймворк для анализа бинарников и symbolic execution
Symbolic execution
Способ выполнения программы с "символическими" значениями
SageMath, PwnTools, RsaCtfTool, CryptoAttacks
SageMath — это как супер-калькулятор для крипто. Он умеет факторизовать числа, работать с эллиптическими кривыми, решать уравнения в модульной арифметике и многое другое. В CTF SageMath используют для всех сложных математических задач.
PwnTools — библиотека Python, которая помогает писать скрипты для CTF. Она упрощает работу с сетью, байтами, RSA, подписями и многим другим. Ты пишешь короткий код — и сразу получаешь результат.
RsaCtfTool — готовый инструмент специально для RSA. Он пробует все известные атаки: Wiener, Hastad, Boneh-Durfee, common modulus и другие. Достаточно вставить n и e — он сам найдёт приватный ключ, если тот слабый.
CryptoAttacks — набор скриптов для разных атак: RSA, ECDSA, LCG, Mersenne Twister и т.д. Часто используется как шпаргалка.
В CTF эти инструменты — основа. Если видишь RSA — сразу запускаешь RsaCtfTool; если нужно решить уравнение — открываешь SageMath; если пишешь эксплойт — используешь PwnTools.
На практике: получил n и e — вставляешь в RsaCtfTool, получаешь d и расшифровываешь флаг; нужно предсказать LCG — пишешь 5 строк в PwnTools и получаешь следующее число.
CyberChef, factordb, ctf.crypto.attacks
CyberChef — это онлайн-инструмент, где ты перетаскиваешь блоки операций: base64 decode, XOR, hex to text и т.д. Он помогает быстро попробовать разные кодировки и шифры.
factordb — сайт, где хранятся уже разложенные на множители большие числа. Если n из RSA уже есть в базе — ты сразу получаешь p и q.
ctf.crypto.attacks — коллекция скриптов на GitHub для самых разных атак: RSA, ECDSA, хэши, RNG и другие. Это как шпаргалка со всеми готовыми решениями.
В CTF CyberChef используют для быстрого декодирования флага, factordb — для проверки n, ctf.crypto.attacks — когда нужна конкретная атака.
На практике: видишь длинную строку — вставляешь в CyberChef и пробуешь разные декодирования; n большое — проверяешь на factordb; нужна атака на ECDSA — ищешь скрипт в ctf.crypto.attacks.
OpenSSL, PyCryptodome, cryptography.io
OpenSSL — это программа и библиотека для работы с сертификатами, ключами, шифрованием и подписями. Можно генерировать ключи, шифровать файлы, проверять подписи.
PyCryptodome — библиотека Python, которая реализует все популярные шифры: AES, RSA, ECDSA, хэши и многое другое. Очень удобна для скриптов.
cryptography.io — более современная и безопасная Python-библиотека. Она проще в использовании и лучше защищена от ошибок.
В CTF эти библиотеки используют для генерации ключей, проверки подписей или расшифровки. OpenSSL — для работы с сертификатами, PyCryptodome/cryptography — для скриптов.
На практике: нужно проверить подпись — берёшь cryptography и пишешь 5 строк кода; работаешь с сертификатом — используешь OpenSSL.
Z3, angr для symbolic execution in crypto
Z3 — это решатель уравнений. Он берёт систему условий и ищет значения переменных, которые их выполняют. В crypto используют для поиска nonce, ключей или сообщений.
angr — фреймворк для анализа бинарников. Symbolic execution — это когда программа выполняется не с конкретными числами, а с символами, и Z3 ищет, какие значения приводят к нужному пути.
В CTF Z3 используют для решения систем из ECDSA или RSA, angr — для анализа бинарных крипто-библиотек или VM.
На практике: получил систему уравнений из подписей — пишешь их в Z3 и получаешь nonce или ключ; бинарник шифрует флаг — запускаешь angr и находишь ввод, который даёт флаг.
Итог
Инструменты и библиотеки — это помощники, которые делают крипто-задачи в десятки раз проще и быстрее. В crypto CTF без них почти невозможно решать задачи на RSA, ECDSA, RNG или большие вычисления.
Главное запомнить: SageMath и PwnTools — для математики и скриптов; Slither и Mythril — для поиска ошибок в коде; CyberChef и factordb — для быстрого анализа; OpenSSL и PyCryptodome — для шифрования; Z3 и angr — для сложных уравнений и бинарников.
Ключевые слова/термины выучить: SageMath, PwnTools, RsaCtfTool, CryptoAttacks, CyberChef, factordb, OpenSSL, PyCryptodome, cryptography.io, Z3, angr, symbolic execution.
Эти знания помогут тебе не тратить часы на ручные расчёты: вставляешь n в RsaCtfTool — получаешь d; пишешь 5 строк в PwnTools — предсказываешь LCG; запускаешь Z3 на уравнениях из подписей — получаешь nonce. В задачах ты сможешь за минуты факторизовать n, найти приватный ключ или сломать подпись — и достать флаг без лишних усилий.
Классическая симметричная криптография
Симметричная криптография — это способ зашифровать сообщение так, чтобы открыть его можно было только одним и тем же ключом. Как замок с одним ключом: и запереть, и открыть — одним и тем же. В категории crypto на CTF эта тема встречается в 70% задач: флаг зашифрован простым алгоритмом, и нужно его расшифровать или найти слабое место. Новичку важно понять основные шифры и их ошибки, потому что это самые частые задания. Знание поможет тебе быстро узнавать алгоритм по зашифрованному тексту и применять стандартные атаки, чтобы достать флаг.
Словарь терминов
Симметричная криптография
Шифрование, где один ключ и для шифрования, и для расшифровки
AES
Современный сильный шифр, использует 128/192/256-битный ключ
ECB
Режим AES, где каждый блок шифруется отдельно (слабый)
CBC
Режим AES, где каждый блок зависит от предыдущего
CTR
Режим AES как потоковый шифр, nonce + счётчик
GCM
Режим AES с встроенной проверкой целостности
Padding oracle
Атака, когда ошибка расшифровки выдаёт информацию о plaintext
DES
Старый слабый 56-битный шифр
3DES
DES, применённый три раза
Blowfish
Потоковый шифр с переменным размером ключа
RC4
Популярный потоковый шифр, теперь считается слабым
Block cipher
Шифр, который работает блоками (обычно 16 байт)
PKCS#7
Стандарт добавления байтов в конец, чтобы длина была кратна блоку
Bit flipping
Изменение битов в шифротексте, чтобы изменить открытый текст
Length extension
Атака на хэш, когда можно добавить данные к сообщению
AES (режимы ECB, CBC, CTR, GCM, padding oracle attacks)
AES — это самый популярный современный шифр. Он берёт ключ (16, 24 или 32 байта) и превращает каждый блок текста (16 байт) в шифротекст. Ключ проходит через 10–14 раундов замен и перестановок.
Режимы AES определяют, как шифровать большие тексты:
ECB — каждый 16-байтовый блок шифруется отдельно. Плюс: простой. Минус: одинаковые блоки дают одинаковый шифротекст — картинка выглядит как мозаика.
CBC — каждый блок XOR'ится с предыдущим шифроблоком перед шифрованием. Нужен IV (случайные 16 байт в начале).
CTR — превращает AES в потоковый шифр: nonce + счётчик шифруется, результат XOR'ится с текстом.
GCM — AES в режиме CTR + встроенная проверка (MAC), чтобы убедиться, что сообщение не изменено.
В CTF AES встречается везде: флаг зашифрован AES-ECB/CBC. ECB легко угадать по паттернам, CBC уязвим к padding oracle, CTR — к повтору nonce.
На практике: если видишь повторяющиеся блоки — это ECB, расшифруй по образцу; если ошибка при расшифровке выдаёт длину padding — делай padding oracle атаку.
DES/3DES, Blowfish, RC4 (потоковые шифры)
DES — старый шифр 1970-х. Ключ 64 бита (56 эффективных), блоки 64 бита. Теперь ломается brute-force за секунды.
3DES — DES три раза подряд. Безопаснее DES, но всё равно медленный и устаревший.
Blowfish — потоковый шифр с ключом до 448 бит. Использовался в старых системах.
RC4 — самый популярный потоковый шифр. Генерирует псевдослучайный поток байтов, XOR'ит с текстом. Слабости: первые байты предсказуемы, повторяющиеся ключи ломаются.
В CTF эти шифры дают в задачах "найди ключ" или "восстанови флаг". DES/3DES ломаются factordb или rainbow tables, RC4 — bias анализом первых байтов.
На практике: если видишь DES — ищи слабый ключ (factordb); RC4 — бери первые 256 байт и ищи bias в первых байтах.
Block cipher padding (PKCS#7, ANSI X.923, zero padding)
Блоковый шифр работает только с блоками кратными размеру (AES — 16 байт). Если текст короче — добавляют padding (набивку).
PKCS#7 — самый популярный: добавляют N байт со значением N (для 5 байт набивки — 5 байт со значением 0x05).
ANSI X.923 — набивка только в последних байтах, остальные 0x00.
Zero padding — просто нули в конце.
При расшифровке padding проверяется: если неверный — ошибка.
В CTF padding oracle — классика: сервер выдаёт ошибку при неверном padding, и по этим ошибкам восстанавливаешь текст поблочно.
На практике: если сервер говорит "padding error" — собираешь oracle и расшифровываешь весь текст за 256 запросов на блок.
Bit flipping, padding oracle, length extension
Bit flipping — изменение битов в шифротексте. В ECB/CBC можно точно изменить символы в открытом тексте, зная, как XOR работает.
Padding oracle — расширенная атака: по ошибкам padding восстанавливаешь весь текст, даже не зная ключ.
Length extension — атака на хэш (не шифр): зная h(secret + message) можно вычислить h(secret + message + append без знания secret.
В CTF bit flipping — для изменения параметров в запросах, padding oracle — для расшифровки файлов, length extension — для подделки MAC.
На практике: в CBC меняешь байт в шифротексте на нужный — в открытом тексте меняется предсказуемо; используй для смены логина/пароля.
Итог
Классическая симметричная криптография — это AES, DES, RC4 и их режимы. В crypto CTF это основа: 70% задач про расшифровку или поиск слабости в режиме/padding.
Главное запомнить: AES-ECB слаб из-за паттернов, CBC уязвим к padding oracle, RC4 ломается bias'ом, всегда проверяй padding при атаке.
Ключевые слова/термины выучить: AES, ECB, CBC, CTR, GCM, padding oracle, DES, 3DES, Blowfish, RC4, PKCS#7, bit flipping, length extension.
Эти знания помогут тебе угадывать шифр по виду текста (ECB — мозаика), восстанавливать флаг через padding oracle (256 запросов на блок) или ломать RC4 bias'ом первых байтов. В задачах это часто даёт флаг за 10–30 минут работы.
Кодировки и слабые реализации
Кодировки — это способы превратить данные (текст, числа, файлы) в другую форму, чтобы их можно было безопасно передавать или хранить. Слабые реализации — это когда программисты используют эти кодировки или случайные числа неправильно, и их легко сломать. В категории crypto на CTF эта тема встречается очень часто: флаг спрятан в закодированном виде или зашифрован с ошибкой. Новичку важно понять, как выглядят популярные кодировки и где они ломаются, потому что это самые простые задачи для начала. Знание поможет тебе быстро узнавать кодировку по виду строки и применять стандартные атаки, чтобы достать флаг за 5–20 минут.
Словарь терминов
Кодировка
Способ превратить данные в другую форму (например текст в символы)
Base64
Кодировка, превращает байты в буквы, цифры и +/=
Hex
Шестнадцатеричная кодировка (0-9, A-F)
URL encoding
Кодировка для адресов: пробел → %20, русский текст → %XX%XX
Padding oracle
Атака, когда ошибка расшифровки выдаёт информацию о тексте
POODLE
Атака на SSL 3.0 через padding в CBC
Lucky Thirteen
Атака на TLS через время обработки padding
Bleichenbacher
Атака на RSA с PKCS#1 v1.5 padding
Format string vulnerability
Ошибка, когда программа выводит данные по формату строки
Weak random number generation
Когда случайные числа легко предсказать
Java SecureRandom
Генератор случайных чисел в Java (иногда слабый)
PHP mt_rand
Функция случайных чисел в PHP, предсказуемая
Base64, hex, URL encoding, custom base encodings
Base64 — это когда байты превращают в текст из 64 символов (A-Z, a-z, 0-9, +, / и =). Используется везде: картинки в HTML, токены, почтовые вложения. Выглядит как строка с = в конце.
Hex — шестнадцатеричная кодировка: каждый байт — два символа (0-9, A-F). Выглядит как строка из цифр и букв A-F.
URL encoding — когда в адресе запрещённые символы заменяют на %XX (например пробел → %20, кириллица → %D0%9F).
Custom base encodings — когда автор задачи придумывает свою кодировку: base36, base91, base122 и т.д.
В CTF кодировки — самая частая вещь для начала. Флаг почти всегда закодирован в base64, hex или URL. Иногда несколько слоёв: base64 внутри hex внутри base64.
На практике: видишь строку с = в конце — это base64; с A-F — hex; с %XX — URL encoding. Декодируешь по очереди — получаешь флаг.
Padding oracle (POODLE, Lucky Thirteen, Bleichenbacher)
Padding oracle — это когда сервер говорит "неправильный padding" при расшифровке, и по этим ошибкам можно восстановить текст поблочно.
POODLE — атака на SSL 3.0: заставляешь сервер использовать SSL 3.0 и по padding ошибкам расшифровываешь трафик.
Lucky Thirteen — атака на TLS: по времени обработки padding угадываешь биты сообщения.
Bleichenbacher — атака на RSA с PKCS#1 v1.5 padding: сервер выдаёт ошибки при расшифровке — по ним восстанавливаешь сообщение.
В CTF padding oracle — классика для задач на CBC и RSA. Если сервер отвечает разными ошибками — это oracle.
На практике: собираешь запросы, где меняешь последний байт — по ответам сервера восстанавливаешь plaintext за 256 запросов на блок.
Format string vulnerabilities in crypto libs
Format string — это когда программа использует printf или sprintf с пользовательскими данными без проверки. Например printf(user_input) вместо printf("%s", user_input).
Если в строке есть %x, %s, %n — программа может читать память или писать в неё.
В крипто-библиотеках это может дать утечку ключа или перезапись важных данных.
В CTF format string — редкая, но эффектная уязвимость. Если видишь, что ввод попадает в printf — пробуешь %x для чтения стека или %n для записи.
На практике: отправляешь %x%x%x... — читаешь стек; %n — пишешь в память и меняешь значение.
Weak random number generation (Java SecureRandom, PHP mt_rand)
Слабая генерация случайных чисел — когда "случайные" числа легко предсказать.
Java SecureRandom иногда использует слабый seed — можно предсказать последовательность.
PHP mt_rand — Mersenne Twister, который ломается по нескольким значениям: зная 624 числа — предсказываешь все следующие.
В CTF слабый RNG — классика для задач на предсказание пароля, nonce или seed.
На практике: если задача выдаёт несколько "случайных" чисел — это mt_rand или SecureRandom, предсказываешь следующие и получаешь флаг.
Итог
Кодировки и слабые реализации — это когда данные прячут или шифруют неправильно, и их легко раскрыть. В crypto CTF это основа многих задач: флаг закодирован в base64/hex или зашифрован с ошибкой padding/RNG.
Главное запомнить: base64/hex/URL — просто декодируешь; padding oracle — восстанавливаешь текст по ошибкам; format string — читаешь/пишешь память; слабый RNG — предсказываешь числа.
Ключевые слова/термины выучить: кодировка, Base64, hex, URL encoding, padding oracle, POODLE, Lucky Thirteen, Bleichenbacher, format string vulnerability, weak random number generation, Java SecureRandom, PHP mt_rand.
Эти знания помогут тебе сразу узнавать base64 по = в конце и декодировать флаг. В задачах ты сможешь восстанавливать текст через padding oracle, предсказывать числа из mt_rand или ломать format string для чтения памяти — и доставать флаг за минуты.
Криптоанализ и решётки (lattice attacks)
Криптоанализ — это наука о том, как ломать шифры и находить слабые места в криптографии. Решётки (lattices) — это специальный математический инструмент, который помогает решать сложные задачи с числами и уравнениями. В категории crypto на CTF lattice attacks встречаются в самых интересных и сложных задачах: когда обычные методы не работают, а флаг спрятан в приватном ключе или nonce. Новичку важно понять основы, потому что это один из самых мощных способов ломать современные подписи (ECDSA, DSA). Знание решёток поможет тебе решать задачи, где нужно найти ключ по нескольким подписям или восстановить часть секретных данных.
Словарь терминов
Криптоанализ
Способы находить слабые места в шифрах и подписях
Решётка (lattice)
Набор точек в пространстве, как сетка координат
Lattice reduction
Упрощение решётки, чтобы найти короткие векторы
LLL
Алгоритм, который находит хорошие короткие векторы в решётке
BKZ
Более сильная версия LLL для сложных решёток
Coppersmith method
Способ находить маленькие решения уравнений с большими числами
Howgrave-Graham
Улучшение Coppersmith, чтобы работать с целыми числами
Hidden number problem
Задача: найти секретное число по его кусочкам и модулям
Partial key exposure
Когда известна часть битов приватного ключа
Biased nonce
Когда случайное число в подписи не совсем случайное
Coppersmith method, Howgrave-Graham
Coppersmith method — это способ найти маленькие решения уравнений вида f(x) ≡ 0 (mod N), где N большое, а x маленькое. Метод превращает задачу в поиск короткого вектора в решётке.
Howgrave-Graham — улучшение: он позволяет работать с целыми числами, а не только по модулю. Вместо модуля N строится решётка из коэффициентов полинома.
Вместе они решают задачи, где известна часть сообщения или ключа.
В CTF Coppersmith и Howgrave-Graham — классика для RSA и ECDSA. Если известна часть сообщения или nonce — строишь полином и ищешь короткий вектор.
На практике: если в RSA сообщение частично известно — используешь Coppersmith, чтобы найти остаток; если nonce частично известен — то же самое.
LLL/BKZ lattice reduction
LLL (Lenstra–Lenstra–Lovász) — алгоритм, который берёт решётку и находит в ней короткие векторы. Это как найти самый маленький шаг в сетке координат.
BKZ — более мощная версия LLL: она делает блоки и ищет ещё лучше короткие векторы, но работает медленнее.
Эти алгоритмы лежат в основе всех lattice-атак.
В CTF LLL/BKZ используют для Wiener, Boneh-Durfee, Coppersmith и атак на nonce bias. Если задача на подпись или RSA — почти всегда нужна решётка.
На практике: берёшь SageMath или fplll, строишь решётку из уравнений и запускаешь LLL или BKZ — получаешь короткий вектор, который даёт ключ или nonce.
Hidden number problem, partial key exposure
Hidden number problem — задача: есть секретное число x и несколько уравнений вида ai × x ≈ bi (mod N), где ≈ значит "примерно". Нужно найти x.
Partial key exposure — когда известна часть битов приватного ключа (например верхние 100 бит из 256).
Обе задачи решаются через решётки: строишь уравнения, делаешь решётку и находишь короткий вектор, который даёт недостающие биты.
В CTF это частая тема для ECDSA и RSA. Если дают несколько подписей с частично известным nonce или часть приватного ключа — это hidden number или partial exposure.
На практике: берёшь подписи, где nonce частично известен — строишь решётку и находишь полный nonce, потом ключ.
Attacks on DSA/ECDSA with biased nonces
DSA и ECDSA используют nonce k для каждой подписи. Если k не случайный, а имеет bias (например всегда чётное или меньше 2^128) — из нескольких подписей можно восстановить приватный ключ.
Атака через решётки: строишь уравнения из подписей и ищешь короткий вектор, который даёт bias в k.
В CTF biased nonces — одна из самых популярных тем в ECDSA. Дают 50–100 подписей — и ключ ломается за минуты.
На практике: видишь много подписей от одного ключа — проверяешь nonce на bias (например все меньше 2^160) — строишь решётку и получаешь приватный ключ.
Итог
Криптоанализ на решётках — это мощный способ ломать подписи и шифры, когда есть несколько уравнений или часть данных известна. В crypto CTF это ключ к сложным задачам на ECDSA, RSA и DSA.
Главное запомнить: решётки находят короткие векторы; Coppersmith и Howgrave-Graham решают уравнения с маленькими корнями; LLL/BKZ — основа всех атак; biased nonce в ECDSA ломается по 20–100 подписям.
Ключевые слова/термины выучить: криптоанализ, решётка, lattice reduction, LLL, BKZ, Coppersmith method, Howgrave-Graham, hidden number problem, partial key exposure, biased nonces.
Эти знания помогут тебе ломать ECDSA по нескольким подписям с biased nonce, находить приватный ключ RSA по части сообщения или восстанавливать nonce через решётку. В задачах ты сможешь построить решётку из уравнений, запустить LLL/BKZ и получить ключ или флаг за 10–60 минут работы.
Постквантовая криптография
Постквантовая криптография — это новые способы шифрования и подписей, которые останутся безопасными даже после появления квантовых компьютеров. Обычные алгоритмы (RSA, ECDSA) ломаются квантовыми компьютерами, а эти — нет. В категории crypto на CTF эта тема встречается всё чаще, особенно в задачах на новые стандарты и атаки на переходные алгоритмы. Новичку важно понять, почему старые шифры скоро устареют и какие новые пришли им на замену. Знание поможет тебе узнавать постквантовые алгоритмы в задачах и понимать, где они уже ломаются классическими методами.
Словарь терминов
Постквантовая криптография
Новые шифры, которые не ломаются квантовыми компьютерами
Квантовый компьютер
Машина, которая решает некоторые задачи намного быстрее обычных
Lattice-based
Криптография на основе математических решёток
NTRU
Один из первых постквантовых алгоритмов шифрования
Kyber
Новый стандарт шифрования от NIST
Dilithium
Новый стандарт цифровой подписи от NIST
Hash-based signatures
Подписи, которые используют только хэш-функции
SPHINCS+
Самая простая и надёжная постквантовая подпись
XMSS
Другая хэш-подпись, используется в некоторых проектах
Code-based
Криптография на основе теории кодов
McEliece
Очень старый и надёжный постквантовый алгоритм шифрования
SIDH
Суперсингулярная изогения Диффи-Хеллмана
SIKE
Улучшенная версия SIDH, но сломана в 2022 году
Lattice-based (NTRU, Kyber, Dilithium)
Lattice-based криптография — это когда безопасность держится на сложности поиска коротких векторов в решётке. Решётка — это как бесконечная сетка точек в пространстве, и найти самый короткий вектор очень трудно.
NTRU — один из первых таких алгоритмов. Он шифрует маленькие сообщения и использует полиномы и решётки. Пока держится, но иногда ломается на маленьких параметрах.
Kyber — победитель конкурса NIST на постквантовое шифрование. Он берёт решётку, добавляет шум и шифрует ключ. Очень быстрый и надёжный.
Dilithium — победитель на подписи. Тоже на решётках, но вместо шифрования создаёт подпись, которую любой может проверить.
В CTF lattice-based алгоритмы дают в задачах на новые стандарты или слабые параметры. Если параметры маленькие — можно попробовать классические lattice-атаки (LLL/BKZ).
На практике: если видишь Kyber или Dilithium с маленькими n или q — пробуешь lattice reduction, чтобы найти короткий вектор и сломать ключ.
Hash-based signatures (SPHINCS+, XMSS)
Hash-based signatures — это подписи, которые используют только хэш-функции (SHA-256, SHA-3). Нет никаких больших чисел или кривых — только хэши.
SPHINCS+ — самая простая и надёжная. Она создаёт огромную подпись (тысячи байт), но её нельзя сломать даже квантовым компьютером, если хэш сильный.
XMSS — другая hash-подпись. Она использует дерево хэшей (Merkle tree) и немного меньше размером.
Обе считаются постквантово безопасными, но в CTF их дают с ошибками: повтор nonce, слабый хэш или неправильная реализация.
На практике: если видишь подпись SPHINCS+ или XMSS — проверяй, не использовался ли один хэш повторно или слабый seed.
Code-based (McEliece)
Code-based криптография — это когда безопасность держится на сложности декодирования случайных кодов. McEliece — самый старый и надёжный постквантовый алгоритм шифрования.
Он шифрует сообщение добавлением случайных ошибок в кодовое слово. Расшифровать можно только если знать секретную матрицу.
McEliece считается очень надёжным против квантовых атак, но ключи огромные (сотни килобайт).
В CTF McEliece дают в задачах на большие ключи или слабые параметры. Если код маленький или ошибки мало — можно декодировать классическими методами.
На практике: если видишь McEliece с маленьким n или t — пробуешь классические атаки на коды (information set decoding).
SIDH/SIKE attacks (classic and post-quantum)
SIDH — это алгоритм обмена ключами на основе изогений суперсингулярных кривых. Он был кандидатом на постквантовый стандарт.
SIKE — его улучшенная версия. Оба сломаны в 2022 году классической атакой (не квантовой!).
Атака использует поиск коротких путей на графе изогений — это ломает обмен ключа за минуты на обычном компьютере.
В CTF SIDH/SIKE — классика: дают публичные ключи и просят восстановить общий секрет.
На практике: если видишь SIDH или SIKE — запускаешь классическую атаку на граф изогений и получаешь ключ.
Итог
Постквантовая криптография — это новые алгоритмы, которые защищают от квантовых компьютеров. В crypto CTF они появляются в задачах на новые стандарты и атаки на переходные системы.
Главное запомнить: lattice-based (Kyber, Dilithium) — самые перспективные; hash-based (SPHINCS+) — простые и надёжные; code-based (McEliece) — старые и огромные; SIDH/SIKE уже сломаны классически.
Ключевые слова/термины выучить: постквантовая криптография, lattice-based, NTRU, Kyber, Dilithium, hash-based signatures, SPHINCS+, XMSS, code-based, McEliece, SIDH, SIKE.
Эти знания помогут тебе узнавать новые алгоритмы в задачах и понимать, что Kyber/Dilithium пока держатся, а SIDH/SIKE ломаются обычным компьютером. В задачах ты сможешь атаковать слабые параметры Kyber через решётки, ломать SIDH графом изогений или проверять hash-подписи на повтор nonce — и доставать флаг через восстановление ключа или подделку подписи.