第5章 高级加密标准(AES) AES的起源 AES的设计原则 AES算法描述

1. AES的起源 1997年9月，NIST征集AES方案，以替代DES。 1999年8月，以下5个方案成为最终候选方案：MARS, RC6, Rijndael, Serpent, Twofish。 2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（ Rijndael 读成Rain Doll。） http://www.esat.kuleuven.ac.be/~rijmen/rijndael/

2. AES的设计原则 能抵抗所有已知的攻击； 在各种平台上易于实现，速度快； 设计简单。 Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。

表 1. 分组长度和密钥长度的不同取值 分组长度（bit） 128 192 256 密钥长度（bit） 128 192 256

3. AES 算法的一般描述

Rijndael Round的构成 ByteSubstitution ByteSubstitution ByteRotation Key + MixColumn Round Key + 一般的轮变换 最后一轮的轮变换

Fig 1. 以明文分组为128bits为例组成的阵列 3. AES 算法加密部分的实现 明文分组和密钥的组织排列方式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 Fig 1. 以明文分组为128bits为例组成的阵列

Fig 2. 以明文分组（或密钥）为128bits、192bits 、256bits为例组成的阵列 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 20 1 5 9 13 17 21 2 6 10 14 18 22 3 7 11 15 19 23 4 8 12 16 20 24 28 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15 19 23 27 31

一些相关的的术语定义和表示 状态（State）：密码运算的中间结果称为状态。 State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。 Nb=分组长度（bits）÷ 32 Nb可以取的值为4，6，8，对应的分组长度为128， 192， 256 bits。 密码密钥（Cipher Key）的表示： Cipher Key类似地用一个4行的矩阵阵列来表示，列数记为Nk。 Nk=密钥长度（bits）÷32 Nk可以取的值为4，6，8，对应的密钥长度为128， 192， 256 bits。

Fig 3. 当Nb=6时的状态和Nk=4时的密钥布局 a0,0 a0,1 a0,2 a0,3 a0,4 a0,5 a1,0 a1,1 a1,2 a1,3 a1,4 a1,5 a2,0 a2,1 a2,2 a2,3 a2,4 a2,5 a3,0 a3,1 a3,2 a3,3 a3,4 a3,5 K0,0 K0,1 K0,2 K0,3 K1,0 K1,1 K1,2 K1,3 K2,0 K2,1 K2,2 K2,3 K3,0 K3,1 K3,2 K3,3 Nb = 6 Block Length = 192 bits Nk = 4 Key Length = 128 bits

Fig 4. 分组长度和密钥长度均为128 bits时的Rijndael加密算法框图 Plain Text Data / Key Addition Rnd Rnd 1 Rnd 8 Final Rnd Key Schedule Cipher Text Key

10 12 14 表 2. 轮数（Round）的不同取值 轮数（Round） Block Length=128 Key Length=128 10 12 14 Key Length=192 Key Length=256

FinalRound(State, RoundKey) Round(State, RoundKey) 用伪代码表示的Rijndael轮变换 结尾轮变换 FinalRound(State, RoundKey) { ByteSubstituion; ByteRotation; AddRoundKey; } 一般的轮变换 Round(State, RoundKey) { ByteSubstitution; ByteRotation; MixColumn; AddRounKey; }

ByteSubstitution(字节替代) 1. 在有限域GF(28)上求乘法逆，‘00’映射到它自身。 2. 在GF(2)上进行下面的仿射变换：

y0 1 1 1 1 1 0 0 0 x0 0 y1 0 1 1 1 1 1 0 0 x1 1 y2 0 0 1 1 1 1 1 0 x2 1 y3 0 0 0 1 1 1 1 1 x3 0 y4 ＝ 1 0 0 0 1 1 1 1 x4 ＋ 0 y5 1 1 0 0 0 1 1 1 x5 0 y6 1 1 1 0 0 0 1 1 x6 1 y7 1 1 1 1 0 0 0 1 x7 1

Fig 6. ByteSubstitution 该变换可以用一个256字节的表来实现 A0,0 A0,1 A0,2 A0,3 A1,0 A1,1 A1,2 A1,3 A2,0 A2,1 A2,2 A2,3 A3,0 A3,1 A3,2 A3,3 B0,0 B0,1 B0,2 B0,3 B1,0 B1,1 B1,2 B1,3 B2,0 B2,1 B2,2 B2,3 B3,0 B3,1 B3,2 B3,3 取逆 仿射变换

ByteRotation(字节移位) Nb C1 C2 C3 4 1 2 3 6 8 在ByteRotation变换中，状态阵列的后3行循环移位不同的偏移量。第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。 偏移量C1、C2、C3与分组长度Nb有关，如下表所示： Nb C1 C2 C3 4 1 2 3 6 8

Fig 7. ByteRotation 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 5 9 13 1 10 14 2 6 15 3 7 11 循环左移1字节 循环左移2字节 循环左移3字节

MixColumn(列混合) 将状态的列看作是有限域GF(28)上的多项式a(x)，与多项式c(x) = 03 x3 + 01 x2 + 01 x +02相乘(模x4＋1)。 令b(x) = c(x) × a(x)，写成矩阵形式为： b0 02 03 01 01 a0 b1 = 01 02 03 01 a1 b2 01 01 02 03 a2 b3 03 01 01 02 a3

Fig 8. MixColumn 这一运算作用在每一列上 A0,0 A0,1 A0,2 A0,3 A1,0 A1,1 A1,2 A1,3 A2,0 A2,1 A2,2 A2,3 A3,0 A3,1 A3,2 A3,3 B0,0 B0,1 B0,2 B0,3 B1,0 B1,1 B1,2 B1,3 B2,0 B2,1 B2,2 B2,3 B3,0 B3,1 B3,2 B3,3 × C(X)

2.4 AddRoundKey(轮密钥加) 将轮密钥与状态按比特异或。轮密钥是通过Key Schedule过程从密码密钥中得到的，轮密钥长度等于分组长度。

A0,0 A0,1 A0,2 A0,3 A1,0 A1,1 A1,2 A1,3 A2,0 A2,1 A2,2 A2,3 A3,0 A3,1 A3,2 A3,3 K0,0 K0,1 K0,2 K0,3 K1,0 K1,1 K1,2 K1,3 K2,0 K2,1 K2,2 K2,3 K3,0 K3,1 K3,2 K3,3 ＋ B0,0 B0,1 B0,2 B0,3 B1,0 B1,1 B1,2 B1,3 B2,0 B2,1 B2,2 B2,3 B3,0 B3,1 B3,2 B3,3 A3,3 ＋ K3,3 ＝ B3,3 (mod 2)

Fig 7. Rijndael加密及解密的标准结构 Block , Key Length = 128 bits Plaintext(128 bits) Ciphertext(128 bits) K0 i = 9 K10 ＋ ＋ ByteSubstitution InvMixCoumn for i=9 to 0 for i=1 to 10 ByteRotation InvByteRotation MixColumn InvByteSubstitution Ki ＋ Ki ＋ i=10 Ciphertext(128 bits) Plaintext(128 bits) 加密 解密

用伪代码表示的Rijndael加密算法 Rijndael ( State, CipherKey ) { KeyExpansion ( CipherKey, ExpandedKey ); AddRoundKey ( State, ExpandedKey ); For ( i=1; i<Rnd; i++ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); }

提前进行密钥扩展后的Rijndael加密算法描述 Rijndael ( State, ExpandedKey ) { AddRoundKey ( State, ExpandedKey ); For ( i=1; i<Rnd; i++ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); }

AES 的密钥调度 密钥调度包括两个部分：密钥扩展和轮密钥选取。 密钥bit的总数＝分组长度×（轮数Round＋1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408bits。 将密码密钥扩展成一个扩展密钥。 从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个圈密钥由接下来的Nb个4字节字组成，以此类推。

密钥扩展 K0,0 K0,1 K0,2 K0,3 K1,0 K1,1 K1,2 K1,3 K2,0 K2,1 K2,2 K2,3 K3,0 K3,1 K3,2 K3,3 K0 K1 K2 K3 + K0 K1 K2 K3 K4 K5 K6 K7 + +

K0 K1 K2 K3 K4 K5 K6 K7 Byte Substitution ByteRotate + Rcon

Wi-4 Wi-3 Wi-2 Wi-1 Wi Key expansion 4 =< i < 4 ( Rnd + 1 ) Wi-4 Wi-3 Wi-2 Wi-1 Byte Substituion Byte Rotate Rcons + + Wi i mod 4 = 0 i mod 4 != 0 Key expansion

轮密钥选取 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 轮密钥0 轮密钥1 轮密钥2

AES的解密算法 解密算法与加密算法不同 每个阶段均可逆，因此易证解密函授的确可以恢复明文 见图5.7，P.121

AES 算法的设计原理 GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。 ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满足以下条件：1. 可逆性； 2. 输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极小化； 3. 异或差分表中最大非平凡值的极小化； 4. GF(28)中代数表示的复杂性； 5. 描述的简单性。

满足前3条准则的S盒的构造方法已被给出，AES的作者从众多候选构造中选择将x映射到它的逆的S盒。该映射过于简单，为了抵抗插入攻击，加入仿射变换： b(x)=(x7 + x6 + x2 + x) + a(x)(x7 + x6 + x5 + x4 + 1) mod x8 + 1 模数多项式x8 + 1选择为可能是最简单的模数多项式。 可以找到其它的S盒满足以上准则。

MixColumn变换符合以下准则： 1. 可逆性； 2. GF(2)中的线性性； 3. 适当的扩散性能； 4. 8位处理器上实现速度快；5 MixColumn变换符合以下准则： 1. 可逆性； 2. GF(2)中的线性性； 3. 适当的扩散性能； 4. 8位处理器上实现速度快；5. 对称性； 6. 描述的简单性。选择模数多项式x4＋1可满足准则2、5、6。准则1、3、4要求系数的值要小，故选00、01、02 、 03。 ByteRotation符合以下准则： 1. 4个位移量互不相同且C0＝0； 2. 能抵抗差分截断攻击； 3. 能抗Square攻击； 4. 简单。 从满足准则2和准则3出发，AES的作者选取了最简单的组合。

与一些其它算法的比较： 与DES相比： 1. 无DES中的弱密钥和半弱密钥； 2. 紧凑的设计使得没有足够的空间来隐藏陷门。 与IDEA相比： 无IDEA中的弱密钥。 具有扩展性：密钥长度可以扩展到为32bits倍数的任意密钥长度，分组长度可以扩展到为64bits倍数的任意分组长度。圈数和循环移位偏移量作为参数，要重新定义。

关于有限域G(28)的一些解释 G(28)可看为8位二进制比特串的集合 直观上有限域的运算可为密码算法的实现带来方便 参加第4章，p.95）

G(28)上的运算 加法 按位异或 乘法 可通过对多个中间结果的移位运算和异或一个特定的比特串（比如00011011）实现。