第三章对称密码体制.ppt

《第三章对称密码体制.ppt》由会员分享，可在线阅读，更多相关《第三章对称密码体制.ppt（60页珍藏版）》请在三一办公上搜索。

1、第三章对称密码体制,回顾上一章的内容,密码的两个基本方法替换和移位(Substitution&transposition)密码分析的两个基本方法系统分析法（解析法和统计法）穷举法,3.1分组密码原理,分组密码算法：把明文分成若干等长的组，每次一组对明文进行加密,称作分组密码(block cipher)。序列密码算法（又称流密码）：每次一位或者一个字符对明文进行加密,称作序列密码或者流密码(steam cipher)。分组密码加密模型(P22图3.2),加密算法,解密算法,明文(x0,xn-1),明文(x0,xn-1),密文(y0,yn-1),密钥k=(y0,yn-1),密钥k=(y0,yn-1

2、),分组密码设计的一般原则,分组长度足够大密钥空间足够大,尽可能消除弱密钥由密钥确定的算法要足够复杂,充分实现明文与密钥的扩散与混淆软件实现的要求硬件实现的要求,DES加密算法的背景,发明人：IBM公司W.Tuchman 和 C.Meyer 1971-1972年研制。基础：1967年美国Horst Feistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encry

3、ption Standard），于1977年7月15日生效。,3.2数据加密标准（DES）,DES加密算法的背景,美国国家安全局（NSA,National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(American National Standard Institute，ANSI)标准。,DES加密算法的背景,在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于DES的

4、解密，而且需要12个小时的破解才能得到结果。1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。1997年1月，美国程序员verser在数万名志愿者的协同工作下，用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天；1998年7月，“第2-2届DES挑战赛（DES Challenge II-2）”把破解DES的时间缩短到了只需56个小时；“第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5小时。,上表中攻击者配有如下计算机资源的攻击能力,抵御系统分析法攻击能力,1982年，能破解3次或者4次迭代

5、的DES系统1985年，6次1990年，以色列学者发明了差分分析方法，他证明任何少于16次的DES算法都可以用比穷举法更有效的方法破译IBM公司的D.CopperSmith：“1974年IBM设计小组就掌握了差分分析方法”,DES概述,为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。64位明文变换到64位密文，密钥64位，实际可用密钥长度为56位。组长这个参数是一个折中的选择,取决于实际应用的环境便于操作和运算，不太长应付密码分析，不太短,利用传统的换位和替换加密。信息被分成64比特的块，密钥是56比特。经过DES加密的密文也是64比特的块。明文：m=m1m2m64 mi=0,

6、1 i=1,2,64密钥：k=k1k2k64 ki=0,1 i=1,2,64 其中k8，k16，k64是奇偶校验位，起作用的仅为56位。加密算法:Ek(m)=IP-1T16T15T1IP(m)其中IP为初始置换，IP-1是IP的逆，Ti，i=1,2,16是一系列的变换。解密算法:Ek-1(c)=IP-1T1T2T16IP(c),64位码,64位码,初始变换,逆初始变换,乘积变换16次迭代,明文,密文,输入,输出,IP,IP-1,交换左右32比特,输入（64位）,58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 66

7、4 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7,输出（64位）,初始变换IP,L0（32位）,R0（32位）,初始变换IP,置换码组(16轮)输入（64位）,40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2

8、 42 10 50 18 58 2633 1 41 9 49 17 57 25,输出（64位）,逆初始变换IP-1,逆初始变换,逆初始变换。用IP-1 表示，它和IP互逆。例如，第58位经过初始置换后，处于第1位，而通过逆置换，又将第1位换回到第58位。可见输入组m和IP(IP-1(m)是一样的。,中间各级算法说明Ki：每级密钥不同,Li-1,Li,Ri-1,Ri,Li-1 f(Ri-1,Ki),加密函数f(A,Ki),A(32位),加密时A=Ri-1,48位结果,48位Ki,+,选择函数组(S1S8),32位结果,(A,Ki)输出,置换运算P,32位,左32位,右32位,Li-1,Ri-1,

9、48位(明文),64位密钥,作第i次迭代的子密钥Ki,密钥程序表,48位(密钥),8组6位码,模2加,选择函数输入：6位输出：4位,+,32位,置换,32位,32位,Li,Ri,左32位,右32位,Ri-1,Li-1,模2加,+.+,乘积变换中的一次迭代,A,32位,32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1,选择运算E,选择运算E的结果,48位,扩展置换E,使用密钥在第i次迭代中，用48位

10、二进制的密钥（由56位密钥生成，下边会介绍）K（i）=k1(i)k2(i）k48(i)与E(Ri1)按位相加（逻辑异或），输出仍是48位，共8行，每行6位，记为Z1,Z1,Z8作为8个Si选择函数的输入,S1,S2.S8选择函数其功能是把6bit数据变为4bit数据。Si(i=1,2.8)的功能表：,S1:14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,15,12,8,2,4,9,1,7,5,11,3,14,10,0

11、,6,13,S2:15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,(P29),使用选择函数S,将以上第j个(1j6)二进制的块（记为Z j=zj1 zj2 zj3 zj4 zj5 zj6）输入第j个选择函数Sj。各选择函数Sj的功能是把6位数变换成4位数，做法是以zj1zj6为行号，zj2 zj3 zj4 zj5为列号，查找Sj，行列交叉处即

12、是要输出的4位数。在此以S1为例说明其功能，我们可以看到：在S1中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，.，14、15列。现设输入为：D101100令：列0110行10坐标为（2，6），然后在S1表中查得对应的数为2，以4位二进制表示为0010，此即选择函数S1的输出。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7

13、 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,S1,1 0 1 1 0 0,102,0 0 1 0,输入6位,输出4位,使用选择函数S1的例子,选择函数的输出,（32位）,16 7 20 2129 12 28 17 1 15 23 26 5 18 31 10 2 8 24 1432 27 3 919 13 30 622 11 4 25,置换P,加密函数的结果,（32位）,置换P（单纯换位表）,L（i+1）=R（i）R（i+1）=L（i）f(R（i）,K（i+1）)(i=0,1,2,15),64位密钥,C0(28位),D0(28位),循环左移,

14、循环左移,C1(28位),D1(28位),K1,(48位),(56位),循环左移,循环左移,Ci(28位),Di(28位),Ki,(48位),(56位),密钥表的计算逻辑,循环左移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1,密钥计算的目的在于产生加密和解密时所需要的16个子密钥，记作Ki。初始密钥Key值为64位，但DES算法规定，其中第8、16、.64位是奇偶校验位，不参与DES运算。故Key 实际可用位数便只有56位。即：经过子密钥换位表PC-1的变换后，Key 的位数由64 位变成了56位，此56位分为

15、C0、D0两部分，各28位。,57 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 2719 11 3 60 52 44 36,63 55 47 39 31 33 15 7 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 4,置换选择1,密钥（64位）,C0(28位),D0(28位),循环移位规则：轮数：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16位数：1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1密钥置换选择256位分为C0、D0

16、两部分，然后分别进行第1次循环左移，得到C1、D1，将C1（28位）、D1（28位）合并得到56位，再经过子密钥换位表PC-2，便得到了密钥K1（48位）。子密钥换位表PC-2给出了选择及选择后的次序，可以看出去掉了第9、18、22、25、35、38、43、54位。,Ci(28位),Di(28位),14 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32,Ki(48位),置换选择2,加密函数(A

17、,Ki),A(32位),加密时A=Ri;解密时A=Li;,48位结果,Ki,+,选择函数组(S1S8),32位结果,(A,Ki),置换运算P,32位,L0R0 IP(明文)L1R0 R1 L0(R0,K1)L2R1 R2 L1(R1,K2)L16R15 R16 L15(R15,K16)密文 IP-1(R16L16),加密方程：L0R0 IP()LnRn-1Rn Ln-1(Rn-1,Kn)IP-1(R16L16),DES设计原理,重复交替使用选择函数S和置换运算P两种变换（confusion+diffusion混淆扩散),混淆(confusion)：使密文与明文的统计关系复杂化。使得输出是输入的

18、非线性函数；用于掩盖明文和密文间的关系。通过替换法实现，如S盒。扩散(diffusion)：使每位明文尽可能影响多位密文。扩展输出对输入的相关性，尽量使密文的每一位受明文中多位影响。通过换位法实现，如P盒。,解密方程(请证明)R16L16 IP()记为 L0=R16，R0=L16Li=Ri-1 Ri=Li-1 f(Ri-1,Ki)IP-1(L0R0),加密方程：L0R0 IP()LnRn-1Rn Ln-1(Rn-1,Kn)IP-1(R16L16),请证明DES的解密流程：,L0=R16，R0=L16因为Li=Ri-1 Ri=Li-1 f(Ri-1,Ki)所以L1=R0 L16=R15R1=L0

19、 f(R0,K1)=R16 f(L16,K16)=L15 f(R15,K16)f(R15,K16)=L15L2=R1=L15=R14R2=L14 L16=R0 R16=L0,DES算法的弱点,DES的主要弱点：密钥容量：56位不太可能提供足够的安全性迭代次数问题S盒：可能隐含有陷井（Hidden trapdoors）提高加密强度（如增加密钥长度），系统开销呈指数增长，除提高硬件、并行处理外，算法本身和软件技术无法提高加密强度。DES的半公开性：S盒的设计原理至今未公布,S 盒是DES 的最敏感部分，其原理至今未公开。人们担心S 盒隐藏陷门，使得只有他们才可以破译算法，但研究中并没有找到弱点。美

20、国国家安全局透露了S 盒的几条设计准则：1 所有的S 盒都不是它输入的线性函数。就是没有一个线性方程能将四个输出比特表示成六个输入比特的函数。2 改变S 盒的1 位输入，输出至少改变2 位。这意味着S 盒是经过精心设计的，它最大程度上增大了扩散量。3 S 盒的任意一位输入保持不变时，输出0 和1 个数之差极小。即如果保持一位不变而改变其它五位，那么其输出0 和1 的个数不应相差太多。4 S盒是精心设计的，它有利于设计者破译密码。,多重DES(Double-DES vs.Triple-DES),二重DES（二个密钥，长度112位）：加密：C=Ek2Ek1(P)解密：P=Dk1Dk2(C)K=K1

21、K2要防止中途攻击三重DES（二个密钥）加密：C=Ek1Dk2 Ek1(P)解密：P=Dk1Ek2 Dk1(C)三重DES（三个密钥）DES-EEE3：三个不同密钥，顺序使用三次加密算法DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法,双重DES加密解密问题：下式成立吗？,两个密钥的三重DES,没有针对三重DES的攻击方法，它是一种较受欢迎的DES替代方案。has been adopted by some Internet applications,eg PGP,S/MIME,DES(分组密码)的工作模式,电码本模式(Electronic Codebook)ECB模式密码分组链接模

22、式(Cipher Block Chaining)CBC模式密码反馈模式(Cipher FeedBack)CFB模式输出反馈模式（Output FeedBack）OFB模式,ECB（Electronic Codebook电码本）模式：各明文组独立地以同一密钥加密；传送短数据,ECB的优势与局限,相同的明文对应于相同的密文 结构化明文 消息有重复部分 主要用于发送少数量的分组数据,CBC模式(Cipher Block Chaining密码分组链接模式),用途：传送数据；认证缺点:导致错误传播,CBC的优势与局限,each ciphertext block depends on all messag

23、e blocks beforethus a change in the message affects all ciphertext blocks after the change as well as the original block 密文中错误传播need Initial Value(IV)known to sender&receiver hence either IV must be a fixed value(as in EFTPOS)or it must be sent encrypted in ECB mode before rest of message 可以用于数据完整性保

24、护,CFB方式(Cipher FeedBack 密码反馈模式)利用CFB、OFB模式，可将DES转换为流密码。流密码无需填充消息，实时运行。流密码中明文和密文长度相同。,Advantages and Limitations of CFB,appropriate when data arrives in bits/bytes most common stream mode note that the block cipher is used in encryption mode at both ends errors propagate for several blocks after the

25、error,Output FeedBack(OFB),输出反馈模式,Advantages and Limitations of OFB,类似于 CFB feedback is from the output of cipher and is independent of message 错误不会被传播，不能用于完整性服务,其它加密算法,IDEA加密算法（瑞士）1990年赖学佳和James Massey of Swiss Federal Institute of Technology64位分组，128位密钥，8圈,同一算法既可加密也可解密Daemen发现该算法有多达251个弱密钥 BLOWFIS

26、HBruce Schneier 1995发表,64位分组,最大到448位可变长密钥(32448bit密钥)。RC5、RC2Ron Rivest开发，可变长加密算法,1.AES的起源1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5个方案成为最终候选方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（Rijndael 读成Rain Doll。）http:/www.esat.kuleuven.ac.be/rijmen/rijndael/AES被开发用

27、于替代DES，但NIST预测Triple DES仍将在近期作为一种实用的算法，单DES将逐步退出。大体了解P36图3.11(a),高级加密标准(AES),2.AES的设计原则,能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单。,Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。,优劣标准：安全性；计算效率；简便灵活。,表 1.分组长度和密钥长度的不同取值,按比特进行数据处理(伪)随机密钥流randomness of stream key completely destroys any statistically properties in the mes

28、sage Ci=Mi XOR Stream Keyi 同步流密码 密钥不依赖于明文自同步流密码 密钥依赖于明文不可重复使用密钥流,3.5流密码简介,流密码属性,设计流密码主要的考虑因素：加密序列的周期要长 密钥流应尽可能地接近一个真正的随机数流的特征 密钥应该足够长,RC4,a proprietary cipher owned by RSA DSI another Ron Rivest design,simple but effectivevariable key size,byte-oriented stream cipher widely used(web SSL/TLS,wireless WEP)key forms random permutation of all 8-bit values,作业:1.Implement DES Algorithm in C or C+or other programming language,