企业官网建设流程全解析

虎符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下的二次剩余；如果找不到这样的r，a就叫二次非剩余。用生活类比的话，这就像判断一个数“能不能开平方开出整数根”，只不过这里是在模运算的世界里开平方。

判断一个数a是不是模p（p为奇素数）下的二次剩余，有一个现成工具叫勒让德符号。符号结果是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题的经验，我整理了一套面对“大整数列表+公钥参数”类题目的通用分析流程，按顺序执行能省下不少试错时间：

1. 先读脚本，找到公钥生成和加密函数的实现，明确方案类型
2. 再把输出文件的结构和脚本输出格式一一对应，确认每个字段的含义
3. 然后根据方案类型选择判定方法，GM对应雅可比符号，二次剩余类题目对应勒让德符号或更高级的判定
4. 最后把比特流还原成字节，先按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则是把“是否为剩余”作为信息载体。弄明白这两者的区别，你对二次剩余类公钥密码的整体理解会扎实很多。以后再遇到类似的赛题，看到大整数和模数，你就能更快地判断出题人到底想考哪一层知识。