CTF实战：从BUUCTF的Samemod题看共模攻击的‘陷阱’与正确解法（附Python3完整脚本）
在CTF竞赛的密码学挑战中，RSA共模攻击是入门者必须掌握的基础技能。但真正考验选手的往往不是算法本身，而是对解密结果的二次处理能力。本文将以BUUCTF平台上的经典题目Samemod为例，揭示那些容易被忽略的"最后一公里"解题技巧。
1. 共模攻击原理与常规解法
共模攻击（Common Modulus Attack）是RSA体系中一种经典的攻击方式，当相同的明文使用相同的模数n但不同的公钥指数e1、e2加密时，在满足gcd(e1,e2)=1的条件下即可实施攻击。其数学基础是扩展欧几里得算法：
def extended_gcd(a, b): if b == 0: return a, 1, 0 else: g, x, y = extended_gcd(b, a % b) return g, y, x - (a // b) * y标准攻击流程可分为三个步骤：
- 使用扩展欧几里得算法找到满足e1s1 + e2s2 = 1的整数s1和s2
- 计算c1^s1 * c2^s2 mod n
- 将结果转换为字节串即得明文
对应Python实现如下：
from Crypto.Util.number import long_to_bytes import gmpy2 def common_modulus_attack(n, e1, e2, c1, c2): _, s1, s2 = extended_gcd(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 long_to_bytes(m)2. Samemod题目的特殊陷阱
当我们将上述标准解法应用于BUUCTF的Samemod题目时，会得到一个看似无意义的数字串：
1021089710312311910410111011910111610410511010710511610511511211111511510598108101125这与常见的flag格式大相径庭。此时许多选手会陷入以下误区：
- 尝试将数字串直接转换为十六进制
- 认为攻击失败而转向其他解法
- 忽略数字串本身的模式特征
实际上，这串数字隐藏着精妙的结构设计：
- 每个ASCII字符对应2-3位十进制数
- 三位数必定以'1'开头（ASCII 100-127）
- 两位数代表常规可见字符（ASCII 32-99）
3. 数字串解析的正确方法
要正确解析这个特殊格式的数字串，需要实现一个智能分割算法：
def parse_special_number(num_str): result = "" i = 0 while i < len(num_str): if num_str[i] == '1' and i + 3 <= len(num_str): # 三位数ASCII码（100-127） char_code = int(num_str[i:i+3]) result += chr(char_code) i += 3 else: # 两位数ASCII码（32-99） char_code = int(num_str[i:i+2]) result += chr(char_code) i += 2 return result这个处理过程揭示了CTF竞赛的一个重要原则：密码学攻击的终点不是数学运算，而是获得可理解的明文。出题者常常在以下环节设置"陷阱"：
| 陷阱类型 | 常见表现 | 解决方法 |
|---|---|---|
| 编码陷阱 | 非标准编码方式 | 观察数字规律 |
| 格式陷阱 | 非常规flag格式 | 分析字符范围 |
| 验证陷阱 | 需要额外验证 | 检查结果合理性 |
4. 完整Python3解题脚本
结合共模攻击和特殊解析方法，完整的解题脚本如下：
from Crypto.Util.number import long_to_bytes import gmpy2 def extended_gcd(a, b): if b == 0: return a, 1, 0 else: g, x, y = extended_gcd(b, a % b) return g, y, x - (a // b) * y def common_modulus_attack(n, e1, e2, c1, c2): _, s1, s2 = extended_gcd(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 str(m) def parse_special_number(num_str): result = "" i = 0 while i < len(num_str): if num_str[i] == '1' and i + 3 <= len(num_str): char_code = int(num_str[i:i+3]) result += chr(char_code) i += 3 else: char_code = int(num_str[i:i+2]) result += chr(char_code) i += 2 return result # 题目参数 n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249 e1, e2 = 773, 839 c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349 c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535 # 攻击与解析 num_str = common_modulus_attack(n, e1, e2, c1, c2) flag = parse_special_number(num_str) print("Flag:", flag)执行后将输出正确flag：flag{whenwethinkitispossible}
5. CTF密码学解题的思维训练
通过这道题目，我们可以总结出CTF密码学挑战的解题思维框架：
算法识别阶段
- 分析题目给出的参数特征
- 判断可能适用的密码学攻击方法
数学运算阶段
- 实现标准的密码学攻击算法
- 验证中间结果的合理性
结果解析阶段
- 观察输出数据的模式特征
- 尝试不同的编码转换方式
- 考虑出题人可能设置的"陷阱"
验证优化阶段
- 检查flag格式是否符合要求
- 优化代码提高运算效率
- 记录解题过程以备复盘
在实战中遇到类似问题时，建议采用以下检查清单：
- [ ] 是否考虑了所有可能的编码方式？
- [ ] 数字串是否有明显的分组规律？
- [ ] 是否存在非标准的ASCII表示方法？
- [ ] 结果是否符合flag的常见格式？
这道Samemod题目看似简单，却巧妙地考察了选手对密码学攻击完整流程的理解。真正的CTF高手不仅精通算法原理，更能敏锐地发现数据中的隐藏模式。
