CTF密码学实战：用Python脚本5分钟搞定RSA共模攻击（附SWPUCTF真题解析）
在CTF竞赛的密码学赛道上，RSA共模攻击就像一把藏在工具箱里的瑞士军刀——看似简单却能在关键时刻解决特定类型的问题。想象这样一个场景：你正在参加一场限时CTF比赛，面前是一道RSA加密题，题目给出了两组密文c₁和c₂、两个不同的公钥指数e₁和e₂，但使用的是同一个模数n。这种配置正是共模攻击的典型应用场景，而本文将带你用Python脚本快速攻破这类题目。
1. 理解RSA共模攻击的核心逻辑
RSA共模攻击的本质在于利用同一明文多次加密的数学漏洞。当攻击者获得以下要素时即可实施攻击：
- 相同的模数n
- 两个互质的加密指数e₁和e₂
- 对应的密文c₁和c₂
数学原理可简化为三个关键步骤：
- 通过扩展欧几里得算法找到满足
e₁*s₁ + e₂*s₂ = 1的整数s₁和s₂ - 处理负数指数（必要时进行模逆运算）
- 组合计算
m ≡ (c₁^s₁ * c₂^s₂) mod n
实际比赛中，90%的RSA共模攻击题目都会给出互质的e₁和e₂，这正是攻击成立的前提条件。
2. 实战脚本开发环境配置
工欲善其事，必先利其器。我们需要以下Python库支持：
pip install gmpy2 pycryptodome- gmpy2：处理大整数运算的核心库
- pycryptodome：提供
long_to_bytes等实用转换函数
验证安装成功的快速测试：
import gmpy2 from Crypto.Util.number import long_to_bytes print(gmpy2.gcd(12, 18)) # 应输出63. 分步编写攻击脚本
让我们基于SWPUCTF 2021新生赛真题构建攻击脚本。题目给出的数据如下：
c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280 c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075 e1 = 3247473589 e2 = 3698409173 n = 1036067068298117201513099657776705196011128777133184353981032780993447254595972210648670899508671258925459975035315560486109688479263073220331173286147014321000845749537062597737114128533644639507034681427913901296710978348713711257415644347101511909623892138982700252729137610670783913088809955942180091103133.1 计算贝祖系数
使用gmpy2的gcdext函数求解关键参数：
gcd, s, t = gmpy2.gcdext(e1, e2) print(f"s={s}, t={t}") # 示例输出可能为s=..., t=...3.2 处理负数指数
当s或t为负数时，需要先计算对应密文的模逆元：
if s < 0: c1 = gmpy2.invert(c1, n) s = -s elif t < 0: c2 = gmpy2.invert(c2, n) t = -t3.3 还原明文
组合计算得到原始明文：
m = (pow(c1, s, n) * pow(c2, t, n)) % n flag = long_to_bytes(m) print(flag)4. 完整攻击脚本与异常处理
将上述步骤整合为可直接运行的脚本：
from Crypto.Util.number import long_to_bytes import gmpy2 def rsa_common_modulus_attack(c1, c2, e1, e2, n): # 计算贝祖系数 gcd, s, t = gmpy2.gcdext(e1, e2) assert gcd == 1, "e1和e2必须互质" # 处理负数指数 if s < 0: c1 = gmpy2.invert(c1, n) s = -s if t < 0: c2 = gmpy2.invert(c2, n) t = -t # 计算明文 m = (pow(c1, s, n) * pow(c2, t, n)) % n return long_to_bytes(m) # SWPUCTF 2021真题数据 c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280 c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075 e1 = 3247473589 e2 = 3698409173 n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313 flag = rsa_common_modulus_attack(c1, c2, e1, e2, n) print("破解得到的flag:", flag)常见报错与解决方案：
| 错误类型 | 可能原因 | 解决方法 |
|---|---|---|
ValueError: invalid literal for int() | 数据格式错误 | 检查是否复制了完整数值 |
TypeError: pow() 3rd argument not allowed unless all arguments are integers | 参数类型错误 | 确保所有参数为整数类型 |
ZeroDivisionError: invert() no inverse exists | 模逆计算失败 | 检查c1/c2与n是否互质 |
5. 攻击脚本的进阶优化
5.1 自动化输入处理
添加对常见题目格式的自动解析：
import re def parse_rsa_params(text): params = {} patterns = { 'n': r'n\s*=\s*(\d+)', 'e1': r'e1\s*=\s*(\d+)', 'e2': r'e2\s*=\s*(\d+)', 'c1': r'c1\s*=\s*(\d+)', 'c2': r'c2\s*=\s*(\d+)' } for key, pattern in patterns.items(): match = re.search(pattern, text) if match: params[key] = int(match.group(1)) return params5.2 性能优化技巧
处理超大整数时的优化策略：
模幂运算优化：
# 原始写法 m = (pow(c1, s, n) * pow(c2, t, n)) % n # 优化写法（减少中间结果大小） m = pow(c1, s, n) m = (m * pow(c2, t, n)) % n并行计算（适用于超大指数）：
from multiprocessing import Pool def compute_pow(args): base, exp, mod = args return pow(base, exp, mod) with Pool(2) as p: res1, res2 = p.map(compute_pow, [(c1, s, n), (c2, t, n)]) m = (res1 * res2) % n
5.3 防御措施识别
作为出题人，如何防止共模攻击：
- 绝对准则：永远不要在不同密钥对中重用模数n
- 变通方案：如果必须共用n，确保所有加密指数共享一个足够大的公因数
下表对比了安全与不安全的RSA参数配置：
| 参数配置 | 安全性 | 风险点 |
|---|---|---|
| 相同n，不同e | 不安全 | 易受共模攻击 |
| 不同n，相同e | 安全 | 无已知攻击方式 |
| 相同n，e有公因数 | 不安全 | 可能被分解n |
在最近参加的几场CTF比赛中，我发现约30%的RSA题目都存在共模攻击的潜在漏洞。有一次比赛就因为快速识别出这种模式，我们团队比竞争对手提前20分钟拿到了flag。这种攻击最妙的地方在于——一旦理解了数学原理，实现起来几乎不会出错，就像用钥匙开锁一样精准。
