The Thirteen Seals of RSA：13 关 RSA 弱点串烧
这题的设计我非常喜欢：13 关，每关一个经典 RSA 弱点，各加密 flag 的一段，按顺序拼接就是完整 flag。
段长：11×3 字节 + 1×5 字节 + 1×7 字节 = 45 字节
FLAG[PART_STARTS[i-1] : PART_STARTS[i-1]+PART_LENS[i-1]]基本等于把 CryptoHack 的 RSA 章节串成一条链，做一遍就是一次系统复习。
关卡速查表
| 关 | 段 | 弱点 | 手法 |
|---|---|---|---|
| 01 | TSC | m^11 < n | 直接整数开 11 次根 |
| 02 | TF- | e=3，只溢出一点点 | 穷举 k<1000：m³ = c + kn |
| 03 | J{H | Rabin，p,q ≡ 3 (mod 4) | 模平方根，4 个根 + 约束筛选 |
| 04 | app | d 只有 64 bit | Wiener 连分数攻击 |
| 05 | y_R | 同明文、e=3、三组公钥 | Håstad 广播：CRT 后开立方 |
| 06 | SA_ | p−1 是 1000-光滑 | Pollard p−1 |
| 07 | Lea | p+1 光滑 | Williams p+1（Lucas 序列） |
| 08 | rni | 同一个 n，e1=65537, e2=17 | 共模攻击（扩展欧几里得） |
| 09 | ng_ | dp, dq 泄露 | CRT 合并两次解密 |
| 10 | wit | dp 泄露，e=257 很小 | 穷举 k < e |
| 11 | h_C | dp 泄露，e 是 128 bit | gcd(a^(e·dp) − a, n) |
| 12 | rypto | 已知 e, d | ed−1 = 2^t·r 分解 n |
| 13 | hack!!} | 已知 p ⊕ q | 从低位逐位剪枝 |
几个值得记的点
整数开根不能偷懒用浮点
第 1 关 m^11 < n，直接用 int(c ** (1/11)) 会因为浮点精度在多字节整数上丢位。必须写整数牛顿迭代：
def iroot(n, k):
"""整数 k 次根（向下取整）"""
x = 1 << ((n.bit_length() + k - 1) // k)
while True:
y = ((k - 1) * x + n // x ** (k - 1)) // k
if y >= x:
break
x = y
while x ** k > n:
x -= 1
while (x + 1) ** k <= n:
x += 1
return x最后那两行”微调”很关键——牛顿迭代收敛到的是近似值，大整数下差 1 就全错。
第 13 关：已知 p ⊕ q 的逐位剪枝
这关是整题最难的。已知 n 和 p ^ q（异或），要求分解 n。
思路是从最低位往高位逐位确定 p 和 q：
# 已知低 i 位，试 p_bit ∈ {0,1}，q_bit = p_bit ^ xor_bit
# 剪枝条件：低位乘积必须等于 n 的低位
def factor_from_xor(n, pxorq, bits):
cands = [(0, 0)]
for i in range(bits):
nxt = []
xb = (pxorq >> i) & 1
for p, q in cands:
for pb in (0, 1):
qb = pb ^ xb
np_ = p | (pb << i)
nq_ = q | (qb << i)
# 低 i+1 位乘积必须匹配 n 的低 i+1 位
if (np_ * nq_) & ((1 << (i + 1)) - 1) == n & ((1 << (i + 1)) - 1):
nxt.append((np_, nq_))
cands = nxt
return cands关键在剪枝条件：如果 p 和 q 的低 i+1 位正确，那么 p·q 的低 i+1 位必然等于 n 的低 i+1 位。这一条把搜索空间死死压住，每一步候选数都很少。
Håstad 广播为什么有效
第 5 关同一明文用 3 组互质模数、都是 e=3 加密。CRT 合并后得到 m³ mod (n1·n2·n3)，而 m³ < n1·n2·n3，所以那个同余式就是真正的 m³，直接开立方即可。
这就是”广播攻击”的本质：不是密码学被破，而是信息量给多了。
踩坑
| 问题 | 原因 | 解决 |
|---|---|---|
| 开根结果差 1 | 浮点精度丢失 | 整数牛顿迭代 + 后置微调 |
| Rabin 出 4 个根 | 数学上本来就有 4 个 | 用”结果必须是合法 ASCII”筛选 |
| Wiener 攻击误判 | 连分数收敛需要判据 | disc = (n−φ+1)² − 4n 必须是完全平方 |
| Pollard p−1 卡住 | 界 B 给小了 | 逐步加 B（1000 → 5000 → 20000） |
小结
做完这题最大的收获不是记住 13 种攻击，而是形成了一个判断流程：
e小不小？（1/2/3/5/17/65537）m大不大？m^e有没有超过n？- 有没有额外泄露？（
dp、dq、d、p⊕q、φ(n)） - 有没有多组密文？（同模 → 共模；不同模同明文 → 广播）
n本身有没有规律？（p−1/p+1光滑 → Pollard/Williams）
按这个顺序走一遍，绝大多数 RSA 题都能定性到具体攻击。