高级加密标准AES

美国国家标准技术研究所(NIST)于1997年9月12日发出征集高级加密标准AES（Advanced Encryption Standard）的通知。

AES 的草案中给出了接受要求和评估标准是：

A.1 AES 应该可以公开定义。

A.2 AES 应该是对称的分组密码。

A.3 AES 应该设计成密钥长度可以根据需要增加。

A.4 AES 应该可以在硬件和软件中实现。

A.5 AES 应该 a) 可免费获得，或 b) 遵守与美国国家标准学会(ANSI)专利政策一致的规定获得。

注：这意味着将把受专利权保护的算法（受 ANSI 政策影响的算法）也考虑在内。已经放弃了这种想法，因此确保了不受保护（即，无专利）的算法成为唯一的选择。

A.6 将根据以下要素评价符合上述要求的算法：

安全性（密码分析所需的努力）、计算效率、内存需求、硬件和软件可适用性、简易性、灵活性、许可证需求（见上面的 A5）。

NIST对所有的参选算法进行了评估并得到世界许多计算机安全公司及大学的密码专家的支持。良好的安全性是算法获胜的先决条件，但侯选算法在各种计算机平台上运行的速度及通用性也是重要因素。即算法必须在大型计算机、台式计算机、甚至智能卡之类的小设备上安全可靠地运行。

当从最初的15个后选标准筛选到5个时，国家标准技术研究所又邀请了密码专家对这5个候选标准进行了强化攻击，并会同世界密码界对各侯选算法的安全性、速度及其通用性等要素进行了评估。

2000 年 10 月，NIST 选择 Rijndael（发音为 "Rhine dale"）作为 AES 算法。开发Rijndael算法的是来自比利时的密码专家：Proton World International的Joan daemen博士、Katholieke Universiteit Leuven电子工程系(ESAT)的Vincent Rijmen博士后，该算法是根据这二位密码专家的姓氏而命名的。

AES被开发用于替代DES，但NIST预测Triple DES仍将在未来一段时间内作为一种实用的算法(如用于美国政府)，单DES将退出历史舞台。

AES被设计为支持128/192/256 bit (/32=Nb)数据块大小；支持128/192/256 bit (/32=Nk)密钥长度，在10进制里，对应3.4×10³⁸、6.2×10⁵⁷、1.1×10⁷⁷个密钥。

依赖于分组长度Nb、密钥长度Nk，Rijndael的迭代次数Nr见下表。相比较而言，AES的128 bit密钥比DES的56 bit密钥多10²¹倍。

表4.1 分组长度、密钥长度、迭代次数对照表

AES比DES支持更长的密钥。假设一台一秒内可找出DES密钥的机器(如，每秒试255个密钥)，如果用它来找出128-bit AES的密钥，大约需要149万亿年。

Rijndael汇聚了安全，性能，效率，易用和灵活等优点。AES有两个主要的优点：

（1）即使是纯粹的软件实现，AES也是很快的。例如，用C++在奔腾200的电脑上实现的AES的加密速度可达到70M位/秒。Rijndael的非常低的内存需求也使它很适合用于受限环境中。

（2）DES的S-Box的选择是人为的，从而可能包含后门；AES的S-Box具有一定的代数结构，并且能够抗击差分密码分析及线性密码分析。

Rijndael中的某些操作是在字节级上定义的，字节表示有限域GF(2⁸)中的元素，一个字节有8位。其它操作都根据4字节字定义。加法对应于字节级的逐位异或EXOR。

由b₇b₆b₅b₄b₃b₂b₁b₀构成的一个字节b可以看成系数在{0，1}中的多项式。

b₇x⁷+b₆x⁶+b₅x⁵+b₄x⁴+b₃x³+b₂x²+b₁x¹+b₀

在多项式表示中，GF(2⁸)的乘法对应于多项式乘法模除阶数为8的不可约多项式。如果一个多项式除了1和它本身之外没有其它因子，则称它为不可约分的。对于Rijndael，这个多项式叫做m(x)

m(x) = (x⁸ + x⁴ + x³ + x + 1)

或者十六进制表示为'11B'。二进制表示为9比特100011011。以下是一个乘法的例子：

(x⁶+x⁴+x²+x+1)(x⁷+x+1)=(x⁷+x+1) mod(m(x))

AES的总体结构如下：

图4.12 AES 迭代

首先密钥K₀和待加密信息按位相与。然后所有要加密的分组都用一个轮函数F进行迭代计算，计算用的子密钥是由一个密钥扩展函数产生的，初始的密钥是主密钥。对于AES 函数F要迭代Nr次。每轮包含4个动作，最后一轮包含3个动作。

Rijndael采用的是代替/置换网络。被Rijndael处理的数据块被分成一个字节阵列，每次加密操作就是一个字节的导向。Rijndael的轮函数分4层。第一层非线性层，由16个S-盒并置而成，起到混淆的作用。第二和第三层是线性混合层，阵列行被移位，列被混叠，确保多轮之上的高度扩散。在第四层，子密钥字节是执行异或操作到阵列中的每个字节的。在最后一轮中，不采用列的混叠。

Rijndael主要的流程如下：

Rijnadel(State, CipherKey) {

//初始化

KeyExpansion( CipherKey, ExpandedKey );//生成子密钥

AddRoundKey( State, ExpandedKey );//与子密钥位与

// 前Nr-1轮

for(i =1; i < Nr; i++) {

ByteSub(State);// S-盒

ShiftRow(State);// 行被移位

MixColumn(State);// 列被混叠

AddRoundKey (State, ExpandedKey ); ////与子密钥位与

}

//最后一轮

ByteSub(State);

图4.13 状态的例子：Nb=6，Nk=4

（1）ByteSub变换

ByteSub(S-box)非线性、可逆，作用在状态的每个字节上表示为ByteSub(State)。该变换由以下两个子变换合成：

首先，将字节看成GF(2⁸)上的元素，按模m(x)映射到自己的乘法逆，0映射到自身，其次，做如下的GF(2)的仿射变换（可逆的）。可以预先将GF(2⁸)上的每个元素做ByteSub变换，从而形成S-box，进行ByteSub变换时只需要查表操作。可以看出该S-box具有一定的代数结构，而DES中S-box是人为构造的。

（2）ShiftRow变换

表4.2 不同分组长度的偏移量

第0行保持不变，其他行内的字节循环移位，第1行移动C1字节，第2行移动C2字节，第3行移动C3字节。C1、C2、C3依赖于分组长度Nb。当Nb=4或6时，取（C1，C2，C3）=（1，2，3）。

（3）MixColumn变换

列作为GF(2⁸)上多项式乘以多项式c(x)，模M(x) = x⁴+1。

多项式c(x) = ‘03’x³+ ‘01’x²+ ‘01’x+ ‘02’，其中系数是用16进制表示的。

令b(x)=c(x) Ä a(x) mod (x⁴+1)，由于xⁱ mod (x⁴+1)= x^{i mod 4}，故有：

可以写成如下的矩阵乘法形式。

c(x)与模x⁴+1互素，可证明上面的变换是可逆的。定义c(x)的逆为d(x)，满足：

c(x) Ä d(x)= ‘01’

d(x)=’0B’x³+ ‘0D’x²+ ‘09’x+ ‘0E’

（4) AddRoundKey变换

子密钥简单地与状态进行EXOR操作。子密钥的长度等于分组长度。

（5）子密钥的计算

密钥K_i是用密钥扩展函数从第i-1轮的子密钥和密钥K₀得到的。下图描述了密钥扩展函数。16个字节的密钥被分成4组，每组4个字节，来进行处理。最后一组的4个字节由替换函数S（这个S和用F函数进行迭代处理时的S是一样的）来进行替换处理。最初的4个字节的结果和Rcon_i系数相加，这个系数是与轮数相关的，它是预先定义的。最后，为了得到K_i，把得到的4个字节的结果和第i-1轮密钥的最初4个字节按位相加，然后得到的结果又和第i-1轮密钥的下面的4个字节按位相加，如此类推。

图4.16 密钥扩展例Nk=4

主密钥生成子密钥数组，(Nr+1)*Nb个字。

当Nk<=6时（i.e. Nk=4 or 6）：

KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)]) {

当Nk>6时(i.e. Nk=8)：

KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)]) {

Rcon[i]定义为：

Rcon[i] = (RC[i],‘00’,‘00’,‘00’)

RC[1] = 1 (i.e. ‘01’)

RC[i] = x (i.e. ‘02’) ·(RC[i-1]) = x^(i-1)

Rcon[i/Nk]为轮常数，其值用16进制表示为：

Rcon[1]=(01,00,00,00)