很多人学密码学喜欢背攻击点：什么低加密指数、共模攻击、彩虹表、时序侧信道，背得滚瓜烂熟，可一问“为什么低指数广播攻击需要三个密文？”就卡住了。我的观点是：安全的本质是对数学结构的理解，不是背口诀。今天拿 RSA“低加密指数广播攻击”开刀，从中国剩余定理讲起，把它的数学底裤彻底翻出来，顺便聊聊这个经典攻击给我们做系统设计埋下的几个警告。
这篇文章适合三类人：学过 RSA 但只会调库的开发者、准备面试但怕被问原理的后端工程师、以及做安全设计时需要向团队解释“为什么不能用小公钥指数”的架构师。读完你不但能在纸上推导一遍完整攻击，还能用代码从零复现一次，更重要的是，你会明白为什么教科书 RSA 几乎不能直接用在生产环境。
1. 核心前提：RSA 的数学骨架与公钥指数
1.1 RSA加解密到底在算什么
先把基础骨架搭起来。RSA 的密钥生成过程是：
- 随机选两个大素数 p 和 q。
- 计算模数 n = p × q，n 的位数就是密钥长度。
- 计算欧拉函数 φ(n) = (p−1)(q−1)。
- 选一个公钥指数 e，要求 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。
- 计算私钥指数 d，满足 e × d ≡ 1 mod φ(n)。
加密时，把明文 m 看成一个大整数，满足 0 ≤ m < n，计算密文：
c = m^e mod n
解密时，恢复明文：
m = c^d mod n
m^e mod n 能还原成原始明文，核心靠的是欧拉定理：因为 e × d ≡ 1 mod φ(n)，所以存在整数 k 使得 e×d = 1 + kφ(n)，于是：
c^d ≡ (m^e)^d ≡ m^(e×d) ≡ m^(1 + kφ(n)) ≡ m × (m^φ(n))^k ≡ m mod n
当 gcd(m, n) = 1 时，欧拉定理直接给出 m^φ(n) ≡ 1 mod n；如果 m 和 n 不互素，其实也能推导出相同的结果，只是证明过程要多绕一步，这里不展开。
题外话：教科书 RSA 说的是这种最原始、没有任何填充的加密形式。实际生产环境里的 RSA 全是带填充的，比如 OAEP。为什么要填充？这就是今天攻击的核心伏笔，你先记住。
1.2 公钥指数 e 为什么不能随便选
公钥指数 e 负责加密，理论上任选，实际中常见的是 65537，也就是 0x10001。为什么不选 3？因为 e 太小时，一旦触发特定条件，攻击成本会断崖式下跌，尤其“低加密指数广播攻击”就是教科书级例子。
e = 65537 有双重好处：二进制是10000000000000001，只有两个 1，做模幂运算时平方次数可控，速度不慢；同时它足够大，能避开小指数带来的解析攻击。你会看到很多库默认就用 65537，面试官问“为什么不选 3”时，答案就藏在本文的攻击原理里。
此外，加密过程中要求 m 和 n 的关系很微妙：明文 m 的数值必须小于 n。实际操作中，m 是填充后的字节串转成的大整数，填充方式不同，m 的取值空间也不同。攻击里对 m 的大小有硬性要求，后面推导时会看到这个约束有多关键。
2. 攻击场景：什么时候触发广播条件
2.1 一封密信被“广播”给了三个人
低加密指数广播攻击的触发条件非常苛刻，也正因为苛刻，才容易被忽略。
假设有一个组织要向三位接收者发送同一条机密消息。发送方出于性能考虑（或者根本没想清楚安全性），把公钥指数统一设成了 e = 3。三位接收者的模数分别是 n1、n2、n3，彼此互不相同，但都远大于消息转换的整数 m。
于是发送方做了三次加密：
c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3
攻击者通过流量监听、日志截获或某些不安全的传输渠道，拿到了三份密文 c1、c2、c3 以及对应的公钥 (n1, e)、(n2, e)、(n3, e)。这就像一封密信被抄送给了三个人，而这三个人还都用了同样的锁型号，攻击者不需要撬开任何一把锁，只需要把三份密文“合并”一下，锁就自己开了。
注意，广播攻击里“广播”这个词指的是同一个明文被加密后发往多个接收方，不是说攻击者在网络上广播密文。这个理解很容易搞错。
2.2 为什么至少需要三份密文而不是两份
这是最值得聊的地方。
当 e = 3 时，加密关系是 c_i ≡ m^3 mod n_i。攻击者的目标是求解 m，而不是去分解 n_i，也不是去求私钥 d。如果只有一份密文 c1，想要直接解同余方程 c1 ≡ m^3 mod n1，太难了，因为 m^3 可能加了无数个 n1 的整数倍。
如果有两份密文，你可以列出同余式：
m^3 ≡ c1 mod n1
m^3 ≡ c2 mod n2
依然很难确定 m^3 到底是多少。但三份密文就不一样了。假设 m < min(n1, n2, n3)，那么显然：
m^3 < n1 × n2 × n3
因为三个 n_i 都大于 m，乘积自然大于 m^3。而中国剩余定理可以构造出一个整数 T，满足：
T ≡ c_i mod n_i (i = 1, 2, 3)
且 0 ≤ T < n1 × n2 × n3。同时，真正的整数 m^3 也满足同样的三条同余关系。由于 T 和 m^3 都在同一个范围内，而且模数乘积远大于它们，所以 T 只能等于 m^3。
于是攻击者只要从密文里恢复出整数 T，再对 T 开三次方根，就能得到明文 m。
如果只有两份密文，攻击者同样能构造出 T 满足两条同余关系，但 T 的取值空间是 n1×n2，此时 m^3 一定小于 n1×n2 吗？不一定。因为 m 可能和 n2 差不多大小，m^3 可能超过 n1×n2，这时 T 可能是 m^3，也可能是 m^3 + k × n1 × n2，无法唯一确定。所以教科书上通常说“低加密指数广播攻击需要至少 e 份密文”，本质是：密文份数要凑够，让模数乘积大于明文 e 次幂。
3. 中国剩余定理：攻击的核心引擎
3.1 从“分治”到“合体”的数学魔法
中国剩余定理是个很反直觉的定理。直觉上，给出一堆模不同模数的余数，信息是分散的；但 CRT 告诉你，当这些模数两两互素时，这些余数能唯一确定一个在 0 到模数乘积之间的整数。
用人话解释：一个数对 5 取余等于 2，对 7 取余等于 3，这个数在 0 到 35 之间只能是 17。CRT 就是给出一套系统方法，把这个 17 算出来。
公式如下。设模数 N1, N2, ..., Nk 两两互素，给定同余方程组：
x ≡ a1 mod N1
x ≡ a2 mod N2
...
x ≡ ak mod Nk
令 N = N1 × N2 × ... × Nk，对每个 i，令 M_i = N / N_i，再求 y_i 为 M_i 在模 N_i 下的乘法逆元，即：
M_i × y_i ≡ 1 mod N_i
那么方程组的唯一解是：
x ≡ Σ (a_i × M_i × y_i) mod N
注意，攻击场景里 n1、n2、n3 是三个接收者的 RSA 模数，它们本质上由各自独立选出的素数构成，两两互素的概率极高。万一其中两个模数恰好有公共因子，那攻击者的路更好走了，直接求公因数就能分解出私钥，根本不用 CRT。所以在攻击模型里，我们总是假设这三个模数两两互素。
3.2 为什么 CRT 组合出来的数恰好是 m^3
回到广播攻击。我们把 CRT 中的 a_i 替换成密文 c_i，N_i 替换成 n_i，就能构造出 T，满足：
T ≡ c1 mod n1
T ≡ c2 mod n2
T ≡ c3 mod n3
因为原始加密关系是 c_i ≡ m^3 mod n_i，那么 m^3 显然也满足上面三条同余式。于是得到两个数：T 和 m^3，它们对 n1、n2、n3 的余数完全相同。
利用“差值是公倍数”的思路：T − m^3 能被 n1、n2、n3 分别整除，也就是说 T − m^3 是 n1、n2、n3 的公倍数。由于 n1、n2、n3 两两互素，它们的公倍数就是 n1×n2×n3 的整数倍。
这时，再用大小比较强行卡死：0 ≤ T < n1×n2×n3，0 ≤ m^3 < n1×n2×n3。所以 |T − m^3| < n1×n2×n3。而 T − m^3 又是 n1×n2×n3 的倍数，唯一的可能是 0。于是 T = m^3。
这就是整个攻击里让我觉得最精巧的部分——CRT 负责把分散在三方的余数条件合并成一个确定数，大小约束负责保证这个数不是“别的版本”，二者缺一不可。
3.3 明文大小条件：不是所有消息都能被打穿
如果 m 太大，比如 m 已经接近 n1，m^3 会大于 N = n1×n2×n3 吗？
假设 n1、n2、n3 都是 2048 位，乘积大约是 6144 位。m 是填充后的明文整数，通常要求小于每个 n_i，理论上可能是 2040 位。2040 位乘以指数 3，大约是 6120 位，仍小于 6144 位乘积，所以攻击依然成立。
但如果是极端情况，比如三个模数中有一个特别小，或者发送方用同一个明文 m 却对每人用了不同的消息编码方式，导致某个接收者的 m_i 并不小于 n_i，那么条件就可能被打破。另一种常见失败原因：发送方向不同接收者发送的“同一条消息”其实被填充成了不同的字节串，m 已经不是同一个整数。这一点在真实系统中几乎决定了攻击是否成立，后面防御部分还会细说。
4. 完整复现：从生成密钥到一键破解
4.1 先构造一个可被攻击的实验环境
为了把原理落到代码里，我用 Python 模拟一次完整攻击。这里用的是教科书 RSA，不带填充，重点展示数学攻击的代码路径。
首先生成三组密钥。为了演示速度，我把素数位数设小一点，比如 512 位，但这不会影响攻击逻辑：
import random def is_probable_prime(n, rounds=32): if n < 2: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]: if n % p == 0: return n == p d = n - 1 r = 0 while d % 2 == 0: d //= 2 r += 1 for _ in range(rounds): a = random.randrange(2, n - 1) x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def gen_prime(bits): while True: p = random.getrandbits(bits) p |= (1 << (bits - 1)) | 1 if is_probable_prime(p): return p def gen_keypair(bits=512): p = gen_prime(bits) q = gen_prime(bits) n = p * q phi = (p - 1) * (q - 1) e = 3 d = pow(e, -1, phi) return (n, e), (n, d) keys = [gen_keypair() for _ in range(3)] ns = [k[0][0] for k in keys] e = 3 message = b"CVE-2024-DEMO: broadcast attack test" m = int.from_bytes(message, "big") print("m < min(n_i)?", m < min(ns)) ciphertexts = [pow(m, e, n) for n in ns]注意一个关键点：密文的生成是pow(m, e, n)，m 必须是整数，不能加随机填充。这正好对应“教科书 RSA”。
4.2 攻击代码：CRT合并 + 整数开三次方
接下来实现 CRT 的合并，以及整数开立方根。很多人在这里踩坑：直接用浮点数m ** (1/3)，大整数会丢失精度，必须用整数立方根。
def egcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = egcd(b, a % b) return g, y1, x1 - (a // b) * y1 def modinv(a, m): g, x, _ = egcd(a, m) if g != 1: raise ValueError("no inverse") return x % m def crt(remainders, moduli): total = 0 N = 1 for modulus in moduli: N *= modulus for r, mod in zip(remainders, moduli): Mi = N // mod yi = modinv(Mi, mod) total = (total + r * Mi * yi) % N return total def iroot(n, k): if n < 0: raise ValueError("negative n") if n == 0: return 0 x = 1 << ((n.bit_length() + k - 1) // k) while True: y = ((k - 1) * x + n // pow(x, k - 1)) // k if y >= x: return x x = y combined = crt(ciphertexts, ns) m_recovered = iroot(combined, 3) assert m_recovered == m, "recovery failed" print("recovered message:", m_recovered.to_bytes((m_recovered.bit_length() + 7) // 8, "big"))这段代码的核心逻辑就两步：
crt()把三个同余式合并成一个大整数combined。iroot()对combined开立方，得到原始整数明文。
为什么iroot用牛顿迭代？因为大整数开方不是简单调用**就能完成的，Python 的**在指数非整数时走浮点路径，超过 2^53 就会丢失精度。iroot每次迭代都在整数域上逼近，收敛速度很快，一般十几次迭代就稳定了。
4.3 如果遇到正常填充，攻击会怎样
上面的攻击建立在 m 完全一致的前提下。如果发送方用的是 PKCS#1 v1.5 或 OAEP 填充，那么即使待加密的原本消息一样，填充后的字节串也不同。具体到广播场景：
- 同一个业务消息，发给三个人，每个人收到的 padding 字节可能相同也可能不同。
- RSA-OAEP 带随机种子，三次填充结果几乎必然不同，导致 m1 ≠ m2 ≠ m3。
- CRT 合并时，三条同余式对应的底数都不一样，T 不再是某个确定的 m^3，攻击就失效了。
这说明低指数广播攻击的命门不在“指数小”，而在“明文完全可预测且无随机化”。历史上很多真实漏洞也源于此，比如某些协议里直接加密同一个对称密钥，密钥本身缺少随机填充，配合 e = 3 就出大事。
5. 防御不是“把 e 换大”这么简单
5.1 不要解方程，要让攻击者无方程可解
很多人学完广播攻击，第一反应是“那把 e 改成 65537 就安全了”。这个说法对了一半。
把 e 调大确实让“广播攻击”变得不现实，因为你至少需要 65537 个接收者拥有相同的加密指数，才能用同样的方法合并。但低指数还有其他衍生攻击，比如 Coppersmith 方法在 e 较小且明文高位已知时，也可能直接恢复明文。换句话说，低指数本来就是一个系统性风险，不只是广播这一条路。
更本质的问题是：教科书 RSA 是确定性加密。同一个明文乘以同一个指数，永远得到同一个密文，这种数学上的“确定性”给了攻击者可乘之机。所以现代 RSA 加密标准强制使用 OAEP 或至少 PKCS#1 v1.5 填充，填充引入了随机性，同一明文每次加密的密文都不同。
生产环境里我见过不少人把“填充”视为可有可无的东西，觉得“反正我消息不长，加个 0 就行”。这个想法很危险。填充的设计不只是为了让 m 变大，而是为了打破数学结构。RSA-OAEP 中有 MGF1 掩码生成函数和随机种子，即使你知道原始消息内容，也无法预知填充后的整数 m。
5.2 从“广播攻击”反推的几条工程铁律
这个攻击能教会我们的，远不止 RSA 本身。
第一，同一个系统里多个接收方共用同一个加密指数，本身要警惕。在真实的密钥管理流程里，即使大家默认用 65537，也有人为了“性能优化”偷偷改成小指数，这种设备一旦出现在同一个消息的收件列表里，就是一颗定时炸弹。
第二，消息层面的随机化比密钥长度更关键。密钥长到 4096 位，如果明文结构可预测且没有随机化，依然存在被结构性攻击的风险。广播攻击只是这种风险最直观的表现形式。
第三，协议设计者要区分“认证”和“加密”场景。RSA 加密要填充，RSA 签名需要 PSS，两者填充方案不能互换。用加密方案给消息做签名，等于把私钥运算暴露给选择明文攻击，那又是一套完全不同的攻击面。
6. 常见坑位与排查实录
6.1 为什么我的攻击代码经常失败
我在带团队复现这个攻击时，最常见的失败原因有三个，建议你对照排查：
- 明文字节序问题。
int.from_bytes(message, "big")和.to_bytes(..., "big")必须保持一致。有人喜欢用 little endian，CRT 算出来的数虽然能解析成字节，但内容会乱。 - 模数之间有公因子。如果两个 n 共享素数，CRT 的互素假设失效。要先用 gcd 检查，查出公因子之后直接分解 n，反而更简单。
- 填充干扰。真实加密流程里几乎所有库都不会对短消息直接做教科书 RSA，即使你指定 e = 3，OpenSSL 或各种密码库也会默认加 OAEP。你做实验时要先把填充关掉。
下面是一段简短的调试代码片段：
for i, j in [(0, 1), (0, 2), (1, 2)]: g = egcd(ns[i], ns[j])[0] if g != 1: print("common factor found:", g)如果发现公共因子，直接用d = pow(e, -1, (p-1)*(q-1))算私钥，压根不需要 CRT 广播。这算是攻击里的“意外惊喜”路径。
6.2 生产环境排查清单
如果你是安全运维或架构评审人员，可以用下面这个清单快速评估系统里是否存在低指数风险：
- 检查 RSA 公钥的 e 值。低于 65537 的一律打黄牌，等于 3 的直接红牌。
- 检查加密路径是否使用 OAEP。凡是教科书 RSA 调用，一律制止。
- 检查同一个 e 值下，是否有同一业务消息被发往多个接收方。若有，即使 e 是 65537，也应审查填充方案。
- 检查日志中是否出现大量“加密失败重试”的记录，某些实现会在 OAEP 解码失败时回退到无填充路径，这个回退本身就是灾难。
我在实际项目中踩过这样一个坑：某内部系统的加密服务为了兼容老设备，保留了“无填充模式”开关，默认关闭，但某次配置迁移时开关被误打开，e 也被一个没读过文档的同事顺手改成了 3。事后排查日志，发现攻击者已经能对部分消息做有效解密。所以，安全检查不能只看代码逻辑，还要看配置项和默认值。
6.3 另一个容易被忽视的细节：密文规模
CRT 合并出的整数 T 是 N = n1×n2×n3 的量级。如果三个 n 都是 2048 位，T 就是 6144 位。开三次方之后才回到约 2048 位。这个中间膨胀很容易让某些实现溢出，尤其是用 C/C++ 处理时，定长缓冲区直接爆掉。
Python 的大整数没有这个问题，但如果你用别的语言，建议先估算 N 的字节数，预留足够空间，再用定点数或大数库处理。这个点听起来很小，但在工程实现里非常容易变成隐藏故障。
7. 写在最后：攻击是最好的一堂课
我把这个攻击完整走一遍之后，最大的感受是：密码学攻击的名字听起来高深，但本质上就是在“数学方程的可解性”上做文章。低加密指数广播攻击没有破解 RSA 本身，它只是利用了同余方程组在特定条件下的唯一确定性。理解这一点，比记住“e=3危险”重要得多。
如果只让我留一个小技巧，那就是：在分析任何密码协议时，永远假设攻击者知道算法、知道参数、知道你的密文数量，然后问自己，在这样透明的模型里，我的设计还能不能扛得住？这个思维模式，比任何密码库的安全默认值都管用。
