3.1　AES算法

AES算法也称为Rijndael算法，是由J.Daemen和V.Rijmen两位密码学家提出的。与DES类似，AES也属于对称加密算法，即通信双方使用相同的密钥，但是AES的密钥长度比DES长，可以有效地对抗穷举密钥攻击。AES的密钥长度可以选为128位、192位或256位。AES的输入明文文本长度为128位，输出密文文本长度也为128位。

本书根据AES的密钥长度命名AES的3种类型，即AES-128表示密钥长度为128位的AES，AES-192表示密钥长度为192位的AES，AES-256表示密钥长度为256位的AES。同时，定义“字”表示32位，“字节”表示8位。这样，AES的明文、密钥和密文长度以及加密轮数见表3-1。

需要说明的是，本章介绍AES算法使用了FIPS 197标准中的英文术语，为避免引起歧义，没有将这些术语译为中文。

3.1.1　AES加密算法

AES加密算法如图3-1所示。AES的输入为明文文本 x 和密钥 k ，密钥 k 经密钥扩展算法生成 Nr ＋1个子密钥{ k _i }， i ＝0，1，2，…， Nr ，每个子密钥长4个字（即128位）。首先，明文 x 与子密钥 k ₀ 相异或；然后，对异或的结果循环执行SubBytes、ShiftRows和MixColumns操作 Nr －1次；最后，将上一步的输出再执行一次SubBytes和一次ShiftRows操作，并与子密钥 k _Nr 相异或得到密文 y 。

在图3-1中，一个完整的轮操作包括一次SubBytes、一次ShiftRows、一次MixColumns和一次异或操作。AES包括 Nr －1个完整的轮操作。但是，最后一个轮操作是不完整的，只包括一次SubBytes、一次ShiftRows和一次异或操作。

下面依次介绍SubBytes、ShiftRows、MixColumns操作，如图3-2所示。AES密钥扩展算法将在3.1.2节中介绍。

1．SubBytes操作

由图3-2可知，SubBytes操作把输入的4字长的数据分成16字节，依次记为 A _i ， i ＝0，1，2，…，15。 A _i 通过查 S 盒得到 B _i 。AES算法只有一个 S 盒，见表3-2。

例如， A _i ＝38（十进制），则查表3-2，将左上角的（0，0）位置记为索引号0，从左上角的（0，0）位置开始逐行计数，计数到第38个位置，该位置的数F7（十六进制）即为 B _i 。或者将 A _i ＝38（十进制）转化为十六进制数0x26，则第2行第6列的数F7（十六进制）即为 B _i 。

2.ShiftRows操作

由图3-2可知，ShiftRows将输入的16字节的位置重新排列，若原来的顺序记为 B _i ， i ＝0，1，2，…，15，则重新排列后的字节顺序为 B ₀ B ₅ B ₁₀ B ₁₅ B ₄ B ₉ B ₁₄ B ₃ B ₈ B ₁₃ B ₂ B ₇ B ₁₂ B ₁ B ₆ B ₁₁ 。

3．MixColumns操作

MixColumns操作由以下4个矩阵乘法得到，即

式（3-1）~式（3-4）中的乘法与加法运算均基于GF（2 ⁸ ）域。

仔细研究图3-2和MixColumns操作，可以通过4种类型的查找表和模2加法运算由 A _i 得到 C _i ，这里以式（3 - 1）为例分析，如图3 - 3所示。

在图3 - 3中，需要构造4种查找表，“ A ₀ 查表”表示由 A ₀ 查第一种查找表可以得到，“ A ₅ 查表”表示由 A ₅ 查第二种查找表可以得到，“ A ₁₀ 查表”表示由 A ₁₀ 查第三种查找表可以得到，“ A ₁₅ 查表”表示由 A ₁₅ 查第四种查找表可以得到。

结合式（3 - 1）~式（3 - 4）可知，第一种查找表供 A ₀ 、 A ₄ 、 A ₈ 和 A ₁₂ 用，第二种查找表供 A ₁ 、 A ₅ 、 A ₉ 和 A ₁₃ 使用，第三种查找表供 A ₂ 、 A ₆ 、 A ₁₀ 和 A ₁₄ 使用，第四种查找表供 A ₃ 、 A ₇ 、 A ₁₁ 和 A ₁₅ 使用。

下面以第一种查找表和 A ₀ 为例，介绍构造第一种查找表的方法。此时，输入为 A ₀ ，取值为0x00~0xFF中的任意值，即1字节的值；输出为transpose（2，1，1，3） B ₀ ，transpose表示转置，即输出为4行1列的4字节。第一种查找表为256行4列的矩阵，第0行的4个元素对应 A ₀ 取为0x00时，计算transpose（2，1，1，3） B ₀ 得到的4字节（的转置）；第1行的4个元素对应 A ₀ 取为0x01时，计算transpose（2，1，1，3） B ₀ 得到的4字节（的转置）；依此类推，第255行的4个元素对应 A ₀ 取为0xFF时，计算transpose（2，1，1，3） B ₀ 得到的4字节（的转置）。

在图3 - 3中，当已知 A ₀ 、 A ₅ 、 A ₁₀ 和 A ₁₅ 时，用 A ₀ 查第一种查找表得到含4字节的向量；用 A ₅ 查第二种查找表得到含4字节的向量；用 A ₁₀ 查第三种查找表得到含4字节的向量；用 A ₁₅ 查第四种查找表得到含4字节的向量。将这4个向量按向量加法取和，得到一个含4字节的向量，这4字节依次为 C ₀ 、 C ₁ 、 C ₂ 和 C ₃ 。

附录A中给出了这4种查找表的阵列值（第3.2.1节给出了这4种查找表的生成算法）。

3.1.2　AES密钥扩展算法

AES的密钥长度可以取为128位、192位或256位，即4个字、6个字或8个字，对应的密码系统依次称为AES-128、AES-192或AES-256。结合表3-1和图3-1可知，AES-128共需要11个子密钥（或称轮密钥），AES-192共需要13个子密钥，AES-256共需要15个子密钥。每个子密钥的长度为4个字，因此，AES-128需要由密钥扩展出44个字，记为 W _i ， i ＝0，1，2，…，43；AES-192需要由密钥扩展出52个字，记为 W _i ， i ＝0，1，2，…，51；AES-256需要由密钥扩展出60个字，记为 W _i ， i ＝0，1，2，…，59。其中， W _{4 i} W _{4 i ＋1} W _{4 i ＋2} W _{4 i ＋3} 为第 i 轮的子密钥 k _i 。

图3-4~图3-6分别为AES-128、AES-192和AES-256的密钥扩展方式。图3-7为密钥扩展中使用的 g 函数和 h 函数。

在图3-4中，输入密钥 k 被分成4个字，记为 K _i ， i ＝0，1，2，3，子密钥 k ₀ 与密钥 k 相同，即 W _i ＝ K _i ， i ＝0，1，2，3。然后，由子密钥 k _i 产生子密钥 k _{i ＋1} ， i ＝0，1，2，…，9，产生规则如下。

其中， i ＝0，1，2，…，9。函数 g 如图3 - 7所示。

图3 - 5为AES-192系统的密钥扩展过程。图3-6为AES-256系统的密钥扩展过程。图3 - 5中， W _i ＝ K _i ， i ＝0，1，2，…，5，其余 W _i 的产生规则如式（3 - 9）~式（3 - 14）所示。

其中， i ＝0，1，2，…，7，且当 i ＝7时，只有式（3 - 9）~式（3 - 12）有效。函数 g 如图3 - 7所示。

在图3 - 6中， W _i ＝ K _i ， i ＝0，1，2，…，7，其余 W _i 的产生规则如式（3 - 15）~式（3 - 22）所示。

其中， i ＝0，1，2，…，6，且当 i ＝6时，只有式（3 - 15）~式（3 - 18）有效。 g 函数和 h 函数如图3 - 7所示。

图3 - 7中，“S”表示 S 盒，见表3 - 2。RC[ i ]， i ＝1，2，…，10的取值见表3 - 3。在AES中，生成的多项式为 P （ x ）＝ x ⁸ ＋ x ⁴ ＋ x ³ ＋ x ＋1，RC[ i ]＝ x ^{i －1} ， i ＝1，2，…，10。所以，RC[ i ]＝1＜＜（ i －1）， i ＝1，2，…，8；RC[9]＝ x ⁸ ＝ x ⁴ ＋ x ³ ＋ x ＋1＝0001 1011B，RC[10]＝ x ⁹ ＝ x • x ⁸ ＝ x ⁵ ＋ x ⁴ ＋ x ² ＋ x ＝0011 0110B。

3.1.3　AES解密算法

AES解密算法是AES加密算法的逆过程，如图3-8所示。

对照图3-1所示的AES加密过程，可知图3-8所示的AES解密过程是图3-1的逆过程。解密过程也需要 Nr 轮，第一轮包含与子密钥 k _Nr 的异或运算、逆向的ShiftRows（用ShiftRows ^－1 表示）和逆向的SubBytes（用SubBytes ^－1 表示）；其余的 Nr －1轮是相似的，都包含了与该轮子密钥的异或运算、逆向MixColumns（用MixColumn ^－1 表示）、ShiftRows ^－1 和SubBytes ^－1 。解密过程完整的轮处理过程如图3-9所示。

对照图3-2可知，图3-9所示解密过程的完整轮处理过程是图3-2的逆过程，下面依次介绍各个操作过程。

1．MixColumns ^-1 操作

由图3-9可知，MixColumns ^－1 操作由以下4个矩阵乘法组成，即

式（3-23）~式（3-26）中的乘法和加法均基于GF（2 ⁸ ）域进行，生成的多项式为 P （ x ）＝ x ⁸ ＋ x ⁴ ＋ x ³ ＋ x ＋1。

2．ShiftRows ^-1 操作

由图3-9可知，ShiftRows ^－1 操作将输入的 B ₀ B ₁ B ₂ B ₃ B ₄ B ₅ B ₆ B ₇ B ₈ B ₉ B ₁₀ B ₁₁ B ₁₂ B ₁₃ B ₁₄ B ₁₅ 重新排列为 B ₀ B ₁₃ B ₁₀ B ₇ B ₄ B ₁ B ₁₄ B ₁₁ B ₈ B ₅ B ₂ B ₁₅ B ₁₂ B ₉ B ₆ B ₃ 。

3．SubBytes ^-1 操作

图3-9中的“S ^－1 ”表示逆向 S 盒。SubBytes ^－1 操作中，依次输入 B ₀ B ₁₃ B ₁₀ B ₇ B ₄ B ₁ B ₁₄ B ₁₁ B ₈ B ₅ B ₂ B ₁₅ B ₁₂ B ₉ B ₆ B ₃ 查 S ^－1 盒，将依次得到 A ₀ A ₁ A ₂ A ₃ A ₄ A ₅ A ₆ A ₇ A ₈ A ₉ A ₁₀ A ₁₁ A ₁₂ A ₁₃ A ₁₄ A ₁₅ 。AES解密过程的 S ^－1 盒见表3-4。

例如， B ₁₃ ＝0x4A（十六进制），则 A ₁ ＝ S ^－1 （ B ₁₃ ）＝0x5C（即处于第4行第A列的值）。 wCzh2Jq3pyWE/W1jJvcLbkDbcgWcz82OCemT3pi2oFScyEb7sOZfqB6NOGY+zhjd