6[1].数据加密标准DES

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,信息安全技术基础,数据加密标准,DES,(Data Encryption Standard,),-,主讲 唐西林,2024/11/25,1,本节课的内容提要：,数据加密标准（,DES,）,3DES,2024/11/25,2,数据加密标准,美国国家标准局,(NBS),，即现在的国家标准和技术研究所,(NIST),于,1973,年,5,月向社会公开征集标准加密算法,并公布了它的设计要求：,-,算法必须提供高度的安全性,-,算法必须有详细的说明，并易于理解,-,算法的安全性取决于密钥，不依赖于算法,-,算法适用于所有用户,-,算法适用于不同应用场合,-,算法必须高效、经济,-,算法必须能被证实有效,2024/11/25,3,1974,年,8,月,27,日,NBS,开始第二次征集，,IBM,提交了算法,LUCIFER,，该算法由,Feistel,领导的团队研究开发，采用,64,位分组以及,128,位密钥,IBM,用改版的,Lucifer,算法参加竞争，最后获胜，成为数据加密标准,(,Data Encryption Standard,DES),1976,年,11,月,23,日，采纳为联邦标准，批准用于非军事场合的各种政府机构。,1977,年,1,月,15,日，数据加密标准，即,FIPS PUB 46,正式发布,DES,是分组密码的典型代表，也是第一个被公布出来的加密标准算法。现代大多数对称分组密码也是基于,Feistel,密码结构,2024/11/25,4,DES,加密过程,DES,同时使用了,代换,和,置换,两种技巧,它用,56,位密钥加密,64,位明文，最后输出,64,位密文,整个过程分为两大部分组成：一是,加密过程,，另一是,子密钥产生过程,图,3.4,是,DES,加密算法简图,2024/11/25,5,2024/11/25,6,图,3.4,左半边,的处理过程可以分三个部分,：,(1)64,位明文经过初始置换被重新排列，然后分左右两半，每半各,32,位；,(2),左右两半经过,16,轮置换和代换迭代，即,16,次实施相同的变换。,然后再左右两半互换；,(3),互换后的左右两半合并，再经过逆初始置换输出,64,位密文。,图,3.4,右半部,则由,56,位密钥，产生,16,个,48,位子密钥，分别供左半边的,16,轮迭代加密使用,2024/11/25,7,初始置换,初始置换,(Initial Permutation,IP),是数据加密的第,1,步,将,64,位的明文按照图,3.5,置换。置换表中的数字表示输入位在输出中的位置,2024/11/25,8,置换后将数据,M,分成两部分：左半部分,L,0,和右半部分,R,0,各,32,位。划分方法原则是,偶数位移到左半部，奇数位移到右半部，即：,2024/11/25,9,DES,每轮结构,上一轮的右边,R,i,-1,直接变换为下一轮的左边,L,i,上一轮的左边,L,i,-1,与加密函数,F,异或后作为下一轮的右边,R,i,加密函数,F,则是上一轮右边,R,i,-1,和子密钥,K,i,的函数。即,L,i,=,R,i,1,R,i,=,L,i1,F,(,R,i,1,K,i,),2024/11/25,10,图,3.6 DES,每一轮结构,L,i,-1,R,i,-1,L,i,R,i,K,i,F,+,2024/11/25,11,加密函数,F,本质上是,R,i,-1,和子密钥,K,i,的异或,从图,3.6,可以看出加密函数,F,是,32,位，而,R,i,-1,是,32,位，子密钥,K,i,是,48,位，因此,R,i,-1,和,K,i,不能直接异或,DES,这样处理这个问题：,先用扩展置换,E(,如图,3.8,所示,),将,R,i,-1,扩展为,48,位，与,48,位子密钥异或，输出,48,位；,再使用,8,个,S,盒压缩成,32,位；,然后经置换函数,P(,如图,3.9,所示,),输出,32,位的加密函数,F,。,2024/11/25,12,加密函数,F,的计算过程,K,i,(48 bits),R,i,-1,(32 bits),48 bits,E,+,S,1,S,2,S,3,S,4,S,5,S,8,S,6,S,7,F,(32 bits),P,2024/11/25,13,图,3.8,扩展置换,E,图,3.9,置换函数,P,2024/11/25,14,S,盒,在加密函数计算过程中使用了,8,个,S,盒；,S,盒,是,DES,保密性的关键所在；,S,盒有,6,位输入，,4,位输出；,48,位数据经过,8,个,S,盒后输出,32,位数据,；,每个,S,盒,都由,4,行,(,表示为,0,1,2,3),和,16,列,(0,1,15),组成，如图,3.10,所示,2024/11/25,15,2024/11/25,16,每行都是全部的,16,个长为,4,比特串的一个全排列,每个比特串用它对应的二进制整数表示,如,1001,用,9,表示。,对每个,S,盒，将,6,位输入的第一位和最后一位组成一个二进制数，用于选择,S,盒中的一行。用中间的,4,位选择,S,盒,16,列中的某一列，行列交叉处的十进制数转换为二进制数可得到,4,位输出。,例如对于,S,1,盒而言,如果输入为,011001,，则行是,01(,十进制,1,，即,S,盒的第,2,行,),，列,1100(12,，即,S,盒的第,13,列,),，该处的值是,9,，转换为二进制数为,1001,，即为该,S,盒的输出,2024/11/25,17,DES,子密钥产生,DES,加密过程共迭代,16,轮，每轮用一个不同的,48,位子密钥,子密钥由算法的,56,位密钥产生,DES,算法的输入密钥长度是,64,位，但只用了其中的,56,位,如图,3.11,所示,图中无阴影部分，也就是每行的第,8,位被忽略，主要用于奇偶校验，也可以是随意设置,子密钥的产生过程如图,3.12,所示,2024/11/25,18,图,3.11 DES,的输入密码,2024/11/25,19,2024/11/25,20,56,位密钥首先经过置换选择,1(,如图,3.13,所示,),将其位置打乱重排,将前,28,位作为,C,0,(,如图,3.13,的上面部分,),，后,28,位,D,0,(,如图,3.13,的下面部分,),2024/11/25,21,接下来经过,16,轮，产生,16,个子密钥,每一轮迭代中,C,i,-1,和,D,i,-1,循环左移,1,位或者,2,位，如图,3.14,所示,C,i,-1,和,D,i,-1,循环左移后变为,C,i,和,D,i,，将,C,i,和,D,i,合在一起的,56,位，经过置换选择,2(,如图,3.15,所示,),，从中挑出,48,位作为这一轮的子密钥,再将,C,i,和,D,i,循环左移后，使用置换选择,2,产生下一轮的子密钥，如此继续，产生所有,16,个子密钥。,2024/11/25,22,图,3.14,每轮左移次数的规定,图,3.15,置换选择,2,2024/11/25,23,DES,解密,DES,解密过程与加密过程本质上一致,加密和解密使用同一个算法，使用相同的步骤和相同的密钥,主要不同点是将密文作为算法的输入，但是逆序使用子密钥,k,i,，即第,1,轮使用子密钥,k,16,，第,2,轮使用子密钥,k,15,，最后一轮使用子密钥,k,1,2024/11/25,24,DES,的强度,从发布时起，,DES,就备受争议,争论的焦点主要集中在密钥的长度、迭代次数以及,S,盒的设计等方面,DES,的安全性是依赖,S,盒,但是,S,盒设计详细标准至今没有公开,有人怀疑,S,盒里隐藏了陷门（,trapdoors,）。然而到目前为止也没有任何证据证明,DES,里确实存在陷门。事实上，后来表明,S,盒是被设计成能够防止差分密码分析,DES,是将,Lucifer,算法作为标准，,Lucifer,算法的密钥长度,128,位，但,DES,将密钥长度改为,56,位,这不能抵抗穷尽密钥搜索攻击,2024/11/25,25,1997,年，克罗拉多州的程序员,Verser,在,Inrernet,上数万名志愿者的协作下用,96,天的时间找到了密钥长度为,40,位和,48,位的,DES,密钥,1998,年电子边境基金会（,EFF,）使用一台价值,25,万美元的计算机在,56,小时之内破译了,56,位的,DES,1999,年，电子边境基金会（,EFF,）通过互联网上的,10,万台计算机合作，仅用,22,小时,15,分破译了,56,位的,DES,另外，,DES,存在,弱密钥,。如果一个密钥所产生的所有子密钥都是一样的，则这个外部密钥就称为弱密钥,DES,的密钥置换后分成两半，每一半各自独立移位。如果每一半的所有位都是“,0”,或者“,1”,，那么在算法的任意一轮所有的子密钥都是相同的,2024/11/25,26,三重,DES,DES,由于安全问题，美国政府于,1998,年,12,月宣布,DES,不再作为联邦加密标准,新的美国联邦加密标准是高级加密标准,(ASE),在新的加密标准实施之前，为了使已有的,DES,算法投资不浪费，,NIST,在,1999,年发布了一个新版本的,DES,标准（,FIPS PUB46-3,），该标准指出,DES,仅能用于遗留的系统，同时将三重,DES,（简写为,3DES,）取代,DES,成为新的标准,3DES,存在几个优点。首先它的密钥长度是,168,位，足以抵抗穷举攻击。其次，,3DES,的底层加密算法与,DES,的加密算法相同，该加密算法比任何其它加密算法受到分析的时间要长得多，也没有发现有比穷举攻击更有效的密码分析攻击方法,2024/11/25,27,但是双重,DES,不安全,双重,DES,存在中间相遇攻击，使它的强度跟一个,56,位,DES,强度差不多,如果,C,=,E,K,2,E,K,1,M,，令,X,=,E,K,1,M,=,D,K,2,C,。若已知,(,M,C,),，攻击方法如下：,-,先用,256,个可能的,K,1,加密,M,，得到,256,个可能的值，将这些值从小到大存入一个表中,-,再对,256,个可能的,K,2,解密,C,，每次做完解密，将所得的值与表中的值比较，如果产生匹配，则它们对应的密钥可能是,K,1,和,K,2,-,用一个新的明文密文对检测所得两个密钥，如果两密钥产生正确的密文，则它们是正确的密钥,2024/11/25,28,为防止中间相遇攻击，可以采用,3,次加密方式，如图,3.17,所示,这是使用两个密钥的三重,EDS,，采用加密,解密,加密,(E-D-E),方案,注意的是,加密与解密在安全性上来说是等价的。这种加密方案穷举攻击代价是,2,112,E,E,K,1,K,1,C,M,B,加密,解密,D,K,2,A,D,D,K,1,K,1,M,C,A,E,K,2,B,2024/11/25,29,目前还没有针对,两个密钥的三重,DES,实际的攻击方法,但是感觉它不大可靠，如果采用,三把密钥的三重,DES,则比较放心,三把密钥的三重,DES,的密钥长度是,168,位，采用,加密,解密,加密,(E-D-E),方案,其加密过程为,C,=,E,K,3,D,K,2,E,K,1,M,，解密过程为,M,=,D,K,1,E,K,2,D,K,3,C,这种加密方式,已经被一些网络应用采用,如本书后面章节要讨论的,PGP,和,S/MIME,采用了这种方案,2024/11/25,30,希望大家能学出好成绩,我们一起努力,!,谢谢大家,!,2024/11/25,31,