从数学到代码：用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 = 56728180268162933440701193325366296194571635700363052968690535322931053796907933860190657544652928677695217364141708032383095352. 扩展欧几里得算法深度解析
标准欧几里得算法用于求最大公约数，而扩展版本则能同时计算出贝祖系数。让我们手动推演这个神奇的过程：
2.1 算法步骤拆解
对于e1=773，e2=839，计算过程如下：
| 步骤 | a | b | q=a//b | r=a%b | x | y |
|---|---|---|---|---|---|---|
| 初始 | 839 | 773 | 1 | 66 | -58 | 63 |
| 迭代 | 773 | 66 | 11 | 47 | 5 | -58 |
| 迭代 | 66 | 47 | 1 | 19 | -3 | 5 |
| 迭代 | 47 | 19 | 2 | 9 | 2 | -3 |
| 迭代 | 19 | 9 | 2 | 1 | -1 | 2 |
| 终止 | 9 | 1 | 9 | 0 | 1 | -1 |
最终得到的贝祖系数为s1=-58，s2=63，验证：
773*(-58) + 839*63 = 12.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) % n4. 明文的特殊解码技巧
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}这个实现不仅解决了题目，更展示了密码学攻防的精髓——数学原理与工程实践的完美结合。
