AES 里的有限域：S 盒其实是在 $\mathbb{F}_{2^8}$ 里求逆

全文分三层：

1. 通俗理解：混淆与扩散，AES 每一轮在干什么
2. 实际用处：AES 无处不在，以及为什么它不怕量子计算机
3. 数学原理：$\mathbb{F}_{2^8}$ 的构造、S 盒、MixColumns，附 FIPS 197 标准里的手算例子

第一层：通俗理解

1.1 对称加密要做两件事

香农在 1949 年提出，好的分组密码要同时做到：

• 混淆（confusion）：密文和密钥的关系要尽量复杂、非线性，不能列个线性方程组就解出来。
• 扩散（diffusion）：明文改动一位，密文要有一半左右的位跟着变（"雪崩效应"）。

AES 就是一台把这两件事反复做 10 到 14 轮的机器。

1.2 AES 的一轮

AES 把 16 字节的数据排成 $4 \times 4$ 的方阵，每一轮做四步：

做两轮之后，任意一个输入字节就已经影响到全部 16 个输出字节。

1.3 为什么要用有限域

字节有 256 种取值。我们想对字节做"乘法"和"除法"，结果还得是一个字节。普通整数乘法会溢出，模 256 又不是域（$2 \times 128 \equiv 0$，有零因子，不能除）。

办法是把字节看成系数为 0 或 1 的多项式，在模一个不可约多项式的意义下做运算。这样 256 个字节恰好构成一个域：能加减乘除，每个非零元都有逆元。

第二层：实际用处

AES 是 2001 年美国 NIST 通过公开竞赛选出的标准（原名 Rijndael，两位比利时密码学家设计）。今天它几乎无处不在：

• HTTPS 里的数据加密（AES-GCM）
• 手机和电脑的全盘加密（iOS、Android、BitLocker、FileVault）
• Wi-Fi WPA2/WPA3、VPN、压缩包加密
• 加密货币钱包文件、密码管理器

硬件加速：Intel、AMD 的 AES-NI 指令和 ARM 的加密扩展直接在芯片里实现一轮 AES，速度可达每秒数 GB。

量子计算机：AES 没有 RSA 那样的代数陷门，Shor 算法用不上；Grover 算法只能把暴力搜索从 $2^{128}$ 降到约 $2^{64}$。所以用 AES-256 就足够应对，详见《后量子密码》。

第三层：数学原理

3.1 构造 $\mathbb{F}_{2^8}$

取 $\mathbb{F}_2 = \{0, 1\}$（加法是异或）。多项式

$$m(x) = x^8 + x^4 + x^3 + x + 1$$

在 $\mathbb{F}_2$ 上不可约，所以 $(m(x))$ 是 $\mathbb{F}_2[x]$ 的极大理想，商环

$$\mathbb{F}_{2^8} = \mathbb{F}_2[x] / (m(x))$$

是一个有 $2^8 = 256$ 个元素的域（抽象代数：$F[x]/(f)$ 是域当且仅当 $f$ 不可约）。

一个字节 $b_7 b_6 \cdots b_0$ 对应多项式 $b_7 x^7 + \cdots + b_1 x + b_0$。例如 0x57 $= 01010111_2$ 对应 $x^6 + x^4 + x^2 + x + 1$。

• 加法：系数逐位模 2 相加，就是异或。
• 乘法：多项式相乘，再模 $m(x)$ 取余。实现上就是"乘 $x$ = 左移一位，溢出了就异或 0x1B"。

3.2 手算例子：乘法

3.3 S 盒 = 求逆 + 仿射变换

对每个字节 $a$：

1. 求逆：$b = a^{-1}$ in $\mathbb{F}_{2^8}$（规定 $0^{-1} = 0$）；
2. 仿射变换：把 $b$ 看成 $\mathbb{F}_2^8$ 中的向量，算 $s = Mb \oplus \texttt{63}$，$M$ 是一个固定的 $8 \times 8$ 循环矩阵： $$s_i = b_i \oplus b_{i+4} \oplus b_{i+5} \oplus b_{i+6} \oplus b_{i+7} \oplus c_i \quad (\text{下标模 } 8,\ c = \texttt{63}).$$

为什么用求逆：$x \mapsto x^{-1}$ 在 $\mathbb{F}_{2^8}$ 上是高度非线性的。Nyberg（1993）证明了这类映射对差分攻击和线性攻击有接近最优的抵抗力：任意输入差分最多以 $4/256$ 的概率产生某个特定输出差分。

为什么还要加仿射变换：纯求逆的代数结构太"干净"，可能被代数攻击利用（比如插值攻击），而且 $0$ 和 $1$ 是不动点。仿射变换打乱这种结构，并保证 S 盒没有不动点和"反不动点"。

3.4 MixColumns = 模 $x^4 + 1$ 的多项式乘法

每一列的 4 个字节看成系数在 $\mathbb{F}_{2^8}$ 中的三次多项式 $a(y) = a_3 y^3 + a_2 y^2 + a_1 y + a_0$，然后

$$a(y) \mapsto c(y) \cdot a(y) \bmod (y^4 + 1),\qquad c(y) = \texttt{03}\,y^3 + \texttt{01}\,y^2 + \texttt{01}\,y + \texttt{02}.$$

因为 $y^4 \equiv 1$，这是一个循环卷积，写成矩阵就是

$$\begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix}.$$

注意 $y^4 + 1 = (y+1)^4$ 在特征 2 下可约，所以这个商环不是域，但 $c(y)$ 与 $y^4 + 1$ 互素，因此可逆，解密时乘它的逆 $c^{-1}(y)$ 即可。

这个矩阵还是一个 MDS 矩阵（和 Reed–Solomon 纠错码里的 MDS 码是同一个概念）：输入和输出中非零字节的总数至少是 5。这保证了扩散的速度，也是 AES 设计者"宽轨迹策略"的核心。

总结