次课分组密码体制-des.ppt

1、2020/8/12,1,第三章 分组密码,一、分组密码概述 二、DES 三、分组密码运行模式 四、IDEA 五、AES 六、分组密码的分析,2020/8/12,2,二、美国数据加密标准DES（Data Encryption Standard）,2020/8/12,3,美国制定数据加密标准简况,目的 通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网络的安全，才能推广使用加密手段，以便于训练、生产和降低成本。,2020/8/12,4,背景,发明人：美国IBM公司 W. Tu

2、chman 和 C. Meyer 1971-1972年研制成功 基础：1967年美国Horst Feistel提出的理论 产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告， 公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳 了IBM的LUCIFER方案 标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标 准局颁布为数据加密标准（Data Encryption Standard），于 1977年7月15日生效,2020/8/12,5,背景,美国国家安全局（NSA, National Security Agency)参与了美国国家标准局制定

3、数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位 1979年，美国银行协会批准使用DES 1980年，DES成为美国标准化协会(ANSI)标准 1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作,2020/8/12,6,DES首次被批准使用五年，并规定每隔五年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。因为按照现有的技术水平，采用不到几十万美元的设备，就可破开DES密码体制

4、。目前的新标准是AES，它是由比利时的密码学家Joan Daemen和Vincent Rijmen设计的分组密码Rijndael（荣代尔）。,2020/8/12,7,美国制定数据加密标准简况,1997年DESCHALL小组经过近4个月的努力，通过Internet搜索了31016个密钥，找出了DES的密钥，恢复出了明文。 1998年5月美国EFF(electronics frontier foundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56 比特密钥的DES。,2020/8/12,8,美国制定数据加密标准简况,尽管如此，DES对于推动密码理论的发展

5、和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值。,2020/8/12,9,DES 算法,分组长度为64 bits (8 bytes) 密文分组长度也是64 bits。 密钥长度为64 bits，有8 bits奇偶校验，有效密钥长度为56 bits。 算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。,2020/8/12,10,DES加密算法框图,子密钥产生器,16轮迭代的乘积变换,2020/8/12,11,DES算法框图,输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代） 逆初始置换IP-1

6、 64 bit密文数据 输出,标准数据加密算法,2020/8/12,12,初始置换IP,逆初始置换IP -1,2020/8/12,13,初始置换IP,将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit，以L0和R0表示，IP中各列元素位置号数相差为8。 逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。 IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系。,2020/8/12,14,DES加密算法的轮结构,密钥流生成器,2020/8/12,

7、15,2020/8/12,16,乘积变换,它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。 每次迭代时只对右边的32 bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。 在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。,2020/8/12,17,选择扩展运算E,将输入的32 bit Ri-1扩展成48 bit的输出，令s表示E原输

8、入数据比特的原下标，则E的输出是将原下标s0或1(mod 4)的各比特重复一次得到的，即对原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重复一次,实现数据扩展。将表中数据按行读出得到48 bit输出。,2020/8/12,18,密钥加密运算 将子密钥产生器输出的48 bit子密钥ki与选择扩展运算E输出的48 bits数据按位模2相加。,2020/8/12,19,选择压缩运算S。将前面送来的48 bit数据自左至右分成8组，每组为6 bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出，运算S的框图如

9、下。,6 bit 选择函数组 4 bit,2020/8/12,20,DES的S1-盒的输入和输出关系,x5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13,(y3 ,

10、 y2, y1 , y0)=(0,0,1,0),2020/8/12,21,置换运算P,对S1至S8盒输出的32 bit数据进行坐标置换，置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。,2020/8/12,22,子密钥产生器,将64 bit初始密钥经过： 置换选择PC1 循环移位置换 置换选择PC2 给出每次迭代加密用的子密钥ki，,置换选择1,64比特,2020/8/12,23,子密钥产生器框图,密钥（64 bit ）,置换选择1，PC1,置换选择2，P

11、C2,Ci(28 bit),Di(28 bit),循环左移ti+1bit,循环左移ti+1bit,除去第8,16, ,64位(8个校验位),ki,2020/8/12,24,置换选择2 PC-2,置换选择1 PC-1,左循环移位位数,2020/8/12,25,2020/8/12,26,DES的安全性,穷举攻击分析 穷举攻击就是对所有可能的密钥逐个进行脱密测试, 直到找到正确密钥为止的一种攻击方法. 穷举攻击判断正确密钥的方法： 将利用试验密钥解密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。,穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随

12、机的，就可实施穷举攻击。,2020/8/12,27,穷举攻击的算法,已知条件：已知密文c及对应的明文m. Step 1 对每个可能密钥k,计算c=D(k,m),并判断c=c是否成立.不成立时返回Step1检验下一个可能密钥,成立时将k作为候选密钥,并执行Step 2. Step 2 利用其它条件对作k进一步确认.确认通过时输出,算法终止.否则返回Step1检验下一个可能密钥.,2020/8/12,28,穷举攻击算法的计算复杂性,定理 设密钥在密钥空间K中服从均匀分布，且没有等效密钥,则穷举攻击平均需要检验完 个密钥后才找到正确密钥。 结论: 对DES算法的穷举攻击平均计算复杂性为255.,20

13、20/8/12,29,二重DES,明文为x，两个加密密钥k1和k2，密文为： y=Ek2Ek1x 解密时， x=Dk1Dk2y,讨论：使用二重DES产生的映射是否等价于单重DES加密?,2020/8/12,30,二重DES,用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112 bit密钥的密码的强度？答案是否定的。 中途相遇攻击法(Meet-in-the-Middle Attack) 由Diffie和Hellman1977最早提出，可以降低搜索量其基本想法如下。若有明文密文对(xi,yi)满足 yi=Ek2Ek1xi 则可得 z=Ek1xi=Dk2yi,2020/8/12,3

14、1,中途相遇攻击,给定一已知明密文对(x1,y1)，可按下述方法攻击。 以密钥k1的所有256个可能的取值对此明文x1加密，并将密文z存储在一个表中； 从所有可能的256个密钥k2中依任意次序选出一个对给定的密文y1解密，并将每次解密结果z在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥k1和k2； 以此对密钥k1和k2对另一已知明文密文对(x2, y2)中的明文x2进行加密，如果能得出相应的密文y2就可确定k1和k2是所要找的密钥。,破译双重DES的难度为257量级，和单次DES的255差不多。,2020/8/12,32,三重DES加密,加密：y=Ek1Dk2Ek1 x 解密：x=Dk

15、1Ek2Dk1y 称其为加密-解密-加密方案，简记为EDE(encrypt-decrypt-encrypt)。 此方案已在ANSI X9.17和ISO 8732标准中采用，并在保密增强邮递(PEM)系统中得到利用。 破译它的穷举密钥搜索量为211251035量级，而用差分分析破译也要超过1052量级。此方案仍有足够的安全性。,2020/8/12,33,Feistel模型分析,优点： 1. 设计容易:f 函数不要求可逆,加、解密算法结构相同； 2.强度高：如果f 函数是随机的,则连续若干圈复合形成的函数与随机置换是无法区分的.,2020/8/12,34,Feistel模型分析,缺点： 每圈加密时

16、输入有一半没有改变; 左右块的加密处理不能并行实施。,2020/8/12,35,Feistel模型实现完全性的性能分析,定义2 如果对每个密钥k ，迭代次数为m的加密变换Ek(x)的每个输入比特的变化都可能会影响到每个输出比特的变化,则称 Ek(x)是完全的. 意义: 实现了Shannon提出的扩散性原则. 扩散原则(Diffusion) 让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。 因为在检验完全性时,无法对所有的密钥都来检验影响的必然性, 只好退而求其次,来分析这种可能性.,2020/8/12,36,结论: (1) Feistel模型至少需要3圈才可实现完全性. (2) 如果Feistel模型的 f 函数