题目（又）给出了一个 32 位控制台 Windows 应用程序 C72.exe:

同样没有任何保护，运行一下：

看起来也是一个经典的输入 flag，输出对错的题目。

这个程序分析起来难度比较小，其本身代码量很小，也没有任何保护，无论是采用 IDA Pro 还是在调试器中跟踪，很快便可以看清程序逻辑，故这里不再给出“如何阅读反汇编”这部分的分析过程，也不在着重分析诸如输入是怎么编码的之类的小细节问题，若有疑问可直接参阅后文的解题代码。

程序首先采用预定义的字符串初始化了一个作为 key 使用的 buffer，接下来读取输入，并对其进行 hex decode，这里的 hex decode 过程写的不太鲁棒（没有判断长度和字符范围），但其采用了转完之后再用 sprintf 重新格式化成大写 hex 串并和原串比较的方法，保证了输入一定是总计 18 个字符的大写 hex 串。将 decode 得到的 9 字节记为 g_input。

程序接下来逐个考虑这 9 个字节中的每一位（共 72 位），根据每一位利用另一张预定义的常量表（共 72 * 16 字节，不妨将其视作72行，每行16字节的表）将原始的 key buffer 进行变换。变换的具体方法为，对于第 i 位，若其是 1，则将 key_buffer+i 开始的 16 字节与预定义的常量表中的第 i 行进行异或。

接下来，程序摸出了一个 16 字节的 buffer，并调用了一个函数对其进行“解密”，要求解密得到的最后两字节为 0，若符合则将解密得到的内容作为字符串输出。结合程序一开始输出的提示，很显然，这里要求解密得到的是对应 序列号输入正确 这七个汉字的 GBK 编码加上两字节 00。

而这个“解密”函数也十分简单：

其对输入进行了 keylen 次操作，每次将数据的最低字节混合上当前 key，用作索引查表，然后将数据移动 8 位，前方补 0 并异或上表中对应的 16 字节。“移位”、“根据输入决定异或上的值”、“异或”……敏锐的读者可能在 10 句话之前就意识到了，这听上去就是一个反馈移位寄存器。
其与教科书般的 FSR 的差别在于其一次做 8 位而非 1 位。
知道了其是一个 FSR 之后，我们首先验证一下它是不是线性的，即对于一字节中 8 位分别的反馈的组合等同于整体的反馈：

程序输出了 OK，同时我们发现：

也成立，因此看起来其就是一个单个的 Galois 模式的 LFSR 的一次处理一字节的“加速处理”版，也就是说，若将上述 C 代码中的 data、key 都视作小端表示的整数，其完全等价于以下代码：

知道了这一点之后，接下来就好办了，线性反馈移位寄存器中的重点在于 线性，也就是说其输出完全是输入的线性组合，注意到输入及 LFSR 的参数已知，key 混合进去和 LFSR 同样是在 GF(2) 上进行的（说人话：都是异或），因此输出可以表示为 key 的各位的线性表示，加上已知的预期输出，可以得到一个线性方程组。

由于 LFSR 的长度是 128 位，这里可以得到 128 个线性方程，而 key 的长度是 138 * 8 位，远超过 128，因此可能的 key 会十分多，但由于 key 的生成方式所限，其中绝大多数都无法找到一个对应的 g_input。因此直接求解 key 再试图反算回程序的输入是不可行的。

注意到 key 生成的过程也是线性的，因此其实可以将 key 的每一位也表示成关于输入的 72 位的线性表示，这样只要解存在，其一定是唯一的，并且可以直接求出。

接下来就是愉快的写代码时间了，由于最后 GF(2) 上的线性方程组打算直接采用 Sage 求解，不如就把整个代码用 Sage 写吧。（当然也可以自己写 Gauss Elimination，但是何必呢……）

运行即可得到本题的“序列号”：

稍微认真一点写题解真的好累呀……

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)