海风月影的帖子：https://bbs.pediy.com/thread-267902.htm
大龙猫赛题设计：https://bbs.pediy.com/thread-267023.htm

本文旨在，彻底研究明白为什么，并且对学习理解海风月影的解法提供帮助

本文 + 代表 xor

PGX门真值表：
0 0 0 -> 1 0 0
0 0 1 -> 0 0 1
0 1 0 -> 0 1 1
0 1 1 -> 1 0 1
1 0 0 -> 0 0 0
1 0 1 -> 0 1 0
1 1 0 -> 1 1 1
1 1 1 -> 1 1 0

我们先考虑前126位变换
我们定义 G((0, a_0), (1, a_1), ..., (41, a_41)) 代表一个126位输入，第i组的3位构成数值 a_i
G 的作用是把序列变成数值。
找短点的举例子，比如 G((0, 1), (1, 3), (2, 4)) 就是 1, 3, 4 拼接起来，即二进制 100011001 = 十六进制 0x119

一个与题目算法无关的客观真理是：
G({(j, a_j), 0 <= j < i}, (i, a_i), {(j, a_j), i < j <= 41}) + G({(j, b_j), 0 <= j < i}, (i, b_i), {(j, b_j), i < j <= 41})
= G({(j, a_j), 0 <= j < i}, (i, a + b), {(j, a_j), i < j <= 41}) + G({(j, b_j), 0 <= j < i}, (i, 0), {(j, b_j), i < j <= 41})
记为 1 式

P是42个PGX门的链接，由于 PGX 的局域性，PG = GP
用 Q 代表 PGX 的逆运算，我们有：
PG({(j, a_j), 0 <= j < i}, (i, Q(a)), {(j, a_j), i < j <= 41}) + PG({(j, b_j), 0 <= j < i}, (i, Q(b)), {(j, b_j), i < j <= 41})
= PG({(j, a_j), 0 <= j < i}, (i, Q(a + b)), {(j, a_j), i < j <= 41}) + PG({(j, b_j), 0 <= j < i}, (i, Q(0)), (i, 0), {(j, b_j), i < j <= 41})
记为 2 式
有 PGX 真值表我们知道 Q(0) = 4，其实这个数值不重要啦
海风月影提到“位没有重叠，不然就放弃了”，就是因为需要上述关系成立。

2 式两边乘以矩阵 M 等式仍成立，记为 3 式
我们再算一组
MPG({(k, a_k), 0 <= k < i}, (i, Q(a)), {(k, a_k), i < k < j}, (j, Q(c)), {(k, a_k), j < k <= 41}) +
MPG({(k, b_k), 0 <= k < i}, (i, Q(b)), {(k, b_k), i < k < j}, (j, Q(d)), {(k, b_k), j < k <= 41})
= MPG({(k, a_k), 0 <= k < i}, (i, Q(a + b)), {(k, a_k), i < k < j}, (j, Q(c)), {(k, a_k), j < k <= 41}) +
MPG({(k, b_k), 0 <= k < i}, (i, Q(0)), {(k, b_k), i < k < j}, (j, Q(d)), {(k, b_k), j < k <= 41})
= MPG({(k, a_k), 0 <= k < i}, (i, Q(a + b)), {(k, a_k), i < k < j}, (j, Q(c + d)), {(k, a_k), j < k <= 41}) +
MPG({(k, b_k), 0 <= k < i}, (i, Q(0)), {(k, b_k), i < k < j}, (j, Q(0)), {(k, b_k), j < k <= 41})

41组完全展开：
MPG({(i, Q(a_i), 0 <= i <= 41}) + MPG({(i, Q(b_i), 0 <= i <= 41}) = MPG({(i, Q(a_i + b_i), 0 <= i <= 41}) + MPG({(i, Q(0), 0 <= i <= 41})

记 B = MPG({(i, Q(0), 0 <= i <= 41}) 是个定值。

这个关系与矩阵形式 Y = A*X + B 是等价的。
如果要从头证明这个等价，必要性是显然的，充分性的证法（这个还真有用）是，
在每个组找线性无关的 3 个向量：
{{(j, Q(0)), 0 <= j < i}, (i, Q(a1)), {(j, Q(0)), i < j <= 41}}
{{(j, Q(0)), 0 <= j < i}, (i, Q(a2)), {(j, Q(0)), i < j <= 41}}
{{(j, Q(0)), 0 <= j < i}, (i, Q(a3)), {(j, Q(0)), i < j <= 41}}
尾部两位不做PGX变换，线性相加在方程中，不影响等式成立。
41 个组有 126 个向量，再加上尾部两位分别置 (0, 1) 和 (1, 0) 得到两个向量，得到 128 个线性无关的向量
这些向量构成128位向量空间的一组基，
剩下的证明，和线性映射可以表示成矩阵乘法的证明，形式完全一样。（注意 +B）

我们会得到 Y = CZ + B, Z = f(X) 的形式，与海风月影的 Y = AX + B 等价，此处的 B 正是上文的 B = MPG({(i, Q(0), 0 <= i <= 41})
所以海风月影能得到那个有大矩阵的式子，海风月影的公式中的 B 也正是我们得到的 B

如果 3 式中没有 Q，海风月影解个方程就直接得到了最终结果。

但是由于 Q 的存在，我们得到的是和基的选取相关的 Z

接下来海风月影需要把 Z 转换成 X
由于 Z 与 X 的关系是局域化映射的 P 和基的选取决定的，所以，
Z 与 X 的对应，是每组组内局域化的对应，组间无关

我们可以局部蛮力穷举把这个关系求出来，怎么蛮力呢，做实验，
MP(r) + MP(s) = MP(t) + MP(0)
我们就知道哪些r,s,t是一组了。
与 3 式的关系是：
r = Q(a)
s = Q(b)
t = Q(a + b)

r,s,t真的是X作为原始输入的值，但Q(a)，Q(b)，Q(a + b)被基的选取加了一层映射，所以这个对应关系和从Z到X是有距离。
但是这个映射也是8元素集合到8元素集合的小规模双射。
海风月影写的关于交换的那一段就是在做这个映射。至于为什么，就难以推导了，我们只知道8元素集合到8元素集合的小规模双射，可以看出简单的规律，海风月影看到的是一些值出现时交换一下就可以了。

海风月影需要的关键步骤不是推导这个可以看出的小规模映射，而是找到r,s,t的正确分组，这是关键的。
怎么着呢？由于局域化，最好的办法是蛮力穷举。
下面节选海风月影的蛮力穷举，我们可以看到，非常的野蛮：

综上所述，求解 AddRoundKey 的逆运算，只需要三步：
基：每个组找三个基，总计126个基，加上尾部2位，128个基
解方程：高斯消元、逆矩阵。。。怎么开心怎么来
Z->X 映射表：局部蛮力穷举

海风月影的解题过程就是这个过程！

鸣谢！
海风月影
看场雪
科锐的优秀学生

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