高级加密标准 (AES)
原书：《Understanding Cryptography: A Text book for Students and Practitioners》
AES: Advanced Encryption Standard 是今天使用最广的对称加密运算。尽管 AES 中的标准是美国政府应用的标准，AES 块运算加密算法依旧在很多工业标准以及商务系统中使用。包括 AES 安全商务安全标准的有网络安全标准 IPsec、TLS、Wi-Fi 加密标准 IEEE 802.11i、SSH、Skype 以及数不清的安全产品。迄今为止，破解 AES 的最好方法还是暴力破解。
4.1 介绍
在 1999 年美国 NIST: National Institute of Standards and Technology 指示 DES 只能用在落后的系统中，其他系统应该使用 3DES。虽然破解 3DES 的最好方法还是暴力破解，它也有很多问题。首先，软件实现这一算法是低效的；其次，加密块大小只有 64 字节，这显然在今天的很多应用中还是落后的；最后，量子计算机在可预见的未来几十年是可能存在的，因此我们需要 256 位长的密钥长度。所有这些因素，促使了 NIST 寻找一种新的块加密算法来替代 3DES。
候补 AES 块运算加密算法需要满足下面的条件：
- 块运算使用 128 位
- 支持 128/192/256 位密钥长度
- 对比其他竞争对手更安全
- 能够高效通过软件/硬件实现
AES 算法的发展过程如下：
- 在 1997 年 1 月 2 日，由 NIST 发布新的块加密算法需求
- 1997 年 9 月 12 日，AES 宣布了这一算法的正式名称
- 1998 年 8 月 20 日，多个国家的研究者提交了共计 15 种候选算法
- 1999 年 8 月 9 日，5 种算法进入决赛圈
- IBM 的 Mars
- RSA 的 RC6
- Joan Daemen 与 Vincent Rijmen 的 Rijndael
- Ross Anderson、Eli Biham 与 Lars Knudsen 的 Serpent
- Bruce Schneier、John Kelsey、Doug Whiting、David Wagner、Chris Hall 与 Niels Ferguson 的 Twofish
- 2000 年 10 月 2 日，NIST 宣布选择 Rijndael 算法做为 AES
- 2001 年 11 月 26 日，AES 正式成为美国联邦加密标准
4.2 AES 算法总览
AES 块运算加密算法与 Rijndael 算法基本一致，只是Rijndael 算法支持 128/192/256 位的块运算，而 AES 只支持 128 位的块运算。后面我们只讨论块长度 128 字节的 Rijndael 算法。
不同的密钥长度，进行的计算轮数不同：
| 密钥长度 | 轮数 |
|---|---|
| 128 位 | 10 |
| 192 位 | 12 |
| 256 位 | 14 |
AES 中不像 DES 那样具有 Feistel 网络。Feistel 网络不会在每次迭代中加密所有的信息块，在 DES 中，每次迭代只加密 64/2 = 32 位的数据块。而 AES 则会在每次迭代加密所有的 128 位数据，这也是为什么它的运算轮数相对较少。
AES 由称作层的结构组成。每一层操作所有的 128 位的数据。只有三种不同类型的层。除了第一轮，每一轮都由所有三层组成。
密钥加法层
128 位密钥或子密钥，通过密钥策略从主密钥中计算得到，进行异或操作
字节替换层(S 盒)
每一个状态的元素通过查表进行非线性转换，这一过程为数据引入混乱
扩散层
为所有状态位提过扩散，它由两个子层组成，二者都进行线性操作：
- ShiftRows 层在字节层面进行数据置换
- MixColumn 层是矩阵操作组合四字节块
4.3 一些数学内容：伽罗瓦域简单介绍
在 AES 中，大部分层使用了伽罗瓦域算法，尤其在 S 盒与 MixColumn 层中。
4.3.1 有限域存在性
一个有限域(伽罗瓦域)，是具有有限成员的集合。在这个域中，我们可以进行加/减/乘/逆运算。
我们先介绍一个简单的代数结构，群。
定义4.3.1 群 群是一簇元素 \(G\) 并具有操作 \(\circ\) 对 \(G\) 的两个元素组合，具有如下特性：
- 群操作 \(\circ\) 是闭合的，既对于所有的 \(a，b\in G\) 满足 \(a \circ b = c \in G\)
- 群操作满足结合律，既 \(a\circ (b\circ c) = (a\circ b)\circ c，a，b，c \in G\)
- 具有零元素 \(1 \in G\)，满足 \(a\circ 1 = 1 \circ a = a，a \in G\)
- 对于 \(a\in G\) 存在 \(a^{-1}\in G\) 称作逆，满足 \(a\circ a^{-1} = a^{-1} \circ a = 1\)
- 如果 \(a\circ b = b\circ a，a，b\in G\) 那么这个群是阿贝尔群
简而言之，群就是具有一个操作与对应逆操作的集合。如果一个操作称作加，那么对应的逆操作就是减；如果一个操作是乘，那么对应的逆操作就是除。
例4.1 对于集合 \(Z_m = {0，1，...，m - 1}\) 与取模运算，组成具有零元素 0 的群。每一个元素 a，具有逆 -a，满足 a + (-a) = 0 mod m，注意到，这个集合对乘法运算并不组成群，因为大部分元素并不具备逆元素，满足 \(aa^{-1} = 1 \quad mod \quad m\)
为了在一个结构中包含所有四种基本代数运算(加减乘除)，我们需要包含加法与乘法的群，我们称之为域。
定义4.3.2 域 域 F 是元素的集合，满足如下特性：
- F 的所有元素通过加法操作组成加法群，其零元素为 0
- F 的所有元素通过乘法操作组成乘法群，其零元素为 1
- 当两个群的操作混合，满足分配律，既\(a(b+c) = (ab) + (ac)，a，b，c\in F\)
例4.2 实数集是一个域，对于加法操作是具有零元素为 0 的群，对于乘法操作是零元素为 1 的群。每一个实数 a 具有一个加法逆 -a，具有一个乘法逆 1/a。
在密码学中，我们总是对具有有限数字的域感兴趣，这样的域称作有限域或伽罗瓦域。在域中的元素数称作它的阶/势。
定理4.3.1 对于正整数 n 与质数 p，只有在 \(m = p^n\) 时，具有 m 阶的域才存在，p 称作有限域的特征
4.3.2 质数域
有限域的最直观的例子是质数阶，n = 1 的域。这样的质数域 GF(p) 可以由整数 0，1，...，p - 1 组成。这个域支持模加运算与模乘运算。
定理 4.3.2 p 为质数，整数环 \(Z_p\) 表示为 GF(p) 是一个质数域。所有 GF(p) 的非零元素都具有逆，所有 GF(p) 的算术都是模 p 的
这意味着如果我们考虑整数环 \(Z_m\)，具有模加与模乘运算，m 为质数，那么 \(Z_m\) 不仅是一个环，它还是一个有限域。
为了在质数域中进行运算，我们必须遵从整数环的规则：加法与乘法操作都要模 p，任何元素有 \(a + (-a) = 0\quad mod \quad p\)，\(a\dot a^{-1} = 1\)。
例 4.3 考虑有限域 GF(5) = {0，1，2，3，4}，下表展示了加法与乘法操作：
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| \(\times\) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
加法逆
\[-0 = 0 \\ -1 = 4 \\ -2 = 3 \\ -3 = 2 \\ -4 = 1 \]乘法逆
\[1^{-1} = 1 \\ 2^{-1} = 3 \\ 3^{-1} = 2 \\ 4^{-1} = 4 \]一个重要的质数域是 GF(2)，它是最小的有限域。在 GF(2) = {0，1} 中，有：
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| \(\times\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
4.3.3 扩展域 \(GF(2^m)\)
在 AES 算法中，有限域包含 256 个元素，表示为 \(GF(2^8)\)。选择这个域，是因为每一个域元素可以表示为单字节。对于 S 盒与 MixColumn 转换，AES 数据中的每一个字节视作域 \(GF(2^8)\) 中的元素，并在这个有限域中对数据进行计算。
如果有限域的阶不是质数，显然 \(2^8\) 不是质数，加法与乘法操作不能被整数的加法与乘法模 \(2^8\) 表示。这样的 $m > 1 $ 的域称作扩展域。为了处理扩展域，我们需要不同的域元素标识，元素进行算术运算的不同规则。下面我们会看到扩展域可以表示为多项式，并通过对多项式运算进行扩展域的计算。
在扩展域 \(GF(2^8)\) 中的元素不是以整数的形式表示的，而是以系数在 \(GF(2)\) 中的多项式表示的。多项式具有最大 m - 1 阶，这样对于每一个元素最多有 m 个系数。在域 \(GF(2^8)\) 中，每一个元素 \(A \in GF(2^8)\) 可以表示为：
\[A(x) = a_7 x^7 + ... + a_1 x + a_0，a_i \in GF(2) = {0，1} \]这样会有 \(256 = 2^8\) 个多项式，每一个多项式可以表示为如下的向量：
\[A = (a_7，a_6，a_5，a_4，a_3，a_2，a_1，a_0) \]4.3.4 \(GF(2^m)\) 中的加法与减法
现在我们就可以进行这个域中的加法与乘法了。AES 的密钥加法层使用加法运算。操作是直白的，只需要进行标准多项式的加法与减法：我们只需要进行系数的加法与减法操作。
定义 4.3.3 扩展域加法与减法
令 \(A(x)，B(x) \in GF(2^m)\)，两个元素的和可通过下式计算：
\[C(x) = A(x) + B(x) = \sum_{i = 0}^{m - 1}c_i x^i，c_i \equiv a_i + b_i \quad mod \quad 2 \]差通过下式计算：
\[C(x) = A(x) - B(x) = \sum_{i = 0}^{m - 1}c_ix^i，c_i \equiv a_i - b_i \equiv a_i + b_i \quad mod \quad 2 \]注意到我们对系数进行模 2 加法/减法操作。在第二章中我们知道，模 2 的加法与减法是相同的操作。模 2 加法等效于按位异或。
例 4.5 \(C(x) = A(x) + B(x)\) 是 \(GF(2^8)\) 中的两个元素
\[A(x) = x^7 + x^6 + x^4 + 1 \\ B(x) = x^4 + x^2 + 1 \\ C(x) = x^7 + x^6 + x^2 \]如果我们进行减法操作，将会得到相同的结果。
4.3.5 \(GF(2^m)\) 中的乘法
在 \(GF(2^8)\) 中的乘法是 AES MixColumn 转换的核心，第一步，两个元素使用标准多项式乘法规则计算：
\[A(x)\cdot B(x) = (a_{m-1}x^{m-1} + ... + a_0)\cdot (b_{m-1}x^{m-1}+...+b_0) \\ C'(x) = c'_{2m-2}x^{2m-2} + ... + c'_0 \]其中：
\[c'_0 = a_0b_0 \quad mod \quad 2\\ c'_1 = a_0b_1 + a_1b_0 \quad mod \quad 2 \\ ... \\ c'_{2m-2} = a_{m-1}b_{m-1} \quad mod \quad 2 \]系数都是 \(GF(2)\) 中的元素。多项式 \(C(x)\) 的阶高于 \(m - 1\)，因此必须要降阶。基本思想与质数域中的乘法类似，在 \(GF(p)\)，我们乘两个整数，除一个质数，并只考虑余数。下面是我们对扩展域做的操作：乘法的积除以指定的多项式，只考虑余数。我们需要不可约的多项式来进行降阶。
定义 4.3.4 扩展域乘法
令 \(A(x)，B(x) \in GF(2^m)\) 且
\[P(x) = \sum_{i=0}^{m}p_ix^i，p_i \in GF(2) \]是一个不可约的多项式。对两个元素 \(A(x)，B(x)\) 的乘法为：
\[C(x) \equiv A(x)\cdot B(x) \quad mod \quad P(x) \]这样每一个 \(GF(2^m)\) 多项式需要一个系数为 \(GF(2)\) 的 m 阶不可约多项式 \(P(x)\)。注意到，不是所有的多项式都是不可约的，比如，\(x^4 + x^3+x+1\) 就是可约的：
\[x^4+x^3+x+1 = (x^2+x+1)(x^2+1) \]例 4.6 我们想要乘 \(GF(2^4)\) 中的两个多项式 \(A(x) = x^3+x^2+1\) 与 \(B(x) = x^2 +x\)，不可约的多项式为：
\[P(x) = x^4 + x + 1 \]原多项式的乘法可以计算得：
\[C'(x) = A(x)\cdot B(x) = x^5+x^3+x^2+x \]我们可以像下面这样计算：
\[x^4 = 1\cdot P(x) + (x+1) \\ x^4 \equiv x+1 \quad \mod \quad P(x) \\ x^5 \equiv x^2 + x \quad mod \quad P(x) \]现在，我们只需将降阶后的表达式代入原方程 \(C'(x)\)：
\[C(x) \equiv x^5 + x^3 + x^2 +x \quad mod \quad P(x) \\ C(x) \equiv (x^2 + x) + (x^3 + x^2 + x) = x^3 \\ A(x)\cdot B(x) \equiv x^3 \]如果我们查看前面的例子，可以以下面的比特操作表示：
\[A \cdot B = C \\ (x^3+x^2+1)\cdot(x^2+x) = x^3 \\ (1 1 0 1)\cdot(0 1 1 0) = (1 0 0 0) \]注意到，这个计算与整数乘法不同。
4.3.6\(GF(2^m)\) 中的逆
\(GF(2^8)\) 的逆是字节替换转换的核心，它组成了 AES 的 S 盒。对于给定的有限域 \(GF(2^m)\) 以及相关的不可约降阶多项式 \(P(x)\)，非零元素 \(A\in GF(2^m)\) 的逆 \(A^{-1}\) 有：
\[A^{-1}\cdot A(x) = 1 \quad mod \quad P(x) \]对于小的域，在实践中，通常意味着具有 \(2^{16}\) 或更少的元素，通常可以使用预先计算好的域的逆表，进行查表。下表展示了 AES S 盒使用的值。表格包含所有 \(GF(2^8)\) 模 \(P(x) = x^8+x^4+x^3+x+1\) 的逆的十六进制表示形式。一个特殊的形式是域元素 0，它的逆并不存在。不过，对于 AES S 盒需要对每一个输入都给到一个输出，因此 S 盒的设计者给到 0 的输出映射为 0。
| x\y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 00 | 01 | 8d | f6 | cb | 52 | 7b | d1 | e8 | 4f | 29 | c0 | b0 | e1 | e5 | c7 |
| 1 | 74 | b4 | aa | 4b | 99 | 2b | 60 | 5f | 58 | 3f | fd | cc | ff | 40 | ee | b2 |
| 2 | 3a | 6e | 5a | f1 | 55 | 4d | a8 | c9 | c1 | 0a | 98 | 15 | 30 | 44 | a2 | c2 |
| 3 | 2c | 45 | 92 | 6c | f3 | 39 | 66 | 42 | f2 | 35 | 20 | 6f | 77 | bb | 59 | 19 |
| 4 | 1d | fe | 37 | 67 | 2d | 31 | f5 | 69 | a7 | 64 | ab | 13 | 54 | 25 | e9 | 09 |
| 5 | ed | 5c | 05 | ca | 4c | 24 | 87 | bf | 18 | 3e | 22 | f0 | 51 | ec | 61 | 17 |
| 6 | 16 | 5e | af | d3 | 49 | a6 | 36 | 43 | f4 | 47 | 91 | df | 33 | 93 | 21 | 3b |
| 7 | 79 | b7 | 97 | 85 | 10 | b5 | ba | 3c | b6 | 70 | d0 | 06 | a1 | fa | 81 | 82 |
| 8 | 83 | 7e | 7f | 80 | 96 | 73 | be | 56 | 9b | 9e | 95 | d9 | f7 | 02 | b9 | a4 |
| 9 | de | 6a | 32 | 6d | d8 | 8a | 84 | 72 | 2a | 14 | 9f | 88 | f9 | dc | 89 | 9a |
| A | fb | 7c | 2e | c3 | 8f | b8 | 65 | 48 | 26 | c8 | 12 | 4a | ce | e7 | d2 | 62 |
| B | 0c | e0 | 1f | ef | 11 | 75 | 78 | 71 | a5 | 8e | 76 | 3d | bd | bc | 86 | 57 |
| C | 0b | 28 | 2f | a3 | da | d4 | e4 | 0f | a9 | 27 | 53 | 04 | 1b | fc | ac | e6 |
| D | 7a | 07 | ae | 63 | c5 | db | e2 | ea | 94 | 8b | c4 | d5 | 9d | f8 | 90 | 6b |
| E | b1 | 0d | d6 | eb | c6 | 0e | cf | ad | 08 | 4e | d7 | e3 | 5d | 50 | 1e | b3 |
| F | 5b | 23 | 38 | 34 | 68 | 46 | 03 | 8c | dd | 9c | 7d | a0 | cd | 1a | 41 | 1c |
例 4.7 从上表中有下面的式子
\[x^7 + x^6 + x = (1100 0010)_2 = (C2)_{hex} = (xy) \]可以确定到 C 行 2 列，查表得到它的多项式逆为：
\[(2F)_{hex} = (00101111)_2 = x^5+x^3+x^2+x+1 \]这可以通过如下乘法验证：
\[(x^7+x^6+x)\cdot(x^5+x^3+x^2+x+1) \equiv 1 \quad mod \quad P(x) \]注意到，上面的表格中并不包含 S 盒本身。
4.4 AES 的内部结构
下面我们会讨论 AES 的内部构造。在 AES 的单轮中，16 字节的输入 \(A_0，...，A_{15}\) 按字节给到 S 盒，S 盒的 16 字节的输出 \(B_0，...，B_{15}\) 在 ShiftRows 层按字节置换，并给到 MixColumn 层进行混合转换 \(c(x)\)，最后，128 位子密钥 \(k_i\) 域中间结果进行异或。AES 是面向字节的块运算。
这与 DES 不同，DES 进行的是按位置换，是面向位的结构。
我们首先想象一个状态 A，由 16 字节的 \(A_0，A_1，...，A_{15}\) 组成，并以 \(4\times 4\) 矩阵准备：
| \(A_0\) | \(A_4\) | \(A_8\) | \(A_{12}\) |
|---|---|---|---|
| \(A_1\) | \(A_5\) | \(A_9\) | \(A_{13}\) |
| \(A_2\) | \(A_6\) | \(A_{10}\) | \(A_{14}\) |
| \(A_3\) | \(A_7\) | \(A_{11}\) | \(A_{15}\) |
AES 对元素当前状态据帧的行列进行操作。相似的，密钥字节以 \(4\times 4\) 矩阵(128 位密钥)，6 列矩阵(192 位密钥)，8 列矩阵(256 位密钥)。下面是 192 位密钥的表示：
| \(k_0\) | \(k_4\) | \(k_8\) | \(k_{12}\) | \(k_{16}\) | \(k_{20}\) |
|---|---|---|---|---|---|
| \(k_1\) | \(k_5\) | \(k_9\) | \(k_{13}\) | \(k_{17}\) | \(k_{21}\) |
| \(k_2\) | \(k_6\) | \(k_{10}\) | \(k_{14}\) | \(k_{18}\) | \(k_{22}\) |
| \(k_3\) | \(k_7\) | \(k_{11}\) | \(k_{15}\) | \(k_{19}\) | \(k_{23}\) |
4.4.1 字节替换层
每一轮的第一层都是字节替换层。字节替换层，可以看作是 16 行的平行 S 盒，具有 8 个输入与输出位。注意到，16 个 S 盒都是相同的。在这一层，每一个状态 \(A_i\) 都被 \(B_i\) 替换：
\[S(A_i) = B_i \]S 盒是 AES 中唯一的非线性元素，既 \(字节替换(A) + 字节替换(B) \ne 字节替换(A+B)\)。S 盒替换是双向映射，既对于 \(2^8 = 256\) 可能的输入，有一一映射的输出元素。在软件中 S 盒可以通过查表实现。
| x\y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 63 | 7c | 77 | 7b | f2 | 6b | 6f | c5 | 30 | 01 | 67 | 2b | fe | d7 | ab | 76 |
| 1 | ca | 82 | c9 | 7d | fa | 59 | 47 | f0 | ad | d4 | a2 | af | 9c | a4 | 72 | c0 |
| 2 | b7 | fd | 93 | 26 | 36 | 3f | f7 | cc | 34 | a5 | e5 | f1 | 71 | d8 | 31 | 15 |
| 3 | 04 | c7 | 23 | c3 | 18 | 96 | 05 | 9a | 07 | 12 | 80 | e2 | eb | 27 | b2 | 75 |
| 4 | 09 | 83 | 2c | 1a | 1b | 6e | 5a | a0 | 52 | 3b | d6 | b3 | 29 | e3 | 2f | 84 |
| 5 | 53 | d1 | 00 | ed | 20 | fc | b1 | 5b | 6a | cb | be | 39 | 4a | 4c | 58 | cf |
| 6 | d0 | ef | aa | fb | 43 | 4d | 33 | 85 | 45 | f9 | 02 | 7f | 50 | 3c | 9f | a8 |
| 7 | 51 | a3 | 40 | 8f | 92 | 9d | 38 | f5 | bc | b6 | da | 21 | 10 | ff | f3 | d2 |
| 8 | cd | 0c | 13 | ec | 5f | 97 | 44 | 17 | c4 | a7 | 7e | 3d | 64 | 5d | 19 | 73 |
| 9 | 60 | 81 | 4f | dc | 22 | 2a | 90 | 88 | 46 | ee | b8 | 14 | de | 5e | 0b | db |
| A | e0 | 32 | 3a | 0a | 49 | 06 | 24 | 5c | c2 | d3 | ac | 62 | 91 | 95 | e4 | 79 |
| B | e7 | c8 | 37 | 6d | 8d | d5 | 4e | a9 | 6c | 56 | f4 | ea | 65 | 7a | ae | 08 |
| C | ba | 78 | 25 | 2e | 1c | a6 | b4 | c6 | e8 | dd | 74 | 1f | 4b | bd | 8b | 8a |
| D | 70 | 3e | b5 | 66 | 48 | 03 | f6 | 0e | 61 | 35 | 57 | b9 | 86 | c1 | 1d | 9e |
| E | e1 | f8 | 98 | 11 | 69 | d9 | 8e | 94 | 9b | 1e | 87 | e9 | ce | 55 | 28 | df |
| F | 8c | a1 | 89 | 0d | bf | e6 | 42 | 68 | 41 | 99 | 2d | 0f | b0 | 54 | bb | 16 |
例 4.8 我们假设 S 盒输入为 \(A_i = (C2)_{hex}\)，那么它的替换值是：
\[S((C2)_{hex}) = (25)_{hex} \]在比特层级，替换可以描述为：
\[S(11000010) = (00100101) \]虽然 S 盒是双向的，它并没有任何固定的点，既不存在输入 \(A_i\) 从而有 \(S(A_i) = A_i\)，即便输入 0 也不是不变的：
\[(00000000) = (01100011) \]例 4.9 让我们假设字节替换的输入为：
\[(C2，C2，...，C2) \]一十六进制表示，输出状态是：
\[(25，25，...，25) \]S盒的数学描述
略
4.4.2 扩散层
在 AES 算法中，扩散由两个子层组成，ShiftRows 转换与 MixColumn 转换。不像 S 盒，扩散层进行的操作是线性的，有：
\[DIFF(A) + DIFF(B) = DIFF(A+B) \]ShiftRows 层
ShiftRows 转换进行下面的移位：第一行不变，第二行循环左移一位，第二行循环左移两位，第三行循环三位。
| \(B_0\) | \(B_4\) | \(B_8\) | \(B_{12}\) |
|---|---|---|---|
| \(B_1\) | \(B_5\) | \(B_9\) | \(B_{13}\) |
| \(B_2\) | \(B_6\) | \(B_{10}\) | \(B_{14}\) |
| \(B_3\) | \(B_7\) | \(B_{11}\) | \(B_{15}\) |
输出新状态如下：
| \(B_0\) | \(B_4\) | \(B_8\) | \(B_{12}\) |
|---|---|---|---|
| \(B_5\) | \(B_9\) | \(B_{13}\) | \(B_1\) |
| \(B_{10}\) | \(B_{14}\) | \(B_2\) | \(B_6\) |
| \(B_{15}\) | \(B_3\) | \(B_7\) | \(B_{11}\) |
MixColumn 层
MixColumn 步是线性转换，会混合每一个状态矩阵的列。因为每一个输入会影响四个输出字节，MixColumn 操作是 AES 中主要带来扩散的组件。ShiftRows 以及 MixColumn 二者组合仅需要三轮，状态矩阵的每一个字节将与所有 16 字节的原文有关。
我们将 16 字节的输入表示为 B，输出表示为 C：
\[MixColumn(B) = C \]这里 B 为 ShiftRows 的输出。
现在每四个字节列考虑为一个向量，乘一个 \(4\times 4\) 矩阵，其中乘法与加法的系数属于 \(GF(2^8)\)。比如，如下例：
\[\begin{equation} \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} B_0 \\ B_5 \\ B_{10} \\ B_{15} \end{pmatrix} \end{equation} \]对应的，第二列输出 \((C_4，C_5，C_6，C_7)^T\) 是由 \((B_4，B_9，B_{14}，B_3)\) 使用相同的常矩阵计算得到，以此类推。
每一个状态字节 \(C_i\) 以及 \(B_i\) 是 8 位值，表示为 \(GF(2^8)\) 中的元素。所有计算都是在伽罗瓦域中进行的。比如矩阵中的常量是以十六进制表示的 01，实际上是 \(GF(2^8)\) 多项式系数 (0000 0001)，既在伽罗瓦域中的 1；02，是多项式系数 (0000 0010)，既伽罗瓦域中的 x；03 是多项式系数 (0000 0011)，既伽罗瓦域 x+1。
在向量矩阵乘法中的加法是 \(GF(2^8)\) 中的加法。我们选择 01，02，03 做为矩阵常量，是因为它十分高效。都可以通过查表快速得到。
例 4.11 假设输入给 MixColumn 层的状态是：
\[B = (25，25，...，25) \]只需要进行 02，03 乘法计算：
\[02\cdot 25 = x\cdot(x^5 + x^2 + 1)\\ = x^6 + x^3 + x \]\[03\cdot 25 = (x+1)(x^5+x^2+1)\\ =(x^6+x^3+x)+(x^5+x^2+1) \\ =x^6+x^5+x^3+x^2+x+1 \]因为中间产物的阶都低于 8，因此不需要通过 \(P(x)\) 进行降阶计算。输出为：
\[C_i = (x^5+x^2+1)+(x^5+x^2+1)+(x^6+x^3+x)+(x^6+x^5+x^3+x^2+x+1) = (x^5+x^2+1) = 25 \]因此输出为：
\[C = (25，25，...，25) \]4.4.3 密钥加法层
输入给密钥加法层的两个输入是当前 16 字节的状态矩阵以及 16 字节的子密钥。两个输入通过按位异或操作结合。注意到异或操作与伽罗瓦域 \(GF(2)\) 的加法等效。子密钥通过密钥策略计算得到。
4.4.4 密钥策略
密钥策略使用原始输入密钥(128/192/256位)计算得到子密钥。子密钥的异或加法在 AES 的输入与输出都会用到。这个过程有时称作密钥漂白。子密钥数量等于轮数加一。对于密钥长度为 128 位，轮数是 10，因此共有 11 个子密钥，每一个子密钥为 128 位。192 位密钥长度有 13 个 128 位子密钥。256 位密钥长度有 15个 128 位子密钥。AES 子密钥递归计算，既计算 \(k_i\) 需要知道 \(k_{i-1}\)。
AES 密钥策略是基于字的(在这里说的字为32位)。对于不同的初始密钥长度，AES 具有不同的密钥策略，不过它们的策略是相似的。
128 位长 AES 密钥策略
11 个子密钥存储在密钥扩展数组 \(W[0]，...，W[43]\)。
第一个子密钥 \(k_0\) 就是 AES 的原始密钥。既 \(W[0] - W[3]\)，剩下的密钥最左侧的字通过下面的步骤计算：
\[W[4i] = W[4(i-1)] + g(W[4i-1]) \quad i = 1，...，10 \]其中 \(g()\) 为非线性函数。
剩下的子密钥三个字通过下面的方式计算：
\[W[4i+j] = W[4i+j-1]+W[4(i-1)+j] \quad i= 1，...，10，j=1，2，3 \]\(g()\) 函数旋转它的四个输入字节，执行按位的 S 盒替换，并添加轮系数 RC。轮系数是伽罗瓦域 \(GF(2^8)\) 中的元素，既一个 8 位的值，只会添加到最左侧的字节。轮系数每一轮都不同：
\[RC[1] = x^0 = (0000 0001)_2 \\ RC[2] = x^1 = (0000 0010)_2 \\ RC[3] = x^2 = (0000 0011)_2 \\ ... \\ RC[10] = x^9 = (00110110)_2 \]函数 \(g()\) 为密钥策略添加非线性属性，并消除了 AES 中的对称性。
192 位长 AES 密钥策略
略
256 位长 AES 密钥策略
略
4.5 解密
因为 AES 不是基于 Feistel 网络，所有的层必须做反转，既字节替换层变成逆字节替换层，ShiftRows 层编程逆 ShiftRows 层，MixColumn 层变成逆 MixColumn 层。不过，我们可以看到，各层的逆操作与用于加密的层是相似的。子密钥的顺序也是逆转的，既，我们需要逆转密钥策略。
因为最后一个加密轮不会进行 MixColum 操作，第一个解密层不会包含对应的逆转层。所有其他的解密层，包含全部的 AES 层。
MixColumn 逆层
为了得到 MixColumn 的逆操作，需要使用 MixColumn 中使用矩阵的逆，计算是遵循 \(GF(2^8)\) 的：
\[\begin{equation} \begin{pmatrix} B_0 \\ B_1 \\ B_2 \\ B_3 \end{pmatrix} = \begin{pmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{pmatrix} \begin{pmatrix} C_0 \\ C_1 \\ C_2 \\ C_3 \end{pmatrix} \end{equation} \]ShiftRows 逆层
为了逆转 ShiftRows 操作，我们必须按照相反的方向移位，比如下面的子层：
| \(B_0\) | \(B_4\) | \(B_8\) | \(B_{12}\) |
|---|---|---|---|
| \(B_1\) | \(B_5\) | \(B_9\) | \(B_{13}\) |
| \(B_2\) | \(B_6\) | \(B_{10}\) | \(B_{14}\) |
| \(B_3\) | \(B_7\) | \(B_{11}\) | \(B_{15}\) |
那么它的逆转就是：
| \(B_0\) | \(B_4\) | \(B_8\) | \(B_{12}\) |
|---|---|---|---|
| \(B_{13}\) | \(B_1\) | \(B_5\) | \(B_9\) |
| \(B_{10}\) | \(B_{14}\) | \(B_2\) | \(B_6\) |
| \(B_7\) | \(B_{11}\) | \(B_{15}\) | \(B_3\) |
字节替换逆层
因为 AES 的 S 盒是一一映射的关系，因此可以获得 S 盒的逆：
\[A_i = S^{-1}(B_i) = S^{-1}(S(A_i)) \]其中 \(A_i\) 以及 \(B_i\) 是状态矩阵的元素。逆 S 盒如下表：
| x/y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 52 | 09 | 6a | d5 | 30 | 36 | a5 | 38 | bf | 40 | a3 | 9e | 81 | f3 | d7 | fb |
| 1 | 7c | e3 | 39 | 82 | 9b | 2f | ff | 87 | 34 | 8e | 43 | 44 | c4 | de | e9 | cb |
| 2 | 54 | 7b | 94 | 32 | a6 | c2 | 23 | 3d | ee | 4c | 95 | 0b | 42 | fa | c3 | 4e |
| 3 | 08 | 2e | a1 | 66 | 28 | d9 | 24 | b2 | 76 | 5b | a2 | 49 | 6d | 8b | d1 | 25 |
| 4 | 72 | f8 | f6 | 64 | 86 | 68 | 98 | 16 | d4 | a4 | 5c | cc | 5d | 65 | b6 | 92 |
| 5 | 6c | 70 | 48 | 50 | fd | ed | b9 | da | 5e | 15 | 46 | 57 | a7 | 8d | 9d | 84 |
| 6 | 90 | d8 | ab | 00 | 8c | bc | d3 | 0a | f7 | e4 | 58 | 05 | b8 | b3 | 45 | 06 |
| 7 | d0 | 2c | 1e | 8f | ca | 3f | 0f | 02 | c1 | af | bd | 03 | 01 | 13 | 8a | 6b |
| 8 | 3a | 91 | 11 | 41 | 4f | 67 | dc | ea | 97 | f2 | cf | ce | f0 | b4 | e6 | 73 |
| 9 | 96 | ac | 74 | 22 | e7 | ad | 35 | 85 | e2 | f9 | 37 | e8 | 1c | 75 | df | 6e |
| A | 47 | f1 | 1a | 71 | 1d | 29 | c5 | 89 | 6f | b7 | 62 | 0e | aa | 18 | be | 1b |
| B | fc | 56 | 3e | 4b | c6 | d2 | 79 | 20 | 9a | db | c0 | fe | 78 | cd | 5a | f4 |
| C | 1f | dd | a8 | 33 | 88 | 07 | c7 | 31 | b1 | 12 | 10 | 59 | 27 | 80 | ec | 5f |
| D | 60 | 51 | 7f | a9 | 19 | b5 | 4a | 0d | 2d | e5 | 7a | 9f | 93 | c9 | 9c | ef |
| E | a0 | e0 | 3b | 4d | ae | 2a | f5 | b0 | c8 | eb | bb | 3c | 83 | 53 | 99 | 61 |
| F | 17 | 2b | 04 | 7e | ba | 77 | d6 | 26 | e1 | 69 | 14 | 63 | 55 | 21 | 0c | 7d |
解密密钥策略
解密时我们需要反方向顺序的子密钥。
4.6 软件与硬件实现
软件
不像 DES，AES 设计通过软件高效实现是可行的。核心的思想是将所有轮通过软件查表实现，只需要四个表格，每一个表格由 256 条目组成，每一个条目是 32 位宽。这些表称为 T 盒。在 1.2 GHz 的英特尔处理器上，可以达到 400Mbps。理论上在 64 位 Athlon CPU 上带宽可达 1.6Gbps。
硬件
实现 AES 相较于 DES 算法需要更多的硬件资源。不过在现今的集成电路上，这都不成问题，AES 可以在现代 ASIC 或 FPGA 技术上实现非常高的带宽。商用 AES ASICs 可以超过 10Gbps。使用并行技术，速度可以更快。
标签：AES,加密,字节,高级,GF,密钥,加法,quad From： https://www.cnblogs.com/arvin-blog/p/17170218.html