从BUUCTF Samemod看共模攻击的陷阱与实战解码

1. 共模攻击基础与BUUCTF Samemod题目解析

密码学中的共模攻击（Common Modulus Attack）是一种针对RSA加密系统的经典攻击方式。简单来说，当同一个明文使用相同的模数n但不同的公钥指数e1和e2进行加密时，攻击者可以利用扩展欧几里得算法恢复出原始明文。这种攻击方式在CTF比赛中经常出现，BUUCTF的Samemod题目就是典型的案例。

我们先来看题目给出的关键参数：

• 模数n：6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
• 公钥指数e1=773，密文c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
• 公钥指数e2=839，密文c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

标准的共模攻击脚本通常会这样写：

import gmpy2 import libnum s,s1,s2 = gmpy2.gcdext(e1,e2) m = (pow(c1,s1,n) * pow(c2,s2,n)) % n print(libnum.n2s(int(m)).decode())

2. 标准共模攻击为何在此失效

在大多数CTF题目中，上述脚本确实可以直接得到flag。但Samemod这道题的特殊之处在于，它设置了一个精妙的陷阱。当我们运行标准脚本时，得到的实际上是一个很长的数字串：1021089710312311910410111011910111610410511010710511610511511211111511510598108101125

这个数字串看似毫无意义，但实际上是ASCII码的另一种表现形式。这里就涉及到CTF密码学题目中常见的编码陷阱。很多选手会习惯性地认为flag是直接可读的字符串，或者经过简单的hex编码，但实际上这道题采用了更隐蔽的编码方式。

我最初尝试用hex解码时也碰壁了，后来通过分析数字结构才发现：

• 数字串中大量出现"1"开头的三位数
• ASCII码中可打印字符的范围是32-126
• "1"开头的三位数正好对应100-126，属于可打印字符的高位区间

3. 数字结构分析与手动解码技巧

理解数字结构是解决这道题的关键。我们得到的数字串可以这样解析：

• 当遇到"1"开头时，取三位数作为一个ASCII码
• 其他情况取两位数作为一个ASCII码

这种编码方式在CTF中并不罕见，但需要选手有敏锐的观察力。下面是我当时使用的完整解码脚本：

result = str(1021089710312311910410111011910111610410511010710511610511511211111511510598108101125) flag = "" i = 0 while i < len(result): if result[i] == '1': c = chr(int(result[i:i+3])) i += 3 else: c = chr(int(result[i:i+2])) i += 2 flag += c print(flag)

运行后会得到最终flag：flag{whenwethinkitispossible}

4. 从实战中总结的密码学解题思维

这道题给我最大的启示是：在CTF密码学挑战中，数学推导只是第一步。真正的难点往往在于：

1. 识别非标准的编码方式
2. 分析原始数据的特殊结构
3. 根据上下文线索推断可能的编码规则

在实际比赛中，我建议养成以下习惯：

• 首先打印出原始解密结果，观察其结构特征
• 尝试常见的编码方式（hex、base64、ASCII码等）
• 注意数字长度和分布规律
• 对于长数字串，可以尝试按不同位数进行分割

密码学题目就像侦探破案，既需要扎实的数学基础，也需要敏锐的观察力和灵活的思维。Samemod这道题完美诠释了这一点 - 它看似是标准的共模攻击，实则暗藏玄机。