文章Articles

RSA 题目的判断顺序

拿到一堆 n、e、c 之后先算什么，六种常见攻击的适用条件，以及怎么快速排除。

更新Updated 2026.10.25securityctfcryptorsa

先看给了什么

RSA 题目的信息量全在附件里。打开先扫一遍，看有几个数：

这一步做完，一半的题已经能定位方向了。

一、小公钥指数（e=3 且 m³ < n）

条件：e 很小，m 不长。直接对 c 开 e 次方根：

import gmpy2
m = gmpy2.iroot(c, 3)[0]

开出来是整数，就是明文。开不出来，说明 m³ > n，得用广播攻击。

二、低指数广播

同一明文用同一个 e（通常是 3），发给三个不同的 n。用中国剩余定理合并 c，再开方。

三、模不互素

给了两个 n。算 gcd(n1, n2)，如果不等于 1，那就是共享了一个质因子：

p = gmpy2.gcd(n1, n2)
q1 = n1 // p

这类题在真实世界里也出现过——随机数生成器质量差，两个密钥撞了同一个质数。看到 n1 和 n2，先算 gcd，一秒钟的事。

四、共模攻击

同一个 n，两个互素的 e，同一明文。用扩展欧几里得求 a、b 使 ae1 + be2 = 1，然后：

m = c1^a * c2^b mod n

五、维纳攻击（d 很小）

e 特别大（接近 n），说明 d 很小。用连分数展开 e/n，逼近 k/d，逐个试。

六、已知高位

给了 p 的高位或者 d 的高位。用 Coppersmith 的格方法，sage 里有现成实现。

不知道用哪种的时候，按这个顺序试，每一步都很便宜：

1. gcd(n1, n2) 有多个 n 时
2. iroot(c, e) 当 e 很小时
3. e 和 n 位数差不多 → 试维纳
4. e 很大且 n 是偶数 → 试 Rabin
5. 以上都不行 → 看有没有 hint，或者是不是别的题型伪装成 RSA

密码学里有一半是编码，不是加密。识别靠特征：

Base64 套娃是常见套路。写个循环自动解，解到不能再解为止，比手工试快。

还有一类：给了段 JS 代码，说「在浏览器控制台运行」。那基本是前端混淆，扔进控制台看输出，或者用 JS 反混淆工具还原。

古典密码的题目通常有提示：要么标题暗示（Rot、栅栏、猪圈），要么密文有明显的结构特征。

凯撒和 ROT 系先暴力跑 26 个位移，看哪个出可读文本。栅栏按栏数试。维吉尼亚需要密钥长度，用卡西斯基测试或者重合指数法估。

这些都不需要技巧，需要的是别在一条路上死磕。试了十分钟没进展，换方向。