94应用密码学第5讲

1应用密码学第五讲AES算法2复习►DES算法分组长度密钥长度f函数S盒轮变换密钥调度3本节内容►AES（高级数据加密标准）算法描述密码分析►RC6算法（自学）RC5算法描述RC6算法描述4AES算法1997年9月12日，为了替代即将退役的DES，美国国家标准与技术研究所（NIST）在《联邦纪事》上发表了征集AES算法的公告。1999年3月22日，公布了5个候选算法：MARS,RC6,Rijndael,SERPENT,Twofish。2000年10月2日，由比利时密码学家JoanDaemen和VincentRijmen提交的Rijndael算法被确定为AES。以下称Rijndael算法为AES算法。2001年11月26日被采纳为一个标准。5AES算法描述►Rijndael分组加密算法的前身是Square分组加密算法，轮变换结构与其基本相同。为了应征AES候选算法，对Square分组加密算法进行了改进。由原来的密钥和分组长均为128比特改为分组和密钥长均可变，可以满足不同的加密需求。►具体参数如下：►①分组长度、密钥长度和加密层数均可变。►②分组长度和密钥长度支持128、192、256比特。►③分组和密钥长度可以独立改变，并由此决定加密层数。6为了后面论述方便，进行如下定义：►(一)设计准则Rijndael加密算法按照如下原则进行设计：⒈抗所有已知的攻击⒉在多个平台上速度要快和编码紧凑⒊设计简单►(二)状态、密钥与轮数定义：状态（State）：中间密码结果称为状态Nb=明文分组的4-字节字数（32比特）Nk=密钥的4-字节字数（32比特）Nr=加密的轮数7►明文分组（密钥）长度为128比特时，Nb=Nk=4►明文分组（密钥）长度为196比特时，Nb=Nk=6►明文分组（密钥）长度为256比特时，Nb=Nk=8►现以Nb=6和Nk＝4为例进行图示说明。a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35Nb=6时状态放置示意图k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33Nk＝4时密钥放置示意图8分组长度、密钥长度都可以在128bit、192比特和256比特间变化，但是不同的组合需要不同的加密轮数。分组长度与轮数的关系：NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414149AES的总体描述：①给定一个明文x，将State初始化为x，并进行AddRoundKey操作，将RoundKey与State异或。②对前Nr-1轮中的每一轮，用S盒进行一次代换操作，称为SubBytes；对State作一个置换ShiftRows，再对State作一次操作MixColumns，然后进行RoundKey操作。③依次进行SubBytes，ShiftRows和AddRoundKey操作。④将State定义为密文。10加密开始时，首先将State定义为明文字节x00，x01,…S00S01S02S03S10S11S12S13S20S21S22S23S30S31S32S33x00x01x02x03x10x11x12x13x20x1x22x23x30x31x32x33AESSubBytes操作所使用的S盒是{0，1}8上的一个置换，见下表。每一个字节都用两个16进制的数字表示。s110123456789abcdef0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973060814fdc222a908846eeb814de5e0bdbAe0323a0a4906245cc2d3ac629195e479Be7c8376d8dd54ea96c56f4ea657aae08cBa78252e1ca6b4c6e8dd741f4bbd8b8ad703eb5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fb054bb1612SuBytes算法ExternalFieldInv,BinaryToField,FieldToBinaryzBinaryToField(a7a6a5a4a3a2a1a0)ifz0thenzFieldInv(z)(a7a6a5a4a3a2a1a0)FieldToBinary(z)(c7c6c5c4c3c2c1c0)(01100011)//在下面的循环中，所有下标都要经过模8约简fori0to7dobi(ai+ai+4+ai+5+ai+6+ai+7+ci)mod2return(b7b6b5b4b3b2b1b0)13►FieldInv：表示求一个域元素的乘法逆►BinaryToField：把一个字节变成一个域元素►FieldToBinary：把一个域元素变成一个字节例题：设算法的输入是16进制的53，在二进制下是01010011表示为域元素为：x6+x4+x+1它的乘法逆元（在有限域F28中）：x7+x6+x3+x在二进制下，我们有：(a7a6a5a4a3a2a1a0)（11001010）14下面我们计算b0=a0+a4+a5+a6+a7+c0mod2=0+0+0+1+1+1mod2=1b1=a1+a5+a6+a7+a0+c1mod2=1+0+1+1+0+1mod2=0….结果是：（b7b6b5b4b3b2b1b0）=(11101101)以16进制表示就是ED。上面的结果可以通过查S盒代换表来验证。行号5，列号3，对应ED。15行变换改图的右移字节数是以Nb=4为例。更一般的情况见下页。16第0行保持不变，第1～3行分别右循环移动移动C1～C3字节。其中C1～C3的大小与Nb大小有关。NbC1C2C341236123813417列混合通过线性变换将列变换到列。算法描述（MixColumn(State)）。作上的多项式运算，即作(modx4+1)相当于作和上的线性变换。可用上矩阵运算描述为)2(8GF)()()(xaxcxb)()()(xaxcxb)2(8GF)2(GF3210321002010103030201010103020101010302aaaabbbb18►Mixcolumn(c)►ExternalFieldMult,BinaryToField,FieldToBinary►fori0to3►dotiBinaryToField(Si,c)►u0FieldMult(x,t0)FieldMult(x+1,t1)t2t3►u1FieldMult(x,t1)FieldMult(x+1,t2)t3t0►u2FieldMult(x,t2)FieldMult(x+1,t3)t0t1►u3FieldMult(x,t3)FieldMult(x+1,t0)t1t2►fori0to3►doSi,cFieldToBinary(ui)//FieldMult表示域元素求积。19密钥编排①密钥比特的总数等于分组长度乘轮数加1.②将密码密钥扩展成一个扩展密钥。③轮密钥是按下述方式从扩展密钥中取出的：第一个轮密钥由第一个Nb字组成，第二个轮密钥由接下来的Nb组成，由此继续下去。下面讨论密钥扩展算法。20密钥扩展算法设将扩展密钥以4-字节字为单位放到数组W[Nb*(Nr+1)]中，则第一Nk字包括密码密钥。其他所有字则由较小脚标的字递归生成。密钥扩展与Nk的取值有关；分为Nk≥6和Nk≤6两个版本当Nk=Nb=4时，Nr=10，我们需要11个轮密钥，每个轮密钥由16个字节4个字组成，共需44个字。21Nk≤6时的密钥扩展算法KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;iNk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;iNb*(Nr+1);i++){temp=W[i-1];if(imodNk==0)temp=SubByte(RotByte(temp))XorRcon[i/Nk];W[i]=W[i-Nk]Xortemp;}//SubByte表示将SubByte作用于其输入的每个字节。//RotByte表示将一个4-字节字左移循环一个字节。22►Nk6的密钥扩展算法KeyExpansion(byteKey[4*Nk]wordW[Nb*(Nr+1)]{for(i=0;iNk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;iNb*(Nr+1);i++){temp=W[i-1];if(imodNk==0)temp=SubByte(RotByte(temp))XorRcon[i/Nk];►else►if(imodNk==4)temp=SubByte[temp];►W[i]=W[i-Nk]Xortemp;►}23轮常数各轮使用独立的轮常数消除轮变换和轮之间的对称性。Rcon[1]=01000000,Rcon[2]=02000000,Rcon[3]=04000000,Rcon[4]=08000000,Rcon[5]=10000000,Rcon[6]=20000000,Rcon[7]=40000000,Rcon[8]=80000000,Rcon[9]=1B000000,Rcon[10]=36000000,24AES解密算法为了解密只需要将所有的操作逆序进行，并逆序使用密钥编排即可。其中ShiftRow、SubBytes、MixCollumns均用它的逆操作代替。