ctf-crypto

CTF 密码学

CTF 密码学挑战速查。此处每种技术都有一行说明；完整详情和代码请参阅配套文件。

前置条件

Python 包（所有平台）：

pip install pycryptodome z3-solver sympy gmpy2 hashpumpy fpylll py_ecc
# Coppersmith (optional): pip install coppersmith
# Alternative Coppersmith lib: git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks && pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt

Linux（apt）：

apt install hashcat

macOS（Homebrew）：

brew install hashcat

手动安装：

• SageMath（可选——仅用于旧版 Sage 回退代码片段（折叠部分））—— Linux：apt install sagemath，macOS：brew install --cask sage
• RsaCtfTool — git clone https://github.com/RsaCtfTool/RsaCtfTool（自动化 RSA 攻击）
• crypto-attacks（Coppersmith）— git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks + pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt（pip install coppersmith 的替代方案）

注意： gmpy2 需要 libgmp——Linux：apt install libgmp-dev，macOS：brew install gmp。

其他资源

• classic-ciphers.md - 古典密码：维吉尼亚密码（+ 卡西斯基检验）、Atbash 密码、替换转轮、XOR 变体（+ 多字节频率分析）、确定性 OTP、级联 XOR、书本密码、OTP 密钥重用 / 多次一密、变长同音替换、缩减网格置换密码密钥空间、基于图像的凯撒移位密码、通过文件格式头恢复 XOR 密钥
• modern-ciphers.md - 现代密码攻击：AES（CFB-8、ECB 泄露）、CBC-MAC/OFB-MAC、填充预言机、S 盒碰撞、GF(2) 消元、LCG 部分输出恢复、复合模数上的仿射密码、使用派生密钥的 AES-GCM、AES-GCM nonce 重用（禁止的攻击）、类 Ascon 减轮差分密码分析、自定义线性 MAC 伪造、CBC 填充预言机（完整块解密）、Bleichenbacher RSA PKCS#1 v1.5 填充预言机（ROBOT）、生日攻击 / 中间相遇攻击、CRC32 碰撞签名伪造、通过逐字节清零预言机恢复 AES 密钥、通过错误消息解密预言机伪造 AES-CBC 密文
• modern-ciphers-2.md - 现代密码攻击（第 2 部分）：Blum-Goldwasser 位扩展预言机、哈希长度扩展、压缩预言机（CRIME 风格）、通过循环检测实现哈希函数时间反转、OFB 模式可逆 RNG 向后解密、通过公钥哈希 XOR 实现弱密钥派生、HMAC-CRC 线性攻击、OFB 模式下的 DES 弱密钥、SRP 协议绕过、修改 AES S 盒暴力破解、对减轮 AES 的平方攻击、AES-ECB 逐字节选择明文攻击、AES-ECB 剪切粘贴块操作、AES-CBC IV 位翻转认证绕过、Rabin LSB 奇偶性预言机、PBKDF2 预哈希绕过、通过 fastcol 实现 MD5 多重碰撞
• modern-ciphers-3.md - 现代密码攻击（第 3 部分）：自定义哈希状态反转、小载荷 CRC32 暴力破解、带错误校正的噪声 RSA LSB 预言机、海绵哈希中间相遇碰撞、CBC IV 伪造 + 块截断、从填充预言机到 CBC 位翻转 RCE、SPN S 盒交集攻击、从时间戳播种的 PRNG 恢复 AES-CFB IV、三轮 XOR 协议密钥抵消、AES-CBC UnicodeDecodeError 侧信道预言机、用于绕过 XOR 聚合哈希的 SHA-256 基攻击、通过 XOR 块抵消伪造自定义 MAC、通过 XOR+加法运算恢复 HMAC 密钥
• modern-ciphers-4.md - 现代密码攻击（第 4 部分）：对 ChaCha20-Poly1305 执行基于 $2^{130}-5$ 的 nonce 重用禁止攻击（RFC 8439、CTR $C_1\oplus C_2=P_1\oplus P_2$、通过 galois/sympy 计算 Poly1305 $\sum c_i r^{n-i}$、2 条 $ad=""$ 向量）、分区预言机 / 密钥承诺 AEAD 分割格、海绵结构的普适性（SHA-3/Keccak $0x06$ 对比 $0x01$、Ascon/Gimli/Sparkle 的 rate/capacity/轮数/填充表 + 字节序工作流）、eSTREAM Trivium 1152 轮预热与立方攻击概要（Grain）
• stream-ciphers.md - 流密码攻击：LFSR（Berlekamp-Massey、相关攻击、已知明文、Galois 与 Fibonacci、通过自相关恢复 Galois 抽头）、RC4 第二字节偏差、连续 XOR 字节相关性
• rsa-attacks.md - RSA 攻击：小 e（立方根）、共模数、Wiener 攻击、Pollard 的 p-1、Hastad 广播攻击、带线性填充的 Hastad 攻击（Coppersmith）、Franklin-Reiter 相关消息（e=3）、Coppersmith 线性相关素数、Fermat / 连续素数、多素数、受限数字、Coppersmith 结构化素数、Manger 预言机、多项式哈希
• rsa-attacks-2.md - RSA 攻击（专门攻击）：RSA p=q 验证绕过、立方根 CRT gcd(e,phi)>1、从 phi(n) 的倍数分解、乘法同态签名伪造、通过基数表示实现弱密钥生成、gcd(e,phi)>1 时的 RSA 指数约简、批量 GCD 共享素数分解、从 dp/dq/qinv 部分恢复密钥、RSA-CRT 故障攻击、同态解密预言机绕过、小素数 CRT 分解、Montgomery 约减时序攻击、Bleichenbacher 低指数签名伪造、使用 e=1 和精心构造的模数绕过 RSA 签名
• ecc-attacks.md - ECC 攻击：小子群、无效曲线、Smart 攻击（异常曲线，附 Sage 代码）、故障注入、时钟群 DLP、Pohlig-Hellman、ECDSA nonce 重用、Ed25519 扭点侧信道、DSA nonce 重用、通过 k 生成中的 MD5 碰撞恢复 DSA 密钥、X25519 低阶点 + 全零检查
• dh-attacks.md - 经典有限域 DH：平凡 g（0/1/p-1）、当 p-1 平滑时的 Pohlig-Hellman、小子群约束 / 通过 CRT 恢复 Lim-Lee 静态密钥、静态与临时密钥 + Logjam 降级分类
• zkp-and-advanced.md - ZKP / 图 3 着色、Z3 求解器指南、混淆电路、Shamir SSS、二元组约束求解、竞态条件、Groth16 设置漏洞、DV-SNARG 伪造、用于恢复置换的 KZG 配对预言机、Shamir SSS 重用多项式系数
• prng.md - PRNG 攻击（基础）：MT19937、通过 GF(2) 魔法矩阵恢复 MT 浮点数以预测令牌、LCG、GF(2) 矩阵 PRNG、通过 Z3 恢复 V8 XorShift128+ Math.random 状态、中间平方、确定性 RNG 爬山搜索、随机模式预言机、基于时间的种子、通过 ctypes 同步 C srand/rand、密码破解、逻辑斯蒂映射混沌 PRNG
• prng-attacks.md - PRNG 攻击（CTF 时代，2017 年起）：MT 子集和种子恢复、MT19937 约束传播、通过 Z3 反转 86 号规则元胞自动机、Java LCG 中间相遇部分模运算、通过模逆元反向步进 LCG、LFSR 位折叠 ASCII 奇偶校验、Z3 求解时间时序预言机、randcrack DSA k 预测、格式字符串 PRNG 种子偏移、受 NTP 污染的 PRNG UUID XOR
• historical.md - 历史密码（Lorenz SZ40/42、书本密码实现）
• advanced-math.md - 高等数学攻击（同源映射、Pohlig-Hellman、一般 DLP 的 baby-step giant-step (BSGS)、LLL、通过 LLL 攻击 Merkle-Hellman 背包、通过 Howgrave-Graham 的 Coppersmith：hg_matrix -> IntegerMatrix -> LLL -> sympy Poly（beta=0.5、单首项检查、dim>100 时可选 flatter）、四元数 RSA、GF(2)[x] CRT、S 盒碰撞代码、LWE 格 CVP 攻击、非素数模数上的仿射密码、通过 GF(2) 线性代数实现自省 CRC）
• lattice-and-lwe.md - 格攻击分类与工作流：LLL/BKZ/Babai、从部分或有偏 nonce 得到的 HNP、截断 LCG 状态恢复、LWE 嵌入与 CVP、识别 Ring-LWE / Module-LWE、NTRU 格 B=[[qI 0],[H I]]（负循环、BKZ、中心化 g）、GGH 嵌入 [[B 0],[c lambda]] 扫描 lambda、Mersenne AJPS p=2^n-1 n=11213 w=10 6x6 s=5、BDD 判定条件 / LadderLeak（>100 个签名，每个 1-4 位）、正交格、子集和 / 背包，以及常见失败模式
• post-quantum.md - 后量子密码识别：ML-KEM（Kyber）k=2/3/4 q=3329 etau dv、ML-DSA、Falcon、Module-LWE 展平、FO 失败预言机、NTT、Kannan/Bai-Galbraith/Arora-Ge/estimator 决策树、Mersenne AJPS 详情
• exotic-crypto.md - 奇特代数结构（辫群 DH / Alexander 多项式、单调函数求逆、热带半环残余、Paillier 密码系统、汉明码螺旋交织、ElGamal 通用重加密、FPE Feistel 暴力破解、二十面体对称群密码、Goldwasser-Micali 复制预言机）
• exotic-crypto-2.md - 奇特代数结构（第 2 部分，2017 年起）：BB-84 QKD 中间人攻击、ElGamal 平凡 DLP（B=p-1）、通过同态倍增实现 Paillier LSB 预言机、差分隐私噪声抵消、同态加密位提取、通过 Jordan 标准形实现矩阵上的 ElGamal、通过 Pollard 伪造 OSS 签名、无需私钥解密 Cayley-Purser、BIP39 部分助记词校验和暴力破解、Asmuth-Bloom CRT 阈值恢复、使用多项式素数的 Rabin、LCG 周期检测、Vandermonde 多项式系数恢复

---

何时切换

• 如果真正的障碍是理解二进制文件、混淆的客户端或奇怪的 VM，请切换到 /ctf-reverse。
• 如果挑战主要涉及在开始任何解密之前进行数据包提取、磁盘恢复或隐写提取，请切换到 /ctf-forensics。
• 如果加密部分已经解决，任务只是针对易受攻击的网络服务实现漏洞利用，请切换到 /ctf-pwn 或 /ctf-web。
• 如果加密挑战涉及对抗性 ML、模型提取或基于神经网络的密码，请切换到 /ctf-ai-ml。
• 如果挑战本质上是编码谜题、稀奇古怪的密码或多语言技巧，而非真正的密码分析，请切换到 /ctf-misc。

快速入门命令

# Identify cipher type
python3 -c "from Crypto.Util.number import *; n=<N>; print(f'bits={n.bit_length()}')"

# RSA quick check
python3 -c "from sympy import factorint; print(factorint(<n>))"  # Small factors?
openssl rsa -pubin -in key.pub -text -noout  # Extract n, e from PEM

# Quick factorization tools
python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c>

# XOR analysis
python3 -c "from pwn import xor; print(xor(bytes.fromhex('<hex>'), b'flag{'))"

# Hash identification
hashid '<hash>'
hashcat --identify '<hash>'

# Quick factorization (sympy, primary)
python3 -c "from sympy import factorint; print(factorint(<n>))"
# Sage alternative: sage -c "print(factor(<n>))"

经典密码

• 凯撒密码： 进行频率分析，或穷举 26 个密钥
• 维吉尼亚密码： 利用带有 Flag 格式前缀的已知明文攻击；通过 (ct - pt) mod 26 推导密钥。未知密钥长度时使用 Kasiski 检验（重复序列距离的 GCD）
• Atbash： A<->Z 替换；留意挑战名称中的 “Abashed” 提示
• 替换轮： 穷举内外字母表映射的所有旋转
• 多字节 XOR： 按密钥位置拆分密文，分别对每列进行频率分析；根据英语字母频率评分（空格 = 0x20）
• 级联 XOR： 穷举第一个字节（尝试 256 次），其余部分可确定性地推出
• XOR 旋转（2 的幂）： 奇偶位不会混合；只有 4 种候选状态
• 弱 XOR 验证： 单字节 XOR 检查的通过率为 1/256；预算充足时进行穷举
• 确定性 OTP： 使用已知明文 XOR 恢复密钥流；匹配负载均衡的后端
• OTP 密钥重用（多次一密）： C1 XOR C2 XOR known_P = unknown_P；没有已知明文时使用 crib dragging
• 同音替换（变长）： 多字符密文组映射为单个明文字符。找出具有相同子 n 元组频率的 n 元组，将其替换为符号，再按单表替换法求解。参见 classic-ciphers.md。
• 网格置换密码： 具有独立行列置换的 5x5 网格可将密钥空间缩小至 5! x 5! = 14,400；几毫秒内即可穷举。参见 classic-ciphers.md。
• 基于图像的凯撒位移： 像素行列按条带分别位移；对比原图与位移后的图像，从位移量中提取 ASCII 编码的 Flag。参见 classic-ciphers.md。
• 波利比奥斯方阵密码： 5x5 网格将字母对映射为明文；数字/坐标编码位置。参见 classic-ciphers.md。
• 通过文件格式头恢复 XOR 密钥： 文件声称是 PDF/PNG/ZIP，但 file 报告为 “data”。将前几个字节与预期的魔数进行 XOR，推导出循环密钥；再利用尾部结构（%%EOF、IEND 标记）扩展密钥。参见 classic-ciphers.md。

完整代码示例请参见 classic-ciphers.md。

现代密码攻击

• **AES-ECB：**通过重排分组，以及逐字节选择明文后缀恢复（每个字节需要 256 次查询，工具：FeatherDuster ecb_cpa_decrypt）进行攻击；图像 ECB 会保留视觉图案。ECB 剪切粘贴：拼接密文分组以伪造 JSON 字段（例如 is_admin: true）。参见 modern-ciphers-2.md。
• **AES-CBC：**通过位翻转更改明文；利用填充预言机，无需密钥即可解密。IV 位翻转：翻转 IV 中的特定位以更改第一个明文分组（不需要 MAC）。参见 modern-ciphers-2.md。
• **CBC IV 伪造 + 分组截断：**对 IV 字节进行 XOR 以更改解密后的分组 0；移除末尾的密文分组（CBC 不具备长度完整性）。当 MAC 嵌入密文时，可伪造经过身份验证的令牌。参见 modern-ciphers-3.md。
• **通过填充预言机实现 CBC 位翻转 RCE：**结合填充预言机（恢复明文）与 CBC 位翻转（注入 shell 元字符），通过加密参数实现命令注入。参见 modern-ciphers-3.md。
• **AES-CFB-8：**静态 IV 搭配 8 位反馈，可在获知 16 个字节后重建状态
• **CBC-MAC/OFB-MAC：**通过 XOR 密钥流伪造签名：new_sig = old_sig XOR block_diff
• **S 盒碰撞：**非置换 S 盒（len(set(sbox)) < 256）可通过 4,097 次查询恢复密钥
• **GF(2) 消元：**通过在 GF(2) 上进行高斯消元求解线性哈希函数（XOR + 旋转）
• **填充预言机：**修改前一个分组并测试填充是否有效，从而逐字节解密
• **LFSR 流密码：**Berlekamp-Massey 可通过 2L 位密钥流恢复反馈多项式；相关性攻击可利用带偏置的组合函数破解组合生成器
• **Galois LFSR 抽头恢复：**将已知文件头（PNG/PDF/ZIP）与密文 XOR 以获取密钥流；将其拆分为 N 位窗口，对 LSB=1 的转换计算 (state >> 1) XOR next_state，直接恢复抽头掩码。通过自相关滑动查找正确长度。参见 stream-ciphers.md。
• **使用可逆 RNG 的 OFB：**任意分组中的已知明文都会泄露 RNG 状态；如果状态转换是双射，就可以反向运行 RNG 来解密所有分组。参见 modern-ciphers-2.md。
• **弱密钥派生（公钥哈希 XOR）：**从 SHA256(public_key) XOR seed 派生的 AES 密钥无需私钥即可完全恢复；“混合” RSA+AES 不提供任何安全性。参见 modern-ciphers-2.md。
• **HMAC-CRC 线性性：**CRC 在 GF(2) 上是线性的，因此可以通过一条消息-MAC 对，利用多项式运算恢复 HMAC-CRC 密钥。参见 modern-ciphers-2.md。
• **OFB 中的 DES 弱密钥：**4 个 DES 弱密钥会使加密自反；OFB 密钥流的周期为 2，因而可归结为 16 字节重复 XOR。参见 modern-ciphers-2.md。
• **Square 攻击（减轮 AES）：**通过积分密码分析破解 4 轮 AES：使用 256 个明文构成的 lambda 集合，通过 XOR 和为 0 的区分器猜测最后一轮密钥字节。参见 modern-ciphers-2.md。
• **AES-GCM nonce 重用（禁用的攻击）：**相同 nonce = CTR 密钥流重用 + 通过 GF(2^128) 上的多项式因式分解恢复 GHASH 认证密钥。工具：nonce-disrespect。参见 modern-ciphers.md。
• **SRP 协议绕过：**发送 A = 0 或 A = n，强制共享密钥为 0，从而完全绕过密码验证。参见 modern-ciphers-2.md。
• **修改 AES S 盒的暴力破解：**只有 16 个唯一输出的自定义 S 盒会降低密钥熵；可以逐轮暴力破解可行的密钥字节。参见 modern-ciphers-2.md。
• **Rabin LSB 奇偶预言机：**对于 Rabin 密文 c = m^2 mod n，LSB 预言机可利用乘法同态性（c * 4 mod n 会使明文加倍），通过 log2(n) 次查询二分搜索恢复明文。参见 modern-ciphers-2.md。
• **带噪声的 RSA LSB 预言机纠错：**当 LSB 预言机偶尔出错时，先运行标准攻击，再检查输出字符集。在错误位置翻转预言机结果，以纠正剩余的解密错误。参见 modern-ciphers-3.md。
• **绕过 PBKDF2 预哈希：**HMAC 会对超过 64 字节的密钥进行预哈希（SHA-1/SHA-256 分组大小）。当原始密码超过 64 字节时，使用 SHA1(password) 而不是 password 登录。参见 modern-ciphers-2.md。
• **MD5 多重碰撞（fastcol）：**串联运行 fastcol，生成 2^k 个 MD5 值相同的文件。Merkle-Damgard 组合：碰撞会在追加后缀后继续传播。参见 modern-ciphers-2.md。
• **自定义哈希状态逆转：**当迭代哈希泄露中间状态时，反转状态更新方程以分离每个分组的哈希值，然后分别暴力破解每个 4 字节分组。参见 modern-ciphers-3.md。
• **CRC32 暴力破解（小型负载）：**ZIP CRC32 标头未经加密；通过将所有可打印字符串与存储的 CRC32 进行比对，暴力破解小文件（≤ 6 字节）的内容。参见 modern-ciphers-3.md。
• **通过 XOR 分组抵消伪造自定义 MAC：**当 MAC 密钥流周期性重复时，构造 3 次查询，使填充分组通过 XOR 相互抵消，从而伪造任意目标命令的 MAC。参见 modern-ciphers-3.md。
• **HMAC 密钥恢复（XOR + 加法运算）：**存在缺陷的 HMAC 使用 sha256((key XOR msg) + msg)，会泄露密钥位：msg=0 时得到 sha256(key)；msg=2^i 时，若密钥第 i 位为 1，结果就会匹配。参见 modern-ciphers-3.md。
• **AES-CBC 密文伪造（错误消息预言机）：**服务器会在错误消息中泄露解密后的字节；发送全零分组以获知中间状态，再与所需明文进行 XOR，逐分组伪造密文。参见 modern-ciphers.md。 完整代码示例请参阅 modern-ciphers.md 和 modern-ciphers-2.md。

RSA 攻击

• 小 e、小消息： 对密文开 e 次方根
• 共模攻击： 扩展欧几里得攻击
• Wiener 攻击： d 较小
• Fermat 因数分解： p 和 q 相近
• Pollard 的 p-1： p-1 是光滑数
• Hastad 广播攻击： 同一消息使用多个 e=3 加密
• 连续素数： q = next_prime(p)；查找小于 sqrt(N) 的最大素数
• 多素数： 使用 sympy 分解 N；根据所有因子计算 phi
• 受限数字素数： 从最低有效位开始逐位分解，并使用模数剪枝
• Coppersmith 结构化素数： 部分已知的素数；使用 coppersmith lib 的 small_roots（详情中提供 Sage 后备方案）
• Manger 预言机（简化版）： 第 1 阶段倍增 + 第 2 阶段二分搜索；对于 64 位密钥，约需 128 次查询
• RSA-OAEP 上的 Manger 攻击（计时）： Python 的 or 短路逻辑会在 Y != 0 时跳过耗时的 PBKDF2，从而形成快/慢计时预言机。完整的 3 步攻击（对于 1024 位 RSA，约需 1024 次迭代）。使用已知的快速/慢速样本校准计时边界。
• 多项式哈希（平凡根）： 多项式哈希满足 g(0) = 0；构造后缀使 msg = 0 (mod P)，签名 = 0
• GF(2)[x] 中的多项式 CRT： 收集约 20 个余数 r = flag mod f，筛选互素项，并通过 CRT 合并
• 复合模数上的仿射变换： 在每个素因子域中使用 CRT；对每个素数分别进行 Gauss-Jordan 消元
• RSA p=q 校验绕过： 设置 p=q，使服务器计算错误的 phi=(p-1)^2，而不是 p*(p-1)；测试解密会失败，从而泄露密文
• RSA 立方根 CRT（gcd(e,phi)>1）： 当所有素数都满足 ≡ 1 mod e 时，使用 nthroot_mod 计算每个素数下的 e 次根，并枚举 CRT 组合（对于较小的 k，3^k 可行）
• 从 phi(n) 的倍数分解因数： phi(n) 的任意倍数（例如 e*d-1）都可通过 Miller-Rabin 平方根技巧分解 n；每次尝试成功概率 ≥ 1/2
• 基数表示导致的弱密钥生成： 较小的 kp 会使素数 p = kp*B + tp 在 n 中形成混合进位制结构；穷举 kp*kq（2^24）以分解 n
• gcd(e,phi)>1 的 RSA（指数约化）： 将 e' = e/g，计算 d' = e'^(-1) mod phi，部分解密得到 m^g，然后在整数范围内求 g 次根
• RSA 部分密钥恢复（dp/dq/qinv）： 部分 PEM 泄露的 CRT 指数可用于 O(e) 素数恢复：遍历 k，检查 (dp*e-1)/k+1 是否为素数。参见 rsa-attacks-2.md。
• RSA-CRT 故障攻击： 单个有故障的 CRT 签名可通过 gcd(s^e - m, n) 泄露因子（Bellcore 攻击）。参见 rsa-attacks-2.md。
• RSA 同态解密绕过： 乘法同态性允许你通过使用 c * r^e mod n 查询预言机来解密 c，然后将结果除以 r。参见 rsa-attacks-2.md。
• RSA 小素数 CRT 分解： 当 n 含有许多小素数因子时，可通过试除分解，对每个素数求解 m mod p_i，再使用 CRT 合并。参见 rsa-attacks-2.md。
• 带线性填充的 Hastad 广播攻击（Coppersmith）： 当 e 个接收方分别在加密前应用已知仿射变换 a_i*m+b_i 时，可通过 CRT + Coppersmith small_roots 恢复 m。参见 rsa-attacks.md。
• RSA Montgomery 约简计时攻击： Montgomery 乘法中泄露的额外减法次数，通过统计相关性揭示从最高有效位到最低有效位的私钥比特。参见 rsa-attacks-2.md。
• Bleichenbacher 低指数签名伪造： 当 e=3 时，可通过计算带有正确填充前缀的值的立方根来伪造 PKCS#1 v1.5 签名；末尾垃圾数据可补足剩余部分。参见 rsa-attacks-2.md。
• Franklin-Reiter 相关消息攻击（e=3）： 两个密文分别加密 m+pad1 和 m+pad2，且填充差已知；在 Zmod(n) 中求多项式最大公因式可直接恢复 m。参见 rsa-attacks.md。
• RSA 签名绕过（e=1，构造模数）： 验证器接受用户提供的 (n, e)；设置 e=1 和 n = sig - PKCS1_pad(msg)，使 pow(sig, 1, n) 等于预期的填充哈希。参见 rsa-attacks-2.md。
• Coppersmith 在线性相关素数上的应用： 当已知 k 且 q ~ k*p 时，近似取 q ~ sqrt(k*n)，并对误差项使用 Coppersmith small_roots。这是 Fermat 因数分解在非连续素数上的推广。参见 rsa-attacks.md。 完整代码示例请参阅 rsa-attacks.md 和 advanced-math.md。

椭圆曲线攻击

• 小子群： 检查曲线阶是否含有小因子；使用 Pohlig-Hellman + CRT
• 无效曲线： 如果缺少验证，则发送位于较弱曲线上的点
• 奇异曲线： 判别式 = 0；DLP 可映射到加法群／乘法群
• Smart 攻击： 异常曲线（阶 = p）；p-adic 提升可在 O(1) 时间内求解 DLP
• 婴儿步—巨人步（BSGS）： 在 O(sqrt(n)) 时间／空间内求解一般 DLP。对于阶平滑的群（p-1 或曲线阶的所有因子都较小），可结合 Pohlig-Hellman。sympy/fpylll 的 BSGS+Pohlig-Hellman（Sage 替代方案已合并）。参见 advanced-math.md。
• 故障注入： 比较正确输出与故障输出；逐位恢复密钥
• 时钟群（x^2+y^2=1）： 阶 = p+1（不是 p-1！）；当 p+1 平滑时使用 Pohlig-Hellman
• 同源： 通过模多项式遍历图；通过 LCA 寻路
• ECDSA nonce 重用： 两个签名中相同的 r 会通过模运算泄露 nonce k 和私钥 d。检查是否有重复的 r 值
• 辫群 DH： Alexander 多项式在辫的连接运算下具有乘法性——Eve 可根据公钥计算共享密钥。参见 exotic-crypto.md
• Ed25519 扭点侧信道： 当密钥派生使用 key = master * uid mod l 时，余因子 h=8 会泄露秘密标量位；查询 2 的幂并检查 y 坐标的一致性
• 热带半环剩余运算： 热带（min-plus）DH 已被攻破——剩余量 b* = max(Mb[i] - M[i][j]) 可直接从公矩阵恢复共享密钥
• FPE Feistel 穷举： 使用 16 位轮密钥的保格式加密可被穷举；剩余的仿射 GF(2) 混合层可通过高斯消元求解。参见 exotic-crypto.md
• 二十面体对称密码： 十二面体面的置换构成一个 120 阶群；通过 API 探测构建包含所有置换的查找表，并匹配可见的面模式。参见 exotic-crypto.md
• Goldwasser-Micali 复制预言机： GM 每个密文加密一个比特；将单个密文值重复 N 次作为 N 位密钥，可强制密钥全为 0 或全为 1，并可通过哈希预言机区分。128 次查询即可恢复完整 AES 密钥。参见 exotic-crypto.md
• DSA nonce 重用： 两个 DSA 签名中相同的 r 会通过与 ECDSA nonce 重用相同的公式泄露私钥。参见 ecc-attacks.md。
• DSA 有限 k 穷举： 当 nonce k 较小时（例如 20 位），穷举所有 k 值，并检查哪个值会产生已知的 r。参见 ecc-attacks.md。
• ECC 共享素因子 GCD： 多条 ECC 曲线的模数共享一个素因子；gcd(n1, n2) 可揭示该共享素因子。参见 ecc-attacks.md。
• 通过 k 生成中的 MD5 碰撞恢复 DSA 密钥： 当 nonce k 根据 MD5(prefix+counter) 派生时，使用 fastcoll 生成 MD5 前缀碰撞以强制重用 nonce，然后按标准方法恢复私钥。参见 ecc-attacks.md。
• BB-84 QKD 中间人攻击： 模拟的 BB-84 未使用经过认证的经典信道，因此允许完全中间人攻击——分别与双方协商密钥，并强制一侧使用固定值。参见 exotic-crypto-2.md。

完整代码示例请参见 ecc-attacks.md、advanced-math.md 和 exotic-crypto.md。

Diffie-Hellman 攻击

• 平凡的 g： 首先尝试 g = 0, 1, p-1 以及对等方的取值 A = 0, 1, p-1, p；未验证范围的检查会产生已知常量密钥。参见 dh-attacks.md。
• Pohlig-Hellman： 分解 p-1；若其为光滑数，则可通过对每个子群使用 BSGS 并结合 CRT 求解完整的 DLP。参见 dh-attacks.md。
• 小子群约束 / Lim-Lee： 静态密钥加上含有小因子的复合数 p-1；发送阶为 r 的元素，通过 MAC/解密预言机暴力破解 b mod r，再对各个 r_i 使用 CRT。参见 dh-attacks.md。
• X25519 低阶点： 余因子为 8，加上钳位处理意味着小阶 u 会强制使 K 全零；始终探测 u = 0, 1。若缺少全零检查，1-2 次查询即可攻破。参见 ecc-attacks.md。

格基 / LWE 攻击

• 快速判断： 如果题目给出模线性方程，并保证隐藏量较小、稀疏、有偏，或只部分泄露，请优先将其视为格问题。参见 lattice-and-lwe.md。
• LLL / BKZ / Babai： fpylll LLL.reduction / BKZ.reduction / GSO.Mat.babai / CVP.closest_vector（详情中也提供 Sage Matrix(ZZ).LLL() / M.BKZ 作为备用方案）——从 LLL 开始，LLL 几乎奏效时改用 BKZ，用 Babai 求近似 CVP。参见 lattice-and-lwe.md。
• 从部分 nonce 泄露中求解 HNP： ECDSA/Schnorr nonce 部分泄露或存在偏差时，通常可化为隐藏数问题（HNP）格；规范化方程，分离有界误差，进行格约化，然后按需暴力搜索最后几位。参见 lattice-and-lwe.md。
• 截断 LCG 状态恢复： 仿射递推中的高位或低位泄露通常只是伪装成其他形式的 HNP；将每个状态写成 observed * 2^t + hidden，并求解较小的隐藏校正值。参见 lattice-and-lwe.md。
• 通过 CVP（Babai）求解 LWE： 根据 [q*I | 0; A^T | I] 构造格，使用 fpylll GSO.Mat.babai 或 CVP.closest_vector 查找最近向量，再投影到三元集合 {-1,0,1}。注意服务器描述与实际编码之间可能存在字节序不匹配。
• 识别 Ring-LWE / Module-LWE： 多项式或反循环结构看起来往往很复杂，但许多 CTF 会通过极小系数、有缺陷的表示或足够的泄露削弱问题，使其还原为普通 LWE。参见 lattice-and-lwe.md。
• 正交格： 隐藏子集或隐藏子空间问题可能需要先恢复正交格，再从其补空间重建实际的二进制基或短基。参见 lattice-and-lwe.md。
• 用 LLL 求近似最大公因数： fpylll LLL.reduction（详情中也提供 Sage Matrix(ZZ).LLL() 作为备用方案）——格中的短向量可揭示隐藏因子
• 子集和 / 背包： 二进制背包和低密度子集和实例仍是经典的格问题领域；构造标准基，并寻找最后一个坐标为零的约化行。参见 lattice-and-lwe.md。
• 多层挑战： 几何 → 子空间恢复 → LWE → AES-GCM 解密链

可参见 advanced-math.md 中的 LWE 求解代码示例，以及 lattice-and-lwe.md 中的攻击选择、嵌入和故障模式判断。

ZKP 与约束求解

• ZKP 欺骗： 对于无解问题（3-着色 K4），寻找哈希碰撞或预测 PRNG 盐值
• 图 3-着色： nx.coloring.greedy_color(G, strategy='saturation_largest_first')
• Z3 求解器： 位级操作使用 BitVec，任意精度使用 Int；求解 BPF/SECCOMP 过滤器
• 混淆电路（自由 XOR）： 对三个真值表条目执行 XOR，恢复全局增量
• 二元组替换： 使用带有已知明文结构自动机约束的 OR-Tools CP-SAT
• 三元组分解： 模 n 的位置构成相互独立的单表密码
• Shamir SSS（确定性系数）： 一份份额 + 带种子的 RNG = 关于秘密的一元方程
• 竞态条件（TOCTOU）： 同步并发请求绕过 counter < N 检查
• Groth16 配置遭破坏（delta==gamma）： 可轻易伪造：A=alpha，B=beta，C=-vk_x。务必先检查验证器常量
• Groth16 证明重放： 未约束的 nullifier + 无跟踪 = 可从 setup tx 无限重放
• DV-SNARG 伪造： 通过访问验证器预言机，从未约束的值对中获知秘密 v 值，再通过 CRS 条目抵消进行伪造
• Shamir SSS 复用多项式系数： 若每个秘密字节都使用相同的随机系数，份额相减会抵消所有随机性，仅留下明文差异。参见 zkp-and-advanced.md。

完整代码示例和求解器模式，请参见 zkp-and-advanced.md。

现代密码攻击（补充）

• 复合模数上的仿射密码： c = A*x+b (mod M)，M 为复合数（例如，65=5*13）。通过单热向量实施选择明文恢复，再对每个素因子进行 CRT 求逆。参见 modern-ciphers.md。
• 自定义线性 MAC 伪造： 基于 XOR 的签名关于秘密块呈线性。通过约 5 组已知对恢复秘密，并为目标伪造。参见 modern-ciphers.md。
• Manger 预言机（RSA 阈值）： RSA 乘法操作 + 对 m*s < 2^128 进行二分搜索。约需 128 次查询即可恢复 AES 密钥。
• 通过逐字节清零预言机恢复 AES 密钥： 密钥槽索引中的整数溢出可选择性地将字节清零；每次暴力破解一个字节（每字节 256 次，共 4096 次）。参见 modern-ciphers.md。

通过 GF(2) 线性代数进行自指 CRC

自指 CRC：找到一个 CRC 等于其自身的 ASCII 字符串。CRC 在 GF(2) 上呈线性，因此该约束可转化为可求解的线性系统。选择自由变量，使其落在可打印 ASCII 范围内。参见 advanced-math.md。

CBC 填充预言机攻击

服务器会透露填充有效或无效 → 无需密钥即可解密任意 CBC 密文。每个 16 字节块约需 4096 次查询。使用 PadBuster 或 Python 库 padding-oracle。参见 modern-ciphers.md。

Bleichenbacher RSA 填充预言机（ROBOT）

RSA PKCS#1 v1.5 填充验证预言机 → 自适应选择密文明文恢复。RSA-2048 约需 10K 次查询。通过时序影响 TLS 实现。参见 modern-ciphers.md。

生日攻击 / 中间相遇攻击

n 位哈希碰撞约需 2^(n/2) 次尝试。中间相遇攻击可在 O(2^k) 而非 O(2^(2k)) 的复杂度下破解双重加密。参见 modern-ciphers.md。

• 海绵哈希 MITM 碰撞： 当海绵结构的速率小于状态大小时，不受控的状态字节可用于 MITM——对不受控字节进行前向加密预计算，并向后搜索匹配项。将 2^48 降至 2^24。参见 modern-ciphers-3.md。

基于 CRC32 碰撞的签名伪造（iCTF 2013）

CRC32 是线性的——附加 4 个选定字节即可强制生成任意目标 CRC32，从而在不知道密钥的情况下伪造 CRC32(msg || secret) 签名。参见 modern-ciphers.md。

Blum-Goldwasser 位扩展预言机（PlaidCTF 2013）

每次预言机查询将密文扩展 1 位，通过奇偶性泄露明文。操纵 BBS 平方序列以生成有效的扩展密文。参见 modern-ciphers-2.md。

哈希长度扩展攻击

利用 Merkle-Damgard 哈希（hash(SECRET || user_data)）——附加任意数据，并在不知道密钥的情况下计算有效哈希。使用 hashpump 或 hashpumpy。参见 modern-ciphers-2.md。

压缩预言机（CRIME 风格）

加密前进行压缩，会通过密文长度变化泄露明文。发送选定的明文；匹配的 n 元组会压缩得更短。与 CRIME/BREACH 属于同一类攻击。参见 modern-ciphers-2.md。

RC4 第二字节偏差

RC4 的第二个输出字节偏向 0x00（概率为 1/128，而非 1/256）。使用约 2048 个样本即可区分 RC4 与随机输出。参见 stream-ciphers.md。

RSA 乘法同态签名伪造

未填充的 RSA：S(a) * S(b) mod n = S(a*b) mod n。如果预言机将目标消息列入黑名单，就对其因子签名后相乘。参见 rsa-attacks-2.md。

常见模式

• RSA 基础： phi = (p-1)*(q-1)，d = inverse(e, phi)，m = pow(c, d, n)。完整示例参见 rsa-attacks.md。
• XOR： from pwn import xor; xor(ct, key)。XOR 的变体参见 classic-ciphers.md。

通过 ctypes 预测 C srand/rand（L3akCTF 2024，MireaCTF）

模式： 二进制程序使用 srand(time(NULL)) + rand() 生成密钥/XOR 掩码。Python 的 random 模块使用不同的 PRNG。使用 ctypes.CDLL('./libc.so.6') 直接调用 C 的 srand(int(time())) 和 rand()，复现完全相同的序列。有关 XOR 解密示例和时序技巧，参见 prng.md。

V8 XorShift128+（Math.random）状态恢复

模式： V8 JavaScript 引擎使用 xs128p PRNG 为 Math.random() 生成随机数。给定 5-10 个连续的 Math.floor(CONST * Math.random()) 输出，使用 Z3 QF_BV 求解器恢复内部状态（state0、state1）并预测后续值。值必须反转（LIFO 缓存）。工具：d0nutptr/v8_rand_buster。参见 prng.md。

从浮点数输出恢复 MT 状态（PHD CTF Quals 2012）

模式： 服务端公开 random.random() 浮点数。标准的反去偏需要 624 个 32 位整数，但浮点数每个只能提供约 8 个可用位。预先计算的 GF(2) 魔法矩阵（not_random 库）可从 3360 个以上的浮点数观测值中恢复完整的 MT 状态。可用于预测由 random.random() 生成的密码重置令牌、会话 ID 或 CSRF 令牌。参见 prng.md。

混沌 PRNG（Logistic 映射）

• Logistic 映射： x = r * x * (1 - x)，r ≈ 3.99-4.0；通过暴力枚举高精度小数恢复种子
• 密钥流： 每次迭代执行 struct.pack("<f", x)；与密文进行 XOR

完整代码参见 prng.md。

SPN S 盒交集攻击

分而治之的 SPN 密钥恢复：分别攻击每个 S 盒位置，并在多个明文-密文对之间求合法密钥候选的交集。将指数级密钥空间缩减为相互独立的子密钥搜索。参见 modern-ciphers-3.md。

实用工具

• Python： pip install pycryptodome z3-solver sympy gmpy2
• SageMath（可选备用方案）： sage -python script.py — 仅适用于简化后的 Sage 替代方案
• RsaCtfTool： python RsaCtfTool.py -n <n> -e <e> --uncipher <c> — 自动化 RSA 攻击套件（尝试 Wiener、Hastad、Fermat、Pollard 等多种攻击）
• quipqiup.com： 自动替换密码求解器（频率和单词模式分析）