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

1. 共模攻击基础与BUUCTF Samemod题目解析密码学中的共模攻击Common Modulus Attack是一种针对RSA加密系统的经典攻击方式。简单来说当同一个明文使用相同的模数n但不同的公钥指数e1和e2进行加密时攻击者可以利用扩展欧几里得算法恢复出原始明文。这种攻击方式在CTF比赛中经常出现BUUCTF的Samemod题目就是典型的案例。我们先来看题目给出的关键参数模数n6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249公钥指数e1773密文c13453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349公钥指数e2839密文c25672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535标准的共模攻击脚本通常会这样写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-1261开头的三位数正好对应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:i3])) i 3 else: c chr(int(result[i:i2])) i 2 flag c print(flag)运行后会得到最终flagflag{whenwethinkitispossible}4. 从实战中总结的密码学解题思维这道题给我最大的启示是在CTF密码学挑战中数学推导只是第一步。真正的难点往往在于识别非标准的编码方式分析原始数据的特殊结构根据上下文线索推断可能的编码规则在实际比赛中我建议养成以下习惯首先打印出原始解密结果观察其结构特征尝试常见的编码方式hex、base64、ASCII码等注意数字长度和分布规律对于长数字串可以尝试按不同位数进行分割密码学题目就像侦探破案既需要扎实的数学基础也需要敏锐的观察力和灵活的思维。Samemod这道题完美诠释了这一点 - 它看似是标准的共模攻击实则暗藏玄机。