RSA加密算法攻击：从数学原理到CTF实战攻击（CTF实战概念篇）
文章目录
- 前言
- 一、先建立一个“攻击全景图”
- 二、基础攻击
- 1、因式分解 n（最直接）
- 2、小指数攻击（e 很小）
- 3、共模攻击（Common Modulus Attack）
- 4、广播攻击（Håstad Attack）
- 三、进阶攻击
- 5、Wiener Attack（小 d 攻击）
- 6、已知部分信息（Coppersmith）
- 7、低熵 / 弱随机数
- 四、真实世界攻击
- 8、Padding Oracle（最经典）
- Side Channel（侧信道攻击）
- 五、CTF 解题思维
- Step 1：看 n
- Step 2：看 e
- Step 3：看密文数量
- Step 4：看提示
- Step 5：看 padding
- 小结
前言
学习这篇文章（其实是共同学习了），只要从知道RSA属于密码学中的Public Key Cryptography（公钥密码学）这个概念开始。如果读者说还不知道这个概念，那么，读者现在应当是知道了，RSA是非对称密码，属于公钥密码学。就可以开始学习实现从零到能打CTF的入门的这一系列。
这是上一篇的前言，复制了一下，学习这一篇，请先学习：
RSA算法详解：从原理到实现（全且深入浅出）
这是系列二，旨在讲解CTF比赛中RSA加密算法可利用的攻击。
一、先建立一个“攻击全景图”
RSA 攻击本质几乎都在利用这三类问题：
1. 数学结构漏洞
- n 被分解
- d 太小
- e 不合理
- 使用方式错误
- 重复使用 n
- 多次加密同一消息
- 没有 padding
- 实现漏洞（真实世界）
- padding oracle
- side-channel（侧信道）
对于正常的CTF来说，首先要学习的是数学结构漏洞。
怎么说。
RSA 本身很安全，出问题的是“人怎么用它”
二、基础攻击
1、因式分解 n（最直接）
- 条件：
n = p × q
p 或 q 太小 / 太接近 - 方法：
直接分解 n - 一旦分解：
φ(n) = (p-1)(q-1)
求 d → 解密
回顾之前的文章：
本质攻击的是：整数分解问题（Integer factorization problem）。
2、小指数攻击（e 很小）
常见：e = 3
如果：
m e < n m^e<nme<n
那么实际上没有发生 mod 运算。
c = m e c=m^ec=me
直接开方：
m = c e m = \sqrt[e]{c}m=ec
道理简单，但是 CTF 里非常常见！
3、共模攻击（Common Modulus Attack）
条件：
- 同一个 n
- 不同 e
- 同一个 m
c 1 = m e 1 , c 2 = m e 2 c_1 = m^{e_1}, \quad c_2 = m^{e_2}c1=me1,c2=me2
且:
gcd ( e 1 , e 2 ) = 1 \gcd(e_1, e_2) = 1gcd(e1,e2)=1
核心思路：
用扩展欧几里得：
a e 1 + b e 2 = 1 a e_1 + b e_2 = 1ae1+be2=1
那么:
m = c 1 a ⋅ c 2 b m o d n m = c_1^a \cdot c_2^b \mod nm=c1a⋅c2bmodn
本质利用的是：指数“线性组合可逆”
4、广播攻击（Håstad Attack）
条件：
- 同一个 m
- 不同 n
- 相同 e（通常 e=3）
用 Chinese Remainder Theorem：
合并多个密文 → 得到：
m e m^eme
再开 e 次方 → 得 m
本质：“多次加密反而泄露信息”
三、进阶攻击
5、Wiener Attack（小 d 攻击）
条件：
d 很小
满足大约：
d < 1 3 n 1 / 4 d < \frac{1}{3} n^{1/4}d<31n1/4
方法：
- 连分数展开 e/n
- 恢复 d
本质：私钥太“简单”
6、已知部分信息（Coppersmith）
条件：
- 知道 p 的一部分
- 或 m 的一部分
使用： - 格攻击（LLL）
本质：“已知一点点 → 推出全部”
7、低熵 / 弱随机数
如果：
p、q 生成不好或重复
会出现：
不同 n 有公共因子
直接：
gcd ( n 1 , n 2 ) ≠ 1 \gcd(n_1, n_2) \ne 1gcd(n1,n2)=1
四、真实世界攻击
8、Padding Oracle（最经典）
针对：
- PKCS#1 v1.5
核心思想：
攻击者：
- 不断试探密文
- 观察“是否合法”
逐步恢复明文
典型攻击：Bleichenbacher Attack
属于 Cryptanalysis
Side Channel（侧信道攻击）
不是攻击数学，而是攻击实现：
比如：
时间（Timing Attack）
功耗（Power Analysis）
缓存（Cache Attack）
例子：
解密时间不同 → 推出 d
五、CTF 解题思维
Step 1：看 n
能不能分解？
多个 n 是否有 gcd？
Step 2：看 e
是否很小（3 / 5）？
是否多个 e？
Step 3：看密文数量
是否重复加密？
是否多个模数？
Step 4：看提示
是否泄露部分 p / d / m？
Step 5：看 padding
是否“裸 RSA”？（最危险）
小结
为什么是概念篇？因为这个密码学的学习给个概念，理解就可以了，这里给出例子，给出代码，用处不大，主要还是自己做题。
推荐一题
2026软件系统安全赛初赛RSA