Crypto / криптография в CTF

Системы счисления

• Бинарная (2), восьмеричная (8), десятичная (10), шестнадцатеричная (16) — базовые для задач CTF/RI. Пример: 0xFF = 255 (10) = 377 (8) = 11111111 (2).
• Hex-пара = 1 байт (например, 41 → 'A'), 4 бита = 1 «ниббл». См. байт и nibble.
• Префиксы встречаются как 0x..., 0b..., 0o.... Подробно: int(radix) в Python.
• Конвертация: быстро через CyberChef/скрипты; подсказки — «ровные» длины, только 0/1, только [0–9A–F]. Для CLI: bc, format(), xxd.

Кодировки (это не шифрование!)

• Base64 (часто = или == на конце, алфавит [A–Za–z0–9+/]), Base64URL (символы - и _, паддинг = может отсутствовать).
• Base32 (алфавит A–Z2–7), Base58 (без похожих символов), Base85/Ascii85, Z85 — «плотные» кодировки.
• Hex, bin, URL-encoding (%20 → пробел), Quoted-Printable (=\r\n переносы).
• Текстовые кодировки: ASCII, UTF-8 (часто «битая» кириллица в условиях — сигнал к конверту, проверь также Windows-1251).

• Цезарь / ROT-N: сдвиг алфавита на N по модулю m. Узнаётся по «сдвинутым» частотам и сохранённой структуре биграмм. Лечится полным перебором N (обычно 0–25) и частотным анализом. Подробнее: Цезарь, ROT13, онлайн-помощники: CyberChef, dCode.
• Виженер: полиалфавитный с ключом-словом. Этапы: Касиски/IC → длина ключа → помодульная «цезарка» по столбцам. Варианты: Autokey, Beaufort, Gronsfeld (цифровой ключ). Инструменты: dCode, CyberChef.
• Атбаш, аффинный шифр: линейные преобразования по модулю m. Атбаш — отражение алфавита; аффинный: E(x) = (a·x + b) mod m, нужен обратимый a (gcd(a,m)=1). Взлом — перебор допустимых a,b + частоты/«cribs». Калькуляторы: dCode.
• Плейфер, Хилл: биграммные/матричные схемы. Плейфер — работа с диграммами по таблице 5×5; Хилл — линейная алгебра над Z_m (матрица должна быть обратима по mod m). Атаки: частотка биграмм/триграмм, известный открытый текст. Инструменты: Playfair, Hill на dCode.
• Транспозиции (колоночные, «забор»/Rail Fence, «скитала»): перестановки индексов без изменения частот букв. Признаки — естественные частоты сохраняются, но текст «ломан» по структуре. Смотри: перестановочный шифр, columnar, rail fence, scytale. Подход — подбирать длину/ключ по делителям длины текста, тестировать читаемость.
• «Календарные»/датовые: ключ — дата/цифровая последовательность (например, DDMMYYYY) для Виженера/Гронсфельда или номера столбцов в транспозиции. Проверяй даты из условия, релевантные события/форматы. По теме: Gronsfeld, Permutation cipher.
• OTP reuse: одноразовый блокнот с повторно использованным ключом → XOR двух шифртекстов даёт XOR открытых (уязвимость «many-time pad»). Дальше — «crib dragging». Читай: One-Time Pad, XOR, исторический кейс VENONA. Утилиты: CyberChef XOR.

• Симметричные: блочные (AES, DES) и поточные (ChaCha20). Ломают не сами алгоритмы, а режимы (ECB, CBC, CTR, GCM), паддинги, nonce/IV при повторе.
• Асимметричные: RSA, ElGamal, схемы на дискретном логарифме (DH/ECDH). Проблемы: плохие параметры (малые модули, ROCA), неверная проверка паддингов (Bleichenbacher), side-channel атаки.
• MAC/AEAD: HMAC, Poly1305, AES-GCM. Ломаются при повторе nonce, неправильной «склейке» аутентифицированных блоков или при неверной валидации тега (CCM vs GCM ошибки).
• Хэши/KDF: MD5, SHA-1, SHA-2, SHA-3. KDF: PBKDF2, bcrypt, scrypt, Argon2. Уязвимости: коллизии, length-extension, слабые параметры (мало итераций, низкая память).
• PRNG: Mersenne Twister, LCG, rand(). Ломаются из-за предсказуемости и возможности восстановить состояние. См. также: Dual_EC_DRBG как пример уязвимого стандартизированного ГПСЧ.

• Классический DH: выбираем большую простую p и генератор g. Алиса: A = g^a mod p, Боб: B = g^b mod p. Общий ключ: K = g^(ab) mod p. Подробнее: Wikipedia, RFC 3526 (модульные группы).
• Ошибки в CTF: «гладкое» p−1 → уязвимость Pohlig–Hellman; использование малых подгрупп; повтор/утечка приватных ключей; отсутствие проверки параметров (атака Logjam). Полезно: Crypto.SE.
• ECDH: те же идеи на эллиптических кривых. Точка: Q = d·G, общий секрет: K = d_A·Q_B = d_B·Q_A. Проблемы: неверная проверка принадлежности точки кривой, плохой выбор кривой (напр. слабые unsafe curves), повтор nonce в ECDSA. См. RFC 7748 (X25519/X448).

• Параметры: поле F_p или F_{2^m}, уравнение кривой, базовая точка G, порядок n. Приватный ключ: d, публичный: Q = d·G. Подробнее: Wikipedia, RFC 4492 (ECC в TLS).
• ECDSA (подпись): R = k·G, r = x(R) mod n, s ≡ k^{-1}(H(m) + r·d) mod n. Классическая уязвимость: повтор или биас k ⇒ утечка приватного ключа. См. Wikipedia, ECDSA security, атака Sony PS3 fail.
• EdDSA: RFC 8032, используется Curve25519/Edwards curves. Генерация k детерминированная из H(m, sk), что исключает ошибки случайности. Нюансы: ко-факторные атаки и ошибки в самописных протоколах. Подробнее: Ed25519 design.
• Классические ошибки: атаки invalid-curve / малых подгрупп, плохая валидация r,s (ECDSA), неправильная реализация детерминированного k в EdDSA. См. также SafeCurves — список безопасных и небезопасных кривых.

• RSA: факторинг, неправильные параметры, мультипликативность, паддинги.
• Diffie–Hellman / ElGamal: плохие группы/параметры, дискретный лог на «гладких».
• ECC (ECDH/ECDSA/EdDSA): повтор/утечка/биас k, invalid-curve/малые подгруппы, валидация r,s.
• AES/ChaCha20: ломают режимы/nonce/IV/паддинг.
• Хэши и MAC: length-extension, неверные схемы подписи.
• PRNG: предсказуемые генераторы → восстановление состояния и nonce/ключей.

RSA

• Fermat (p≈q), Wiener (малый d), Boneh–Durfee/Coppersmith (малые корни/частичные биты).
• Håstad (e мал, одно и то же m на разных n); общие делители gcd(n1,n2)>1, общий модуль.
• PKCS#1 v1.5 padding oracle (Bleichenbacher), OAEP oracle (Manger).
• Утечки CRT (dp, dq, qInv), мультипликативность c=m^e mod n.

DH / DLP

• Pohlig–Hellman (p−1 «гладкое»), Logjam/малые подгруппы.
• Слабые параметры/повторы, предсказуемые секреты.

ECC / ECDSA / EdDSA

• Nonce reuse / partial leak (k): одинаковый r → приватный; частичные биты k → HNP/LLL.
• Bias в k, баги в RFC6979; invalid-curve/малые подгруппы; валидация r,s (1 ≤ r,s < n).
• EdDSA: ко-факторные сюрпризы у самописных схем.

Блочные режимы и поточные

• ECB: видны паттерны.
• CBC: padding-oracle, bit-flipping, фиксированный IV.
• CTR/stream: повтор nonce ⇒ C1⊕C2 = P1⊕P2.
• GCM: повтор nonce фатален (подделка тегов/утечка ключа MAC).

Хэши, MAC, подписи

• Length-extension на Merkle–Damgård («secret||msg» вместо HMAC).
• Коллизии на MD5/SHA-1; неверные «подписи» (hash вместо HMAC).

PRNG

• MT19937: по 624 выходам — состояние.
• LCG: по 2–3 значениям → (a,b,m).
• rand()/time, nonce/IV из времени/счётчика.

• Это кодировка/СС или шифр? Разберись с base64/hex/rot сначала.
• Режимы: ECB-плитка, CBC-паддинг, CTR/GCM — повтор nonce.
• RSA: gcd(n1,n2), e, близость p и q, утечки CRT.
• EC: одинаковый r, некорректные r,s, странные точки.
• Хэш-подпись: HMAC или «hash(secret||msg)»?
• PRNG: время/LCG/MT «светится»?

Для смежных задач: z3/angr (решатели/симв. исполнение).

• CTR nonce reuse: C1⊕C2 = P1⊕P2 — угадываешь шаблоны и вытягиваешь тексты.
• CBC padding oracle: разные ошибки/тайминги → посимвольное восстановление.
• ECDSA повтор k: одинаковый r у двух подписей → приватный ключ за секунды.
• RSA e=3 + одинаковое сообщение на разных ключах → китайка + целый корень.