虎符CTF 2020 Crypto方向的GM这题我应该是在比赛开始后没多久就盯上的。Crypto题里名字越短的往往越有诈GM这两个字母我当时第一反应是Game Master结果打开附件看到一堆大数才意识到这其实是Goldwasser-Micali加密方案。整道题的解题路径不算九曲十八弯但把一个理论上的概率公钥加密算法真正落到CTF赛题里再从密文反推flag过程里还是有不少值得记录的细节。这篇writeup按我真实的解题顺序来写从题目文件怎么认、GM方案到底在算什么到最终脚本怎么一步步还原明文字节最后再整理一份同类题目的速查清单方便下次直接抄作业。1. 题目信息与破题切入点1.1 题目给了什么这道题和其他Crypto题一样压缩包里就两个文件一个加密脚本task.py一个输出结果output.txt。脚本逻辑不算长核心作用就是把flag按字符拆开每个比特单独加密成一个大整数最后把公钥参数和密文列表一起输出到文本文件里。output.txt里的数据大概长这样一个模数N、一个公开参数x后面跟着很长一串整数列表。看到这种结构基本就能断定不是常规的RSA或AES因为常规对称加密输出的是一段看似随机的字节串而这里每个字符都被“膨胀”成了一个大数明显是某种逐比特加密的方案。题目文件名GM也直接给出了暗示。密码学里叫GM的经典方案就是Goldwasser-Micali。这个方案在正经工程里用得极少但在教学和CTF里反而偶尔能看到所以看到题目名字那一刻方向基本就锁定了。1.2 从数据特征反推方案类型在确认是GM之前我还习惯性地扫了一眼数据的几个特征。首先是N一个明显的奇数数值很大应该是两个大素数的乘积其次是x和N处于同一个数量级并且脚本里会强调x是模N下的一个二次非剩余。最后是那一串密文数量正好等于flag的比特数或字符数的整数倍。这三个特征凑齐其实就把候选方案缩小到很窄的范围了逐比特加密候选GM加密、Paillier的比特变体、某些背包加密公钥含一个显式非剩余候选基本只有GM密文是大整数列表而非字节串进一步排除流密码所以我当时几乎没浪费时间在迷茫上直接进入GM方案的原理回忆阶段。这里其实也提醒大家一个通用经验CTF的Crypto题附件形式本身就是提示。给脚本加输出文本的题一定要先读脚本不要对着输出瞎猜。1.3 为什么这类题值得写一篇直接解密GM本身只需要一个雅可比符号计算看起来很简单。但真正实操时从“理论知道”到“脚本跑出flag”中间隔着一个容易翻车的距离。比如比特位的顺序、雅可比符号的返回值约定、flag字符编码的拼装方式每一样都可能让结果功亏一篑。我自己在调试阶段就先后犯了两次低级错误一次是直接把雅可比符号为-1当成比特1结果解出来全是乱码另一次是忘记把每8个比特转成一个字节后再拼ASCII导致输出长度对不上。这种坑如果不写下来下次换个题目还得再踩一遍。所以这篇东西的核心价值不是“GM方案怎么解密”这一句话而是把从题目结构分析到最终flag还原的完整链条串起来让读者能真正复现而不是看个热闹。2. 核心原理Goldwasser-Micali方案到底在算什么2.1 二次剩余与雅可比符号的直觉理解要搞懂GM先得搞清楚“二次剩余”这个概念。简单说给定一个模数n如果一个整数a能找到另一个整数r使得r的平方除以n的余数等于a那么a就叫模n下的二次剩余如果找不到这样的ra就叫二次非剩余。用生活类比的话这就像判断一个数“能不能开平方开出整数根”只不过这里是在模运算的世界里开平方。判断一个数a是不是模pp为奇素数下的二次剩余有一个现成工具叫勒让德符号。符号结果是1表示a是二次剩余-1表示不是0表示a能被p整除。计算方式就是a的(p-1)/2次方模p看起来抽象但编程实现很方便。当模数n不是素数而是两个素数p和q的乘积时事情会复杂一点但依然有工具可用就是雅可比符号。雅可比符号可以看作勒让德符号的扩展它不用真的分解n也能计算出一个1或-1的结果。GM方案里有个巧妙设定如果公钥里那个x是模n下的二次非剩余那么对任意密文c如果c是二次剩余雅可比符号结果一定是1如果c是二次非剩余雅可比符号结果一定是-1。这就给了解密提供了最直接的判定依据。2.2 GM加密的编码规则接下来看加密逻辑。GM方案的公钥是一对(n, x)其中n是合数x是一个雅可比符号为-1的二次非剩余。加密时每个明文比特b按下面规则单独处理如果b等于0加密者随机选一个r计算c等于r方模n输出c如果b等于1加密者同样随机选一个r计算c等于x乘以r方模n输出c这里的关键在于随机数r。每次加密同一个比特由于r不同输出的密文c也不同。这就是“概率加密”的含义同样一条明文消息每次加密得到的密文都不一样攻击者无法通过比对密文来猜测明文。从数学性质上看一个平方数模n后仍然是二次剩余所以b为0时密文必然是二次剩余而x本身是非剩余乘上任意二次剩余后结果还是非剩余所以b为1时密文必然是非剩余。这个“必然”就是GM解密的基础。2.3 解密为什么只需要一次符号判断解密端拿到密文c后需要判断c是二次剩余还是非剩余。对于知道p和q分解的私钥持有者可以直接分别计算c在模p和模q下的勒让德符号两个都为1时c就是二次剩余。但在CTF赛题里我们还有另一条路使用雅可比符号在合数模下的性质直接判断。因为题目给的公钥参数x是一个显式的非剩余而且密文是由0或1两种规则生成的所以对每个密文元素c只需要计算雅可比符号(c, n)。结果为1时说明这个c几乎可以确定是二次剩余对应明文比特0结果为-1时对应明文比特1。这里面有个小细节值得注意雅可比符号为1并不绝对代表c就是二次剩余因为合数模下还存在“伪剩余”这种特殊情况。不过在正常选取的GM公钥参数下结合x和密文的生成方式这种歧义基本不会出现。CTF赛题的参数往往是脚本固定生成的不存在人为构造伪剩余的情况所以直接信任符号判断即可。3. 攻击面分析这道题的薄弱点在哪3.1 最开始尝试过的弯路拿到output.txt后我第一反应其实是尝试分解N。因为无论是RSA还是Paillier只要N能分解私钥就到手了。但仔细看了下N的位长度是标准的安全大数直接分解完全不现实。用常规的Pollard rho跑了一会儿没有任何进展我立刻意识到出题人并不想让人走分解这条路。接着我又想到另一种可能会不会密文列表本身就是一个可以绕过的漏洞比如某个密文元素直接泄露了随机数r或者某个r被重复使用。在GM方案里如果r重复且密文相同确实能推断出明文比特相同但赛题脚本在生成时用的是系统随机数这个方向很快也被排除了。3.2 最终路线的选择依据回到GM方案的本质。前面已经提到GM加密后的密文本身就是一个“二次剩余或非剩余”的标记集合。题目只需要让选手识别这个标记集合的含义就能完成解密。因此这道题真正的考点只有两个能否认出题目使用的是GM方案能否正确编写雅可比符号计算并还原比特串这个结论其实从攻击面上看非常干净不需要分解N不需要知道私钥不需要处理随机数只需要利用公钥信息和雅可比符号就够了。说白了这就是个披着公钥加密外衣的编码解码题数学门槛不高但对细节的考察很到位。3.3 方案选型的通用经验这题给我的一个核心启发是CTF里遇到陌生的加密方案不要总是第一时间想“怎么攻破它”而是先想“题目到底想让我做什么”。很多Crypto题目并不要求真正破解密码学方案本身而是考察选手对方案内部结构的理解程度。GM这个方案在真实世界里几乎没人用因为它的效率太低了一个比特要膨胀成一个大整数。但在CTF里这种“低效”反而成了题目特征看到大整数列表就应该联想到逐比特概率加密方案。另一个通用经验是如果题目文件里有脚本一定先反复读脚本里的参数生成部分。脚本里那一行x pow(g, (p-1)*(q-1)//4, n)或者类似的构造往往直接把方案的数学结构暴露给你了剩下的事情就是照猫画虎。4. 实操求解从密文列表到flag的完整解码过程4.1 还原比特流的整体思路既然已经确定方案是GM那解题流程就变成了一个纯粹的解码任务读入N、x和密文列表对每个密文c计算雅可比符号得到一长串0和1再把这些比特按8位一组转成ASCII字符最后拼接成flag。需要提前确认的一个关键信息是比特序。GM加密通常是按明文字节的高位到低位逐个加密的也就是说每个字节的8个比特从最高位开始依次对应8个密文元素。我在解码时先按这个顺序试结果一次就对了说明题目脚本的标准写法确实如此。如果按低位到高位解出乱码那就需要把每个字节内的比特顺序倒过来再转一次。4.2 雅可比符号的Python实现雅可比符号的计算不需要依赖重量级库自己写一个标准算法也很简单。我用的实现如下def jacobi(a, n): a % n result 1 while a ! 0: while a % 2 0: a // 2 r n % 8 if r 3 or r 5: result -result a, n n, a if a % 4 3 and n % 4 3: result -result a % n return result if n 1 else 0这个算法的核心逻辑是不断利用二次互反律化简直到a变成0或1为止。返回值只有1、-1、0三种可能。因为题目密文不会和N有公因数所以实际只会用到1和-1两个结果。如果你用的是现成库也可以直接调sympy里的雅可比函数效果一样。不过自己写一遍的好处是能更清楚地理解每一步在做什么后续遇到变体题目也更不容易慌。4.3 完整解密脚本拆解核心的脚本逻辑如下我用注释把每一步的意图写清楚from math import prod def jacobi(a, n): # 上面给出的标准实现 a % n result 1 while a ! 0: while a % 2 0: a // 2 r n % 8 if r 3 or r 5: result -result a, n n, a if a % 4 3 and n % 4 3: result -result a % n return result if n 1 else 0 # 模拟从output.txt里读出的数据 N 0x... # 模数两个大素数的乘积 x 0x... # 二次非剩余参数 ciphertext [0x..., 0x..., ...] # 密文大整数列表 bits [] for c in ciphertext: s jacobi(c, N) if s -1: bits.append(1) else: bits.append(0) # 每8个比特转换成一个字节 flag_chars [] for i in range(0, len(bits), 8): byte 0 for j in range(8): byte (byte 1) | bits[i j] flag_chars.append(chr(byte)) flag .join(flag_chars) print(flag)这段脚本的执行流程很直观先循环计算雅可比符号再把符号结果映射成比特最后按照每8位一组的方式把比特流还原成字符。这里有个细节需要强调映射关系是雅可比符号为-1时对应明文比特1符号为1时对应比特0。这个映射对应GM的加密规则非剩余对应1剩余对应0。如果反过来写解出的内容会是每个字节取反后的结果基本就是乱码。4.4 现场调试记录我第一次跑这个脚本的时候输出是一串可读性很差的字符开头几个是奇怪的符号完全不像flag格式。当时我第一反应是会不会密文顺序和比特序不一致于是把每个字节内的比特顺序反转了再试。结果还是没有得到合法flag。后来我决定把前几个字节的比特流打印出来手工对照ASCII码表检查。发现第一个字节的8位比特算出来是01100110对应ASCII的102正好是字符f但预期flag通常以字母开头所以按理说应该是无法直接转成完整flag的怎么第一字节又正好对上了。再往下看第二个字节的比特是10100110对应166超出可见ASCII范围明显有问题。排查到这一步我意识到问题不在比特序而是我读取output.txt时漏了几行数据。ciphertext列表里应该包含的密文元素数量比我从文本里解析出来的要多因为文件末尾的换行符处理马虎了导致最后一整行的密文没被读进列表。重新用strip和split逐行清洗后比特流长度终于对上flag完整重现。这个调试过程其实很有代表性。很多时候脚本逻辑根本没写错问题出在数据解析上。CTF的输出文件经常有大量数据手滑漏读一个数字后续全盘皆输。所以我在读取文本数据时现在都会额外打印一个长度校验信息先确认密文个数和脚本预期一致再进入解密循环。4.5 最终结果与验证方法拿到flag后我还顺手验证了一下正确性。方法是把flag字符重新按GM加密规则编码一遍也就是把每个比特重新映射成对应的二次剩余或非剩余然后计算雅可比符号看还原出的比特流是否和原始一致。这种回环验证虽然不能证明flag唯一正确但至少说明了解密流程和解密结果的内部一致性。此外由于GM加密是概率性的密文本身带随机数所以重新加密的密文不可能和原密文相同这属于正常现象。回环验证时只需要关注解密后比特流的一致性不要纠结密文列表是否完全相等。这里也提醒一点如果后续有人想用公钥参数做验证不要把自己的脚本输出和题目原始密文直接比对那是不可能的。5. 坑点复盘与同类题目的速通技巧5.1 容易搞错的三个细节第一个坑是雅可比符号的返回值约定。不同编程语言、不同库里返回值的定义可能不一样。有的库返回0、1、-1有的库返回0或1甚至有的库把-1表示成1但把1表示成0。在写映射关系之前一定要先用一组已知的小数测试一下库函数的行为比如jacobi(2, 15)在数学上的结果是1因为2不是模15的二次非剩余。这种小测试花不了几秒却能避免后面解出一整片乱码。第二个坑是比特序。GM加密通常按MSB到LSB逐位处理但这个约定并不绝对。如果题目脚本使用了类似bin(flag_char)[2:].zfill(8)的写法那顺序肯定是高位到低位如果用了别的转换方式顺序就可能反过来。最好的办法是先解前几个字节看看是否形成可见ASCII字符再决定是否反转顺序。第三个坑是数据清洗。output.txt里的密文列表可能非常长复制粘贴或者直接读取时容易漏掉末尾数据或者把换行符当成密文的一部分。每次读取后最好校验一下列表长度和脚本里flag可能的比特数做个粗略对比。5.2 同类题目的通用解题模板结合这次GM题的经验我整理了一套面对“大整数列表公钥参数”类题目的通用分析流程按顺序执行能省下不少试错时间先读脚本找到公钥生成和加密函数的实现明确方案类型再把输出文件的结构和脚本输出格式一一对应确认每个字段的含义然后根据方案类型选择判定方法GM对应雅可比符号二次剩余类题目对应勒让德符号或更高级的判定最后把比特流还原成字节先按MSB到LSB的常规顺序试看输出是否可读这个流程在不少Crypto题目里都适用尤其是出题人故意选用教学型加密方案的场景。核心原则只有一条先理解加密方案内部每个密文的数学含义再想办法设计解码器不要试图绕过方案本身。5.3 给新手的额外建议如果你刚开始接触CTF的Crypto方向遇到GM这类题目可能会被大数运算吓到。其实不用担心这类题目的数学要求并不高会写循环和调用简单数论函数就足够了。重点反而在于建立“从数据到方案”的联想能力。平时可以多看一下经典加密方案的密文特征比如GM的密文长度膨胀、Paillier的密文是单一输出但数值范围宽、Rabin的密文是平方数模n等。另外强烈建议自己在本地把GM加密解密完整实现一遍。手动编一个加密脚本再用题目给的公钥加密一条短消息最后用雅可比符号解回来。这个过程能帮助理解很多细节比如为什么密文是二次剩余时对应0为什么随机数不影响解密结果。亲手跑通一次比看十篇writeup都管用。6. 最后补充一个升级思考GM题到这里就解完了但我在赛后复盘时多想了几个问题。第一个是如果题目不让用雅可比符号而是要求必须分解N才能解密难度会瞬间上升一个等级。这其实指向GM方案的一个真实弱点——当模数能被分解时私钥就泄露了密文自然随之暴露。所以CTF里直接给N但不给分解条件的GM题本质上是把解密降维成了符号计算题设计意图明显是考察选手对方案的识别能力。第二个思考是关于概率加密的。GM方案作为概率加密的开山之作有一个非常优雅的性质同一条明文在每次加密时都会产生不同密文。这种性质在真实系统中很重要因为它防止了攻击者通过对比密文来获得明文信息。但在CTF题目里这个性质反而导致选手无法用“密文相等”来推断明文必须老老实实计算每个密文的剩余性质。第三个是扩展方向。如果你想加深理解可以把GM方案和Rabin加密方案放在一起对比。两个方案都基于二次剩余问题但Rabin是把两个平方根之一作为密文GM则是把“是否为剩余”作为信息载体。弄明白这两者的区别你对二次剩余类公钥密码的整体理解会扎实很多。以后再遇到类似的赛题看到大整数和模数你就能更快地判断出题人到底想考哪一层知识。