谨以此题纪念高光荣教授（1945年-2021年9月12日）。

高光荣教授是中国第一位 MIT 计算机博士，也是整个计算机学界中泰斗级的人物，与其导师 Jack Dennis 一同开创了数据流编程模型的先河，在并行计算与计算机系统结构领域产生了深远的影响。

本题目在高光荣教授提出的 Codelets 的细粒度线程执行模型下，采纳了基于共享内存模型的运行时 DARTS 作为框架，试图通过并行多线程调度的方式打断传统逆向工程中所习惯的控制流分析方法。在单核性能停滞不前的背景下，传统的代码混淆往往会带来无法容忍的性能开销，而并行编程范式则可以在混淆数据变换算法的前提下，甚至带来额外的性能提升。

本题算法主要由三部分构成：

这三个部分分别对应密码学中最常见的三种算法：信息摘要，非对称加密，对称加密，旨在模拟实际情况中所用的密码学算法（为了避免侧信道等非预期解法故而避开了标准的 AES 和 RSA 等等）。

题目代码已经上传，如需详细研究可以对照源代码（还有源代码中的解题脚本 .ipynb 文件）一同参看。

题目验证流程如图所示，直线箭头标识着主要的 Codelets/ThreadedProcedure 之间的数据依赖。曲线箭头则标识了一些内部的 Codelets 的数据依赖。在 DARTS 运行时下，无数据依赖的 codelets 会被并行调度。高度并行化使得在任意时刻下断点，内存中可能都不会存在一个严格的算法中间状态。比如 Feistel 算法中的不同层级可能会同时执行。blockHash 的结果可能也并未存储在某个特定的位置，而是仅仅存在于其后的 blockAdder 加法器中。

本题主要数据都在于 Poly 结构体中：

Poly 是一个最高次数为 23 次的多项式。加上常数项一共有 24 项，从低到高每 3 项为一个 PolyBlock，一共有 6 个 PolyBlock。

PolyBlock 是一个包含了 4 个系数的多项式块，每个系数都是模 61 意义下的。故而可以用 6 个 bit 表示一个系数（61 < 2^6）。四个系数一共 4*6 = 24 个 bit，也就是 3 个 bytes。把多项式块的内部 bits 顺序全部打乱，再异或一个固定的随机 mask，就是 PolyBlock 的混淆后的二进制表示：

本题中大部分数据变换的最小单位都是 PolyBlock。

这个是基于 xorshift 结构构造的一个简易的类似于 PRF (pseudo random function) 的作用。算法很简单：

这个 PRF 在构造用户名 hash 和 Feistel 对称加密中都有用到。

随手写的一个基于上述 blockHash 的 Hash 算法。没用到什么构造，所以效果很差。因为做出来本题不需要研究这种不可逆的 Hash 算法，所以没太花功夫。具体算法可以自己看看代码，做题的时候只需要在内存里提取 'KCTF' 对应的 Hash 数据即可。

一个随机生成的 16 层的 6 路 Feistel 网络，目的是把 blockHash 这种类似于 PRF 的玩意转化为 PRP (pseudo random permutation)（参看 Luby-Rackoff 定理）。
一层随机 Feistel 结构如图所示：（随机生成的结构展示，与实际中具体的数据变换不同）

程序从上一层的多项式中随机选取 3 个 polyBlock 作为 blockHash 的输入，生成的输出与剩下三个 polyBlock 相加（在多项式环中），然后将用来 hash 的 block 和 blockAdder 的输出随机排列成下一层的多项式。

因为 Feistel 结构可逆，所以这一层结构可以逆向回去。

PolyRSA 是一个在 GF(61) 下模多项式 t^24 + 51*t^21 + 55*t^20 + 2*t^19 + 3*t^18 + 35*t^17 + 13*t^16 + 5*t^15 + 25*t^14 + 40*t^13 + 11*t^12 + 17*t^11 + 48*t^10 + 26*t^9 + 48*t^8 + 54*t^7 + 5*t^6 + 19*t^5 + 28*t^4 + 43*t^2 + t + 38 的商环中进行的 RSA。
首先题目中实现了模上述多项式的乘法，然后通过快速幂算法，计算出 poly 的 2^0 + 2^7 + 2^21 + 2^31 次方。
通过 SageMath 很容易求得上述多项式可以分解为 (t^11 + 19*t^6 + 55*t^5 + 2*t^4 + 7*t^3 + 30*t^2 + 59*t + 30) * (t^13 + 51*t^10 + 55*t^9 + 44*t^8 + 9*t^7 + 33*t^6 + 13*t^5 + 29*t^4 + 29*t^3 + 2*t^2 + 58*t + 46)。所以对应的 RSA 的 phi 为 (61^11-1)*(61^13-1)，按照类似于 RSA 的算法，取逆后即可还原。

多项式的乘法经过了复杂的混淆，（是由 trivial 的 O(n^2) 多项式乘法算法的中间步骤累加而成，生成方法可以看脚本），可能比较难以识别出模多项式。实际上如果通过快速幂算法识别出 RSA 的结构，可以简单通过特殊数据尝试出实际的模多项式。另一种可能的方法是已知多项式最高次幂必为 24，然后猜测分解后两多项式的幂次，从而直接得到 phi（不需要分解）。

本题主要为尝试结合并行计算的数据流模型和代码混淆的思路，通过多线程的方法干扰选手进行调试，通过数据流调度的思路打断选手进行控制流分析。同时，程序中尽可能将相互没有数据依赖的计算分离开来，在提高性能的同时，还避免了程序的某个时刻的某个 buffer 里存放着算法完整的某个中间状态。

另外，随机生成的 Feistel 网络，将算法的核心由控制流图转化为数据部件的依赖关系。而这种依赖关系 Declaration 的位置和数据真正发生计算的位置并不相同。将算法描述和算法运行解耦，也是代码混淆的一个重要思路。

最后，我们可以更多的想象一下，现有 OLLVM 已经可以对控制流进行复杂的混淆变化，是否以后可以有算法对数据流图进行自动混淆呢？可能有 Dataflow flattening，或者 bogus dataflow 等等，又或者其他专用于数据流的混淆方法？

本题采用 Username/SerialNumber 的规则，以下给出两组序列号：
程序的 SHA256 为 56DF4D8D86305660747BC63FE31E8A8A6ADEA5D2211A723E153E018CA55E1CB4。第一组序列号如下（内容与附件 ctf.7z 压缩包中的 SN.txt 相同）
Username：56DF4D8D86305660
SN: 4A2CD38229906B47E4C04723C0BEAD86A599

第二组为所要求的序列号：
Username：KCTF
SN: 4E6B0C83AA2E6B6E946477B2149A8816D730

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