对AES加密流程的介绍，以及对四轮AES的Square Attack分析。
AES
首先 AES 属于对称密码中的分组加密算法，是最著名的 SPN 结构分组密码。在 AES 标准中，分组长度只能是 128 位（16 字节）。密钥的长度可以使用 128 位、192 位或 256 位。对应的加密轮数：
| AES | 密钥长度 | 分组长度 | 加密轮数 |
|---|---|---|---|
| AES-128 | 128位 | 128位 | 10 |
| AES-192 | 192位 | 128位 | 12 |
| AES-256 | 256位 | 128位 | 14 |
在下述的介绍和分析中，我们均使用 AES-128 作为分析对象。
密钥扩展（Key Expansion）
AES 在加密前，需要根据初始密钥生成各轮使用的轮密钥（Round Keys）。AES-128 一共会得到 11 组轮密钥：第 0 组就是初始密钥本身，后面 10 组由密钥扩展生成。介绍密钥扩展的详细操作之前，先介绍 RotWord、SubWord，以及轮常量 Rcon：
RotWord
输入为 4 bytes，输出同为 4 bytes。具体操作是将 4 个字节循环左移一个字节：
SubWord
输入为 4 bytes。对每一个字节做 S 盒映射，即 $x \mapsto S[x]$。密钥扩展中的非线性就来自这一步，而不是来自后面的 Rcon。
Rcon
Rcon 是密钥扩展中的轮常量，用来打破不同轮密钥之间的对称性。它本身只是常数异或，并不引入非线性。形式为一个 4 字节的 word，其中只有第一个字节非零：
其中 $x=02$，运算在 $\mathbb{F}_{2^{8}}$ 上进行，模多项式为 $m(x)=x^8+x^4+x^3+x+1$。
实现一般直接预计算后存入数组（下标 0 的 $0x00$ 是占位，真正从 $Rcon[1]=0x01$ 开始用）。
扩展流程
AES-128 首先接收 16 字节的初始密钥，并将其按照列优先填入 $4\times 4$ 的矩阵中。如对于0x000102030405060708090a0b0c0d0e0f，将其排入矩阵中即：
生成下一组轮密钥时，对上一组轮密钥做如下操作（生成 RoundKey 1 时，上一组就是初始密钥）：
- 对最后一列依次进行 RotWord 和 SubWord
- 异或上 Rcon(Round)
- 前两步得到的结果异或上第一列的值
经过以上操作后，即可得到下一组轮密钥的第一列。举个例子：
初始密钥为：
对最后一列进行 RotWord 和 SubWord：
异或上 Rcon(Round) 即 $Rcon[1]$：
异或上第一列的值:
所以 RoundKey 1 的第一列即为：
剩下的三列，则是将前一列和上一轮的相同列进行异或。
如第二列：
同样的操作，可以得到 RoundKey 1 为：
⚠️：AES-256（$Nk=8$）的密钥扩展还要在 $i \bmod Nk = 4$ 时额外做一次 SubWord；AES-128 / AES-192 没有这一步。
加密（Encryption）
在 AES 加密中，每一块的输入均为 16 字节，并和密钥扩展一样按列优先填入 $4\times 4$ 的 State 矩阵。
加密中使用的主要操作为：
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
下面先对各操作进行介绍。
SubBytes
对 State 中每一个字节做 S 盒替换，所用 S 盒与 KeyExpansion 中的 SubWord 相同。
ShiftRows
对 State 的每一行做循环左移：第 0 行不移，第 1 行左移 1 字节，第 2 行左移 2 字节，第 3 行左移 3 字节。如下所示：
MixColumns
把每一列看作 4 维向量，左乘一个固定矩阵（矩阵里的 $02$、$03$、$01$ 都是字节的十六进制写法）：
即：
⚠️：其中乘法在 $\mathbb{F}_{2^{8}}$ 上进行，模多项式 $m(x)=x^8+x^4+x^3+x+1$。这里的加法就是异或。
AddRoundKey
将当前 $4\times 4$ 的状态矩阵与当前 16 字节轮密钥按对应位置异或。轮密钥同样按列优先排成 $4\times 4$ 矩阵。
加密流程
AES-128 加密共 10 轮，但完整流程并不是每一轮都做完全相同的四步。顺序是：
- 加密开始前：AddRoundKey（第 0 轮密钥，即初始密钥）
- 第 1–9 轮：SubBytes → ShiftRows → MixColumns → AddRoundKey
- 第 10 轮：SubBytes → ShiftRows → AddRoundKey（跳过 MixColumns）
解密（Decryption）
按照加密的过程，对每一个组件进行对应的逆操作即可。
Square Attack
Square 攻击最早由 Daemen、Knudsen、Rijmen 在 1997 年针对 Square 密码提出。AES 沿用了 Square 的 SPN 结构，所以同样适用。它是一种选择明文攻击，也是后来积分攻击（Integral cryptanalysis / 饱和攻击）的原型：不看一对明文的差分，而看一组明文的整体积分性质。
基本思想很简单：构造 256 个有结构的明文，让某些字节跑遍 $\mathbb{F}_{2^8}$，然后追踪这 256 个中间态在每个字节位置上的异或和是否保持为 $0$。线性层会把这种性质扩散开；只要某个字节还是活跃的，S 盒作为双射也会把它保持为活跃。一旦字节只剩下“异或和为 $0$、但不再取遍 256 个值”，再过 S 盒这个性质就会坏掉。四轮 AES 的 Square 攻击，靠的就是下面这个三轮积分区分器。
δ-set 与活跃状态
考虑 256 个 AES 状态构成的集合
对某个字节位置 $(r,c)$：
- 活跃（Active，$A$）：集合在该位置取遍 $\mathbb{F}_{2^8}$ 中每个值恰好一次
- 常数 / 非活跃（Constant / Passive，$C$）：该位置在 256 个状态里都等于同一个常数
- 平衡（Balanced，$B$）：该位置 256 个值的异或和为 $0$，即 $\displaystyle\bigoplus_{i=0}^{255}s^{(i)}_{r,c}=0$
活跃一定平衡，256 个相同常数也一定平衡，但平衡不一定活跃。
狭义 δ-set：恰好一个字节位置活跃，其余 15 个字节都是常数。这就是 Square 攻击一开始选用的明文集合。例如活跃字节放在 $(0,0)$：
广义 δ-set（原论文中的 $\Lambda$-set）：允许若干个字节同时活跃，其余字节为常数。第 1 轮 MixColumns 之后出现的“一整列都是 $A$”，就是典型的广义 δ-set。
⚠️：广义 δ-set 的集合大小仍然是 256。 多个 $A$ 只表示每个活跃位置各自取遍 $00$–$FF$，它们之间通常是相关的，并不是 $k$ 个字节独立遍历（否则集合大小会变成 $256^k$）。
δ-set 的异或和性质
先看单个字节上的求和。活跃字节取遍全空间：
原因是每个比特在 $0$–$255$ 中恰好出现 $128$ 次 $1$，$128$ 为偶数。常数字节同样有
因为相同值异或偶数次结果为 $0$。所以 δ-set 在每一个字节位置上都是平衡的，无论该位置是 $A$ 还是 $C$。
再看四个组件怎么作用在这 256 个状态上：
- AddRoundKey：每个状态异或同一轮密钥。$256$ 为偶数，常数密钥会被消掉：活跃字节变成 $A\oplus k_{r,c}$，仍取遍 256 个值；常数字节仍是常数。
- ShiftRows：只是搬位置，不改变某个字节是 $A$ 还是 $C$，只改变活跃位置。
- MixColumns：列上的线性双射。对 256 个状态求异或可以和矩阵乘法换序：因此：一列的输入异或和为 $0$，输出这一列的异或和仍为 $0$。更强的一点是，MixColumns 是 MDS 的——一列里只要有 1 个 $A$、3 个 $C$，输出 4 个字节就全是 $A$。
- SubBytes：S 盒是字节上的双射，所以 $A$ 仍是 $A$，$C$ 仍是 $C$。但如果一个字节只是 $B$ 而不是 $A$，S 盒一般会把平衡性毁掉。这就是为什么区分器只能用到第 3 轮 MixColumns / AddRoundKey 之后，不能再白白过第 4 轮 SubBytes。
三轮传播
下面跟踪一个狭义 δ-set 走完 3 个完整轮。不妨设明文的活跃字节在 $(0,0)$；活跃字节换到别的位置时，只是被激活的列不同，传播方式相同。四轮 AES 在第 1 轮之前还有一次初始 AddRoundKey，一并写上。起始状态与初始 AddRoundKey
明文是狭义 δ-set。异或常数密钥不改变活跃 / 常数模式：变换后活跃位置：仍是 $(0,0)$。第 1 轮
SubBytes变换后活跃位置：$(0,0)$。S 盒双射，$A$ 变成 $S(A)$ 仍取遍 256 个值；$C$ 变成 $S(C)$ 仍是常数。
ShiftRows
变换后活跃位置：仍是 $(0,0)$。活跃字节在第 0 行，循环左移 $0$ 字节，所以这一轮 ShiftRows 看起来像没动。若一开始 $A$ 在第 $r$ 行，这里会沿该行左移 $r$ 个字节，随后 MixColumns 激活的就是那一列。
MixColumns
此时只有第 0 列含有活跃字节：$(A,C,C,C)^{\mathrm{T}}$。写成
系数 $02$、$01$、$03$ 都非零，每个输出字节都是 $A$ 的双射仿射函数，因此这一列 4 个字节全部变成 $A$；其余三列输入全是 $C$，输出仍全是 $C$。
变换后活跃位置：$(0,0),\ (1,0),\ (2,0),\ (3,0)$。集合从狭义 δ-set 变成了“一列全活跃”的广义 δ-set。这 4 个 $A$ 都是同一个明文字节的函数，彼此线性相关。
AddRoundKey
变换后活跃位置：仍是第 0 列四个字节。
第 2 轮
SubBytes
变换后活跃位置：$(0,0),\ (1,0),\ (2,0),\ (3,0)$。四个 $A$ 各自再过一遍双射，仍然活跃。
ShiftRows
这一步是扩散的关键：同一列里的 4 个 $A$ 被拆到 4 个不同列。按 AES 的行左移：
- 第 0 行左移 0：$[A\ C\ C\ C]\to[A\ C\ C\ C]$
- 第 1 行左移 1：$[A\ C\ C\ C]\to[C\ C\ C\ A]$
- 第 2 行左移 2：$[A\ C\ C\ C]\to[C\ C\ A\ C]$
- 第 3 行左移 3：$[A\ C\ C\ C]\to[C\ A\ C\ C]$变换后活跃位置：$(0,0),\ (1,3),\ (2,2),\ (3,1)$，每列恰好一个 $A$。
MixColumns
现在每一列都是“1 个 $A$ + 3 个 $C$”，和第 1 轮 MixColumns 同一件事，只是活跃字节所在的行不同。MDS 性质保证：无论 $A$ 在列中的哪一行，输出整列都变成 $A$。于是 4 列同时被激活：
变换后活跃位置：全部 16 个字节。这仍是广义 δ-set，但 16 个 $A$ 全部依赖于最初那一个明文活跃字节。
AddRoundKey
变换后活跃位置：仍是全部 16 个字节。
第 3 轮
SubBytes
变换后活跃位置：全部 16 个字节。每个位置仍是最初那个 $x$ 的双射函数，所以仍取遍 $0$–$255$。
ShiftRows
变换后活跃位置：仍是全部 16 个字节。这一步只是把各行的 $A$ 换了列，模式看起来一样。
MixColumns
到这里，每个字节都还是 $A$，但同一列的 4 个字节不再是“一个 $A$ 加三个 $C$”，而是 4 个相关的 $A$。记一列为 $(z_0,z_1,z_2,z_3)$，每个 $z_j=f_j(x)$ 都是双射，输出例如
$y_0$ 作为 $x$ 的函数一般不再是双射，所以不再活跃。但异或和仍然为 $0$：
因为每个 $f_j$ 取遍全空间。于是每个输出字节都从 $A$ 退化成 $B$：
变换后：16 个位置全部平衡，但已经不是 δ-set。
AddRoundKey
变换后：仍是 16 个 $B$。这就是三轮 Square 区分器：对这个 256 元明文集合，3 轮 AES 之后每个字节都满足
对随机置换来说，单个字节位置上异或和恰好为 $0$ 的概率只有 $2^{-8}$。
⚠️：第 4 轮一开始的 SubBytes 会作用在 $B$ 而不是 $A$ 上，平衡性一般被破坏。 所以密文上不能直接求和，要把最后一轮剥掉。
四轮密钥恢复
四轮 AES 的结构是：
- 初始 AddRoundKey（$K_0$）
- 第 1–3 轮：SubBytes → ShiftRows → MixColumns → AddRoundKey（$K_1,K_2,K_3$）
- 第 4 轮（最后一轮）：SubBytes → ShiftRows → AddRoundKey（$K_4$，没有 MixColumns）
第 3 轮出口 $s_3$ 的每个字节都是 $B$。最后一轮把 $s_3$ 变成密文 $C$：
第 0 行 ShiftRows 不动，所以左上角最干净：
单字节检验
正确密钥下，$s_3$ 的每个位置都满足异或和为 $0$。把上式反过来：
于是对猜测值 $g$，只要检查
成立则 $g$ 可能是 $K_4[r][c]$。
这里不用单独再猜 InvShiftRows：密钥字节按密文位置来猜，$S^{-1}$ 之后自然对应 $s_3$ 的某个字节，而 $s_3$ 的 16 个位置全部是 $B$，检验哪一个都合法。
正确的 $g$ 永远能通过。错误的 $g$ 通过一次检验的概率大约是 $2^{-8}$，原因如下。
记正确密钥为 $k=K_4[r][c]$，猜错时 $\Delta=k\oplus g\neq 0$。把密文代回去：
其中 $x_i$ 是对应的 $s_3$ 字节。检验值其实是
$\pi_\Delta$ 是一个与 $\Delta$ 有关的固定置换，而且因为 S 盒非线性，$\Delta\neq 0$ 时它不会保持异或和。
如果 $\{x_i\}$ 仍是活跃字节，取遍 $00$–$FF$ 各一次，那么 $\pi_\Delta(x_i)$ 也会取遍全空间，$\sigma(g)$ 对所有 $g$ 都是 $0$，检验就废了。第 3 轮 MixColumns 之后 $x_i$ 只是平衡、不再活跃：256 个值有重复、有缺失，只保证 $\bigoplus x_i=0$。再套上非线性的 $\pi_\Delta$，这个“和为 $0$”不再被强制成立。
$\sigma(g)$ 是一个字节，有 $2^{8}$ 种可能。把错误密钥下的 $\sigma(g)$ 看成近似均匀随机，就得到
一组 δ-set 扫完 256 个猜测：正确密钥必留下，错误密钥大约还剩 $255\times 2^{-8}\approx 1$ 个，所以通常还要用第二组 δ-set 再滤一次。
恢复一个密钥字节
以 $K_4[0][0]$ 为例。
- 选一个狭义 δ-set：256 个明文，只有一个字节遍历 $00$–$FF$，其余 15 个字节固定。
- 用四轮 AES 加密，得到 256 个密文 $C^{(0)},\ldots,C^{(255)}$。
- 对每个猜测 $g=0,1,\ldots,255$，计算若 $\sigma(g)=0$，把 $g$ 放进候选集合。
- 再选一个 δ-set（活跃位置可以不变，但常数部分要换），重复第 2、3 步，只保留两组都满足 $\sigma(g)=0$ 的 $g$。
两组之后，正确密钥几乎一定唯一剩下。极少数情况再加第三组即可。
恢复完整的 $K_4$
$s_3$ 的 16 个字节都平衡，因此 同一批密文可以同时打 $K_4$ 的全部 16 个字节：对每个位置 $(r,c)$ 独立做上面的单字节检验。密钥字节之间没有 MixColumns 搅在一起，复杂度是 $16\times 2^{8}$，不是 $2^{128}$。
步骤可以写成：
- 加密 2 组 δ-set，每组 256 个明文，共 512 个选择明文。
- 对 $K_4$ 的 16 个位置分别穷举 $2^{8}$ 个猜测，用两组密文做异或和检验。
- 得到完整的 16 字节 $K_4$。
从 $K_4$ 反推主密钥
AES-128 的密钥扩展可逆，我们只需要从$K_{4}$进行逆操作，即可得到主密钥。