密码学4 分组密码-2

分组密码4.1分组密码概述4.2数据加密标准（DES）4.3分组密码工作模式4.4高级加密标准AES4.5国际数据加密算法IDEA2/3/20231HANMENG20104.2DES小结是对称密码体制，加密和解密使用同一密钥，有效的密钥长度是56位。DES是分组密码算法，分组长度为64位，即对数据加密解密的单位是64位。算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16轮子密钥产生器。2/3/20232HANMENG2010DES加密算法框图子密钥产生器16轮迭代的乘积变换?2/3/20233HANMENG20101、DES的初始置换和逆置换初始置换（IP）目的：将原明文块的位置进行换位。逆初始置换（IP-1）是初始置换的逆置换。2/3/20234HANMENG2010eg：已知1010101101011111110001100100001010111000000011101100110001010101经过初始置换后第2行值是什么？100100102/3/20235HANMENG20103、DES的F函数DES的一次迭代迭代过程主要是轮函数F，由3部分组成：扩展置换（E盒）、S盒和P盒。初始置换将64比特的轮输入分成各为32比特的左、右两半，分别记为L0和R0。2/3/20236HANMENG2010DES加密算法的轮结构每轮变换可由以下公式表示：2/3/20237HANMENG2010函数F(R,K)的计算过程2/3/20238HANMENG20103、DES的F函数（1）扩展置换E盒作用：将32位输入扩展为48位输出。扩展方法：将32位输入分成8行，每行四个字符，同时两侧补充与其相邻位置的字符。eg：已知10101011010111111100011001000010经过扩展E盒后值是什么？0101010101101010111111111110000011000010000001012/3/20239HANMENG2010eg：已知101010110101111100000101011001010000110010111111经过S盒变换以后前16位的值是什么？（2）代换盒S盒01100111111010112/3/202310HANMENG2010（3）置换运算P盒eg：已知输入为10101011010111110011010101100000经过P盒置换以后最后4位的值是什么？10002/3/202311HANMENG2010DES轮结构--完整版2/3/202312HANMENG2010子密钥生成图3、DES的子密钥生成56比特56比特48比特2/3/202313HANMENG2010置换选择PC1（1）PC1置换2/3/202314HANMENG2010置换选择PC256到48位的转换已知输入为：00111101000111110011000110110011111000001100001100010110经过PC2置换后第1、5行的值是什么？100101…1110112/3/202315HANMENG2010循环左移位轮序12345678910111213141516移位数1122222212222221已知为第10轮密钥：C10=0011110100011111001100011011D10=0011111000001100001100010110那么经过循环左移位后，第11轮密钥的输入是什么？C10=1111010001111100110001101100D10=11111000001100001100010110002/3/202316HANMENG20104、DES加/解密数学描述消息传递过程发送方已知：明文M（64位）和密钥K（56位）。输出：密文C（64位）

。接收方已知：密文C（64位）和密钥K（56位）。输出：明文M（64位）

。2/3/202317HANMENG20104、DES加/解密数学描述加密过程明文M-->IP-->L0R0Li=Ri-1Ri=Li-1f(Ri-1,ki)i=1,...,16R16L16-->IP-1-->密文C解密过程：DES的加密运算是可逆的，其解密过程可类似地进行。密文C-->IP-1-->R16L16Ri-1=Li

Li-1=Rif(Li,ki)i=16,...,1R0L0-->IP-->明文M2/3/202318HANMENG2010双重DES：双重DES是分别用两个不同的密钥k1和k2对明文进行两次DES变换以实现对数据的加密保护，即双重DES的密钥长度是112比特。三重DES

根据密钥的相同与否和加密解密顺序分为四种。5、多重DES了解2/3/202319HANMENG2010MMMM2/3/202320HANMENG2010三重DES的优、缺点优点：密钥长度增加到112位或168位，可以有效克服穷举搜索攻击；相对于DES，增强了抗差分分析和线性分析的能力；具备继续使用现有的DES实现的可能。缺点：处理速度相对较慢，特别是对于软件实现。明文分组的长度仍为64位，就效率和安全性而言，与密钥的增长不相匹配。2/3/202321HANMENG20106.DES算法的安全强度对DES的分析主要有：蛮力攻击、差分密码分析、线性密码分析DES的脆弱性DES的安全性完全依赖于所用的密钥，56位不太可能提供足够的安全性DES的半公开性S盒的设计原理至今未公布，可能隐含有陷井软件实现太慢2/3/202322HANMENG20104.3分组密码工作模式分组密码只能加密固定长度的明文。明文长度是任意的，因此加密时需要进行处理---工作模式。工作模式通常是基本密码块、反馈和简单运算的组合：电子密码本（ECB）模式密文块链接（CBC）模式密文反馈（CFB）模式输出反馈（OFB）模式2/3/202323HANMENG20101、电子密码本(ECB)模式密钥为K，明文分成t个长度为n的块M1,M2,…,Mt。输出t个长度为n的密文块C1,C2,…,Ct。加密：Cj=Ek(Mj)(j=1,2,…,t)解密：Mj=Dk(Cj)(j=1,2,…,t)2/3/202324HANMENG2010加密M1C1K加密M2C2K解密C1M1K解密C2M2K加密过程解密过程2/3/202325HANMENG2010电子密码本(ECB)模式示例2/3/202326HANMENG2010电子密码本(ECB)模式示例2/3/202327HANMENG2010ECB模式的优缺点模式操作简单。无错误传播，可用并行计算提高加密速度。明文中的重复内容将在密文中表现出来，特别对于图像数据和明文变化较少的数据。适于短报文的加密传递。适用于对密钥加密。2/3/202328HANMENG20102、密文块链接(CBC)模式密钥为K，长度为n的初始向量IV，明文分成t个长度为n的块M1,M2,…,Mt。输出t个长度为n的密文块C1,C2,…,Ct。加密之前，每个分组块与前面的密文进行异或运算。加密：C1=Ek(M1⊕IV)Cj=Ek(Mj⊕Cj-1)(j=2,3,…,t)解密：M1=Dk(C1)⊕IVMj=Dk(Cj)⊕Cj-1(j=2,3,…,t)2/3/202329HANMENG2010加密M1C1K加密C2K加密过程IVM2解密C1K解密过程IVM1解密C2KM22/3/202330HANMENG2010密文块链接模式示例2/3/202331HANMENG2010密文块链接模式示例2/3/202332HANMENG2010密文块链接模式的特点同一个明文分组重复出现时产生不同的密文分组。加密函数的输入是当前的明文分组和前一个密文分组的异或；对每个分组使用相同的密钥。有错误传播。多用于字符文件加密。2/3/202333HANMENG20103、密文反馈(CFB)模式用分组密码生成流密码，密钥和明文块一样长。包括密文反馈模式和输出反馈模式。密钥为K，长度为n的初始向量IV，明文分成t个长度为r(r一般为8比特)的块M1,M2,…,Mt。2/3/202334HANMENG2010密文反馈(CFB)模式加密过程Ci=Mi⊕Lr(Ek(Ii))Ii=Rn-r(Ii-1)||Cii=2,3,…I1=IVIV加密r比特KM1加密r比特KM2C1移位r比特C2I1I22/3/202335HANMENG2010密文反馈模式的特点改变IV，则相同的明文得到不同的密文。有错误传播。多用于字符文件加密。2/3/202336HANMENG20104、输出反馈(OFB)模式加密过程IV加密r比特KM1加密r比特KM2C1移位r比特C2Ci=Mi⊕Lr(Ek(Ii))Ii=Rn-r(Ii-1)||

Lr(Ek(Ii-1))i=2,3,…I1=IV2/3/202337HANMENG2010输出反馈模式的特点改变IV，则相同的明文得到不同的密文。无错误传播。难以检测出是否对密文进行过篡改。多用于语音、图像文件等冗余度大的文件加密。常用于加密卫星传输。2/3/202338HANMENG20104.4高级加密标准AESAES特征对AES的基本要求是：比三重DES快、至少与三重DES一样安全、软件实现快。数据分组长度和密钥长度可变，可以为128/192/256比特。结构简单、速度快。能在多种平台上以较快的速度实现。2/3/202339HANMENG20101、算法的结构常用的算法结构算法中间的加密过程也需要分组（称为状态），以字节为元素的矩阵阵列表示，该阵列有4行4列。种子密钥也以字节为元素的矩阵阵列描述，阵列为4行4列。2/3/202340HANMENG2010明文分组和密钥的组织排列方式(128位=16字节)01234567891011121314150481215913261014371115分组为128bits为例组成的阵列2/3/202341HANMENG2010

AES

算法的一般描述2/3/202342HANMENG2010AES的算法结构第10轮没有列混合2/3/202343HANMENG2010网络工程系©AES的流程图2/3/202344HANMENG20101、将待加密的明文分组以字节为单位填充状态矩阵（4×4字节矩阵），和初始密钥做异或运算。2、进行10轮迭代，每轮包含四个变换（最后一轮不包含列混合）：（1）字节代替变换（S盒）；（2）行移位变换；（3）列混合变换；（4）轮密钥加（按位异或）。3、第10轮的输出即为密文（输出状态）。算法步骤：2/3/202345HANMENG20102、轮函数重点2/3/202346HANMENG2010（1）字节代替作用：是非线性置换，使用S盒对中间状态的字节进行置换。扩展方法：查S盒，S盒是16*16的矩阵。设x（高位4比特）y(低位4比特)为状态中的一个字节，则代替表(S盒)中第x行第y列的字节就是对应的字节代替变换的结果。2/3/202347HANMENG2010eg：设输入为EA，则经过字节替换输出是什么？2/3/202348HANMENG2010字节代替示例eg:已知字节代替的输入为3CA10B2157F01916902E1380ACC107BD则经过字节代替后，前4个字节输出是什么？EB322BFD---->111010110011001000101011111111012/3/202349HANMENG20102、轮函数（2）行移位作用：对矩阵状态进行变换。方法：变换时，矩阵的每一行按照不同的偏移量循环左移位。第一行不移位，第二行移1个字节，第三行移2个字节，第四行移3个字节.2/3/202350HANMENG2010行移位04812159132610143711150481259131101426153711循环左移1字节循环左移2字节循环左移3字节2/3/202351HANMENG2010行移位示例eg:已知行移位的输入为3CA10B2157F01916902E1380ACC107BD则经过行移位后，输出是什么？3CA10B21F01916571380902EBDACC1072/3/202352HANMENG2010（3）列混合方法：通过移位后的矩阵与固定的矩阵相乘，得到混合矩阵。S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3S’0,0S’0,1S’0,2S’0,3S’1,0S’1,1S’1,2S’1,3S’2,0S’2,1S’2,2S’2,3S’3,0S’3,1S’3,2S’3,3×C(X)2/3/202353HANMENG2010eg：s’0,j=(2∙s0,j)(3∙s1,j)

s2,j

s3,j其中j=0,1,2,3令s’(x)=c(x)×s(x)，写成矩阵形式为：S’00S’01S’02S’03S’10S’11S’12S’13S’20S’21S’22S’23S’30S’31S’32S’33S00S01S02S03S10S11S12S13S20S21S22S23S30S31S32S3302030101010203010101020303010102=eg：s’0,0=(2∙s0,0)(3∙s1,0)

s2,0

s3,016进制2/3/202354HANMENG2010补充：多项式计算解：1、转换为二进制数(02)16∙(F0)16=00000010∙11110000知识点：乘法计算规则2∙n=(00000010)∙(a7a6a5a4a3a2a1a0)=(a6a5a4a3a2a1a00)a7=0(a6a5a4a3a2a1a00)(00011011)a7=13∙n=(00000011)∙(a7a6a5a4a3a2a1a0)=[(00000010)∙(a7a6a5a4a3a2a1a0)](a7a6a5a4a3a2a1a0)eg1：求(2)16∙s0,j,其中s0,j=(F0)16。2/3/202355HANMENG2010eg1：求(2)16∙s0,j,其中s0,j=(F0)16。解：计算00000010∙11110000=11100000(00011011)

=11111011=(FB)16eg2：求2∙(4E)16。解：计算00000010∙01001110=10011100=(9C)16eg3：求3∙(4E)16。解：计算00000011∙01001110=[00000010∙01001110]

01001110

=10011100

01001110=11010010=

(D2)16知识点：乘法计算规则2∙n=(00000010)∙(a7a6a5a4a3a2a1a0)=(a6a5a4a3a2a1a00)a7=0(a6a5a4a3a2a1a00)(00011011)a7=13∙n=(00000011)∙(a7a6a5a4a3a2a1a0)=[(00000010)∙(a7a6a5a4a3a2a1a0)](a7a6a5a4a3a2a1a0)2/3/202356HANMENG2010（4）轮密钥加对状态和每轮的子密钥进行简单的异或操作。2/3/202357HANMENG2010AES算法示例Eg：设某轮的输入状态如下表所示，分别求其经过字节代替、行移位、列混合后的输出。122A210B45BD04C1230A001C89112AFC字节代替C9E5FD2B6E7AF2782667639CA782E5B02/3/202358HANMENG2010C9E5FD2B6E7AF2782667639CA782E5B0行移位C9E5FD2B7AF2786E639C2667B0A782E5D4E7CD662802E5BBBEC6D6BF220FDFA5列混合S’00=(2∙C9)(3∙7A)63B0解：2∙C9=00000010∙11001001=1001001000011011=100010013∙7A=10001110S’00=110101002/3/202359HANMENG20103、AES：密钥编排密钥编排密钥编排是指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成轮密钥的比特数等于分组长度乘以轮数加1=[32×

Nb

×(Nr+1)]；种子密钥被扩展成为扩展密钥；轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。2/3/202360HANMENG2010

密钥调度包括两个部分：密钥扩展和轮密钥选取。密钥bit的总数＝分组长度×（轮数Round＋1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408bits。将密码密钥扩展成一个扩展密钥。从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个轮密钥由接下来的Nb个4字节字组成，以此类推。2/3/202361HANMENG2010密钥扩展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+++K4的生成：下页K5、K6、K7的生成：如右2/3/202362HANMENG2010K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+Rcon密钥扩展2/3/202363HANMENG2010在密钥扩展中，函数RotByte(a,b,c,d)=(b,c,d,a),即是输入字的1字节循环

K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3RotByteK0,0K0,1K0,2K1,3K1,0K1,1K1,2K2,3K2,0K2,1K2,2K3,3K3,0K3,1K3,2K0,3密钥扩展-RotByte2/3/202364HANMENG2010AES密钥扩展算法密钥按照矩阵列进行分组，如果前4列为k(0),k(1),k(2),k(3),那么新的列如下递归：如果k(i)中，i不是4的倍数，那么i列由如下等式确定：k(i)=k(i-4)XORk(i-1)如果k(i)中，i是4的倍数，那么i列由如下等式确定：k(i)=k(i-4)XORT[k(i-1)]其中T[k(i-1)]是k(i-1)的一种转换形式，按以下方式实现：循环地将k(i-1)的元素左移位，每次一个字节，如abcd

变成bcda将这4个字节作为S盒的输入，输出新的4个字节efgh计算一轮的常量r(i)=2(i-4)/4这样生成转换后的列：[eXORr(i),f,g,h]第i轮的轮密钥组成了列k(4i),k(4i+1),k(4i+2),k(4i+3)2/3/202365HANMENG2010Wi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Rnd+1)imod4=0imod4!=02/3/202366HANMENG2010轮密钥选取K0K1K2K3K4K5K6K7K8K9K10K11K12轮密钥0轮密钥1轮密钥22/3/202367HANMENG2010AES：KeyExpansion(key[],w[])KeyExpansion(key[],w[])key[]用于存储扩展前的密钥；w[]用于存储扩展后的密钥；以128比特的密钥为例输入的密钥key[]直接被复制到密钥数组的前四个字，w[0],w[1],w[2],w[3]；w数组中下标不为4的倍数的元素按以下规则扩展w[i]=w[i-1]⊕

w[i-4]2/3/202368HANMENG2010AES：KeyExpansion(key[],w[])下标为4的倍数的元素按以下规则扩展将一个字的四个字节循环左移一个字节，即将[b0,b1,b2,b3]变为[b1,b2,b3,b0]；基于SubBytes对输入字中的每个字节进行代替；——S盒将步骤1和步骤2的结果再与轮常量Rcon[i]相异或。Rcon[i]=(RC[i],‘00’,‘00’,‘00’)RC[1]=‘01’RC[i]=2.(RC[i-1])2/3/202369HANMENG2010瑞士联邦技术学院来学嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，国际数据加密算法）于1990年公布，当时称为PES（proposedencryptionstandard，建议加密标准）。1991年，在Biham和Shamir提出差分密码分析之后，设计者推出了改进算法IPES，即改进型建议加密标准。1992年，设计者又将IPES改名为IDEA，目前已在PGP中采用。4.5国际数据加密算法IDEA2/3/202370HANMENG20104.5国际数据加密算法IDEA特征：算法中明文和密文分组长度都是64比特，密钥长128比特。非常便于软硬件的实现。加密过程：将输入的64比特的明文进行8轮迭代，得到临时密文组。将临时密文组进行输出变换，生成最终的密文组。2/3/202371HANMENG20104.5.1设计原理算法中明文和密文分组长度都是64比特，密钥长128比特。其设计原理可从强度和实现两方面考虑。1.密码强度算法的强度主要是通过有效的混淆和扩散特性而得以保证。2/3/202372HANMENG2010混淆是通过使用以下3种运算而获得，3种运算都有两个16比特的输入和一个16比特的输出：①逐比特异或，表示为。②模216（即65536）整数加法，表示为其输入和输出作为16位无符号整数处理。③模216+1（即65537）整数乘法，表示为⊙，其输入、输出中除16位全为0作为216处理外，其余都作为16位无符号整数处理。例如0000000000000000⊙1000000000000000=1000000000000001这是因为216×215mod(216+1)=(216+1)×215-215=-215=215+1mod(216+1)+2/3/202373HANMENG2010算法中扩散是由称为乘加（multiplication/addition,MA）结构的基本单元实现的。该结构的输入是两个16比特的子段和两个16比特的子密钥，输出也为两个16比特的子段。MA结构2/3/202374HANMENG20104.5.2实现IDEA可方便地通过软件和硬件实现。①软件实现采用16比特子段处理，可通过使用容易编程的加法、移位等运算实现算法的3种运算。②硬件由于加、解密相似，差别仅为使用密钥的方式，因此可用同一器件实现。2/3/202375HANMENG2010加密过程由连续的8轮迭代和1个输出变换组成.每轮迭代以4个16比特的子段作为输入，输出也为4个16比特的子段,链接起来后形成64比特的密文分组。每轮需使用6个16比特的子密钥，输出变换需使用4个16比特的子密钥，所以子密钥总数为52。IDEA加密过程2/3/202376HANMENG2010轮结构模216+1的整数乘模216的整数加2/3/202377HANMENG2010输出变换输出变换的结构和每一轮开始的变换结构一样，不同之处在于输出变换的第2个和第3个输入首先交换了位置，目的在于撤销第8轮输出中两个子段的交换。第9步仅需4个子密钥，而前面8轮中每轮需要6个子密钥。轮开始的变换结构2/3/202378HANMENG2010子密钥的产生

前8个子密钥Z1，Z2，…，Z8直接从加密密钥中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次类推。然后加密密钥循环左移25位，再取下面8个子密钥Z9，Z10，…，Z16，取法与Z1，Z2，…，Z8的取法相同。这一过程重复下去，直到52子密钥都被产生为止。2/3/202379HANMENG2010左边为加密过程，由上至下，右边为解密过程，由下至上。将每一轮进一步分为两步，第1步是变换，其余部分作为第2步，称为子加密。解密过程输出2/3/202380HANMENG20102/3/202381HANMENG2010总结数据加密标准（DES）算法构成：初始置换IP16轮迭代E盒扩展—S盒代换—P盒置换逆初始置换IP-116轮子密钥产生器。2/3/202382HANMENG2010分组密码工作模式电子密码本(ECB)模式Cj=Ek(Mj)(j=1,2,…,t)密文块链接(CBC)模式C1=Ek(M1⊕IV)Cj=Ek(Mj⊕Cj-1)(j=2,3,…,t)密文反馈(CFB)模式Ci=Mi⊕Lr(Ek(Ii))Ii=Rn-r(Ii-1)||Cii=2,3,…

I1=IV输出反馈(OFB)模式Ci=Mi⊕Lr(E