第4章 高级加密标准

4.1 高级加密标准的起源

严格地说，AES和Rijndael加密法并不完全一样（虽然在实际应用中二者可以互换），因为Rijndael加密法可以支持更大范围的分组和密钥长度：AES的分组长度固定为128比特，密钥长度则可以是128比特、192比特或256比特；而Rijndael使用的密钥和分组长度可以是32比特的整数倍，以128比特为下限，256比特为上限。加密过程中使用的密钥由Rijndael密钥生成方案产生。

4.2 代替置换网络结构

代替置换网络（SPN）将数学运算应用于分组密码。

SPN将输入的明文进行交替的代替操作和置换操作产生密文。每一轮使用的子密钥产生于输入的密钥，且在有些基于SPN算法的加密算法中，用于进行代替操作的S盒也是基于子密钥产生的。

上图为一个使用2轮SPN结构的算法，其中单轮经过密钥异或、S盒代替盒P盒置换三个步骤。

4.3 高级加密标准的结构

AES使用SPN网络作为基础进行设计，保留了SPN网络的框架，但是在每轮SPN中添加了行移位的变换过程，并且指定了分组长度为128比特，但是密钥可以是128比特、192比特或256比特。

4.3.1 总体结构

上图展示了AES加密过程的总体结构。明文分组的长度为128比特，密钥可以为3种长度。根据密钥的长度，算法被称为AES-128、AES-192和AES-256，并且密钥长度的改变也将导致SPN网络轮次的改变。

加密和解密算法的输入是一个128比特的分组，通常将这个分组描述为一个4x4的字节方针，存储于state数组，并且在加密或解密的各个阶段被修改。而在整个AES算法中，变换state分组的子算法只有七个，分别为字节代换、逆字节代换、行移位、逆行移位、列混合、逆列混合和轮密钥加变换。

4.3.2 详细结构

在AES-128的加密过程中，明文首先复制入state数组中，进行一次初始变换（实际上是一次轮密钥加变换），紧接着进行9轮变换，和最后第10轮的变换。在9轮变换中，每一轮均按照字节代替、行移位、列混合和轮密钥加这样的顺序进行。但是在最后一轮，即第十轮变换中，只进行3种变换，即字节代替、行移位和轮密钥加。而对于解密过程，密文同样被复制入一个state数组，进行一次初始变换（使用加密第十轮密钥的轮密钥加变换），接着进行9轮变换和第十轮变换。在9轮变换中，每一轮均按照逆向行移位、逆向字节代替、轮密钥加和逆向列混合这样的顺序进行。在最后一轮，即第十轮变换中，只进行逆向行移位、逆向字节代替和轮密钥加。

4.3.3 轮密钥加变换

轮密钥加变换是一个state数组和子密钥异或的操作。

4.3.4 字节代换

字节代替和逆字节代换实际上就是一个S盒替换的过程。

AES中定义了两个S盒，S盒和逆S盒，其中加密的字节代换使用S盒，解密的逆字节代换使用逆S盒。

state中的每个字节按照如下的方式替换为一个新的字节：把该字节的高四位比特作为行值，低四位比特作为列值，以这些行列值从S盒或逆S盒中索引到位置的元素作为输出。例如，在加密过程中，十六进制数（EA）所对应的行为14，列为10(从0开始)，S盒中在此位置的是（87），则（EA）被替换为（87）。

4.3.5 行移位

行移位和逆行移位是一个简单的移位过程。根据state行标不同，每一行移动的位数也不同。

按照大多数程序语言来说，在加密过程中，第0行循环左移0个字节，第1行循环左移1个字节......

解密过程，就是整个操作的逆过程。

在不同密钥长度的AES中，行移位的长度略不相同。在AES-128和AES-192中，行移位的偏移量是0、1、2、3，而在AES-256中，行移位的偏移量是0、1、3、4。

4.3.6 列混合

列混合是对每列独立地进行操作。每列中的每个字节被映射为一个新的值，该值由该列中的四个字节通过函数变换得到。该变换可以由下面所示的基于state的矩阵乘法表示。

列混合：

逆向列混合：

AES的软件优化（*）

4.3.7 密钥扩展算法（*）

AES-128中的密钥扩展算法的输入值是16字节，输出值是一个由176字节组成的移位线性数组。

4.4 AES设计上的考虑

与DES相比，AES在设计上的特点：
1.扩散速度更快

AES算法是一种SPN体制，与DES的Feistel体制的每次循环时有一半数据未被更改不同，AES中数据的所有比特同等对待，使得输入比特的扩散影响更快，通常两轮循环就足以得到完全的扩散，即所有的128比特输出都完全依赖于128比特输入。这一扩散效果有一部分依赖于行移位和列混合。

2.S盒的构造方法

与DES的S盒构造方法存在神秘色彩不同，AES的S盒构造使用一种简单而清晰的方法。

3.抗攻击能力

AES的S盒是基于有限域来建立的，用它对付差分分析盒线性分析效果显著。

4.5 有限域（*）

4.5.1 什么是有限域

只需在定义域和值域相同的情况下，满足以下条件的即可以认为S是一个有限域：

4.5.2 阶为P的有限域

给定一个素数p，则元素个数为p的有限域GF(p)被定义为整数{0,1,...,p-1}的集合Z，其运算为模p的算术运算。最简单的有限域是GF(2)，它的算术运算可以简单地描述为：

4.5.3 有限域GF(2^8)的动机

实际上所有的加密算法都涉及整数集上的算术运算。

为了方便使用和提高效率，我们希望这个整数集中的数与给定的二进制比特数所能表达的信息意义对应而不出现浪费。前面我们提到的有限域可以满足这一要求，但是，要求阶是素数。对于计算机来说，这是不可能的。因为2^{n可以除以2，不肯能是素数。实际上，有限域的要求并没有那个严格，阶为p}n也可以为一个有限域，只需定义适当的运算。

为了方便硬件上的实现，AES使用了GF(2^8)有限域，并且寻找了一种有效的运算——多项式模运算。

4.5.4 普通多项式算术

4.5.5 GF(2^n)上的多项式运算（*）

4.5.6 GF(2^8)运算的计算机实现

1.加法

GF(2^{8)上的加法运算，实际上就是一个计算机上的异或运算，所以GF(2}8)中的两个多项式加法等同于按比特异或运算。

2.乘法

通过上述式子结合实例，可以得知乘以x的运算可以通过左移1比特后再根据最高位按比特异或来实现。

乘以x的更高次幂可以通过重复上述过程来实现。