企业官网建设流程全解析

CTF 密码学 RSA 共模攻击：3 种 Python 实现方案对比与效率分析

在CTF竞赛中，RSA共模攻击是一种常见的密码学攻击手段。当两个不同的公钥使用相同的模数n时，攻击者可以利用扩展欧几里得算法恢复出明文。本文将深入探讨三种Python实现方案，并分析它们在处理2048位大数时的计算效率差异。

1. 共模攻击原理与数学基础

RSA共模攻击的核心数学原理基于以下条件：

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

根据扩展欧几里得算法，我们可以找到整数s₁和s₂满足：

e₁*s₁ + e₂*s₂ = 1

然后通过以下公式恢复明文：

m = (c₁^s₁ mod n) * (c₂^s₂ mod n) mod n

关键数学运算：

• 模反元素计算（当s₁或s₂为负数时）
• 大数模幂运算
• 扩展欧几里得算法实现

2. 三种Python实现方案

2.1 标准扩展欧几里得实现

def common_modulus_attack_standard(n, c1, c2, e1, e2): def extended_gcd(a, b): if b == 0: return a, 1, 0 else: gcd, x, y = extended_gcd(b, a % b) return gcd, y, x - (a // b) * y _, s1, s2 = extended_gcd(e1, e2) if s1 < 0: c1 = pow(c1, -1, n) s1 = -s1 if s2 < 0: c2 = pow(c2, -1, n) s2 = -s2 m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return m

特点：

• 纯Python实现，无外部依赖
• 使用递归实现扩展欧几里得
• 需要手动处理负指数情况

2.2 gmpy2优化版本

import gmpy2 def common_modulus_attack_gmpy2(n, c1, c2, e1, e2): gcd, s1, s2 = gmpy2.gcdext(e1, e2) if s1 < 0: c1 = gmpy2.invert(c1, n) s1 = -s1 if s2 < 0: c2 = gmpy2.invert(c2, n) s2 = -s2 m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return int(m)

优化点：

• 使用gmpy2的gcdext函数计算扩展GCD
• gmpy2.invert比Python内置pow求逆更快
• 大数运算效率显著提升

2.3 Crypto.Util.number实现

from Crypto.Util.number import inverse def common_modulus_attack_crypto(n, c1, c2, e1, e2): def extended_gcd(a, b): if b == 0: return a, 1, 0 else: gcd, x, y = extended_gcd(b, a % b) return gcd, y, x - (a // b) * y _, s1, s2 = extended_gcd(e1, e2) if s1 < 0: c1 = inverse(c1, n) s1 = -s1 if s2 < 0: c2 = inverse(c2, n) s2 = -s2 m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return m

特点：

• 使用Crypto库的inverse函数求模逆
• 保持标准算法的结构
• 比纯Python实现稍快但不及gmpy2

3. 性能对比测试

我们在2048位RSA参数下测试三种实现的性能：

测试环境：

• Python 3.8
• Intel i7-10750H @ 2.60GHz
• 16GB RAM

注意：实际性能会因具体输入参数和硬件环境有所不同。gmpy2在连续大数运算中优势明显。

4. 无gmpy2环境的替代方案

当目标环境无法安装gmpy2时，可以考虑以下优化：

4.1 预计算优化

def optimized_attack(n, c1, c2, e1, e2): # 预计算所有可能的模逆 inv_cache = {} def get_inv(x): if x not in inv_cache: inv_cache[x] = pow(x, -1, n) return inv_cache[x] # 其余代码与标准实现相同 ...

4.2 并行计算

from concurrent.futures import ThreadPoolExecutor def parallel_pow(bases, exps, mod): with ThreadPoolExecutor() as executor: results = list(executor.map(pow, bases, exps, [mod]*len(bases))) return results[0] * results[1] % mod

5. 实战案例分析

以BUUCTF的RSA3题目为例，我们演示攻击流程：

n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e1 = 11187289 e2 = 9647291 # 使用gmpy2版本解密 m = common_modulus_attack_gmpy2(n, c1, c2, e1, e2) print(bytes.fromhex(hex(m)[2:]))

输出结果：

b'flag{49d91077a1abcb14f1a9d546c80be9ef}'

6. 效率优化建议

1. 缓存计算结果：对于固定模数n的多次计算，缓存模逆结果
2. 并行计算：独立的大数模幂运算可以并行处理
3. 算法选择：
   • 竞赛环境优先使用gmpy2
   • 受限环境使用Crypto库+优化算法
4. 输入验证：添加对n、e、c的合法性检查

def validate_input(n, c1, c2, e1, e2): assert n > 1 and c1 > 0 and c2 > 0 assert e1 > 1 and e2 > 1 assert math.gcd(e1, e2) == 1

7. 不同场景下的方案选择

根据实际需求选择最佳实现：

在实际CTF比赛中，遇到共模攻击题目时，建议优先尝试gmpy2方案，特别是在时间紧张的竞赛环境下。而对于需要代码审计或教学的情况，标准实现更能清晰展示算法原理。