密码学课件：六、分组密码-AES

1、分组密码主要内容AES算法的数学基础AES介绍分组密码的工作模式国际数据加密标准-IDEAAES算法的数学基础有限域及其运算群和交换群的定义一个非空集合G上定义一个二元运算“”，如果满足下列条件（1）封闭性： a,bG，有abG；（2）结合律： a,b,cG，有abc=(ab)c=a(bc)；（3）单位元： eG, aG，有ae=ea=a，e称为单位元；（4）逆元： aG, a-1G，使得aa-1=a-1a=e, a-1称为逆元；则称该代数系统为群，记为(G,)。（5）交换律： a,bG，有ab=ba；如果群满足交换律，则称为交换群。如果一个群的元素是有限的，则为有限群，否则为无限群。定义：有

2、限群中元素的个数为群的阶。元素的阶的定义定义：an=aaa（n个a进行运算），a0=1，a-n=(a-1)n对于群(G,)中的一个元素a，满足an=e（e为单位元）的最小正整数n称为元素a的阶。若这样的n不存在，则称元素a是无限阶的。Lagrange（拉格朗日）定理有限群G的元素的阶能够整除G的阶。循环群的定义定义：群G被称作循环群，如果aG，使得bG，存在某个整数i使得b=ai。将这样的元素a称为循环群的生成元，记G=。定理阶为素数的群必是循环群。证明：设群G的阶为素数p，由于G的任一元素的阶能够整除p，故任取aG，a的阶要么是1要么是p。设单位元为1，若a1，则a的阶为p（若阶为1，有a1

3、=1，矛盾），根据元素的阶的定义， 有ap=1且a,a2,a3,a(p-1),ap彼此不同。根据群中运算的封闭性有a,a2,a3,a(p-1),apG，又因为G的阶为p，故G=1, a,a2,a3,a(p-1)，这就证明了G是循环群。群的性质除了定义中的性质，群还有以下性质。（1）群中的单位元具有唯一性；（2）群中的逆元具有唯一性；（3）（消去律） a,b,cG，如果ab=ac，则b=c；同样，如果ba=ca，则b=c。例如m为素数，a是m的本原根，在集合Zm*=1,2,m-1定义二元运算”如下：xy=(ax mod m)(ay mod m)=a(x+y) mod m, x,yZm*则(Zm*

4、,)为循环群。其中，单位元为1。任意元素的阶都为m-1，任何元素都可以作为群的生成元。m为素数，a是m的本原根，集合Zm*=a mod m, a2 mod m, a3 mod m,am-1 mod m上定义的数乘”运算构成群，且为循环群。即群(Zm*,)为循环群。其中，单位元为1。环的定义环是一个代数系统，它由一个至少包含两个元素的集合R构成，在集合R上定义有两个二元运算：加法“+”和乘法“”，并满足下列条件。（1）R关于加法“+”是一个交换群，其单位元为“0”，称为环的零元，元素a的逆元为-a；与加法对应的逆运算（减法）定义为：a-b=a+(-b)。（2）乘法满足结合律： a,b,cR，有a

5、bc=(ab)c=a(bc) 。（3）乘法在加法上满足分配律： a,b,cR，有a(b+c)=(b+c)a= ab+ac将满足上面性质的代数系统称为环R，即为 。例如整数集关于整数的加法和乘法构成整数环。类似地，有理数集关于有理数的加法和乘法构成有理数环；实数集关于有理数的加法和乘法构成实数环；复数集关于有理数的加法和乘法构成复数环。此外，若令 表示全体偶数构成的集合，则 关于偶数的加法和乘法构成一个环，称为偶数环。一般地，凡是数（无论是实数还是复数）集关于数的加法和乘法构成的环都称为数环。显而易见，凡是数环都以数0为其零元。例如例3 设n是一个正整数，设集合 Zn=0n, 1n, , n-1

6、n是模n的剩余类构成的集合，在Zn上定义”+”运算：an+bn=a+bn 则(Zn,+)是加法交换群。在Zn上定义”运算：anbn=abn则(Zn,+,)构成一个环，称为模n的剩余类环。当n为素数，a与n互素，根据费尔马小定理有an-11 mod n，对任意整数a有ana mod n。因此在模n的剩余类环中，对每个整数a有an=a。域的定义域是一个代数系统，它由一个至少包含两个元素的集合F构成，在集合F上定义有两个二元运算：加法“+”和乘法“”，并满足下列条件。（1）F关于加法“+”是一个交换群，其单位元为“0”，称为域的零元，元素a的逆元为-a；与加法对应的逆运算（减法）定义为：a-b=a+

7、(-b)。（2）F0关于乘法“”是一个交换群，其单位元为“1”，仍称为域的单位元或么元，元素的a的逆元为a-1；与乘法对应的逆运算除法定义为：a/b=ab-1。（3）乘法在加法上满足分配律： a,b,cF，有a(b+c)=(b+c)a= ab+ac将满足上面性质的代数系统称为域F，即为 。有限域的定义如果域F只包含有限个元素，则称域F为有限域，也称为伽罗华域或Galois域。有限域中元素的个数称为有限域的阶。同构的定义设代数系统和都是域，如果一一映射h，对于任意的a,bF，有h(a+b)=h(a)h(b)h(ab)=h(a)h(b)则称一一映射h是从到的同构，称与是同构的。定理1每个有限域的阶

8、必为素数的幂，该素数称为有限域的特征。定理2对任意的素数p与正整数n，存在pn阶有限域，记为GF(pn)。当n=1时，有限域GF(p)也称为素域。 定理3同阶的有限域必同构。以上三个定理说明：pn阶有限域存在，且彼此同构，也就是说在同构意义下，含有pn个元素的有限域只有一个。密码学中常用的域为素域GF(p)（p为素数）或GF(2n)域。有限域的几个性质（1）F为q阶有限域，则aF，有aq=a。（2）有限域F中非零元组成的集合F*（即F0）关于有限域F乘法“”构成的群是一个循环群。F*称为有限域的乘法群。定义：有限域F的乘法群F*的生成元称为有限域F的本原元。说明：F*的生成元不唯一，但不是F*

9、中所有的元素都是生成元。根据循环群的生成元的定义，只有阶等于F的阶的元素才是生成元。本原元的性质设F为q阶有限域，则F中共有(q-1)个本原元。有限域的构造举例：对任意素数p可以按照如下所述构造一个p阶有限域。代数系统，Np=0,1,2,p-1。 a,bNp，定义a+pb=(a+b) mod p, apb=(ab)mod p。可以证明，如上构造的代数系统是一个有限域。设p=5，则GF(5)的加法和乘法代数运算如下：+501234001234112340223401334012440123501234000000101234202413303142404321域上多项式的定义域上x的多项式定义为

10、形如anxn+an-1xn-1+a1x+a0的多项式，其中nN，an,an-1,a1,a0F。若an0，称n为多项式的次数，并称an为首项系数。首项系数为1的多项式称为首1多项式。称0为-次多项式。其中0和1分别为域F的零元和单位元。F上的多项式anxn+an-1xn-1+a1x+a0简记为 。F上x的多项式的全体记为Fx。多项式a(x)的次数记为deg(a(x)。多项式的运算的定义设上的两个多项式 与 ，定义F上的多项式的加法”+”与乘法”如下：（1）加法”+”其中，M=max(m,n)，当in时，取ai=0；当im时，取bi=0。（2）乘法”其中，当in时，取ai=0；当im时，取bi=0

11、。多项式的带余除法定理设a(x)和b(x)为F上的多项式，且b(x)0，则存在唯一的一对元素q(x),r(x)F(x)，使：a(x)=q(x)b(x)+r(x)其中，deg(r(x)deg(b(x)，q(x)称为商式，r(x)称为余式。即r(x)=a(x) mod b(x)。例：a(x)=2x3+9x2+5，b(x)=x2+4x-3，则q(x)=2x+1，r(x)=2x+8。定义若存在q(x)和b(x)使a(x)=q(x)b(x)，且deg(q(x)1，deg(b(x)1，则a(x)为可约多项式，否则称a(x)为不可约多项式。Fx上域的构造对Fx中的每个不可约多项式p(x)，可以如下构造一个域

12、Fxp(x)。设p(x)是Fx中的n次不可约多项式，令Fxp(x)为Fx中所有次数小于n的多项式的集合，即：Fxp(x)=an-1xn-1+an-2xn-2+a1x+a0|an-1,an-2,a1,a0F任取a(x),b(x)Fxp(x)，定义Fxp(x)上的二元运算和如下：a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)域Fxp(x)中的单位元和零元分别是F中的单位元与零元。多项式域的定理是域，当且仅当p(x)是F上的不可约多项式，其中F是有限域。可以证明，对于任意素数p和正整数n，存在p阶域F上的n次不可约多项式f(x)，Fxf

13、(x)即为pn阶域。有限域元素的多项式表示由定理，对每个素数p，都可以构造一个p阶有限域。这样，可以得出如下结论：任何有限域必与某一多项式域同构，因此，可以用多项式域来表示其他有限域。有限域元素还有其他许多表示方法，而不同的表示方法可能在计算的效率有一些差别。例：16阶域GF(24)的构造16阶域GF(24)可在2阶域上构造。设集合F=0,1，F上定义运算+和如下：1+1=0,0+0=0,1+0=0+1=1；11=1,00=0,10=01=0。则以上F和运算构成的代数系统为2阶域。设p(x)为以上2阶域上的一个4次不可约多项式，则Fxp(x)中的所有16个元素为：0, 1, x, x+1, x

14、2, x2+1, x2+x, x2+x+1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1，且多项式域为16阶域。其中a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)例：16阶域GF(24)的构造下面确定p(x)。因F上的4次不可约多项式有x4+x3+x2+x+1，x4+x3+1和x4+x2+1，而同阶的有限域是同构的，故可从上述不可约多项式中任选一个作为p(x)。例如，取p(x)=x4+x3+x2+x+1。例如，任取a(x)=x2+x+1，b(x)=x3+x2

15、+x+1，求a(x)b(x)以及a(x)b(x)。根据定义：a(x)b(x)=(a(x)+b(x) mod p(x)=(x2+x+1)+(x3+x2+x+1) mod p(x) =x3 mod (x4+x3+x2+x+1)=x3a(x)b(x)=(a(x)b(x) mod p(x)=(x2+x+1)(x3+x2+x+1) mod p(x) = x5+x3+x2+1 mod (x4+x3+x2+x+1)=x3+x2因此以上构造的多项式域为16阶域。例：16阶域GF(24)的构造分析：针对多项式域，群为循环群，对除0外的所有15个元素1, x, x+1, x2, x2+1, x2+x, x2+x+

16、1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1的阶进行计算，阶为15的元素即为该群的生成元，也就是域的本原元，共有(16-1)=8个，分别是：x+1, x2+1, x2+x, x2+x+1, x3+1, x3+x, x3+x+1, x3+x2+x因此循环群可以表示成这些生成元的幂的形式。如：设生成元=x+1，则a(x)=x2+x+1=7 mod p(x)和b(x)=x3+x2+x+1=3 mod p(x)，进一步有a(x)b(x)=73 mod p(x)=10 mod p(x)=x3+x216阶域的结构同阶有限域都同构

17、，故下表包含了所有16阶域运算的全部信息。域中的元素关于乘法的阶=x+1的幂=x2+x+1的幂0111515x5126x+11513x25912x2+115211x2+x15134x2+x+1157x3563x3+115814x3+x15142x3+x+115118x3+x231010 x3+x2+1355x3+x2+x1547x3+x2+x+1539阶为15的元素即为该域乘法群的生成元，即该域的本原元，如=x+1、 =x2+x+1等都是该域的本原元，共有(16-1)=8个。表中给出了关于这两个本原元、 的运算结果，显然是同构的，因为i=7i。例，构造域GF(28)同理，可构造256阶域GF(

18、28)例如可取不可约多项式为p(x)=x8+x4+x3+x+1，则Fxp(x)中的所有256个元素为：0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1, , x7, x7+1, x7+x, x7+x+1, ,x7+x6+x5+x4+x3+x2+x+1。定义运算：a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)则多项式域为256阶域。256阶有限域GF(28)256阶有限域的特征为2，根据前面

19、的介绍，用2阶域F上的8次不可约多项式p(x)构造的多项式域Fxp(x)即为GF(28)。有限域GF(28)256阶有限域GF(28)以下说明256阶数域的元素255,254,0与256阶多项式域Fxp(x)的元素如何对应。首先将数域的元素表示成二进制形式为：11111111,b7b6b5b4b3b2b1b0,00000000。有限域GF(28)可将256阶数域的元素b7b6b5b4b3b2b1b0与256阶多项式域Fxp(x)的元素对应关系如下：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0这样任意8位二进制数就和一个多项式建立了一一对应的关系。例：十六进制数57，

20、二进制为：01010111，对应的多项式为：x6+x4+x2+x+1GF(28)中元素的多项式表示AES算法对字节进行运算，把一个字节（8bit: b7b6b5b4b3b2b1b0 ）对应成多项式域Fxp(x)上的一个元素。这样， AES中对字节的运算可以转换为256阶域GF(28)上的多项式的运算。下面介绍多项式的运算特点。GF(28)中元素的多项式表示GF(28)上的加法说明：根据域运算的封闭性，域GF(28)中任意两个元素的和仍在域中，运算结果的系数等于两个元素对应多项式的系数的异或。例：57+83=？57: 01010111，83:10000011(x6+x4+x2+x+1)+(x7+

21、x+1)=x7+x6+x4+x2即：11010100（D4）， 57+83=D4GF(28)上的乘法说明：根据域运算的封闭性，多项式域GF(28)中任意两个元素的乘积仍在域中，乘积采用模乘，结果也是一个次数不超过7的多项式。多项式域GF(28) 上的模常使用的一个不可约多项式为m(x)=x8+x4+x3+x+1，它的二进制表示为：100011011，十六进制表示为“11B”GF(28)上的乘法例： 5783=C1(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=(x13+x11+x9+x8+x6+x5+x4+x

22、3+1)x7+x6+1 mod (x8+x4+x3+x+1) （多项式的分解）对应二进制11000001GF(28)上的x乘法GF(28)上还定义了一个运算，称为x乘法，定义为：xb(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x) mod m(x)如果b7=0，求模结果不变，若b7=1，则结果加上m(x)。由此得出x乘法的高效运算方法：因多项式x对应于元素00000010，则要求xb(x)，可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与“1B”（其二进制为00011011）进行逐位异或来实现。因此：x乘法实现的效率非常高。该运算记

23、为xtime(b) x乘法实现的效率非常高，可利用x乘法来加快GF(28)中任意两个元素的乘法运算。例如：5713的实现：13=01+02+10（将13分解）5702=xtime(57)=AE （01010111,左移1位, 010101110,b7=0,结果不变为010101110,即AE）5704=570202=xtime(AE)=47AE: 10101110,左移1位, 101011100,b7=1,与1B异或得1000111，即475708=570402=xtime(47)=8E5710=570802=xtime(8E)=075713=57(01+02+10)=57+AE+07=FE字

24、运算字运算也是定义在域上的运算。AES中的一个字由4个字节构成，每个字节看成是GF(28)中的一个元素。4个字节构成的字可以表示成一个次数小于4的多项式，其系数取自GF(28)。例如，对于字： 57 83 4A D1对应的多项式为：57x3+83x2+4Ax+D157、83、4A、D1分别对应GF(28)中的一个多项式。字的加法两个字相加：对应的多项式的系数相加，对应系数简单按位异或。例如：57 83 4A D1+26 ED 41 22对应的系数相加就是GF(28)中多项式的相加：57+26：83+ED：4A+41：D1+22：字的乘法多项式的乘法：设a(x)=a3x3+a2x2+a1x+a0

25、，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)b(x)，又设c(x)= c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0，则有c0=a0b0，c1=a1b0a0b1，c2=a2b0a1b1a0b2c3=a3b0a1b2a2b1a0b3，c4=a3b1a2b2a1b3c5=a3b2a2b3，c6=a3b3上式中c(x)不是次数小于4次的多项式，不能表示成4字节，通过模一个4次多项式M(x)进行化简，使得结果变为次数小于4次的多项式。字（多项式）的乘法取4次多项式M(x)=x4+1，设(a3x3+a2x2+a1x+a0)(b3x3+b2x2+b1x+b0) mod

26、x4+1= d3x3+d2x2+d1x+d0=d(x) 可证： 表示成矩阵形式为：（利用性质xj mod (x4+1)=xj mod 4）d0=a0b0+a3b1+a2b2+a1b3d1=a1b0+a0b1+a3b2+a2b3d2=a2b0+a1b1+a0b2+a3b3d3=a3b0+a2b1+a1b2+a0b3以上运算中aibj即是GF(28)上多项式乘法。字（多项式）的乘法说明：因为M(x)=x4+1=(x+1)(x3+x2+x+1)，故M(x)不是不可约多项式。这样，字的乘法运算中，与一个多项式的模x4+1乘法将不一定可逆（因与M(x)不一定互素）。AES中，特意选择一个具有逆元的固定多

27、项式a(x)=03x3+01x2+01x+02进行模x4+1乘法，从而保证了模x4+1乘法的可逆，使得解密的逆运算可行。a(x)模x4+1的乘法逆为a-1(x)=0bx3+0dx2+09x+0e，即a(x)a-1(x)= 1 mod x4+1高级数据加密标准Advanced Encryption Standard: AES历史1997年1月2日，美国国家标准与技术研究所（NIST）开始征集DES的替代工作，称为高级加密标准，即AES。要求：安全性可达100年，在三重DES之上。 1997年9月12日，NIST发布正式的征集公告，要求AES具有128位分组长度，并支持128位、192位、256位

28、密钥长度。 1998年6月15日，收到提交的21个算法 1998年8月20日，第一次AES候选大会，宣布其中15个候选算法 1999年3月，第二次AES候选大会 1999年8月，5个候选算法进入决赛：MARS,RC6,Rijndael,Serpert和Twofish历史 2000年4月，第三次AES候选大会 2000年10月2日，Rijndael被选择为高级加密标准。 2001年2月28日，NIST宣布AES的草案供公众讨论 2001年11月26日，AES被采纳成为标准 2001年12月4日，联办纪事中作为FIPS197公布。15个候选算法作者的国家：澳大利亚、比利时、加拿大、哥斯达黎加、法国

29、、德国、以色列、日本、韩国、挪威、英国及美国。Rijndael算法是由两位比利时的研究者J. Daemen 和V. Ri jmen提出。AES的总体描述分组长度为128位，三种可选的密钥长度：128位、192位和256位。加密轮数Nr与密钥长度有关。AES中的操作都是以字节为基础，所有变量都由适当数量的字节组成。中间变量state用44字节矩阵表示：128位的输入：16个字节 x0,.,x15标准密钥长度加解密轮数AES-12812810AES-19219212AES-25625614x0 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15SS00SS01SS02SS0

30、3SS10SS11SS12SS13SS20SS21SS22SS23SS30SS31SS32SS33AES的总体描述AES的总体结构AES的总体描述AES的加密、解密流程AES的总体描述加密算法的执行过程描述如下：（1）给定一个明文M，将M赋值状态矩阵State，即将State初始化为M，并将轮密钥Roundkey与State异或，称为：AddRoundkey(State,Roundkey)（2）在加密算法的前Nr-1轮中，每一轮加密操作如下：用S-盒进行替换操作：SubBytes(State) ；对替换的结果State做行移位操作：ShiftRows(State)；再对State 做列混合变换

31、：MixColumns(State)；最后进行密钥异或运算：AddRoundkey(State,Roundkey) 。AES的总体描述（3）在最后一轮中，对前Nr-1轮的结果State再依次进行SubBytes(State)ShiftRows(State)AddRoundkey(State,Roundkey)操作。（4）将输出的State定义为密文C。AES的总体描述AES的总体执行过程算法的基本变换字节替换变换（SubBytes(State)）例如： 设State中的一个字节为53，SubBytes(53)=？使用一个S-盒对每个字节进行替换。下面介绍S-盒的构造方法。算法的基本变换字节替换

32、变换（SubBytes(State)）S-盒按如下方法构造：（1）一个字节表示成十六进制的xy，x,y分别为行和列输入（2）求该字节在GF(28)中的乘法逆（模m(x)=x8+x4+x3+x+1），设乘法逆为（ b7b6b5b4b3b2b1b0） （3）然后进行如下计算，求得（ b7b6b5b4b3b2b1b0） ，即为结果。算法的基本变换字节替换变换（SubBytes(State)）例：十六进制的53，二进制为01010011，GF(28)中的元素为x6+x4+x+1在GF(28)中的乘法逆(模m(x)=x8+x4+x3+x+1下的乘法逆)元素为x7+x6+x3+x（即对应11001010）

33、因此，在二进制下，有b7b6b5b4b3b2b1b0=11001010下面计算b0=b0+b4+b5+b6+b7+1 mod 2 =0+0+0+1+1+1 mod 2=1同理可得： b7b6b5b4b3b2b1b0=11101101，十六进制为ED，故S-盒中的5行3列的元素为ED ，即SubBytes(53)=ED算法的基本变换字节替换变换（SubBytes(State)）按以上方法计算出所有元素的结果，形成S-盒如下表：算法的基本变换字节替换变换（SubBytes(State)）与DES的S-盒相比，AES的S-盒能进行代数上的定义，而不像DES的S-盒看起来像是“随机”的代换。算法的基本

34、变换行移位变换（ShiftRows(State) ）State的第一行保持不动，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移三个字节SS00SS01SS02SS03SS11SS12SS13SS10SS22SS23SS20SS21SS33SS30SS31SS32SS00SS01SS02SS03SS10SS11SS12SS13SS20SS21SS22SS23SS30SS31SS32SS33不移动左移一个字节左移两个字节左移三个字节算法的基本变换列混合变换（MixColumns(State)）对State中每列进行独立操作，把每列看成一个3次多项式s(x)，再与固定多项式a(x)=

35、03x3+01x2+01x+02进行模x4+1的乘法运算。3次多项式系数的运算即是有限GF(28)中多项式的运算。如对第c列（0c3），其对应的3次多项式为sc(x)=s0,c+s1,cx+s2,cx2 +s3,cx3，则列混合变换后的值为sc(x)=sc(x)a(x)。矩阵表示如下：轮密钥生成算法Roundkey的产生： 对于需要进行N轮加密的AES算法，共需要N+1个子密钥。 轮密钥生成算法以字为基础，每个字包含32位（4个字节）。 下面以128位的种子密钥为例，说明产生11个轮密钥的方法。 首先将128位的种子密钥分成16个字节，分别为key0, key1, key2, . , key1

36、5，每个keyi（0i15）8位，共128位。每一轮的轮密钥由4个字（128位）组成，11个轮密钥共包含44个字，表示为w0,w43.具体算法步骤如下：轮密钥生成算法一、初始化10个字RCon（ 32位，4个字节）：RCon1=01000000 RCon9=1B000000RCon2=02000000 RCon10=36000000RCon3=04000000RCon4=08000000RCon5=10000000RCon6=20000000RCon7=40000000RCon8=80000000轮密钥生成算法二、当0i3时，wi=(key4i, key4i+1, key4i+2, key4i

37、+3)三、当4i43且i0 mod 4时，wi=wi-4wi-1四、当4i43且i=0 mod 4时wi=wi-4(SubWord(RotWord(wi-1) RConi/4)其中，RotWord(B0,B1,B2,B3)对四个字节(B0,B1,B2,B3)进行循环移位操作：RotWord(B0,B1,B2,B3)=(B1,B2,B3,B0)SubWord进行置换操作：SubWord(B0,B1,B2,B3)=(B0,B1,B2,B3)其中，Bi=SubBytes(Bi)，i=0,1,2,3解密算法AES的解密与加密算法相似但不对称，伪代码描述如下：AESDecipher(byte in16,

38、 byte out16,word w4*(Nr+1) byte state4,4; state=in;AddRoundKey(state, w4*Nr, 4*Nr+3);/前Nr-1轮解密 for(int round=Nr-1; round0;round-) InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w4*Nr, 4*Nr+3); InvMixColumns(state);/最后一轮解密 InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w0,3)

39、; 解密算法AES的解密使用了四种逆变换： InvSubBytes() InvShiftRows() InvMixColumns() AddRoundKey()（ AddRoundKey() 的逆变换是它自身）以相反的顺序对由密文映射得到的state进行变换完成。另外，AES的解密过程使用的子密钥相同，但使用的顺序相反。解密算法1.InvSubBytes变换InvSubBytes变换是字节替换SubBytes逆变换，即先用到仿射变换的逆变换，再计算GF(28)中的乘法逆。逆S-盒对状态矩阵中的每一个字节进行逆变换。通过如下逆S-盒实现：解密算法1.InvSubBytes变换也就是根据 b7b6

40、b5b4b3b2b1b0反过来求得 b7b6b5b4b3b2b1b0 ，再求b7b6b5b4b3b2b1b0在GF(28)中的乘法逆，乘法逆即为逆S-盒的结果。解密算法2.InvShiftRows变换InvShiftRows变换是行移位变换ShiftRows的逆变换，对状态矩阵的各行按照相反的方向进行循环移位操作。第一行保持不变；第二行循环右移一个字节；第三行循环右移二个字节；第四行循环右移三个字节；解密算法3.InvMixColumns变换InvMixColumns变换是列混合变换MixColumns的逆变换，对状态矩阵的各列进行处理，把每一列当作系数在GF(28)有限域上的四项多项式。与M

41、ixColumns对应， InvMixColumns变换把列多项式与多项式a(x)相对于模多项式x4+1的逆a-1(x)相乘a-1(x)=0bx3+0dx2+09x+0e设列多项式为sc(x)=s0,c+s1,cx+s2,cx2 +s3,cx3，0c3， InvMixColumns变换写成矩阵形式如下：AES的分析（1）在AES算法中，轮密钥生成算法的非线性性质消除了产生相同轮密钥的可能性。加/解密过程中使用不同的变换可以避免出现弱密钥、半弱密钥、半半弱密钥等。（2）经过验证，AES能够抵抗所有针对DES的攻击方法的攻击，如部分差分攻击、相关密钥攻击等。（3）到目前为止，最有效的攻击方法是穷举

42、搜索攻击，因此AES是安全的。AES的主要特点 不属于Feistel结构 加密、解密相似但不对称 支持128数据块大小 支持128/192/256密钥长度 有较好的数学理论作为基础 结构简单、速度快AES的设计原则简单性简单性便于分析理解是如何抵抗所有类型的攻击。对称性（1）各轮之间的对称性各轮之间具有对称性，好处是在密钥的控制下对同一轮交换进行循环迭代，优点是只要描述一轮变换即可将整个规范描述清楚，另外，在软件实现中可仅对一轮进行编辑。AES的设计原则对称性（2）轮变换内部的对称性（3）D-盒的对称性（4）S-盒的对称性（5）加密和解密过程的对称性AES的设计原则对抗攻击方面（1）选择差分均

43、匀性比较小和非线性度比较高的S-盒（2）适当选择线性变换，使得固定轮数中的活动S-盒的个数尽可能多。优点是可以估计算法的最大差分特征概率和最大线性逼近概率，这样可以评估抵抗差分密码分析和线性密码分析的能力。AES的硬件实现在硬件实现方面，算法依靠有限域GF(28)的有关定义给加密和解密提供了良好的理论基础，并且算法的结构紧凑、规整，加密和解密过程相似，非常适合硬件实现，但有不利因素：（1）在轮变换过程中，变换函数的作用顺序不同，解密过程与加密过程无法完全实现资源共享（2）算法的列变换过程和逆列变换过程中变换系数较大，矩阵乘法运算耗时较多，影响加解密的速度（3）在每一轮变换的过程中，4个函数先后

44、执行，增大了时延，因此应对其优化，使变换可以并行执行，以减小时延，同时增加吞吐量。分组密码的工作模式概述分组密码以固定的分组长度作为基本的处理单元，要加密的消息长度通常比分组长度长很多。为了将算法应用于实际，定义了几种工作模式：NIST（美国国家标准技术研究所）定义了7种，其中5种比较常用。在之后的介绍中设分组的长度为b，分组的个数为n。电子本模式（ECB）电子密码本ECB模式（Electronic Codebook Mode）是最简单的模式。对每个分组Pi使用相同的密钥加密。Ci=Ek(Pi)，Mi=Dk(Ci) ，i=1,2,n加密前将整个明文分成长为b的分组，必要的话对最后一个进行填充。

45、因k唯一，对每个分组只有唯一的密文。电子本模式（ECB）电子本模式（ECB）优点：简单、易行加密后的输出直接作为密文，不进行任何形式的反馈，每个分组的处理相互独立，是分组密码的标准工作模式。电子本模式（ECB）缺点：（1）不能隐藏明文的模式信息在处理具有固定数据结构的明文时，容易暴露明文数据的固有格式。例如，某些报文具有标准化的形式，如作业号、通信地址、发表时间、密级等数据，这些数据除了有固定的位置，明文数据也非常有规律。这些信息在加密后将出现在同一位置，为破译带来线索。电子本模式（ECB）缺点：（2）对明文的主动攻击是可能的：因分组相互独立，信息块可被替换、重排、删除、重放。（3）无法纠正传

46、输中的同步错误如果密文在传输中增加或丢失一个bit，将引起密文分组的对齐错误，整个密文序列将不能正确解密。密码分组链接模式（CBC）Cipher Block Chaining Mode加密算法的输入是当前明文分组Mi和上一次产生的密文分组Ci的异或，即：C0=IVCi=Ek(MiCi-1)，1in解密：C0=IVMi=Dk(Ci)Ci-1，1inIV（初始化向量）在加解密中都用到，通信双方必须都知道，一般无需保密，随消息进行更换。CBC加解密示意图：密码分组链接模式（CBC）特点：（1）能够隐藏明文的数据模式，相同的明文可对应不同的密文。（2）在一定程度上抵抗主动攻击：信息块不容易被替换、重排

47、、删除、重放（3）误差有限传递：密文中一个位的错误只影响当前分组和下一个分组的解密。密码反馈模式（CFB）Cipher Feedback Mode模式中，引入一个整数参数s，1sb，明文按s进行分组，且明文的长度必须是s的整数倍。CFB的加解密过程密码反馈模式（CFB）令函数LSBi()表示输入的前i个最低有效位，MSBi()表示输入的前i个最高有效位。例如，LSB3(111011011)=011， MSB4(111011011)=1110。加解密规则如下：密码反馈模式（CFB）特点：CFB模式由于有密文反馈，若密文分组中有一位或多位出错，将引起当前分组和后续部分分组的解密错误。只有当错误的密文比特从寄存器中移出后，解密才会恢复正常。故一个密文分组的错误，影响后面最多 个分组的解密。 表示大于等于x的最小正整数。输出反馈模式（OFB）Output Feedback Mode通过反复加密一个初始向量IV来得到密钥流，这种机制独立于明文和密文。定义Z0=IV，然后计算：Zi=Ek(Zi-1)，1in加密： Ci=MiZi解密： Mi=CiZiOFB的加解密过程输出反馈模式（OF