CTF实战：手把手教你用Python脚本破解RSA共模攻击（附完整代码）

当你第一次在CTF比赛中遇到RSA共模攻击题目时，可能会感到无从下手。别担心，这篇文章将带你从零开始，一步步理解攻击原理，并亲手编写Python脚本破解这类题目。我们会以一个真实的CTF题目为例，详细讲解每个步骤和可能遇到的坑。

1. 认识RSA共模攻击

RSA共模攻击（Common Modulus Attack）是一种针对RSA加密系统的攻击方式。它发生在以下场景：

• 相同的明文m用相同的模数n但不同的公钥指数e1和e2加密
• 对应的密文分别为c1和c2
• 攻击者知道n、e1、e2、c1和c2

关键点 ：当e1和e2互质（gcd(e1,e2)=1）时，我们可以利用扩展欧几里得算法恢复出明文m，而无需知道私钥d。

注意：这种攻击之所以有效，是因为使用了相同的模数n加密相同的信息。在实际应用中，绝对不应该重复使用相同的模数。

2. 数学原理深入解析

要理解共模攻击，我们需要掌握几个关键数学概念：

2.1 扩展欧几里得算法

这个算法不仅能计算两个数的最大公约数，还能找到满足贝祖等式（Bézout's identity）的整数系数：

对于整数e1和e2，如果gcd(e1,e2)=1，那么存在整数s和t，使得：

e1*s + e2*t = 1

2.2 攻击的核心推导

给定：

c1 ≡ m^e1 mod n
c2 ≡ m^e2 mod n

利用扩展欧几里得算法找到s和t后，我们可以计算：

m = (c1^s * c2^t) mod n

这是因为：

c1^s * c2^t ≡ (m^e1)^s * (m^e2)^t ≡ m^(e1*s + e2*t) ≡ m^1 ≡ m mod n

2.3 处理负指数

在实际计算中，s或t可能为负数。这时需要使用模逆元来处理：

如果s为负数：

c1^s ≡ (c1^{-1})^{-s} mod n

其中c1^{-1}是c1在模n下的逆元。

3. 实战演练：破解SWPUCTF题目

让我们以SWPUCTF 2021新生赛的crypto2题目为例，一步步破解。

3.1 题目分析

题目给出了以下数据：

flag1= 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
flag2= 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1= 3247473589
e2= 3698409173
n= 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

3.2 环境准备

首先安装必要的Python库：

pip install gmpy2 pycryptodome

3.3 编写攻击脚本

完整攻击代码如下：

from Crypto.Util.number import long_to_bytes
from gmpy2 import gcdext, invert

# 题目给出的数据
c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1 = 3247473589
e2 = 3698409173
n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

# 使用扩展欧几里得算法找到s和t
gcd, s, t = gcdext(e1, e2)

# 处理负指数情况
if s < 0:
    s = -s
    c1 = invert(c1, n)
elif t < 0:
    t = -t
    c2 = invert(c2, n)

# 计算明文
m = (pow(c1, s, n) * pow(c2, t, n)) % n

# 将长整数转换为字节并打印
print(long_to_bytes(m))

3.4 代码逐行解析

1. 导入库 ：

   • long_to_bytes ：将长整数转换为字节串
   • gcdext ：扩展欧几里得算法实现
   • invert ：计算模逆元

2. 输入数据 ：

   • 直接复制题目给出的c1、c2、e1、e2和n

3. 计算贝祖系数 ：

   • gcdext(e1, e2) 返回三个值：gcd(e1,e2)，以及满足e1 s + e2 t = gcd(e1,e2)的s和t
   • 由于题目保证e1和e2互质，gcd应为1

4. 处理负指数 ：

   • 如果s为负，取其绝对值并计算c1的模逆元
   • 如果t为负，同理处理

5. 计算明文 ：

   • 使用公式m = (c1^s * c2^t) mod n
   • 注意使用模幂运算提高效率

6. 输出结果 ：

   • 将长整数m转换为字节串，即flag

3.5 常见问题与调试技巧

问题1 ： gcdext 返回的s和t都是正数怎么办？

这种情况理论上不会发生，因为e1和e2都是大素数，且互质。如果真的发生，可以检查输入是否正确。

问题2 ：运行时报 ValueError: invalid literal for int() with base 10 ？

这通常是因为直接从题目复制数据时包含了非数字字符（如换行符）。确保只复制纯数字。

问题3 ：结果输出乱码？

可能原因：

1. 计算过程中某一步出错，导致m值不正确
2. flag本身不是可打印字符
3. 需要进一步处理（如base64解码）

可以尝试打印m的十进制值，看看是否合理。

4. 攻击的防御措施

了解攻击方法后，我们更应该知道如何防御：

1. 绝不重复使用模数 ：每个用户/每次加密都应生成独立的n
2. 使用标准填充方案 ：如OAEP，避免明文可预测
3. 定期更换密钥 ：即使没有泄露，也应定期更新密钥对
4. 监控异常行为 ：如多次加密相同明文

5. 扩展学习：其他RSA攻击方式

除了共模攻击，RSA还有多种攻击方式值得了解：

攻击类型	条件	防御措施
小公钥指数攻击	e很小(如3)	使用标准e值(65537)
共享素数攻击	两个n有共同因子	确保p,q独立随机生成
侧信道攻击	物理访问设备	恒定时间实现
选择密文攻击	可提交密文解密	使用适当填充方案

6. 工具与资源推荐

Python库 ：

• gmpy2 ：高性能数学运算
• pycryptodome ：密码学工具集
• sympy ：符号数学计算

学习资源 ：

• 《应用密码学：协议、算法与C源程序》
• Cryptopals挑战（https://cryptopals.com/）
• CTF Wiki密码学部分（https://ctf-wiki.org/）

7. 实战技巧与经验分享

在实际CTF比赛中，处理RSA题目时我通常会：

1. 首先检查n是否可以被分解（factordb.com）
2. 查看e是否异常（特别小或特别大）
3. 检查是否有多个密文/公钥（可能共模或共享素数）
4. 尝试已知攻击方式的脚本
5. 如果所有方法都失败，考虑是否有非标准编码或额外加密层

记得在一次比赛中，题目看起来像共模攻击，但实际需要先对密文进行简单异或处理才能应用标准方法。这提醒我们：永远不要假设数据已经准备好直接使用。