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

2026/6/28 23:56:39

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}