第5章 AES -2014

1、AES(Advanced Encryption Standard)本节内容 一、AES的概况 二、AES的流程图 三、AES的数学基础回顾 四、AES的基本变换 五、圈密钥生成 六、AES的加密算法 七、AES的基本逆变换 八、AES的解密算法 九、AES的抗攻击能力 十、AES的实现一、AES的概况1、历史时间1997年，NIST开始了遴选DES替代者 AES的工作 。要求AES具有128比特的分组长度，并支持128、192和256比特的密钥长度，而且能在全世界免费使用1998年从提交的21个算法中选出15个作为候选1999年5个算法入围了最后决赛： RC6、Rijndael、SERPENT

2、、Twofish和MARS2000年评选出最终结果Rijndael2001年11月26日接受其作为标准2001年12月4日正式公布：FIPS1972、AES的设计要求安全性：抵抗所有已知攻击实用性：适用各种环境，速度快扩展性：分组长度和密钥长度可扩展由于Rijndael算法集安全性、性能、效率、可实现性 及灵活性于一体，而在决赛中胜出 3、AES特点 分组密码：明文长度分组密码：明文长度128，密文长度和密钥长度，密文长度和密钥长度可变可变(128/192/256等等,现在一般取现在一般取128.) 不属于不属于Feistel结构结构,加密、解密相似但不对称加密、解密相似但不对称,加加解密使用

3、不同的算法解密使用不同的算法 整体结构：基本轮函数加迭代，轮数可变，整体结构：基本轮函数加迭代，轮数可变，10 综合运用置换、代替、代数等多种密码技术综合运用置换、代替、代数等多种密码技术 有较好的数学理论作为基础有较好的数学理论作为基础 结构简单、速度快结构简单、速度快AES参数Key Length(Nk words)Block Size(Nb words)Number of Rounds (Nr)AES-1284410AES-1926412AES-2568414二、AES的流程图AES的总体描述三、AES的数学基础域的概念：一个域的概念：一个field 是一个是一个group并且满足下面的

4、性质并且满足下面的性质（1）乘法封闭性：如果a,b属于G，则ab属于G.（2）乘法结合律：如果a,b,c 属于G，则有a(bc)=(ab)c恒成立。（3）分配律：如果a,b,c 属于G,则有a(b+c)=ab+ac。（4）乘法交换律：如果a,b属于G,则有ab=ba。（5）没有0的除法：如果a,b属于G,并且ab=0,不能得出a=0 or b=0（6）存在乘法单位元：aI=Ia=a.（7）存在乘法逆元：如果a属于G,且a不等于0,则有ba=ab=I. 给定一个素数，则必存在一个有限域，域中的元素个数为：这类有限域用 来表示。 有限域中的元素可以用多种不同的方式表示。对于任意素数的方幂，都有惟一

5、的一个有限域，因此GF(28)的所有表示是同构的)(npGFnp三、AES的数学基础AES数据处理的单位是字节和字字节：8比特为1字节字：4个字节（32位）为一个字一个字节：有限域GF(28)中的一个元素一个字：系数在GF(28)中并且次数小于4的多项式1、有限域GF(28)AES的理论基础定义在GF(28) ,其基本运算有三种：加法、乘法和x乘；AES的GF(28)表示AES采用GF(28)的多项式元素表示：将b7b6b5b4b3b2b1b0构成的字节看成系数在0,1中的多项式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0加法：两元素多项式的系数按位模2加；乘法：

6、两元素多项式相乘，模m(x)AES采用的既约模多项式为：乘法逆元：a(x)b(x)=1modm(x)根据推广的Euclid算法求出X乘xTime：用x乘以GF(28)的元素若b7=0,则字节左移一位补0；若b7 0,则左移一位补0后，与1B异或；1)(348xxxxxm2、系数在GF(28)中的多项式字：系数在GF(28)中并且次数小于4的多项式例：57 83 4A D1 57x3+83x2+4Ax+D1三种基本运算：字加法、字乘法、字x乘法字加法：对应项系数按位模2加字乘法：多项式乘积再模m(x)=x4+1 AES选定一个固定的可逆多项式做乘法；字X乘法：相当于字节循环移位；43232103

7、2321032321000321110322210333210( )1,( ) ( ) ( )( )( ) M xxa xa xa xa xab xb xb xb xba xb xd xd xd xd xddaaaadaaaadaaaadaaaa乘法：多项式乘积再模记为。 设，则有，其中0123bbbb注：这里矩阵运算中的加法和乘法均为有限域GF(28)中定义的运算 X4+1是可约多项式，所以a(x)不一定可逆；32132324321043243210AES ( )03010102 ( )0 0 090 ( ):( )()mod(1) =()mod(1a xxxxaxb xd xxexb xx

8、b xx b xb xb xbxb xb xb xb xx中选用一个有逆元的固定多项式来作乘法，达到处理字的目的 考虑多项式 乘322103) =GFb xb xb xbx8对(2 )上的多项式的 乘等价于按字节循环左移！四、AES的基本变换四、AES的基本变换 注意：矩阵中的字节是按列进行排序的AES的流程图AES的总体描述四、AES的基本变换四、AES的基本变换四、AES的基本变换4、S盒变换SubBytes(state)4、S盒变换SubBytes(state)字节代换示意图。每个字节用十六进制数表示，每个字节按S盒进行独立代换；4、S盒变换SubBytes(state)四、AES的基本

9、变换4、S盒变换SubBytes(state)SubBytes SubBytes 四、AES的基本变换5、行移位变换ShiftRows (state)四、AES的基本变换5、行移位变换ShiftRows (state)行移位示意图四、AES的基本变换5、行移位变换ShiftRows (state)例如当Nb=4时，具体的操作如下：每行四字节构成的字做不同次数的每行四字节构成的字做不同次数的x乘操作乘操作(按按字节字节循环左移）循环左移）四、AES的基本变换5、行移位变换ShiftRows (state) ShiftRow的逆变换是对状态阵列的后3行分别以位移量Nb-C1、Nb-C2、Nb-C3

10、进行循环左移位，使得第i行第j列的字节移位到(j+Nb-Ci) mod Nb。四、AES的基本变换6、列混合变换MixColumns (state)四、AES的基本变换6、列混合变换MixColumns (state)6、列混合变换MixColumns (state) 这个运算需要做GF(28)上的乘法，但由于所乘的因子是3个固定的元素02、03、01，所以这些乘法运算仍然是比较简单的。 列混合运算示意图6、列混合变换MixColumns (state)6、列混合变换MixColumns (state)6、列混合变换MixColumns (state)6、列混合变换MixColumns (st

11、ate) 列混合运算的逆运算是类似的，即每列都用一个特定的多项式d(x)相乘。d(x)满足(03x3+01x2+01x+02)d(x)=01由此可得d(x)=0Bx3+0Dx2+09x+0E四、AES的基本变换密钥加运算示意图密钥加运算的逆运算是其自身。五、圈密钥生成扩展密钥的比特数等于分组长度乘以轮数加1；例如要将128比特的明文经过10轮的加密，则总共需要（10+1）*128=1408比特的密钥。五、圈密钥生成五、圈密钥生成五、圈密钥生成看AES动画理解密钥扩展算法五、圈密钥生成KeyExpansion (byteKey4*Nk , WNb*(Nr+1) for (i =0; i Nk;

12、i +)Wi=(Key4* i,Key4* i +1,Key4* i +2,Key4* i +3 ); for (i =Nk; i 6的密钥扩展说明： 与Nk6的密钥扩展的不同之处在于：如果j被Nk除的余数=4,则在异或之前，对wj-1进行SubBytes变换； 增加了SubBytes变换，因为当Nk6时，密钥很长，仅仅对Nk的整数倍的位置处的字进行Sub Bytes变换就显得SubBytes变换的密度较稀，安全程度不够强。KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0; i Nk; i +)Wi=(Key4* i, Key4* i +1, K

13、ey4* i +2, Key4* i +3 );for (i =Nk; i 6时，扩展算法如下：时，扩展算法如下：五、圈密钥生成Nb=6且Nk=4时的密钥扩展与轮密钥选取 看看flash动画演示（密钥编排过程）。动画演示（密钥编排过程）。 密钥编排方案 密钥编排方案六、AES的加密算法七、AES的基本逆变换 AES的解密算法框图 七、AES的解密算法首先给出几个引理。 引理3.1 设字节代换（ByteSub）、行移位（ShiftRow）的逆变换分别为InvByteSub、InvShiftRow。则组合部件“ByteSubShiftRow”的逆变换为“InvByteSubInvShiftRow”

14、。 七、AES的解密算法 证明：组合部件“ByteSubShiftRow”的逆变换原本为“InvShiftRowInvByteSub”。由于字节代换（ByteSub）是对每个字节进行相同的变换，故“InvShiftRow”与“InvByteSub”两个计算部件可以交换顺序。（证毕） 七、AES的解密算法 引理3.2 设列混合（MixColumn）的逆变换为InvMixColumn。则列混合部件与密钥加部件（AddRoundKey）的组合部件“MixColumnAddRoundKey (, Key)”的逆变换为“InvMixColumnAddRoundKey (, InvKey)”。 其中密钥I

15、nvKey与Key的关系为： InvKey=InvMixColumn (Key)。 七、AES的解密算法证明：组合部件“MixColumnAddRoundKey (, Key)” 的逆变换原本为“AddRoundKey (, Key)InvMixColumn”，由于列混合（MixColumn）实际上是线性空间GF(28)4上的可逆线性变换，因此“AddRoundKey (, Key)InvMixColumn”=“InvMixColumnAddRoundKey (, InvMixColumn (Key)”（证毕） 七、AES的解密算法引理3.3 将某一轮的后两个计算部件和下一轮的前两个计算部件组

16、成组合部件，该组合部件的程序为MixColumn (State)； AddRoundKey (State, Key(i); ByteSub (State); ShiftRow (State)则该组合部件的逆变换程序为InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)七、AES的解密算法 证明：这是引理3.1和引理3.2的直接推论。 注意到在引理3.3所描述的逆变换中，第2步到第4步在形状上很像加密算法的轮函数，这将是解密算法的轮函数。注意到

17、结尾轮只有3个计算部件，因此可以得到如下定理。 七、AES的解密算法定理2 Rijndael密码的解密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。其中解密算法的轮函数为InvRound (State, RoundKey) InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, RoundKey) 七、AES的解密算法解密算法的结尾轮为InvFinalRound (State, RoundKey) InvByteSub (State); InvShiftRow (State); AddRoundKey (State, RoundKey) 七、AES的解密算法 设加密算法的初始密钥加、第1轮、第2轮、第Nr轮的子密钥依次为k(0), k(1), k(2), , k(Nr-1), k(Nr) 则解密算法的初始密钥加、第1轮、第2轮、第Nr轮的子密钥依次为k(Nr), InvMixColumn (k(Nr-1), InvMixColumn (k(Nr-2), ,InvMixColumn (k(1), k(0)。七、AES的解密算法综上所述，Rijndael密码的解密算法与加密算法的计算网络相同，只是将各计算部件换为对应的逆部件。七、