数据加密标准概述37570

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数据加密标准,（,Data Encryption Standard,DES,),序列密码和分组密码,一次只对明文中的单个位（有时对字节）运算的算法称,为序列算法（stream algorithm）或序列密码（stream cypher）,另一类算法是对明文的一组位进行运算，这些位称,为分组（block）,，相应的算法称,为分组算法（block algorithm）或分组密码（block cypher）。,背景,发明人：美国IBM公司 W.Tuchman 和 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日生效,背景,美国国家安全局（,NSA,National Security Agency,)参与了,美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位,1979年，美国银行协会批准使用DES,1980年，DES成为美国标准化协会(ANSI)标准,1984年2月，ISO成立的数据加密技术委员会(SC20),在DES基础上制定数据加密的国际标准工作,DES,概述,分组加密算法：明文和密文为,64,位分组长度,对称算法：加密和解密除密钥编排不同外，使用同一算法,采用混乱和扩散的组合，每个组合先替代后置换，共,16,轮,只使用了标准的算术和逻辑运算，易于实现,密钥长度：,56,位（,密钥通常表示位,64,位，但第8位、16位第64位都用作奇偶校验,）产生,16,个,48,位的子密钥,Shannon,乘积密码,设有两个子密码系统,T,1,和,T,2,，则先以,T,1,对明文进行加密，然后再以,T,2,对所得结果进行加密。其中，,T,1,的密文空间需作为,T,2,的“明文”空间。乘积密码可表示成,T,=,T,1,T,2,利用这两种方法可将简单易于实现的密码组合成复杂的更为安全的密码。,扩散（diffusion）和混乱（confusion）,扩散：,就是将明文的统计特性迅速散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，即密文中每一位受明文中多位影响；将密钥的每位数字尽可能扩散到更多个密文数字中去，以防止对密钥进行逐段破译。根据扩散原则，分组密码应设计成明文的每个比特与密钥的每个比特对密文的每个比特都产生影响。,混乱：,的目的在于使明文和密文之间的统计关系变得尽可能复杂。使用复杂的,非线形代换,算法可得预期的混淆效果。,Feistel网络,很多分组密码的结构从本质上说都是基于一个称为,Feistel网络,的结构。,Feistel,提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行,多个基本密码系统,，使得最后结果的密码强度高于每个基本密码系统产生的结果。,Feistel网络,一层结构,取一个长度为,n,的分组（n为偶数），然后把它分为长度为,n/2,的两部分：,L和R,。定义一个迭代的分组密码算法，其第,i,轮的输出取决于前一轮的输出：,L,（i）,=R,（i-1）,R,（i）,=L,（i-1）,f（R,（i-1）,，K,（i）,）,K,（i）,是i轮的子密钥，f是任意轮函数。,容易看出其逆为：,R,（i-1）,=L,（i）,L,（i-1）,=R,（i）,f（R,（i-1）,，K,（i）,）,=R,（i）,f（L,（i）,，K,（i）,）,L,（i-1）,R,（i-1）,Feistel网络,DES,工作原理,基于Feistel网络,假定信息空间都是由,0，1,组成的字符串，信息被分成,64,比特的块，密钥是,56,比特。经过DES加密的密文也是,64,比特的块。设用m表示信息块，k表示密钥，则：,m=m,1,m,2,m,64,m,i,=0或1,k=k,1,k,2,k,64,k,i,=0或1,其中k,8,，k,16,，k,24,，k,32,，k,40,，k,48,，k,56,，k,64,是奇偶校验位，真正起作用的仅为56位。,加密算法：,E,k,（m）=IP,-1,T,16,T,15,T,1,IP（m）,其中IP为初始置换，IP,-1,是IP的逆，T,i,是一系列的变换。,解密算法：,m=E,k,-1,E,k,（m）,=IP,-1,T,1,T,2,T,16,IPE,k,（m）,输入64比特明文数据,初始置换IP,在密钥控制下,16轮迭代,初始逆置换IP,-1,输出64比特密文数据,DES加密过程,DES加密过程,令,i,表示迭代次数，,表示逐位模2求和，,f,为加密函数,DES解密过程,DES算法实现过程,（1）,初始变换,IP,移位操作：仅对,64,比特明文,(8*8),进行操作,列经过偶采样和奇采样置换后再对各行进行逆序得到,IP,57 58 59 60 61 62 63 64,IP,57 58 59 60 61 62 63 64,一轮DES,L,i-,1,（32比特）,R,i-,1,（32比特）,L,i,（32比特）,48比特寄存器,选择扩展运算E,48比特寄存器,子密钥,K,i,（48比特）,32比特寄存器,选择压缩运算S,置换运算P,R,i,（32比特）,L,i,=,R,i-,1,DES算法实现过程,（2）,选择扩展运算,选择运算E，输入32位数据，产生48位输出。,设B,（i）,=b,1,（i）,b,2,（i）,b,64,（i）,是第i+1次迭代的64个二进制位输入区组，将B,（i）,分为左右两个大小相等的部分，每部分为一个32位二进制的数据块,：,L,（i）,=l,1,（i）,l,2,（i）,l,32,（i）,=b,1,（i）,b,2,（i）,b,32,（i）,R,（i）,=r,1,（i）,r,2,（i）,r,32,（i）,=b,33,（i）,b,34,（i）,b,64,（i）,分别表示为,84 86,扩展置换-盒,32位扩展到48位,扩展,DES算法实现过程,（3）,使用密钥,在第i+1次迭代中，用48位二进制的密钥（由56位密钥生成）,K,（i+1）,=k,1,（i+1）,k,2,（i+1）,k,48,（i+1）,与E（R,（i）,）按位相加（逻辑异或），输出仍是48位，,86,DES算法实现过程,（4）,选择函数（,压缩替代S-盒）,48位压缩到32位,S-盒1,S-盒2,S-盒3,S-盒4,S-盒5,S-盒6,S-盒7,S-盒8,S-盒实现,S-盒是算法的关键所在,DES中其它算法都是线性的，而S-盒运算则是非线性的。,S-,盒不易于分析，它提供了更好的安全性。,提供了密码算法所必须的混乱作用。,DES算法实现过程,（5）,选择函数输出的拼接与换位,X,（i）,=f（R,（i）,，K,（i+1）,）,p-盒的构造准则,P置换的目的是提供雪崩效应,明文或密钥的一点小的变动都引起密文的较大变化,DES算法实现过程,（6）,一轮输出,把L,（i）,与X,（i）,按位相加，形成R,（i+1）,，且令R,（i）,为L,（i+1）,，即得到经第i+1次迭代加密后的输出,L,（i+1）,=R,（i）,R,（i+1）,=L,（i）,f（R,（i）,，K,（i+1）,）,（i=0，1，2，15）,可以看出，DES密码体制的每一次迭代都用替代法和换位法对上一次迭代的输出进行加密变换。用硬件实现DES算法时，实际上,用替代盒实现替代函数S,j,（1j8），用换位盒实现换位函数P,。,为了使最后输出的密码文与原始输入的明码文没有明显的函数关系，DES算法采用16次迭代。在前15次迭代中，L,（i）,表示左32位，R,（i）,表示右32位。对最后一次迭代，L,（16）,表示右32位，R,（16）,表示左32位，即在,最后一次迭代时不再左右交换,，以保证加密和解密的对称性。,DES算法实现过程,（7）,逆初始变换,用IP,-1,表示，它和IP互逆。例如，第1位经过初始置换后，处于第,58,位，而通过逆置换，又将第,58,位换回到第1位。,IP,IP,1,DES,中的子密钥的生成,密钥置换算法的构造准则,设计目标：子密钥的统计独立性和灵活性,实现简单,速度,不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系),种子密钥的所有比特对每个子密钥比特的影响大致相同,从一些子密钥比特获得其他的子密钥比特在计算上是难的,没有弱密钥,DES,三重DES,为了增加密钥的长度，人们建议将一种分组密码进行级联，在不同的密钥作用下，连续多次对一组明文进行加密，通常把这种技术称为,多重加密技术,。对DES，建议使用3DES增强加密强度。3DES可以用两个密钥对明文进行三次加密，假设两个密钥是K1和K2：,（1）用密钥K1进行DES加密。,（2）用K2对步骤1的结果进行DES解密。,（3）对（2）的结果使用密钥K1进行DES加密。,3DES的缺点是加、解密速度比DES慢。,三重DES Triple-DES,加密：C=E,k1,D,k2,E,k1,(P),解密：P=D,k1,E,k2,D,k1,(C),DES的安全性,F,函数(S-Box)设计原理未知,密钥长度的争论,DES的,破译,弱密钥与半弱密钥,DES密钥长度,关于,DES,算法的另一个最有争议的问题就是担心实际,56,比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个,早在,1977,年，,Diffie,和,Hellman,已建议制造一个每秒能测试100万个密钥的,VLSI,芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要,2000万,美元,DES密钥长度,在,CRYPTO93,上，,Session,和,Wiener,给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以,16,次加密能同时完成。花费,10万,美元，平均用,1.5,天左右就可找到,DES,密钥,美国克罗拉多洲的程序员,Verser,从,1997,年2月,18,日起，用了,96,天时间，在,Internet,上数万名志愿者的协同工作下，成功地找到了,DES,的密钥，赢得了悬赏的,1,万美元,DES密钥长度,1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES,1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥,破译DES,1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击,线性密码分析比差分密码分析更有效,演讲完毕，谢谢观看！,