注意：下面有很多数学上不严谨的地方，且省略了大量的细节。

题目（又³）给出了一个 32 位控制台应用程序，无任何保护。

程序里的各种 timestamp 写的都是 Mon Dec 10 09:34:29 2018，只能说出题人有背景啊，作为防守方在比赛开始之后还能改题的，其他人做得到吗，呵呵呵呵呵。

从读取输入的方式来看，非常的看场雪了。

程序明面上的逻辑比较简单，可参考如下代码。

后面的计算是在 hexdecode 过的输入上做的，而后面的计算过程又受一个用 hexdecode 之前的输入上算出来的某种 CRC or 上 0xA4A4A4A4 生成的 table （后文称作 ControlDword）有关。这大概就是描述中的“鸡生蛋，蛋生鸡”的部分吧。简单观察后面的计算，不妨设其在 ControlDword 确定的情况下解唯一。这里可以控制用来造出这个行为的变量看起来只有 kTableInput。看起来作者是先确定了 ControlDword 和后面的解之后再构造的前面的部分。具体构造方法比较简单，感兴趣的读者可以自行推一推，只要注意到 CRC32 是线性的，修改一段输入的任意32 bit即可构造出任意输出值就不难理解。根据之前接触到的“看场雪”所出的题目来看，作者是个十分喜欢自hi的人，不妨认为 ControlDword 就是描述中提到的“天书”，并且其至少包含一段有意义的文本。

注意到 0xA4A4A4A4 包含 12 位，因此实际有效的输入只有 20 bit，不妨直接枚举一遍，按照原程序中的 GenerateControlDword 的逻辑算出输出，然后找里面有 “森林” 两个字的。结果可以得到如下文本（GBK 编码，共 1958 字节）：

呵呵呵，一如“看场雪”既往的不说人话。还“不是我看不起对手故意放水”，咋看着就这么像呢？

不妨认为现在 ControlDword 已经确定了，接下来只要看后面的计算即可。
后面的计算只包含一种操作，即查一张 255 x 255 的表，看起来是把某个原群 (Q, •) 的二元运算 • 的结果打成了表而不是直接写出运算过程，以此来对程序进行混淆，这也是一种通用方法。注意到 ControlDword 用来控制运算的左右顺序，所以多半这个二元运算不是可交换的，验证一下可以发现确实如此。同时注意到这张表是一个 Latin square，因此它是一个拟群。简单验证一下其他容易发现的性质可以发现不满足结合律，但存在恰好一个幂等元素 89。

注意到后面一通运算的输入和输出都是可见字符串，我们只能控制中间混合进去的 serial，这个 challenge 整体的形式是给出一组“明文”和“密文”对，求满足运算的“密钥"。这个拟群一定是通过某种形式构造的，具有某种性质，否则很难实现以上这一点。

显然，本题的秘密就藏在这个拟群的构造方式上了。观察 a•b/a 的结果（这里中间当然有一番各种其他尝试）：

这提示了我们这个拟群可能是 medial 的。验证一下发现确实如此。阅读一会儿各种 pdf，发现有一个叫 Bruck-Murdoch-Toyoda theorem 的东西，接下来就是体力活了。Bruck-Murdoch-Toyoda 定理告诉我们，对于任意 medial quasigroup (Q, •)，都存在一个阿贝尔群 (Q, +)，满足

x • y = φ(x) + ψ(y) + c

其中 φ、ψ 是 (Q, +) 上的自同构映射，c 是 Q 中的一个元素。我们只要能找出这两个映射，就可以找出这个 mask 过的运算在 (Z_{255}, +) 上的等价表示，从而方便我们后续的求解。

这两个映射可以不同，这不太方便我们后续的处理。从我们的目标出发考虑，我们希望找到一种方法，将运算表示为 (Z_{255}, +) 上的线性运算，否则的话将还是难以求解。因此我们猜测这里实现的运算实际上是：

x • y = a * x + b * y + c

其中 * 为 (Z{255}, +) 上的“乘法”，a, b 为常数。当然，由于给定的运算表并不是定义在 Z{255} 上的，因此直接带入原始问题中的值 / 运算表的时候需要经过一次映射，这个任意可以是 (Q, +) 上的任意自同构映射。

这里 a、b、c 的范围都是 [0, 255)，我们可以直接枚举。剩下的问题就是如何找出这个映射。这可以通过刻画这个拟群上元素的一些性质（比如每个元素的阶等），和枚举出来的结果进行匹配，这是一个体力活。如此这般，确实可以找到几组合理的匹配，说明这个操作是可以等价到 (Z_{255}, +) 上的线性运算的，因此可以解。

经过一番体力活之后，我们可以得到程序里的 kBinOpTable 的其中一种可能的构造是下面这个玩意：

注意到映射的过程可以拿出来放到输入和输出的时候做，也就是说映射到 Z_{255} 上之后这个运算是线性的，所以可以直接解。

Sage 代码。

运行即可得到答案 64AD6A44B63F9EA5630D4E13335D54A6，验证可以发现 CRC 也符合，运行一下会发现程序输出了 “恭喜你走出森林了”。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课