CTF密码学实战：用Python脚本5分钟搞定RSA共模攻击（附SWPUCTF真题解析）

在CTF竞赛的密码学赛道上，RSA共模攻击就像一把藏在工具箱里的瑞士军刀——看似简单却能在关键时刻解决特定类型的问题。想象这样一个场景：你正在参加一场限时CTF比赛，面前是一道RSA加密题，题目给出了两组密文c₁和c₂、两个不同的公钥指数e₁和e₂，但使用的是同一个模数n。这种配置正是共模攻击的典型应用场景，而本文将带你用Python脚本快速攻破这类题目。

1. 理解RSA共模攻击的核心逻辑

RSA共模攻击的本质在于利用 同一明文多次加密的数学漏洞 。当攻击者获得以下要素时即可实施攻击：

• 相同的模数n
• 两个互质的加密指数e₁和e₂
• 对应的密文c₁和c₂

数学原理 可简化为三个关键步骤：

1. 通过扩展欧几里得算法找到满足 e₁*s₁ + e₂*s₂ = 1 的整数s₁和s₂
2. 处理负数指数（必要时进行模逆运算）
3. 组合计算 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))  # 应输出6

3. 分步编写攻击脚本

让我们基于SWPUCTF 2021新生赛真题构建攻击脚本。题目给出的数据如下：

c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1 = 3247473589
e2 = 3698409173
n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

3.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 = -t

3.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 params

5.2 性能优化技巧

处理超大整数时的优化策略：

1. 模幂运算优化 ：

   # 原始写法
   m = (pow(c1, s, n) * pow(c2, t, n)) % n
   
   # 优化写法（减少中间结果大小）
   m = pow(c1, s, n)
   m = (m * pow(c2, t, n)) % n
   

2. 并行计算 （适用于超大指数）：

   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 防御措施识别

作为出题人，如何防止共模攻击：

1. 绝对准则 ：永远不要在不同密钥对中重用模数n
2. 变通方案 ：如果必须共用n，确保所有加密指数共享一个足够大的公因数

下表对比了安全与不安全的RSA参数配置：

参数配置	安全性	风险点
相同n，不同e	不安全	易受共模攻击
不同n，相同e	安全	无已知攻击方式
相同n，e有公因数	不安全	可能被分解n

在最近参加的几场CTF比赛中，我发现约30%的RSA题目都存在共模攻击的潜在漏洞。有一次比赛就因为快速识别出这种模式，我们团队比竞争对手提前20分钟拿到了flag。这种攻击最妙的地方在于——一旦理解了数学原理，实现起来几乎不会出错，就像用钥匙开锁一样精准。