AES算法介绍姓名万天添学号141080054日期2015.3.23目录CONTENTS03AES起源Part105AES算法参数Part207AES算法总体Part308轮函数Part420密钥编排Part525解密算法Part628AES和DES的比较Part7AES起源随着计算能力的突飞猛进,已经超期服役的DES终于显得力不从心。1997年4月5日,NIST(美国国家加密标准和技术协会)开始征集和评估新的数据加密标准AES(advancedencryptionstandard),目的是寻找一个安全性更好的分组加密算法代替DES。AES的基本要求是安全性不能低于三重DES,而且必须是分组长度为128位,并能支持长度为128位、192位、256位的密钥。在1998年6月15日提交的21个算法里,有15个满足所有的必备条件并被接纳为AES的候选算法。NIST在1998年8月20日的“第一次AES候选大会”上宣布了15个AES的候选算法。1999年3月举行了“第二次AES候选大会”,之后,在1999年8月,5个候选算法入围了最后决赛:MARS,RC6,Rijndael,Serpent和Twofish。2000年4月举行了“第三次AES候选大会。在2000年10月2日,Rijndael被选择为高级加密标准AES的候选算法根据以下三条主要原则进行评判:安全性代价算法与实现特性5个入围最后决赛的算法都被认为是安全的。Rijndeal之所以最后当选是因为它集安全性、性能、效率、可实现性和灵活等优点,尤其是该算法在无论有无反馈模式的计算环境下的硬、软件中都能显示出其非常好的性能。它的密钥安装时间刚刚好,也具有好的灵敏度。Rijndeal的非常低的内存需求也使它是适用于受限环境中。Rijndeal的操作简单,并可抵御强大和实时的攻击。AES算法参数Rijndael是一个迭代型分组密码,其分组是长度和密钥长度都可变,各自可以独立地指定为128比特、192比特、256比特,对应的迭代轮数(Nr)为10、12、14。状态(State)类似于明文分组和密文分组,算法的中间结果也须分组,称算法的中间结果的分组为状态,所有的操作都在状态上进行。状态用以字节为基本构成元素的矩阵阵列来表示,该阵列有4行,列数记为Nb。Nb等于分组长度除以32。种子密钥种子密钥类似的用一个以字节为元素的矩阵阵列表示,该阵列有4行,列数记为Nk,Nk等于分组长度除以32。NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414算法参数说明算法的输入(包括最初的明文输入和中间过程的输入)以字节为单位按a00a10a20a30a01a11a21a31……的顺序放置到状态阵列中。同理密文也是如此。而输出(包括中间过程的轮输出和最后的密文的输出)也是以字节为单位按按相同的顺序从状态阵列中取出。a0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb=6K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk=4加密总体结构读入明文密钥编排初始轮密钥加法SubByteShiftRowMixColumnAddRoundKeySubByteShiftRowAddRoundKey密文Nr-1读入种子密钥中间轮变换最后轮变换K0KiKNr轮变换SubByte(State)ShiftRow(State)MixColumn(State)•AES算法的轮函数包括:每一轮字节代换(SubByte)、行移位变换(ShiftRow)、列混合变换(MixColumn)、轮密钥加变换(AddRoundKey)组成(最后一轮没有列混合变换,类似DES中最后一轮没有变换)。输入state输出stateAddRoundKey(State,ExpandedKey)输入ExpandedKey[i]SubByte(字节代换)SubByte(字节代换)是可逆的非线性变换,独立的对状态的每个字节进行。可将字节变换方法制成S盒,通过查表进行快速变换。S盒设计原理AES的S盒设计不像DES的S盒设计那么神秘,而是有严格的数学计算。其设计原理是将一个字节非线性地变换为另一个字节。由两个变换复合而成:①首先,将字节看做GF(28)上的元素,计算乘法逆,规定'00'的逆为它本身②彷射变换。SubByte涉及有限域GF(28))1/(][348228xxxxxF有限域GF(28)有限域中的元素可以用多种不同的方法表示。对于任意素数的方幂,都有唯一的一个有限域,因此GF(28)的所有表示是同构的,但不同的表示方法会影响到GF(28)上的运算的复杂度,本算法采用传统的多项式表示法。将b7b6b5b4b3b2b1b0构成的字节看做系数在(0,1)中的多项式例如:十六进制数‘57’对应的二进制为01010111,看成一个字节,对应的多项式x6+x4+x2+x+1。在多项式表示中,GF(28)上两个元素的和仍然是一个次数不超过7的多项式,其系数等于两个元素对应的系数的模2加(比特异或)。如'57'+'83'='D4'。由于每个元素的加法的逆元等于自己,所以减法和加法相同。要计算GF(28)上的乘法,必须先确定一个GF(28)上的8次不可约多项式;GF(28)上两个元素的乘积就是这两个多项式的模乘(以这个8次不可约多项式为模)。在Rijndael密码中,这个8次不可约多项式确定为,例如,‘57’·‘13’=‘FE’。01223344556677bxbxbxbxbxbxbxb1348xxxx•以上定义的乘法满足交换律,且有单位元'01'。另外,对任何次数小于8的多项式b(x),可用扩展的Euclidean算法得到b(x)的乘法逆元。再者乘法还满足分配律。所以,256个字节值构成的集合,在以上定义的加法和乘法运算下,有有限域GF(28)的结构。•GF(28)上还定义了一个运算,称为x的乘法,其定义为:如果b7=0,求模结果不变,否则为乘积结果减去m(x),即求乘积结果与m(x)的异或。记该算法为b=xtime(a)。从而可以把任意常数的乘法转化为简单的对中间结果相加来实现例如:‘57’·‘13’可以按如下方式实现‘57’·‘02’=xtime(01010111)=10101110‘57’·‘04’=xtime(10101110)=101011100+100011011=01000111‘57’·‘08’=xtime(01000111)=10001110‘57’·‘10’=xtime(10001110)=100011100+100011011=00000111‘57’·‘13’=57·('01'+'02'+'10')=01010111+10101110+00000111=11111110='FE'))(mod()(021324354657687xmxbxbxbxbxbxbxbxbxbx系数在GF(28)上的多项式4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对应系数的相加,也就是4个字节向量的逐比特异或。规定多项式的乘法运算必须要取模M(x)=x4+1,这样使得次数小于4的多项式的乘积仍然是一个次数小于4的多项式。在Rijndael密码中,对多项式b(x),这种乘法算法只限于一个固定的有逆元的多项式可记为所以由于。设,),1mod(1)()()()(,)(30211203333201102232231001131221300044012233012233012233babababacbabababacbabababacbabababacxxcxcxcxcxaxaxcbxbxbxbxaaxaxaxaxa321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc’‘’‘’‘’‘02010103)(23xxxxa逆变换1.BinaryToField:把一个字节转换为一个域元素2.FieldInv:求一个域元素的乘法逆(规定00的逆为00)3.FieldToBinary:把一个域元素转换为一个字节彷射变换这里的A为一个规定的矩阵BinaryToField输入z(8bits)FieldInvFieldToBinary彷射变换输出z(8bits)TTT)()xxxxxxxA(x)yyyyyyy(y110001107654321076543210彷射变换Luv0110001111111000011111000011111000011111100011111100011111100011111100017654321076543210aaaaaaaabbbbbbbb效果。速进行,且具有混淆的位。可见计算可快的第为其中足:从另一个角度来看,满iccaaaaabiiiiiiii)01100011()63(88mod)7(8mod)6(8mod)5(8mod)4(SubByte例子以F5为例说明S盒的替代操作。不通过查表,而通过代数运算。1.首先求得F5在GF(28)上的逆元输入F5对应11110101,对应多项式为,求其模的逆。令通过扩展的Euclidean算法,求得其逆。二进制表示为”01000110“。2.再进行彷射变换,带入矩阵得到二进制结果为:11100110,对应的十六进制结果为E6)1(24567xxxxx)1()(348xxxxxm,)(mod1)()1(24567xmxaxxxxxxxxxa26)(1110011001100011010001101111100001111100001111100001111110001111110001111110001111110001ShiftRow(行移位)将状态矩阵第i行循环左移i位。i=0,1,2,3。即04812159132610143711150481259131101426153711循环左移3位循环左移1位循环左移2位不移位行移位实现了字节在每一行的扩散,自然地,还需要字节的改变在列的扩散MixColumns(列混合变换)把转态矩阵每4个字节表示为GF(28)上的多项式S(x),再将该多项式与固定多项式c(x)做模x4+1乘法。即由于c(x)固定。故可将该乘法写成如下形式于是,可以记列混合运算为:M(S)=CS。)1mod()()()(4xxSxcxS333231302322212013121110030201003332313023222120131211100302010002010103030201010103020101010302ssssssssssssssssssssssssssssssssEDBBEDDBEDBEC009000009000009090001AddR