数据加密标准论述35871.pptx

《数据加密标准论述35871.pptx》由会员分享，可在线阅读，更多相关《数据加密标准论述35871.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据加密标准数据加密标准（Data Encryption Standard,DES)序列密码和分组密码序列密码和分组密码n一一次次只只对对明明文文中中的的单单个个位位（有有时时对对字字节节）运运算算 的的 算算 法法 称称 为为 序序 列列 算算 法法（stream algorithm）或或 序序 列列 密密 码码（stream cypher）n另另一一类类算算法法是是对对明明文文的的一一组组位位进进行行运运算算，这这些些位位称称为为分分组组（block），相相应应的的算算法法称称为为分分组组算算法法（block algorithm）或或分分组组密密码码（block cypher）。）。背景背

2、景发明人：美国发明人：美国IBM公司公司 W.Tuchman 和和 C.Meyer 1971-1972年研制成功年研制成功基础：基础：1967年美国年美国Horst Feistel提出的理论提出的理论产生：美国国家标准局（产生：美国国家标准局（NBS)1973年年5月到月到1974年年8月两次发布通告，月两次发布通告，公公开开征征求求用用于于电电子子计计算算机机的的加加密密算算法法。经经评评选选从从一一大大批批算算法法中中采采纳纳 了了IBM的的LUCIFER方案方案标准化：标准化：DES算法算法1975年年3月公开发表，月公开发表，1977年年1月月15日由美国国家日由美国国家标准局颁布为数

3、据加密标准（标准局颁布为数据加密标准（Data Encryption Standard），于），于1977年年7月月15日生效日生效背景背景美国国家安全局（美国国家安全局（NSA,National Security Agency)参与了参与了美国国家标准局制定数据加密标准的过程。美国国家标准局制定数据加密标准的过程。NBS接受了接受了NSA的某些建议，对算法做了修改，并将密钥长度从的某些建议，对算法做了修改，并将密钥长度从LUCIFER方方案中的案中的128位压缩到位压缩到56位位1979年，美国银行协会批准使用年，美国银行协会批准使用DES1980年，年，DES成为美国标准化协会成为美国标准

4、化协会(ANSI)标准标准1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会(SC20)在在DES基基础上制定数据加密的国际标准工作础上制定数据加密的国际标准工作DES概述概述分组加密算法：明文和密文为分组加密算法：明文和密文为64位分组长度位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法对称算法：加密和解密除密钥编排不同外，使用同一算法采用混乱和扩散的组合，每个组合先替代后置换，共采用混乱和扩散的组合，每个组合先替代后置换，共16轮轮只使用了标准的算术和逻辑运算，易于实现只使用了标准的算术和逻辑运算，易于实现密钥长度：密钥长度：56位（位（密钥通常表示位

5、密钥通常表示位64位，但第位，但第8 8位、位、1616位位第第6464位都用作奇偶校验位都用作奇偶校验）产生）产生16个个48位的子密钥位的子密钥Shannonn乘积密码乘积密码 设有两个子密码系统设有两个子密码系统T1和和T2，则先以，则先以T1对明文进行加密，然对明文进行加密，然后再以后再以T2对所得结果进行加密。其中，对所得结果进行加密。其中，T1的密文空间需作为的密文空间需作为T2的的“明文明文”空间。乘积密码可表示成空间。乘积密码可表示成 T=T1T2 利用这两种方法可将简单易于实现的密码组合成复杂的更为利用这两种方法可将简单易于实现的密码组合成复杂的更为安全的密码。安全的密码。扩

6、散（扩散（diffusion）和混乱（）和混乱（confusion）n扩扩散散：就是将明文的统计特性迅速散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，即密文中每一位受明文中多位影响；将密钥的每位数字尽可能扩散到更多个密文数字中去，以防止对密钥进行逐段破译。根据扩散原则，分组密码应设计成明文的每个比特与密钥的每个比特对密文的每个比特都产生影响。n混混乱乱：的目的在于使明文和密文之间的统计关系变得尽可能复杂。使用复杂的非非线线形形代代换换算法可得预期的混淆效果。Feistel网络网络 很很多多分分组组密密码码的的结结构构从从本本质质上上说说都都是是基基于于一一个个称称为为Feist

7、el网网络络的的结结构构。Feistel提提出出利利用用乘乘积积密密码码可可获获得得简简单单的的代代换换密密码码，乘乘积积密密码码指指顺顺序序地地执执行行多多个个基基本本密密码码系系统统，使使得得最最后后结结果果的的密密码码强强度度高高于于每每个个基本密码系统产生的结果。基本密码系统产生的结果。Feistel网络网络 一层结构一层结构 取取一一个个长长度度为为n的的分分组组（n为为偶偶数数），然然后后把把它它分分为为长长度度为为n/2的的两两部部分分：L和和R。定定义义一一个个迭迭代代的的分分组组密密码码算算法法，其其第第i轮轮的输出取决于前一轮的输出：的输出取决于前一轮的输出：nL（i）=R

8、（i-1）nR（i）=L（i-1）f（R（i-1），K（i）K（i）是是i轮的子密钥，轮的子密钥，f是任意轮函数。是任意轮函数。容易看出其逆为：容易看出其逆为：nR（i-1）=L（i）nL（i-1）=R（i）f（R（i-1），K（i）=R（i）f（L（i），K（i）L（i-1）R（i-1）nFeistel网络网络DES工作原理工作原理 基于基于Feistel网络网络n假假定定信信息息空空间间都都是是由由0，1组组成成的的字字符符串串，信信息息被被分分成成64比比特特的的块块，密密钥钥是是56比比特特。经经过过DES加加密密的的密密文文也是也是64比特的块。设用比特的块。设用m表示信息块，表示信

9、息块，k表示密钥，则：表示密钥，则：nm=m1m2m64 mi=0或或1 nk=k1k2k64 ki=0或或1 其其中中k8，k16，k24，k32，k40，k48，k56，k64是是奇奇偶偶校验位，真正起作用的仅为校验位，真正起作用的仅为56位。位。n加密算法：加密算法：Ek（m）=IP-1T16T15T1IP（m）其其中中IP为为初初始始置置换换，IP-1是是IP的的逆逆，Ti是是一一系系列列的的变换。变换。n解密算法：解密算法：nm=Ek-1 Ek（m）=IP-1T1T2T16IPEk（m）输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初

10、始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES加密过程加密过程DES加密过程加密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程DES算法实现过程算法实现过程 （1）初始变换初始变换IP移位操作：仅对64比特明文(8*8)进行操作n列经过偶采样和奇采样置换后再对各行进行逆序得到列经过偶采样和奇采样置换后再对各行进行逆序得到IP57 58 59 60 61 62 63 64IP57 58 59 60 61 62 63 64一轮一轮DESLi-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特

11、）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES算法实现过程算法实现过程 （2）选择扩展运算选择扩展运算n选择运算选择运算E，输入，输入32位数据，产生位数据，产生48位输出。位输出。n设设B（i）=b1（i）b2（i）b64（i）是是第第i+1次次迭迭代代的的64个个二二进进制制位位输输入入区区组组，将将B（i）分分为为左左右右两两个个大大小小相相等等的的部部分分，每每部部分为一个分为一个32位二进制的数据块位二进制的数据

12、块：nL（i）=l1（i）l2（i）l32（i）=b1（i）b2（i）b32（i）nR（i）=r1（i）r2（i）r32（i）=b33（i）b34（i）b64（i）n分别表示为分别表示为84 86扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展DES算法实现过程算法实现过程 （3）使用密钥使用密钥n在第i+1次迭代中，用48位二进制的密钥（由56位密钥生成）nK（i+1）=k1（i+1）k2（i+1）k48（i+1）n与E（R（i）按位相加（逻辑异或），输出仍是48位，86DES算法实现过程算法实现过程 （4）选择函数（选择函数（压缩替代压缩替代S-盒）盒）n48位压缩到位压缩到32

13、位位S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒实现盒实现S-盒是算法的关键所在盒是算法的关键所在nDES中其它算法都是线性的，而S-盒运算则是非线性的。nS-盒不易于分析，它提供了更好的安全性。n提供了密码算法所必须的混乱作用。DES算法实现过程算法实现过程 （5）选择函数输出的拼接与换位选择函数输出的拼接与换位 X（i）=f（R（i），K（i+1）p-盒的构造准则盒的构造准则P置换的目的是提供雪崩效应置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引起密文的较大变化DES算法实现过程算法实现过程 （6）一轮输出一轮输出

14、n把把L（i）与与X（i）按按位位相相加加，形形成成R（i+1），且且令令R（i）为为L（i+1），即得到经第，即得到经第i+1次迭代加密后的输出次迭代加密后的输出nL（i+1）=R（i）nR（i+1）=L（i）f（R（i），K（i+1）（i=0，1，2，15）n可以看出，DES密码体制的每一次迭代都用替代法和换位法对上一次迭代的输出进行加密变换。用硬件实现DES算法时，实际上用用替替代代盒盒实实现现替替代代函函数数Sj（1j8），用用换换位位盒盒实实现现换换位位函函数数P。为了使最后输出的密码文与原始输入的明码文没有明显的函数关系，DES算法采用16次迭代。在前15次迭代中，L（i）表示左3

15、2位，R（i）表示右32位。对最后一次迭代，L（16）表示右32位，R（16）表示左32位，即在最最后后一一次次迭迭代代时时不不再再左左右右交交换换，以保证加密和解密的对称性。DES算法实现过程算法实现过程 （7）逆初始变换逆初始变换 n用IP-1 表示，它和IP互逆。例如，第1位经过初始置换后，处于第58位，而通过逆置换，又将第58位换回到第1位。IPIP1DES中的子密钥的生成中的子密钥的生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：不存在简单关系：(给定两个有某种关系的种子密

16、钥给定两个有某种关系的种子密钥,能预测它们轮子密能预测它们轮子密钥之间的关系钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥nDES三重三重DES n为了增加密钥的长度，人们建议将一种分组密码进行级联，在不同的密钥作用下，连续多次对一组明文进行加密，通常把这种技术称为多多重重加加密密技技术术。对DES，建议使用3DES增强加密强度。3DES可以用两个密钥对明文进行三次加密，假设两个密钥是K1和K2：n（1）用密钥K

17、1进行DES加密。n（2）用K2对步骤1的结果进行DES解密。n（3）对（2）的结果使用密钥K1进行DES加密。n3DES的缺点是加、解密速度比DES慢。三重三重DES Triple-DESn加密：加密：C=Ek1Dk2 Ek1(P)n解密：解密：P=Dk1Ek2 Dk1(C)DES的安全性的安全性 F F函数函数(S-Box)(S-Box)设计原理未知设计原理未知 密钥长度的争论密钥长度的争论 DES DES的的破译破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DES算法的另一个最有争议的问题就是担心实际算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御

18、穷举式攻击，因为密钥量只比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有有 个个 早在早在1977年，年，Diffie和和Hellman已建议制造一个每秒能测已建议制造一个每秒能测试试100100万个密钥的万个密钥的VLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要制造这样的机器大约需要2000万万美元美元DES密钥长度密钥长度在在CRYPTO93上，上，Session和和Wiener给出了一个非常详细给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于

19、并行运算的密的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以钥搜索芯片，所以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet上数万名志愿者的协同工作下，成功上数万名志愿者的协同工作下，成功地找到了地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFE

20、FF）使用一台）使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据安全会议期间，电子前沿基金会用数据安全会议期间，电子前沿基金会用2222小小时时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色列密码学家年，以色列密码学家Eli BihamEli Biham和和Adi ShamirAdi Shamir提出了差提出了差分密码分析法，可对分密码分析法，可对DESDES进行选择明文攻击进行选择明文攻击线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥（弱密钥（weak key）半弱密钥（半弱密钥（semiweak key）弱密钥弱密钥:E EK K E EK K=I=I ，DESDES存在存在4 4个弱密钥个弱密钥 所有子密钥相同所有子密钥相同 即：即：半弱密钥半弱密钥:E EK1K1=E=EK2K2 ，至少有，至少有1212个半弱密钥个半弱密钥 只产生只产生2 2个不同的密钥个不同的密钥 即：即：