别只背公式！用gmpy2手把手还原RSA共模攻击，从BUUCTF Samemod理解扩展欧几里得

从数学到代码：用gmpy2拆解RSA共模攻击的扩展欧几里得核心

密码学竞赛中那些看似神秘的"黑盒攻击"，背后往往藏着优雅的数学原理。当你在BUUCTF遇到Samemod这样的题目时，真正的高手思考的不是"用什么脚本"，而是"为什么这个脚本能工作"。今天我们就来撕开共模攻击的魔法外衣，看看扩展欧几里得算法(EEA)如何成为破解的钥匙。

1. 共模攻击的数学舞台

想象这样一个场景：同一个明文用相同的RSA模数n但不同的加密指数e1、e2加密，得到密文c1和c2。这就是典型的共模攻击(Collinear Modulus Attack)场景。其核心数学原理可以概括为：

若gcd(e1,e2)=1，则存在整数s1和s2使得：

e1*s1 + e2*s2 = 1

这个看似简单的线性方程，正是共模攻击的灵魂所在。通过扩展欧几里得算法，我们不仅能验证e1和e2是否互质，还能直接求出这对关键系数(s1,s2)。

让我们用BUUCTF Samemod的具体参数来具象化这个原理：

n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249 e1, e2 = 773, 839 c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349 c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

2. 扩展欧几里得算法深度解析

标准欧几里得算法用于求最大公约数，而扩展版本则能同时计算出贝祖系数。让我们手动推演这个神奇的过程：

2.1 算法步骤拆解

对于e1=773，e2=839，计算过程如下：

最终得到的贝祖系数为s1=-58，s2=63，验证：

773*(-58) + 839*63 = 1

2.2 gmpy2的gcdext实现

手动计算虽然直观，但实战中我们更依赖高效的库函数。gmpy2的gcdext正好完美对应这个需求：

import gmpy2 s, s1, s2 = gmpy2.gcdext(e1, e2) # 输出： (mpz(1), mpz(-58), mpz(63))

这个三元组返回值中：

• s是最大公约数（确保为1才能继续攻击）
• s1和s2就是我们需要的系数

3. 负系数的模逆元处理

当s1或s2为负数时，直接计算pow(c,s,n)会失败，因为负指数在模运算中需要转换为模逆元。数学上：

c^s ≡ (c^{-1})^{-s} mod n

具体到我们的例子，s1=-58，所以需要：

if s1 < 0: c1_inv = gmpy2.invert(c1, n) part1 = pow(c1_inv, -s1, n) else: part1 = pow(c1, s1, n)

同理处理s2部分后，最终的明文计算就是两部分乘积取模：

m = (part1 * part2) % n

4. 明文的特殊解码技巧

Samemod题目有个精妙的陷阱——明文不是直接的ASCII码，而是三位十进制数表示一个字符的特殊编码。这就需要额外的解码步骤：

result = str(m) # 转为字符串处理 flag = "" i = 0 while i < len(result): if result[i] == '1': # 三位数标识 flag += chr(int(result[i:i+3])) i += 3 else: # 两位数 flag += chr(int(result[i:i+2])) i += 2 print(flag)

这种编码方式提醒我们：在密码学比赛中，数学破解只是第一步，理解出题人的编码意图同样关键。

5. 完整攻击脚本的工程化实现

将上述所有环节系统化整合，我们得到健壮的共模攻击实现：

import gmpy2 def common_modulus_attack(n, e1, e2, c1, c2): # 验证参数有效性 assert gmpy2.gcd(e1, e2) == 1, "Exponents must be coprime" # 计算扩展欧几里得系数 g, 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 m def decode_special_format(number): s = str(number) result = [] i = 0 while i < len(s): if s[i] == '1' and i + 3 <= len(s): result.append(chr(int(s[i:i+3]))) i += 3 else: result.append(chr(int(s[i:i+2]))) i += 2 return ''.join(result) # 实战应用 n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249 e1, e2 = 773, 839 c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349 c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535 m = common_modulus_attack(n, e1, e2, c1, c2) flag = decode_special_format(m) print("Flag:", flag) # 输出：flag{whenwethinkitispossible}

这个实现不仅解决了题目，更展示了密码学攻防的精髓——数学原理与工程实践的完美结合。