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轮轮的输出取决于前一轮的输出：的输出取决于前一轮的输出
8、：nL（i）=R（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）n Feistel网络网络DES工作原理工作原理 基于基于Feistel网络网络n假定信息空间都是由假定信息空间都是由0，1组成的字符串，信息被分组成的字符串，信息被分成成64比特的块，密钥是比特的块，密钥是56比特。经过比特。经过DES加密的密文加密的密文也是也是64比特的块。设用比特的块。
9、设用m表示信息块，表示信息块，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在密钥控制下在
10、密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES加密过程加密过程DES加密过程加密过程)(6416,2,1),(16,2,1)64(1616111100LRIPbitikRfLRiRLbitIPRLiiiiii密文输入码令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程DES算法实现过程算法实现过程 （1）初始变换初始变换IP移位操作：仅对64比特明文(8*8)进行操作n列经过偶采样和奇采样置换后再对各行进行逆序得到列经过偶采样和奇采样置换后再对各行进行逆序得到IP57 58 59 6
11、0 61 62 63 642014MMIP57 58 59 60 61 62 63 64一轮一轮DESLi-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）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次迭代的
12、次迭代的64个二进制个二进制位输入区组，将位输入区组，将B（i）分为左右两个大小相等的部分，每部分为左右两个大小相等的部分，每部分为一个分为一个32位二进制的数据块位二进制的数据块：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（
13、i+1）n与E（R（i）按位相加（逻辑异或），输出仍是48位，86DES算法实现过程算法实现过程 （4）选择函数（选择函数（压缩替代压缩替代S-盒）盒）n48位压缩到位压缩到32位位S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒实现盒实现1 2 3 4 5 61 6262 3 4 521133 911001110019bbbbbbbbSbbbb行：-盒子 行 列列：值：14=1100S-盒是算法的关键所在盒是算法的关键所在nDES中其它算法都是线性的，而S-盒运算则是非线性的。nS-盒不易于分析，它提供了更好的安全性。n提供了密码算法所必须的混乱作用。DES算法实现过程
14、算法实现过程 （5）选择函数输出的拼接与换位选择函数输出的拼接与换位 X（i）=f（R（i），K（i+1）p-盒的构造准则盒的构造准则P置换的目的是提供雪崩效应置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引起密文的较大变化DES算法实现过程算法实现过程 （6）一轮输出一轮输出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可以看
15、出，DES密码体制的每一次迭代都用替代法和换位法对上一次迭代的输出进行加密变换。用硬件实现DES算法时，实际上用替代盒实现替代函数用替代盒实现替代函数Sj（1j8），用换位盒实现换位函数），用换位盒实现换位函数P。为了使最后输出的密码文与原始输入的明码文没有明显的函数关系，DES算法采用16次迭代。在前15次迭代中，L（i）表示左32位，R（i）表示右32位。对最后一次迭代，L（16）表示右32位，R（16）表示左32位，即在最最后一次迭代时不再左右交换后一次迭代时不再左右交换，以保证加密和解密的对称性。DES算法实现过程算法实现过程 （7）逆初始变换逆初始变换 n用IP-1 表示，它和IP互
16、逆。例如，第1位经过初始置换后，处于第58位，而通过逆置换，又将第58位换回到第1位。2014MM1420MMIPIP1 k1 （56 位）(48 位)ki （56 位）（48 位）64 位 密 钥置 换 选 择 1 C0（28 位）D0（28 位）循 环 左 移循 环 左 移 C1（28 位）D1（28 位）循 环 左 移循 环 左 移 Ci（28 位）Di（28 位）置 换 选 择 2置 换 选 择 2密 钥 表 的 计 算 逻 辑循 环 左 移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1DES中的子密钥的
17、生成中的子密钥的生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：不存在简单关系：(给定两个有某种关系的种子密钥给定两个有某种关系的种子密钥,能预测它们轮子密能预测它们轮子密钥之间的关系钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥nDES三重三重DES n为了增加密钥的长度，人们建议将一种分组密码进行级
18、联，在不同的密钥作用下，连续多次对一组明文进行加密，通常把这种技术称为多重加密技术多重加密技术。对DES，建议使用3DES增强加密强度。3DES可以用两个密钥对明文进行三次加密，假设两个密钥是K1和K2：n（1）用密钥K1进行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)设计原理未知设计原理未知 密钥长度的
19、争论密钥长度的争论 DESDES的的破译破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DES算法的另一个最有争议的问题就是担心实际算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有有 个个 早在早在1977年，年，Diffie和和Hellman已建议制造一个每秒能测已建议制造一个每秒能测试试100100万个密钥的万个密钥的VLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计
20、制造这样的机器大约需要制造这样的机器大约需要2000万万美元美元1756102DES密钥长度密钥长度在在CRYPTO93上，上，Session和和Wiener给出了一个非常详细给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以钥搜索芯片，所以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet
21、上数万名志愿者的协同工作下，成上数万名志愿者的协同工作下，成功地找到了功地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）使用一台）使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据安全会议期间，电子前沿基金会用数据安全会议期间，电子前沿基金会用2222小小时时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色
22、列密码学家年，以色列密码学家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个不同的密钥个不同的密钥 即：即：()kkpE E P12()()kkC E PE P
