AES加密算法详解

1、第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.kuleu

2、ven.ac.be/rijmen/rijndael/2. AES的设计原则的设计原则 能抵抗所有已知的攻击；能抵抗所有已知的攻击； 在各种平台上易于实现，速度快；在各种平台上易于实现，速度快； 设计简单。设计简单。 Rijndael是一个分组密码算法，其是一个分组密码算法，其分组长度和密钥长度相互独立，都可以分组长度和密钥长度相互独立，都可以改变。改变。分组长度分组长度（bit）128192256密钥长度密钥长度（bit）128192256表表 1. 分组长度和密钥长度的不同取值分组长度和密钥长度的不同取值3. AES 算法的一般描述算法的一般描述Rijndael Round的构成的构成Byt

3、eSubstitutionByteRotationMixColumn+RoundKey一般的轮变换一般的轮变换ByteSubstitutionByteRotation+RoundKey最后一轮的轮变换最后一轮的轮变换3. AES 算法加密部分的实现算法加密部分的实现明文分组和密钥的组织排列方式明文分组和密钥的组织排列方式 0 1 2 3 4 5 6 789 10 11 12 13 14 150481215913261014371115Fig 1. 以明文分组为以明文分组为128bits为例组成的阵列为例组成的阵列04 81215 91326 10 1437 11 1504812 16 2015

4、913 17 21261014 18 22371115 19 2304812 16 20242815913 17 2125292610 14 18 2226303711 15 19 232731Fig 2. 以明文分组（或密钥）为以明文分组（或密钥）为128bits、192bits 、256bits为例组成的阵列为例组成的阵列 一些相关的的术语定义和表示一些相关的的术语定义和表示 状态（状态（State）：）：密码运算的中间结果称为状态。密码运算的中间结果称为状态。 State的表示：状态用以字节为基本构成元素的矩的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有阵阵列来表示，该阵列

5、有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时的密钥布局时的密钥布局a

6、0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb = 6Block Length = 192 bitsK0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk = 4Key Length = 128 bitsFig 4. 分组长度和密钥长度均为分组长度和密钥长度均为128 bits时的时的Rijndael加密算法框图加密算法框图Data / Key AdditionRnd0R

7、nd1Rnd8FinalRndKeyScheduleCipherTextKeyPlainText表表 2. 轮数（轮数（Round）的不同取值）的不同取值轮数轮数（Round）Block Length=128Block Length=192Block Length=256Key Length=128101214Key Length=192121214Key Length=256141414用伪代码表示的用伪代码表示的Rijndael轮变换轮变换一般的轮变换一般的轮变换Round(State, RoundKey) ByteSubstitution; ByteRotation; MixColumn

8、; AddRounKey; 结尾轮变换结尾轮变换FinalRound(State, RoundKey) ByteSubstituion; ByteRotation; AddRoundKey; ByteSubstitution(字节替代字节替代) ByteSubstitution是一个非线性的字节替代，独立地在是一个非线性的字节替代，独立地在每个状态字节上进行运算。它包括两个变换。每个状态字节上进行运算。它包括两个变换。 1. 在有限域在有限域GF(28)上求乘法逆，上求乘法逆，00映射到它自身。映射到它自身。 2. 在在GF(2)上进行下面的仿射变换：上进行下面的仿射变换： y0 1 1 1

9、1 1 0 0 0 x0 0y1 0 1 1 1 1 1 0 0 x1 1y2 0 0 1 1 1 1 1 0 x2 1y3 0 0 0 1 1 1 1 1 x3 0y4 1 0 0 0 1 1 1 1 x4 0y5 1 1 0 0 0 1 1 1 x5 0y6 1 1 1 0 0 0 1 1 x6 1y7 1 1 1 1 0 0 0 1 x7 1Fig 6. ByteSubstitution该变换可以用一个该变换可以用一个256字节的表来实现字节的表来实现B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A

10、0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3取逆取逆仿射变换仿射变换ByteRotation(字节移位字节移位) 在在ByteRotation变换中，状态阵列的后变换中，状态阵列的后3行循环移位不行循环移位不同的偏移量。第同的偏移量。第1行循环移位行循环移位C1字节，第字节，第2行循环移位行循环移位C2字字节，第节，第3行循环移位行循环移位C3字节。字节。 偏移量偏移量C1、C2、C3与分组长度与分组长度Nb有关，如下表所示：有关，如下表所示：NbC1C2C3412361238134Fig 7. ByteRotation

11、04812159132610143711150481259131101426153711循环左移循环左移1字节字节循环左移循环左移2字节字节循环左移循环左移3字节字节MixColumn(列混合列混合) 将状态的列看作是有限域将状态的列看作是有限域GF(28)上的多项式上的多项式a(x)，与多，与多项式项式c(x) = 03 x3 + 01 x2 + 01 x +02相乘相乘(模模x41)。 令令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 0

12、1 02 a3Fig 8. MixColumn这一运算作用在每一列上这一运算作用在每一列上A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3 C(X)2.4 AddRoundKey(轮密钥加轮密钥加)将轮密钥与状态按比特异或。轮密钥是通过将轮密钥与状态按比特异或。轮密钥是通过Key Schedule过程从密码密钥中得到的，轮密钥长度等于分组长度。过程从密码密钥中得到的，轮密钥长度等于分组长度

13、。A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A3,3 K3,3 B3,3 (mod 2)Fig 7. Rijndael加密及解密的标准结构加密及解密的标准结构Block , Key Length = 128 bitsPlaintext(128 bits)By

14、teSubstitutionMixColumnCiphertext(128 bits) K0Kii=10ByteRotationfor i=1 to 10Ciphertext(128 bits) K10InvMixCoumnInvByteRotationInvByteSubstitution KiPlaintext(128 bits)i = 9for i=9 to 0加密加密解密解密用伪代码表示的用伪代码表示的Rijndael加密算法加密算法Rijndael ( State, CipherKey ) KeyExpansion ( CipherKey, ExpandedKey ); AddRou

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

16、FinalRound ( State, ExpandedKey + Nb*Rnd ); AES 的密钥调度的密钥调度 密钥调度包括两个部分：密钥扩展和轮密钥选密钥调度包括两个部分：密钥扩展和轮密钥选取。取。 密钥密钥bit的总数分组长度的总数分组长度（轮数（轮数Round1）例如当分组长度为例如当分组长度为128bits和轮数和轮数Round为为10时，时，轮密钥长度为轮密钥长度为128(101)1408bits。 将密码密钥扩展成一个扩展密钥。将密码密钥扩展成一个扩展密钥。 从扩展密钥中取出轮密钥：第一个轮密钥由扩展从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个密钥的第一个Nb个个4

17、字节字，第二个圈密钥由接字节字，第二个圈密钥由接下来的下来的Nb个个4字节字组成，以此类推。字节字组成，以此类推。密钥扩展密钥扩展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+RconWi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Key expansion4 = i 4 ( Rnd + 1 )i mod 4 = 0i mod

18、4 != 0 轮密钥选取轮密钥选取K0K1K2K3K4K5K6K7K8K9K10K11K12轮密钥轮密钥0轮密钥轮密钥1轮密钥轮密钥2AES的解密算法 解密算法与加密算法不同 每个阶段均可逆，因此易证解密函授的确可以恢复明文 见图5.7，P.121AES 算法的设计原理算法的设计原理 GF(28)中乘法使用的多项式是中乘法使用的多项式是8次不可约多项式列次不可约多项式列表中的第一个多项式。表中的第一个多项式。 ByteSubstitution（称为（称为S盒）在设计时考虑到盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满抵抗差分密码分析、线性密码分析的要求，应满足以下条件：足以下条

19、件：1. 可逆性；可逆性； 2. 输入比特的线性组合输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极与输出比特的组合之间的最大非平凡相关性的极小化；小化； 3. 异或差分表中最大非平凡值的极小化；异或差分表中最大非平凡值的极小化； 4. GF(28)中代数表示的复杂性；中代数表示的复杂性； 5. 描述的简单描述的简单性。性。 满足前满足前3条准则的条准则的S盒的构造方法已被给出，盒的构造方法已被给出，AES的作者从众多候选构造中选择将的作者从众多候选构造中选择将x映射到它的映射到它的逆的逆的S盒。该映射过于简单，为了抵抗插入攻击，盒。该映射过于简单，为了抵抗插入攻击，加入仿射变换：

20、加入仿射变换：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. 对称性；对称性； 6. 描述的简单描述的简单性。选择模数多项式性。选择模数多项式x