CTF Crypto 解题

识别密码体制 → 定位弱点 → 写求解脚本拿明文。

环境约定

• $PY = 64 位解题 Python（含 pycryptodome/z3/sympy/gmpy2）。 环境不确定时先运行 ctf-router 技能的 scripts/env-check.py 自检。
• hashcat：哈希爆破；字典建议 rockyou（Kali 自带 /usr/share/wordlists/）。
• SageMath（可选）：格攻击与高级数论（Coppersmith、离散对数）。 本机没有时用 pip install fpylll 替代格归约，或装 Sage： Linux sudo apt install sagemath；Windows 建议走 WSL。

识别速查

$PY -c "n=<N>; print('bits=', n.bit_length())"      # RSA 模数位宽
$PY -c "from sympy import factorint; print(factorint(<n>))"  # 小因子？
# 哈希识别：看长度（32=MD5, 40=SHA1, 64=SHA256 hex）；hashcat --example-hashes 对照
# XOR 试探
$PY -c "from pwn import xor; print(xor(bytes.fromhex('<hex>'), b'flag{'))"

按体制的攻击清单

RSA（最高频）

• 小 e + 小消息：直接开 e 次方
• 共模攻击：同一 m 两个 (n, e) → 扩展欧几里得
• Wiener：小 d（d < n^0.25 / 3）
• Fermat：p q 接近
• Pollard p-1：p-1 光滑
• Hastad 广播：e 组同明文（含线性填充用 Coppersmith）
• 已知 phi(n) 的倍数（如 e*d-1）：Miller-Rabin 平方根法分解
• dp/dq/qinv 部分泄露：遍历 k 还原素数
• 同态性绕过解密预言机：查 c*r^e 再除 r
• 先跑自动攻击组合：写脚本批量试（小e/共模/Wiener/Fermat/多素数）

对称加密

• ECB：块重排、逐字节选择明文（每字节 256 次查询）、cut-and-paste 伪造字段
• CBC：位翻转改明文；padding oracle 逐字节解密（每块约 4096 次查询）；IV 位翻转改第一块
• GCM nonce 重用：CTR 密钥流复用 + GHASH 密钥恢复
• CBC-MAC/线性 MAC：XOR 差分伪造签名
• 哈希长度扩展：hash(SECRET||msg) 用 hashpumpy（pip 可装）
• CRC32：GF(2) 线性 → 追加 4 字节强制目标 CRC，伪造签名

流密码与 PRNG

• LFSR：Berlekamp-Massey 从 2L bit 密钥流恢复反馈多项式
• RC4：第二字节偏置识别
• MT19937：624 个输出克隆状态；float 输出用 GF(2) 矩阵恢复（not_random 库）
• LCG：已知部分输出 → 模逆回退 / 格恢复截断状态
• C srand(time(NULL))：用 ctypes 调 libc 的 srand/rand 同步序列（Windows 无 libc 时走 WSL）

ECC / DLP

• 检查曲线阶的小因子 → Pohlig-Hellman
• 异常曲线（阶= p）→ Smart 攻击
• 无效曲线：服务端不校验点是否在曲线上
• ECDSA/DSA nonce 重用：同 r 直接解私钥
• 小 k 空间：暴力遍历

格 / LWE

• 判据：模线性方程组 + 未知量小/稀疏/偏置/部分泄露 → 格问题
• 工具顺序：LLL → BKZ → Babai 近似 CVP
• HNP：ECDSA 部分 nonce 泄露的标准归约
• 无 Sage 时：pip install fpylll（C 扩展，Windows 装不上就转 WSL）

经典与杂项

• 维吉尼亚：已知 flag{ 前缀直接推 key；未知长度用 Kasiski（重复串距离 GCD）
• 多字节 XOR：按 key 位置分列做频率分析
• OTP 重用：C1 xor C2 xor P_known = P_unknown，crib dragging
• 约束求解：Z3（BitVec/Int）解自定义变换、S-box、方程组

Z3 通用骨架

from z3 import *
flag = [BitVec(f'f{i}', 8) for i in range(N)]
s = Solver()
# 按题目逻辑加约束（异或、乘、模、比较）
# 可加 Printables 约束: And(f>=32, f<=126)
if s.check() == sat:
    m = s.model()
    print(bytes(m[f].as_long() for f in flag))

何时换技能

• 要先逆向出算法实现 → 逆向技能。
• 数据要从流量/文件里先挖出来 → 取证技能。
• 其实是编码谜题而非密码分析 → Misc 技能。

深度知识库（按需读取）

本技能目录 references/ctf-crypto/ 下参考文件（含完整攻击代码）：

| 文件 | 内容 | |---|---| | rsa-attacks.md / rsa-attacks-2.md | RSA 全攻击目录（含 Coppersmith、故障攻击、同态绕过） | | modern-ciphers.md / -2 / -3 | AES 各模式攻击、padding oracle、MAC 伪造、GCM | | classic-ciphers.md | 经典密码与 XOR 变体、文件格式头恢复密钥 | | ecc-attacks.md | ECC/DSA 攻击全集 | | lattice-and-lwe.md | 格攻击分诊、嵌入构造、失败模式 | | advanced-math.md | LLL/BSGS/Coppersmith/同态等数学攻击代码 | | prng.md / prng-attacks.md | MT/LCG/V8 random/ctypes 同步等 PRNG 攻击 | | stream-ciphers.md | LFSR/RC4 | | zkp-and-advanced.md | Z3 模式、Shamir、ZKP 伪造 | | exotic-crypto*.md | 冷门代数结构（Paillier、热带半环等） |