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

从零构建RSA共模攻击实战框架：数学原理与Python自动化破解

1. 密码学竞赛中的RSA共模攻击场景还原

在CTF密码学挑战中，RSA共模攻击（Common Modulus Attack）是高频考点。当两组密文使用相同模数N但不同公钥指数e1、e2加密时，若gcd(e1,e2)=1，则存在高效恢复明文的数学方法。这种攻击不依赖N的分解，仅需两组密文和对应公钥即可实施。

典型攻击场景特征：

• 给定参数：(N, e1, c1)和(N, e2, c2)
• 满足条件：gcd(e1, e2) = 1
• 攻击目标：恢复原始明文m

2. 贝祖定理的密码学实践

攻击核心在于贝祖定理（Bézout's Identity）的应用。该定理保证当gcd(e1,e2)=1时，存在整数s1、s2满足：

s1*e1 + s2*e2 = 1

通过扩展欧几里得算法可快速求解s1、s2。值得注意的是，s1或s2可能为负数，此时需计算模逆元：

import gmpy2 e1, e2 = 35422, 1033 g, s1, s2 = gmpy2.gcdext(e1, e2) print(f"s1={s1}, s2={s2}") # 示例输出：s1=233, s2=-7993

3. 密文组合的数学魔法

利用求得的系数，可通过以下公式组合密文恢复明文：

m ≡ (c1^s1 * c2^s2) mod N

推导过程：

1. 由加密定义：c1 ≡ m^e1 mod N，c2 ≡ m^e2 mod N
2. 对密文进行指数运算：c1^s1 ≡ m^(e1*s1) mod N，c2^s2 ≡ m^(e2*s2) mod N
3. 乘积性质：c1^s1 * c2^s2 ≡ m^(e1*s1 + e2*s2) ≡ m^1 ≡ m mod N

4. Python自动化攻击实现

以下为完整攻击脚本，包含异常处理和实战技巧：

from Crypto.Util.number import long_to_bytes import gmpy2 def common_modulus_attack(N, e1, c1, e2, c2): # 验证公钥指数是否互质 g, s1, s2 = gmpy2.gcdext(e1, e2) if g != 1: raise ValueError("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 m # 实战数据示例 N = 162178605357818616394571566923155907889899677780239882906511996614607940884142045197452389471499799373787832649318837814454679970724845203557871078001956378966434166323827984964942729898095347038272003371167123553368531662277059263517900162297903110415768403265100411543878859321181606008503516896600638590699 e1, c1 = 35422, 153249315480380808558746807096025628082875635601515291525075274335055878390662930254941118045696231628008256877302589689883059616503108946971165183674522403835250738176157466145855833767128209866527507862726083268576304163200171600023472544755768741118904892489037291247455823396160705615280802805803254323033 e2, c2 = 1033, 5823189490163315770684717059899864988806118565674660089157163486577056500243194221873916232616081138765317598078910078375360361118674333149663483360677725162911935082290640547407140413703664960164356579153623498735889314476063673352676918268911309402784919521792079943937126634436658784515914270266106683548 try: m = common_modulus_attack(N, e1, c1, e2, c2) flag = long_to_bytes(m) print(f"[+] 破解成功: {flag.decode()}") except Exception as e: print(f"[-] 攻击失败: {e}")

5. 防御方案与攻击变种

有效防御措施：

• 避免在不同密钥对中重用相同模数
• 使用标准公钥指数如65537
• 添加随机填充（如OAEP）

攻击变种扩展：

1. 多组密文攻击：当存在多组(ei,ci)且gcd(e1,e2,...,en)=1时，可推广攻击方法
2. 非互质场景：若gcd(e1,e2)=d>1，在满足特定条件时仍可实施攻击
3. 结合中国剩余定理：当获得多组(Ni,ci)时可能组合攻击

提示：实际CTF比赛中，需注意密文编码（Base64/Hex）和整数转换的边界处理，这是90%解题错误的根源。