第5讲 分组密码体制(续2)PPT课件

2020/5/22,.,1,应用密码学,张仕斌万武南张金全孙宣东编著,西安电子科技大学出版社,二00九年十二月,2020/5/22,.,2,第3章分组密码体制,2020/5/22,.,3,知识点：,分组密码的基本概念对称密码基本原理数据标准加密（DES）高级加密标准(AES)对称密码体制工作模式对称密码应用,2020/5/22,.,4,3.4.4基本变换,AES算法每次明文分组以及每次变换的中间结果分组称为状态（State）。状态用以字节（8比特位）为基本构成元素的矩阵阵列来表示，该阵列有4行，即每列为32比特，因而列数为分组长度除以32，通常记为Nb。列数：Nb=分组长度（比特）32Rijndael算法列数Nb可以取的值为4,6,8,对应的分组长度为128,192,256比特。而AES算法的分组长度固定为128比特，以字节为基本单位转换为状态字节，依顺序a00,a10,a20,a30,a01,a23,a33，前4个字节组成第1列，后四个字节组成第2列，依次类推，AES算法明文分组可以构成一个44的字节矩阵，如下页图所示，加密结束时，输出也是从状态字节中按相同的顺序提取。,2020/5/22,.,5,阵列状态图：,AES算法加密和解密过程中密码密钥（CipherKey）同样以字节为基本单位转换，因而依顺序k00,k10,k20,k30,k01,k23,k33,，为类似地用一个4行的矩阵阵列来表示，前4个字节组成第1列，后四个字节组成第2列，依次类推，列数记为Nk。Nk=密钥长度（比特）32,2020/5/22,.,6,Rijndael算法和AES算法的密码密钥的列数Nk可以取的值为4、6、8,对应的密钥长度为128、192、256bits，因而密码密钥构成一个44、46、48的密钥字节矩阵。如下图所示，192比特密钥的密码密钥矩阵，Nk为6。,密码密钥阵列状态,2020/5/22,.,7,下面我们以一个128位块为例，介绍AES加密算法基本变换的具体过程。若示例块是由0和1组成的，输入的128位块为10000000010111100110101000110110010100110010010100111010011001100110001100110101011010010000001100100000011011000010100000000110为了表达简洁，下面的AES算法基本变换的中间结果都用16进制来表示。则128比特二进制示例块用16进制表示则对应为805E6A3653253A6663356903206C2806(如下表所示)。,2020/5/22,.,8,在进行AES加密算法过程中，首先把输入明文128比特示例块805E6A3653253A6663356903206C2806按照AES算法规则构成一个构成一个44的字节矩阵，如下图所示。,阵列状态,1字节代替（SubBytes）,Rijndael算法的字节变换（SubBytes）使用一个S盒（不像DES算法使用8个S盒）进行非线性置换。如下页表所示，它将输入或中间态的每一个字节通过一个简单的查表操作，映射为另外一个字节。,2020/5/22,.,9,映射方法：输入字节前4位指定S盒的行值，后4位指定S盒的列值。有行和列所确定S盒位置的元素作为输出（如下页图所示）。例如输入字节“03”，行值为0，列值为3；根据上表可以查得第0行第3列对应的值为“7B”，输出字节为“7B”。,2020/5/22,.,10,Rijndael算法字节代替操作,例如，输入矩阵（用16进制表示）进入S盒替换操作，则相应的输出如下所示：,2020/5/22,.,11,其实S盒是一个复杂的代数结构，S盒的设计是有一定限制条件的，其中的一些限制条件是：它应当是可逆的，不能存在这种情况：行i列j位置上的值为ij。实际Rijndael的S盒字节替代操作它包括两个代数变换：,2020/5/22,.,12,上面仿射变换用矩阵可以表示如下：,下面以输入“F5”为示例来说明S盒替代操作它包括两个变换，不通过查S盒表，而通过代数计算求解。首先求解“F5”由f(x)=x8+x4+x3+x+1构造GF(28)有限域上的乘法逆元，然后进行上式的变换。,2020/5/22,.,13,1）其输入十六进制“F5”对应二进制为“11110101”，多项式为(x7+x6+x5+x4+x2+1)，求其模f(x)=x8+x4+x3+x+1的逆，即求b(x)：(x7+x6+x5+x4+x2+1)b(x)1(modf(x)通过多项式欧几里得扩展算法，求解得：(x7+x6+x5+x4+x2+1)(x6+x2+x)1mod(x8+x4+x3+x+1)即：(x7+x6+x5+x4+x2+1)模(x8+x4+x3+x+1)的乘法逆元为x6+x2+x，即F5的乘法逆元为46。,2）十六进制46其二进制为01000110，进行第2步的仿射变换，代入矩阵运算运行：即二进制结果为11100110，对应十六进制结果为“E6”，与查表S盒替代操作结果一样。,2020/5/22,.,14,2行移位（ShiftRows）,在Rijndael算法中，行移位操作作用于S盒的输出。其中，状态阵列的4个行循环以字节为基本单位进行左移，而每1行循环做移的偏移量是由明文分组的大小和所在行数共同确定，即列数Nb和行号确定。设状态阵列的每行用Ci来表示，那么每行偏移量如下表所示：,AES算法中Nb为4，即第1行循环左移0字节，第二行循环左移1字节，第三行循环左移2字节，第四行循环左移3字节，如下页图。从该图中可以看出，这使得列完全进行了重排。,2020/5/22,.,15,行移位操作,例如，输入矩阵（用16进制表示）进入行移位操作，则相应的输出如下所示：,2020/5/22,.,16,3列混合（MixColumns）,列混合操作可以将输入的状态矩阵的每列看作是有限域GF(28)上的多项式a(x)，与多项式s(x)=03x3+01x2+01x+02相乘然后模x4+1，其中多项式的系数为有限域GF(28)的运算。其方法为令c(x)=s(x)b(x)mod（x41），因而列混合是可以表示为矩阵相乘来实现，进行移位后的矩阵与固定矩阵（十六进制表示）相乘，如下所示：,2020/5/22,.,17,列混合操作如下图所示：,例如，输入矩阵（用16进制表示）进入列混合操作，则相应的输出如下所示：,2020/5/22,.,18,例如：第1行02，03，01，01与第1列E6,1B，50，18相乘，其中符号“*”和“”分别为有限域GF(28)的乘法和加法运算，具体操作如下：,可以看到通过列混合操作第1列包含字节为B2、38、75、4A，经过这些操作明文经过几轮迭代后高度打乱了，同时还保证输入和输出之间关联很少了。,2020/5/22,.,19,4轮密钥加（AddRoundKey）,最后一阶段是将列混合的状态矩阵与子密钥进行XOR逻辑运算（子密钥是从初始密钥派生而来的），即将轮密钥与状态按比特异或。轮密钥是通过密钥调度过程从密码密钥中得到的，轮密钥长度等于分组长度。如下图，这完成了算法的一次迭代。,2020/5/22,.,20,例如，输入状态矩阵和子密钥矩阵（用16进制表示）进入轮密钥加操作，则相应的输出如下所示：,2020/5/22,.,21,-AES加密过程的流程图(如右)：,.,22,加密算法的描述及实现,Rijndael解密算法用伪C语言表示如下：Rijndael-Chiper(bytein4*Nb,byteout4*Nb,wordwNb*Nr+1)Beginbytestate4,Nbstate=inAddRoundKey(State,w0,Nb-1)forround=1step1toNr-1SubBytes(state)ShiftRows(state)MixColumn(state)AddRoundKey(State,wround*Nb,(round+1)*Nb-1)EndforSubBytes(state)ShiftRows(state)AddRoundKey(State,wNr*Nb,(round+1)*Nb-1)Out=stateend,加密的具体过程：首先将明文分组复制到矩阵中，经过初始轮密钥加后，在执行Nr-1次轮变换来转变状态矩阵，最后一轮与前Nr-1轮不同之处在于这一轮没有列混合变换；最后将状态矩阵中的各个字节按顺序输出就得到密文分组。,2020/5/22,.,23,3.4.5密钥扩展,Rijndael算法的密钥按照矩阵的列进行分组，密钥比特的总数等于明文分组长度乘以轮数加1，即密钥bit的总数分组长度（轮数Round1）。例如当明文分组长度为128bits和轮数Round为10时，轮密钥长度为128(101)1408bits，则需要添加40个新列来进行扩充；当明文分组为128bits和轮数Round为12时，轮密钥长度为128(121)1664bits，则需要添加46个新列来进行扩充。Rijndael算法由于密码密钥Nk列数的不同，其密钥扩展算法有所不同。,2020/5/22,.,24,下面以密钥长度128比特为例，Nk=4,其密钥扩展示意图如下图。,首先初始密钥按照矩阵列进行分组，前4列初始密钥计为K0,K1,K2,K3，那么新的列如下递归：（1）如果Ki中，i不是4的倍数，那么i列由如下等式确定：Ki=Ki-4XORKi-1,NK=4的密钥扩展示意图,2020/5/22,.,25,其中TKi-1是Ki-1的一种转换形式，按以下方式实现：循环地将Ki-1的元素左移位，每次一个字节，如abcd变成bcda将这4个字节作为S盒的输入，输出新的4个字节efgh计算一轮的常量r(i)=Rcon(j/NK)这样生成转换后的列：eXORr(i),f,g,h,第i轮的轮密钥组成了列K4i,K4i+1,K4i+2,K4i+3.,(2)如果Ki中，i是4的倍数，那么i列由如下等式确定：Ki=Ki-4XORTKi-1,实例：设初始种子密钥为K0=75356B99，K1=05613956,K2=73620531,K3=00550932,下一个子密钥段为K4,由于i是4的倍数，所以K4计算如下：K4=K0XORTK3,2020/5/22,.,26,TK3的计算要涉及Rcon数组，下面解释下Rcon数组的计算。,密钥扩展中：Rconi=(RCi,00,00，00)RC1=1（即01）RCi=2*RCi-1=(02)(i-1)；i=2,3,.也即RCi=x(i-1)modp(x)；i=2,3,.其中p(x)=x8+x4+x3+x+1,-Rconi的计算：,.,27,RC1=01(00000001)Rcon1=(01,00,00,00)RC2=02(00000010)Rcon2=(02,00,00,00)RC3=04(00000100)Rcon3=(04,00,00,00)RC4=08(00001000)Rcon4=(08,00,00,00)RC5=10(00010000)Rcon5=(10,00,00,00)RC6=20(00100000)Rcon6=(20,00,00,00)RC7=40(01000000)Rcon7=(40,00,00,00)RC8=80(01000000)Rcon8=(80,00,00,00)RC9=1b(00011011)Rcon9=(1b,00,00,00)RC10=36(00110110)Rcon10=(36,00,00,00),RCi,2020/5/22,.,28,实例：设初始种子密钥为K0=75356B99，K1=05613956,K2=73620531,K3=00550932,下一个子密钥段为K4,由于i是4的倍数，所以K4计算如下：K4=K0XORTK3,2020/5/22,.,29,TK3的计算步骤如下：（1）循环将K3按照字节为单位左移1字节，00550932变成了55093200（2）将55093200作为S盒的输入，查表得到输出fc012363（3）计算常量Rcon(i)=(RCi,00,00,00)异或，RCi/NK=RC4/4RC1=0 x01(十六进制)（4）将01000000与fc012363异或运算得fd012363因此，TK3=fd012363K4=75356B99XORfd012363=883448fa接着三列密钥计算如下：K5=Ki-4XORKi-1=K1XORK4=05613956XOR883448fa=8d5571ac；K6=Ki-4XORKi-1=K2XORK5=73620531XOR8d5571ac=fe37749d；K7=Ki-4XORKi-1=K3XORK6=00550932XORfe37749d=fe627daf；,2020/5/22,.,30,因此下一轮得密钥为：883448fa8d5571acfe37749dfe627daf按照上述算法依次扩展，128位密钥由种子密钥扩展K4,K5,K43为止。密钥扩展完成之后，进行轮密钥选取。密钥选取非常简单，从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个字（其实就是Nb列），第二个轮密钥由接下来的Nb个字组成，以此类推。其结构如下图所示：,轮密钥选择,.,31,Wi-4,Wi-3,Wi-2,Wi-1,Wi,ByteSubstituion,ByteRotate,+,Rcons,+,密钥扩展（128）,4=i4(Rnd+1),imod4=0,imod4!=0,.,32,Wi-6,Wi-5,Wi-4,Wi-3,Wi-2,ByteSubstituion,ByteRotate,+,Rcons,+,密钥扩展（192）,6=i6(Rnd+1),imod6=0,imod6!=0,Wi-1,Wi,.,33,Nk=6,若Nk=6，则有：KeyExpansion（byteKey4*Nk，WNb*(Nr+1)）for(i=0;iNk;i+)Wi=(Key4*i,Key4*i+1,Key4*i+2,Key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=SubByte(RotByte(temp)Rconi/Nk;Wi=Wi-Nktemp;,.,34,Wi-6,Wi-5,Wi-4,Wi-3,Wi-2,ByteSubstituion,+,+,密钥扩展,8=i8(Rnd+1),imod8=0,imod4!=0,Wi-1,Wi,Wi-8,Wi-7,ByteSubstituion,ByteRotate,+,Rcons,imod4=0,密钥扩展（256）,.,35,Nk=8时的密钥扩展,KeyExpansion（byteKey4*Nk，WNb*(Nr+1)）for(i=0;iNk;i+)Wi=(Key4*i,Key4*i+1,Key4*i+2,Key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=SubByte(RotByte(temp)Rconi/Nk;elseif(i%Nk=4)temp=SubByte(temp);Wi=Wi-Nktemp;,.,36,Rijndael密钥扩展算法用伪C语言表示如下：Rijndael-KeyExpansion(bytekey4*Nk,wordwNb*(Nr+1),Nk)Beginwordtempi=0while(iNk)wi=word(key(4*i,key(4*i+1,key(4*i+2,key(4*i+3)i=i+1endwhilei=Nkwhile(iNb*(Nr+1)temp=wi-1if(imodNk=0)temp=Subword(RotWord(temp)xorRconi/Nkelseifwi=wi-Nkxortempi=i+1endwhileend,密钥扩展算法的描述及实现（Nk=4或6）,2020/5/22,.,37,3.4.6解密过程,由AES解密过程中的基本运算，除了轮密钥加AddRoundKey与AES加密算法中一样，其它基本运算字节替代SubBytes、行移位ShiftRows、列混合MixColumns都要求逆，解密过程中的基本运算为逆字节替代InvSubBytes、逆行移位InvShiftRows、逆列混合InvMixColumns。解密结构如下图所示。,2020/5/22,.,38,1逆字节代替（InvSubBytes）,Rijndael算法的逆字节变换（InvSubBytes）是与字节替代一样，它将输入或中间状态的每一个字节通过一个简单查表操作，只是查表操作变为查逆S盒，逆S盒如右表所示。映射方法是：输入字节前4位指定逆S盒的行值，后4位指定逆S盒的列值，有行和列所确定逆S盒位置的元素作为输出。,2020/5/22,.,39,同样，Rijndael的逆S盒替代操作它包括两个变换，其变换顺序与S盒刚好相反，先并且仿射变换的逆变换，然后进行求逆运算：（1）在GF(2)上进行下面的仿射变换，每个字节可以依次记为（b7,b6,b5,b4,b3,b2,b1,b0），依次做下面的仿射变换：其中di是指字节（05=00000101）中的第i位的值。上面逆仿射变换用矩阵可以表示为：,2020/5/22,.,40,2020/5/22,.,41,2.逆行移位（InvShiftRows）,在Rijndael算法中，逆行移位操作与行移位操作相反，行移位操作循环左移，而逆行移位操作则循环向右移。若AES算法中Nb为4，即第1行循环右移0字节，第2行循环右移1字节，第3行循环右移2字节，第4行循环右移3字节，如下图所示。从该图中可以看出，这使得列完全进行了重排。,2020/5/22,.,42,3逆列混合（InvMixColumns）,逆列混合操作与列混合操作一样，只是多项式不同，则逆列混合操作多项式d(x)=0Bx3+0Dx2+09x+0E相乘然后模x41，因而逆列混合是可以表示为矩阵相乘来实现，输入的矩阵与固定矩阵（十六进制表示）相乘，如下所示：,其图形表示如下图所示：,.,43,Rijndael加密算法用伪C语言表示如下：Rijndael-InvChiper(bytein4*Nb,byteout4*Nb,wordwNb*Nr+1)Beginbytestate4,Nbstate=inAddRoundKey(State,wNr*Nb,(round+1)*Nb-1)forround=Nr-1step-1downto1InvSubBytes(state)InvShiftRows(state)AddRoundKey(State,wround*Nb,(round+1)*Nb-1)InvMixColumn(state)EndforInvSubBytes(state)InvShiftRows(state)AddRoundKey(State,w0,Nb-1)Out=stateend,解密算法的描述及实现,解密的具体过程：首先将密文分组复制到矩阵中，使用加密时最后一轮的轮密钥进行密钥加，通过执行Nr-1次轮变换来转变状态矩阵，其中轮密钥的使用顺序恰好与加密时正好相反，最后一轮不进行逆列混合变换；最后将各状态矩阵中的各字节按顺序输出就得到明文分组。,2020/5/22,.,44,3.4.7具体实例,现在我们来跟踪AES加密算法的每一个迭代，以观察所有操作对输出影响。假设加密的明文消息为128比特示例块为十六进制为：805E6A3653253A6663356903206C280616；初始密钥也为128比特，十六进制表示为：75356B99056139567362053100550932首先，将128比特的明文块写成44的矩阵形式为：,2020/5/22,.,45,再将初始密钥写成44的矩阵形式为：,接下来，将明文分组阵列与初始密钥进行一次轮密钥加操作，如下所示：,然后进入循环迭代操作，第一步为轮密钥加的输出作为S盒的输入，进行字节替代操作，如下所示：,2020/5/22,.,46,第二步为：S盒的输出作为行移位的输入，向左的循环移位，如下所示：,第三步为：列混合（MixColumn），在GF(28)域上进行如下矩阵运算：,第四步为：列混合的输出与子密钥进行轮密钥加，在这之前先进行密钥扩展，得到子密钥。设初始密钥扩展之后下一轮子密钥（K4、K5、K6、K7），如下：,2020/5/22,.,47,密钥扩展具体过程,计算K4：K4=K1SubByte(RotByte(K3)Rcon1第一步，对K3执行RotByte(K3)，然后字节替代SubByte(RotByte(K3)在密钥扩展中，函数RotByte(a,b,c,d)=(b,c,d,a),即是输入字的1字节循环，然后根据S盒表进行替代。如下所示：,第二步，K4=K1SubByte(RotByte(K3)Rcon1，其中Rcon1值为如下表所示：,2020/5/22,.,48,第三步，计算K5、K6、K7K5