Skip to content

06_AES

优质讲解 【【AES加密算法】| AES加密过程详解| 对称加密| Rijndael-128| 密码学| 信息安全】

1. 算法基本概述与参数

AES 是一种对称的分组加密 (Block Cipher) 算法，旨在取代老旧的 DES 算法。其核心设计遵循严格的矩阵替换与置换网络。

  • 明文/密文长度：固定为 128 位（即 16 字节）。在运算中，这 16 字节会被按列优先的方式排布成一个 \(4 \times 4\) 的状态矩阵。

  • 密钥长度与循环轮数：密钥长度有三种规格，处理方式极其相似，唯一的区别在于密钥长度每增加 64 位，算法的循环次数增加两轮：

    • 128 位 (16 字节)：10 轮循环

    • 192 位 (24 字节)：12 轮循环

    • 256 位 (32 字节)：14 轮循环

2. 数学基础

AES 的极高安全性来源于其并非使用普通的算术加乘法，而是完全构建在有限域 (Galois Field) 抽象代数之上。

2.1 有限域 GF(\(2^8\)) 的定义

本质上，域（Field）是一个可以在其上进行加减乘除运算而不脱离该集合的元素集。AES 采用了 GF(\(2^8\))，该群内包含区间 [0000 0000, 1111 1111] 内的 256 个元素 。

  • 不可约多项式：为了确保乘法后结果仍在该域内，AES 规定所有乘法都必须模除一个 8 次不可约多项式 \(p(x) = x^8 + x^4 + x^3 + x + 1\)。

  • 该多项式对应的二进制数为 1 0001 1011，对应的十六进制为常数 0x11B。

  • 不可约多项式 (Irreducible Polynomial)：在多项式环中，如果一个多项式不能被分解为两个次数较低且系数也在该域中的多项式的乘积，它就被称为不可约多项式。它的地位类似于整数集中的素数（质数）。

  • 在 GF(\(2^8\)) 中，所有元素都可以表示为最高次数不超过 7 次的多项式。当两个这样的多项式相乘时，结果的最高次数可能达到 14 次，这超出了 8 位的表示范围（即发生了溢出）。为了让结果重新回到 GF(\(2^8\)) 域内（保持在 8 位以内），必须将其除以一个 8 次多项式并取余数（即求模）。

  • 只有模一个不可约多项式，才能保证集合内的每一个非零元素都存在“乘法逆元”（即满足 \(a \cdot a^{-1} \equiv 1\)）。如果多项式可约，域中就会出现“零因子”（两个非零元素相乘为零），这就破坏了“域”的代数结构，导致无法进行解密。

  • 一定得是 0x11B 吗？

    不一定。在 GF(2) 上，8 次不可约多项式总共有 30 个。AES 算法设计者从中选定了 \(x^8 + x^4 + x^3 + x + 1\)（对应的二进制表示即为 0x11B）。选择它的原因主要是为了提升软硬件的计算效率：它的非零项极少（汉明重量低），且非零项集中在低次幂，这使得在硬件电路和代码移位计算中非常高效且节省资源。

2.2 GF(\(2^8\)) 上的基本运算方法

  • 加法 (等同于减法)：在 GF(\(2^8\)) 中，加法就是多项式系数的模 2 加法，等价于按位异或 (XOR) 运算。例如：\(10110110 \oplus 11000011 = 01110101\) 。

  • 乘法与农夫算法 (Peasant Algorithm)：有限域的乘法相当于多项式相乘后 \(\pmod{\text{0x11B}}\)。由于硬件或代码实现多项式长除法效率低，通常采用“农夫算法”逐步计算：

    • 将被乘数 \(x\) 不断左移 1 位，乘数 \(y\) 不断右移 1 位。

    • 如果 \(y\) 的最低位是 1，就把当前的 \(x\) 累加（异或）到最终乘积结果中。

    • 关键处理：在每次 \(x\) 左移后，如果 \(x \ge \text{0x100}\)（即溢出 8 位），必须令其与不可约多项式异或（即 \(x = x \oplus \text{0x11B}\)）以完成求模，确保数值安全地落回 8 位以内。

3. AES-128 核心加密流程拆解

以 128 位密钥为例，总共需要进行初始变换、9 轮常规循环以及 1 轮最终轮。

步骤 0：初始变换 (AddRoundKey)

在进入主体循环前，首先将 \(4 \times 4\) 的明文矩阵与原始的 \(4 \times 4\) 密钥矩阵进行逐字节的异或（XOR）运算。

常规循环 1~9 轮（4个环节）

每一轮依次执行以下四个步骤：

① 字节代换 (ByteSub)

这是 AES 的唯一非线性变换，将矩阵中的每个字节送入 S-box（代换盒）查找替换表。

S-box 的查表方式 (Lookup Table)：

S-box 在物理上存储为一个 \(16 \times 16\) 的二维字节数组（包含 256 个元素），查表的依据是输入字节的十六进制值。

  • 拆分字节：将需要替换的 1 个字节（8 位二进制）拆分为高 4 位和低 4 位。

  • 行与列的定位：高 4 位（前一个十六进制字符）决定了 S-box 的行号（\(0 \sim \text{F}\)），低 4 位（后一个十六进制字符）决定了 S-box 的列号（\(0 \sim \text{F}\)）。

  • 举例说明：如果输入的字节是 0x5A（二进制 0101 1010）。其中高 4 位为 5，低 4 位为 A。那么就去查找 S-box 的第 5 行、第 A 列，将该位置交叉点存储的字节作为代换后的输出结果返回。

  • S-box 生成原理：它并非随机生成，而是具备严谨的数学结构：

    1. 求逆元：首先在 GF(\(2^8\)) 上求该字节 \(a\) 的乘法逆元 \(a^{-1}\)（可使用扩展欧几里得算法求得；若 \(a=0\) 则其逆元规定为自身）。

    2. 仿射变换：对得到的逆元进行 GF(2) 上的仿射变换。公式化简表示为：

      \[ sbox[a] = (((a^{-1} \pmod{\text{0x11B}}) \cdot \text{0x1F}) \pmod{\text{0x101}}) \oplus \text{0x63} \]

      这个设计是为了破坏数据的代数结构，抵抗差分密码分析和线性密码分析。

② 行移位 (ShiftRow)

在 \(4 \times 4\) 状态矩阵上进行行操作，实现数据的横向扩散：

  • 第一行 (Row 0)：保持不变。

  • 第二行 (Row 1)：循环左移 1 个字节。

  • 第三行 (Row 2)：循环左移 2 个字节。

  • 第四行 (Row 3)：循环左移 3 个字节。

③ 列混合 (MixColumn)

该步骤利用有限域矩阵乘法，将矩阵每一列的 4 个字节进行混淆，实现纵向扩散。

  • 加密计算公式：将状态矩阵的每一列视为一个 \(4 \times 1\) 向量，左乘一个给定的 \(4 \times 4\) 固定矩阵。

    固定矩阵的生成基于多项式 \(3x^3 + x^2 + x + 2\)，具体相乘结构如下：

    \[ \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \begin{bmatrix} p_{00} \\ p_{10} \\ p_{20} \\ p_{30} \end{bmatrix} = \begin{bmatrix} p'_{00} \\ p'_{10} \\ p'_{20} \\ p'_{30} \end{bmatrix} \]

    (注：矩阵乘法中的加法为异或，乘法为 GF(\(2^8\)) 的模 0x11B 乘法)

状态矩阵列的多项式化

设状态矩阵的某一列包含四个字节，从上到下依次为 \(c_0, c_1, c_2, c_3\)。

这四个字节可以构建为一个 3 次多项式：

\[ c(x) = c_3x^3 + c_2x^2 + c_1x + c_0 \]

(注：这里的 \(c_i\) 本身也是 GF(\(2^8\)) 中的多项式，通常用两位十六进制数表示。)

核心运算：模 \(x^4 + 1\) 的多项式乘法

AES 规定，将输入的列多项式 \(c(x)\) 与一个给定的固定 3 次多项式 \(a(x)\) 进行多项式乘法。

  • 加密时的固定多项式：\(a(x) = 3x^3 + 1x^2 + 1x + 2\)

  • 降次取模：两个 3 次多项式相乘，最高次幂会达到 6 次。为了保证相乘后的结果依然是一个 3 次多项式（正好能严丝合缝地填回矩阵的一列 4 个字节中），这种乘法必须再模一个特定的多项式 \(x^4 + 1\)。

  • 降次核心规律：模 \(x^4 + 1\) 的数学特性是 \(x^4 \equiv -1 \pmod{x^4+1}\)。在 GF(2) 下，加法与减法等价（即 \(1 = -1\)），因此 \(x^4 \equiv 1\)。

    这推导出了一个极其重要的周期性降次规律：

    \[ x^i \equiv x^{i \bmod 4} \]

    也就是说计算中出现的 \(x^4\) 变成了常数 \(1\)，\(x^5\) 变成了 \(x\)，\(x^6\) 变成了 \(x^2\)，以此类推。

从多项式代数展开到循环矩阵的推导

正是因为 \(x^i \equiv x^{i \bmod 4}\) 的降次特性，使得多项式相乘展开后的系数项发生了循环移位组合。

设 \(a(x) = a_3x^3 + a_2x^2 + a_1x + a_0\)，与 \(c(x)\) 相乘后得到结果多项式 \(d(x) = d_3x^3 + d_2x^2 + d_1x + d_0\)。

根据代数展开并应用 \(x^4 \equiv 1\) 的降次规则，我们可以计算出 \(d(x)\) 的各项系数：

  • 常数项 \(d_0\)：除了 \(a_0c_0\) 外，\(a_3x^3 \cdot c_1x = a_3c_1x^4 \equiv a_3c_1\)。同理，各项组合为：\(d_0 = a_0c_0 + a_3c_1 + a_2c_2 + a_1c_3\)

  • 一次项 \(d_1\)：\(d_1 = a_1c_0 + a_0c_1 + a_3c_2 + a_2c_3\)

  • 二次项 \(d_2\)：\(d_2 = a_2c_0 + a_1c_1 + a_0c_2 + a_3c_3\)

  • 三次项 \(d_3\)：\(d_3 = a_3c_0 + a_2c_1 + a_1c_2 + a_0c_3\)

如果我们将上述等式组写成矩阵相乘的形式，就会得到：

\[ \begin{bmatrix} d_0 \\ d_1 \\ d_2 \\ d_3 \end{bmatrix} = \begin{bmatrix} a_0 & a_3 & a_2 & a_1 \\ a_1 & a_0 & a_3 & a_2 \\ a_2 & a_1 & a_0 & a_3 \\ a_3 & a_2 & a_1 & a_0 \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{bmatrix} \]

结论：结果矩阵的每一行，实际上就是将 \(a(x)\) 的系数排列后，逐行向右循环移位一位得到的。这就是为什么多项式乘法可以完美转化为左乘一个循环固定矩阵的根本代数原因。

  • 解密对应：解密时左乘加密多项式的逆多项式（数组表示为 {0x0B, 0x0D, 0x09, 0x0E}）构成的固定逆矩阵。
\[ \begin{bmatrix} \text{0E} & \text{0B} & \text{0D} & \text{09} \\ \text{09} & \text{0E} & \text{0B} & \text{0D} \\ \text{0D} & \text{09} & \text{0E} & \text{0B} \\ \text{0B} & \text{0D} & \text{09} & \text{0E} \end{bmatrix} \]

④ 轮密钥加 (AddRoundKey)

将前一步的结果与当前轮生成的子密钥矩阵（也是 \(4 \times 4\)）进行简单的异或运算。

第 10 轮最终轮 (The Final Round)

最终一轮省略了列混合（MixColumn）步骤（为了使加密和解密的结构能够保持对称）。只包含：

  1. 字节代换 (ByteSub)

  2. 行移位 (ShiftRow)

  3. 轮密钥加 (AddRoundKey)

4. 密钥扩展逻辑 (Key Expansion)

AES 算法需要从 128 位的原密钥扩展出 11 组轮密钥（1组用于初始变换，10组用于10轮循环，相当于新生成 10 个 \(4 \times 4\) 矩阵，共计 44 个列/字）。

设原密钥构成的 \(4 \times 4\) 矩阵的四列（每个列为一个 32-bit 的“字”/Word）分别为：\(W_0, W_1, W_2, W_3\)。

要生成后续的第 \(i\) 列（\(i\) 从 4 取到 43），遵循以下核心等式机制：

情景 A：如果 \(i\) 不是 4 的倍数

计算极为简单，直接将其前一列和四列前（上一组同一位置）的列进行异或：

\[ W[i] = W[i-4] \oplus W[i-1] \]

情景 B：如果 \(i\) 是 4 的倍数（每一轮起始列的处理）

需调用非线性函数 \(T\)：

\[ W[i] = W[i-4] \oplus T(W[i-1]) \]

其中，非线性变换函数 \(T\) (Function T) 由三个精密步骤串联组成：

  1. 字循环 (RotWord)：将上一列的 \(4\) 个字节循环左移 \(1\) 个字节。即将输入的字节序列 \([b_0, b_1, b_2, b_3]\) 物理挪动为 \([b_1, b_2, b_3, b_0]\)。

  2. 字节代换 (SubWord)：将位移后的四个字节分别送入 S-box 进行替换查表操作。

  3. 轮常量异或 (Rcon XOR)：将上一步结果的首个字节（或整个字的特定位）同轮常量 \(Rcon[j]\) 进行异或（\(j\) 表示当前生成的轮数）。

    • 轮常量计算：第 \(j\) 轮常数的首字节 \(r = 2^{j-1} \pmod{\text{0x11B}}\)。

    • 1到10轮的常量值序列为：0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36。