从CTF实战到原理剖析：RSA共模攻击的数学之美与脚本实现

1. 从一道CTF赛题看RSA共模攻击实战

第一次遇到BUUCTF的RSA3题目时，我盯着两组密文和公钥参数发了半天呆。题目给出了两个加密结果c1、c2，以及相同的模数n和不同的加密指数e1、e2。按照常规RSA思路，没有私钥d根本无法解密，但这里却藏着精妙的数学机关——当两个加密指数互质时，我们就能上演"空手套白狼"的好戏。

具体题目参数如下：

• 模数n = 22708078...（2048位大整数）
• 第一组公钥e1=11187289，密文c1=22322035...
• 第二组公钥e2=9647291，密文c2=18702010...

实战中我注意到三个关键点：首先，两组密文对应同一个明文；其次，模数n完全相同；最重要的是，通过gcd验证发现e1和e2确实互质。这就像找到了两把不同锁孔的钥匙，虽然单把钥匙打不开保险箱，但组合使用就能破解机关。

2. 共模攻击的数学心脏：扩展欧几里得算法

这个攻击最精妙之处在于运用了扩展欧几里得算法。我刚开始理解这个原理时，总觉得像在变魔术——明明没有私钥d，怎么就能算出明文呢？后来画了无数张演算纸才明白，关键在于构造出e1s1 + e2s2 = 1这个等式。

具体推导过程是这样的：

1. 由于gcd(e1,e2)=1，存在整数s1、s2使得e1s1 + e2s2 = 1
2. 根据RSA加密原理：
   • c1 ≡ m^e1 mod n
   • c2 ≡ m^e2 mod n
3. 将两个等式变形后相乘：
   • c1^s1 ≡ m^(e1*s1) mod n
   • c2^s2 ≡ m^(e2*s2) mod n
4. 乘积结果： c1^s1 * c2^s2 ≡ m^(e1s1+e2s2) ≡ m^1 ≡ m mod n

这个推导就像搭积木，每一步都严丝合缝。特别要注意s1或s2可能是负数，这时需要用到模反元素。比如当s1为负时，要先计算c1关于n的逆元，再对结果的绝对值求幂。

3. Python实现中的五个技术细节

把数学公式转化成代码时，我踩过几个坑。最初写的脚本在处理负数指数时总是报错，后来才明白需要引入模反元素。这里分享优化后的代码关键点：

from gmpy2 import invert import binascii def egcd(a, b): if b == 0: return a, 0 else: x, y = egcd(b, a % b) return y, x - (a // b) * y def gongmo(n, c1, c2, e1, e2): s1, s2 = egcd(e1, e2) # 处理负数指数 if s1 < 0: c1 = invert(c1, n) s1 = -s1 if s2 < 0: c2 = invert(c2, n) s2 = -s2 m = pow(c1, s1, n) * pow(c2, s2, n) % n return m

这段代码有五个技术要点：

1. 使用gmpy2库处理大整数运算
2. 递归实现扩展欧几里得算法
3. 负数指数处理流程
4. 模幂运算的链式调用
5. 最终结果的模约简

实际运行时会发现，当n是2048位大数时，普通Python的pow函数会很慢，这就是为什么我们要用gmpy2的原因。在我的测试中，优化后的脚本解密题目只需0.3秒左右。

4. 防御方案与攻击变种

理解了攻击原理后，我自然想到如何防御。最直接的方法是确保不同用户使用不同的模数n，但这在PKI体系中难以实施。更实用的方案是：

1. 加密时添加随机填充（如OAEP）
2. 避免使用互质的加密指数对
3. 对相同明文的不同加密版本进行关联检测

在更复杂的场景中，共模攻击还有这些变种：

• 多组密文攻击（当有c1,c2,c3...时）
• 部分密钥暴露攻击
• 结合中国剩余定理的攻击

有个有趣的发现：如果e1和e2不互质但gcd(e1,e2)=g，仍然可以计算m^g mod n。当g较小时，可以通过开方运算恢复明文。这提醒我们，密钥生成时不仅要考虑单个密钥的安全性，还要考虑密钥对之间的关系。

5. 密码学竞赛中的实战技巧

打CTF比赛时，识别共模攻击场景有这些特征指纹：

• 题目给出多组密文
• 模数n相同但e不同
• 提示"共享模数"或"common modulus"
• 密文长度相同且前缀相似

我常用的诊断流程是：

1. 检查所有模数是否相同
2. 计算所有e的gcd
3. 验证密文是否同源
4. 尝试构造贝祖等式

在去年某次比赛中，就遇到过一个变种题：题目给出了三组密文，要求至少用两组解密。这其实就是共模攻击的高阶应用，需要选择最合适的e对来构造等式。当时我用了e1和e3的组合，因为它们的gcd计算最稳定。

6. 从理论到实践的深度思考

最初学这个攻击时，我以为只是又一种解题技巧。但后来在分析某区块链项目的签名方案时，意外发现了类似的漏洞。这才意识到，教科书上的攻击方法在真实世界中依然存在。

一个值得深思的现象：很多开发者知道要用不同的n，但在密钥轮换场景中，为方便起见还是会复用模数。我曾审计过一个系统，他们的密钥生成逻辑存在缺陷，导致每批密钥的n都相同，只是e不同——这简直就是为共模攻击量身定做的靶场。

密码学实现就像走钢丝，理论上的安全边界很清晰，但工程实践中总会因为各种"合理"的妥协而留下隐患。共模攻击的魅力就在于，它用优雅的数学公式揭示了一个朴素的道理：在密码系统中，任何形式的复用都可能成为阿喀琉斯之踵。