CTF实战：用Python+gmpy2破解RSA共模攻击的五个关键步骤

第一次参加CTF比赛时，我盯着那道RSA题目整整两小时毫无头绪。直到发现两个密文共享同一个模数n，才意识到这是典型的共模攻击场景。本文将用最直白的方式，带你重现从茫然到破解的全过程。

1. 环境准备与工具选择

在开始前，我们需要配置合适的开发环境。推荐使用Python 3.8+版本，这是目前最稳定的选择。关键库gmpy2的安装可能会让新手头疼——特别是在Windows系统上。

# 安装必备库
pip install gmpy2 pycryptodome

如果遇到 gmpy2 安装失败，可以尝试以下替代方案：

• Linux/macOS用户 ：先安装依赖库

  # Debian/Ubuntu
  sudo apt install libgmp-dev libmpfr-dev libmpc-dev
  # macOS
  brew install gmp mpfr libmpc
  

• Windows用户 ：直接下载预编译的whl文件

  # 从https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy2下载对应版本的whl
  pip install gmpy2‑2.1.0b5‑cp38‑cp38‑win_amd64.whl
  

提示：遇到 ImportError 时，检查Python版本与gmpy2是否匹配。32位和64位系统也需要对应版本。

2. 识别共模攻击的特征

共模攻击有三大典型特征，就像侦探破案的线索：

1. 相同的模数n ：两个密文使用完全一样的n值
2. 不同的公钥指数 ：e1和e2互质（通常为不同的素数）
3. 加密相同明文 ：c1和c2是对同一消息m的加密

在实际CTF题目中，这些信息可能隐藏在JSON数据、网络流量或注释里。以BUUCTF的rsa3为例，题目通常会给出：

n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
e2 = 9647291
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397

3. 数学原理的实战解读

共模攻击的核心在于 扩展欧几里得算法 。我们不需要完全理解其数学证明，但必须掌握如何应用：

1. 找到满足 e1*s1 + e2*s2 = 1 的整数s1和s2
2. 利用这两个系数组合密文： m = (c1^s1 * c2^s2) mod n

这个等式成立的秘密在于：

m^(e1*s1 + e2*s2) ≡ m^1 ≡ m (mod n)
(c1^s1 * c2^s2) ≡ (m^e1)^s1 * (m^e2)^s2 ≡ m^(e1*s1 + e2*s2) ≡ m (mod n)

4. 完整攻击脚本与逐行解析

下面是我们破解BUUCTF rsa3的完整代码，每一行都有详细注释：

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

# 题目给出的参数
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1, e2 = 11187289, 9647291
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397

# 关键步骤1：使用扩展欧几里得算法找到s1和s2
gcd, s1, s2 = gcdext(e1, e2)
print(f"系数s1: {s1}, s2: {s2}")  # 通常一正一负

# 关键步骤2：处理负指数（需要模逆元）
if s1 < 0:
    c1 = powmod(c1, -1, n)  # 计算c1的模逆元
    s1 = -s1
if s2 < 0:
    c2 = powmod(c2, -1, n)
    s2 = -s2

# 关键步骤3：组合计算明文
m = (powmod(c1, s1, n) * powmod(c2, s2, n)) % n

# 结果转换
flag = long_to_bytes(m)
print("破解结果:", flag)  # b'flag{49d91077a1abcb14f1a9d546c80be9ef}'

5. 常见错误与调试技巧

即使按照脚本操作，仍可能遇到各种问题。以下是五个常见错误及解决方案：

注意：当s1或s2为负数时，必须计算对应密文的模逆元。这是新手最容易忽略的关键步骤。

实际比赛中，我建议先验证小数字示例。比如用n=3233, e1=17, e2=19加密字母'A'（ASCII 65），确保脚本能正确解密后再处理大赛题目。