第3讲_分组密码DES

1、密密 码码 学学韦韦 宝宝 典典 副教授副教授 中山大学电子系分组密码标准分组密码标准DES安全保密亦要求安全保密亦要求标准化标准化只有标准化，才能真正实现网的只有标准化，才能真正实现网的安全安全， 才能才能推广使用推广使用加密手段，加密手段， 便于便于训练训练、生产生产和降低和降低成本成本。美国美国国家标准局国家标准局NBSNBS( (商业部国家标准技术研究所商业部国家标准技术研究所NIST的前身的前身) )1973年年5月月13日日 联邦记录联邦记录FR1973 征求用于保护政府部门非机密敏感数据的征求用于保护政府部门非机密敏感数据的加密算法加密算法 提供高质量的数据保护，防止数据未经授权

2、的泄露和未被察觉的修改；提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；相当高的复杂性，使破译开销超过可能获得的利益，同时便于理解和掌握；相当高的复杂性，使破译开销超过可能获得的利益，同时便于理解和掌握； 安全性应该不依赖于算法的保密，仅以加密密钥的保密为基础；安全性应该不依赖于算法的保密，仅以加密密钥的保密为基础； 实现经济，运行有效，并且适用于多种不同的应用。实现经济，运行有效，并且适用于多种不同的应用。导致了数据加密标准导致了数据加密标准DES(Data Encryption Standard)算法的研制。算法的研制。19751975年年3 3月月1717日日，NBSNBS

3、在联邦记录中在联邦记录中向社会宣布向社会宣布IBMIBM公司提交的公司提交的改进改进LuciferLucifer算法算法中选，中选，并征求公众的评论。并征求公众的评论。IBM公司公司从从60年代年代末末即看到通信网对于加密标准算法的即看到通信网对于加密标准算法的需求需求，投入了相当的投入了相当的研究力量研究力量开发，开发，成立了以成立了以Tuchman博士为领导的、研究博士为领导的、研究新密码体制的小组新密码体制的小组，H. Fistel进行设计，进行设计，并在并在1971年年完成的完成的LUCIFER密码密码改进成为建议的改进成为建议的DES体制、体制、NSA 组织有关专家对组织有关专家对I

4、BM的算法进行了鉴定，成为的算法进行了鉴定，成为DES。19771977年年1 1月月NBSNBS正式采纳此算法为数据加密标准，正式采纳此算法为数据加密标准，同年同年7 7月成为美国联邦信息处理标准月成为美国联邦信息处理标准FIPS-46FIPS-46。19801980年年美国国家标准协会美国国家标准协会ANSIANSI正式采用这个算法作为美国正式采用这个算法作为美国商用商用加密算法加密算法DEADEA。每隔五年，每隔五年，NSANSA都要对都要对DESDES进行评估，并重新审议它是否适合继进行评估，并重新审议它是否适合继续作为联邦加密标准。续作为联邦加密标准。19831983年年DESDES

5、经受第一次审核，仍被认定为一个好的标准。经受第一次审核，仍被认定为一个好的标准。19881988年年第二次审核后，第二次审核后，DESDES重新以重新以FIPS46-1FIPS46-1标准发布。标准发布。19931993年年，DESDES再次以再次以FIPS46-2FIPS46-2标准发布。标准发布。在最后的在最后的FIPS46-3FIPS46-3标准中，标准中，EDEEDE模式模式( (加密加密- -解密解密- -加密加密) )的三重的三重DESDES成为提供更高安全级别的替代算法。成为提供更高安全级别的替代算法。19981998年年美国政府终于决定不再继续延用美国政府终于决定不再继续延用D

6、ESDES作为联邦加密标准，作为联邦加密标准，DESDES退出加密标准的舞台退出加密标准的舞台。 DES算法的颁布引起了算法的颁布引起了学术界学术界和和企业界企业界的广泛重视。的广泛重视。20多年来，多年来，DES已经在世界范围内成为已经在世界范围内成为事实上的加密标准事实上的加密标准， 一直作为分组密码设计的一直作为分组密码设计的标准参照物标准参照物。 学术界学术界对对DES密码进行了深入的研究，密码进行了深入的研究， 围绕它的围绕它的安全性安全性和和破译方法破译方法展开了激烈的争论，展开了激烈的争论， 这在一定意义上对密码学的理论研究起了这在一定意义上对密码学的理论研究起了推动作用推动作用

7、。DES出色地顶住了年复一年、形形色色的密码分析，出色地顶住了年复一年、形形色色的密码分析， 其其精巧的设计精巧的设计至今仍闪烁着人类思想的精华，至今仍闪烁着人类思想的精华， 其其结构和部件结构和部件仍被后人效仿。仍被后人效仿。虽然虽然DES没能长期地作为数据加密标准算法，没能长期地作为数据加密标准算法，但它仍是迄今为止得到但它仍是迄今为止得到最广泛应用最广泛应用的一种算法，的一种算法，也是一种也是一种最有代表性最有代表性的分组加密体制。的分组加密体制。详细地研究这一算法的基本原理、设计思想、安全性分析详细地研究这一算法的基本原理、设计思想、安全性分析以及实际应用中的有关问题，以及实际应用中的

8、有关问题，对于掌握分组密码对于掌握分组密码理论理论和当前的和当前的实际应用实际应用都很有意义。都很有意义。DES 算法算法明文分组长度：明文分组长度：64 bits 密文分组长度：密文分组长度：64 bits密钥分组长度：密钥分组长度：64bits/56 bits初始置换初始置换IP16轮迭代的乘积变换迭代的乘积变换逆初始置换逆初始置换IP-116个子密钥产生器IP和和IPIP-1-1作用在于作用在于打乱打乱原来输入原来输入x x的的ASCII码字划分的关系，码字划分的关系，并将原来明文的并将原来明文的校验位校验位x8, x16, x64变成为变成为IP输出的输出的一个字节一个字节。在密码意义

9、上在密码意义上作用不大作用不大，因为输入组因为输入组x x与其输出组与其输出组y y=IP(x x) (或或IP-1(x x)是已知的是已知的一一对应一一对应关系。关系。初始置换初始置换IP和和逆初始置换逆初始置换IP-1初始置换初始置换IP和和逆初始置换逆初始置换IP-1 Li-1(32bit) Ri-1(32bit) 选择扩展运算选择扩展运算 E 48 bit寄存器寄存器 按按bit模模2加密加密 48 bit寄存器寄存器 选择压缩运算选择压缩运算 S 32 bit寄存器寄存器 置换运算置换运算 P 按按bit模模2和和 Li (32bit) Ri (32bit)乘积变换框图乘积变换框图密

10、钥产生器密钥产生器乘积变换乘积变换乘积变换乘积变换DES: Function fExpansion: 32 48S-box: 6 4Permutation: P将输入的将输入的32 bit Ri-1扩展成扩展成48 bit的输出，的输出，原原下标下标s 0或或1(mod 4)的各比特重复一次的各比特重复一次得得到的，即对原第到的，即对原第32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29各位都重复一次各位都重复一次,实实现数据扩展。现数据扩展。将表中数据按行读出得到将表中数据按行读出得到48 bit输出。输出。1 6 bit 选选

11、 择择 函函 4 bit 数数 组组 选择压缩运算选择压缩运算S 48 bit 寄存器寄存器32 bit 寄存器寄存器S1S2S3S4S5S6S7S8S-Box第第1、6比特组成二进制数确定行，比特组成二进制数确定行，中间中间4位二进制数用来确定的列。位二进制数用来确定的列。S1S1输入输入101001， 行数行数11，列数列数0100第第3行第行第4列十进制数列十进制数为为2 2：0010 输出为输出为0010 置换运算置换运算P P 对对S1至至S8盒输出的盒输出的32 bit数据进行坐标置换数据进行坐标置换子密钥产生器：子密钥产生器：将64 bit初始密钥经过置换选择置换选择PC1PC1

12、、循环循环移位置换、置换选择移位置换、置换选择PC2PC2给出每次迭代加密用的子密钥ki， 密钥（密钥（64 bit ）置换选择置换选择1，PC1置换选择置换选择2，PC2 Ci(28 bit) Di(28 bit) 循环左移循环左移ti+1bit 循环左移循环左移ti+1bit除去第除去第8,16, ,64位位(8个校验位个校验位)ki k1 （ 56 位 ） (48 位 ) ki （ 56 位 ） （ 48 位 ） 64 位 密 钥 置 换 选 择 1 C0（ 28 位 ） D0（ 28 位 ） 循 环 左 移 循 环 左 移 C1（ 28 位 ） D1（ 28 位 ） 循 环 左 移 循

13、 环 左 移 Ci（ 28 位 ） Di（ 28 位 ） 置 换 选 择 2 置 换 选 择 2 密 钥 表 的 计 算 逻 辑 循 环 左 移 ： 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1 为什么为什么是这几是这几个个1、2呢？呢？ 密钥（密钥（64 bit ）置换选择置换选择1，PC1置换选择置换选择2，PC2 Ci(28) Di(28) 循环左移循环左移 循环左移循环左移ki加密过程加密过程: :运算进行运算进行16次后就得到密文组次后就得到密文组 L0R0 IP(64 bit 输入输入)

14、 i=1,., 16 LiRi-1 RiLi-1 f(Ri-1, ki) 64 bit密文密文IP-1 (R16L16)解密过程解密过程:DES的加密运算是可逆的，其解密过程可类似地进行的加密运算是可逆的，其解密过程可类似地进行 R16L16 IP(64 bit密文密文) i=16,. , 1 Ri-1 Li Li-1Ri f(Li-1, ki) 64 bit明文明文IP-1 (R0L0) QUESTION f 函数中的函数中的S盒为盒为6 x 4的多对一映射，的多对一映射， S盒无法求逆，如何做逆向加密过程盒无法求逆，如何做逆向加密过程/解密？解密？ANSWER 无论是在加密过程中还是在解密

15、过程中使用的都是正无论是在加密过程中还是在解密过程中使用的都是正向的向的f 函数，逆向的函数函数，逆向的函数f-1从未被使用过，因而不存在从未被使用过，因而不存在S盒的求逆问题盒的求逆问题(S盒无须设计成可逆的盒无须设计成可逆的)！ 见见PPT第第24、12页。页。DES 安全性安全性安全性 DES的安全性完全依赖于所用的密钥。的安全性完全依赖于所用的密钥。 从从DES诞生起，对它的安全性就有激烈的争论，一直延续到现在。诞生起，对它的安全性就有激烈的争论，一直延续到现在。互补性互补性 对对y=DESk(x)，若明文组，若明文组x逐位取补得，密钥逐位取补得，密钥k逐位取补得，则有逐位取补得，则有

16、 这种互补性会使这种互补性会使DES在在选择明文破译下所需的工作量减半选择明文破译下所需的工作量减半。)(xDESyk由于各轮密钥是通过改变初始密钥得到由于各轮密钥是通过改变初始密钥得到(参见第参见第21页图页图)，因此当初始值分成两部分，每部分都是因此当初始值分成两部分，每部分都是0或都是或都是1时，时，那么算法的每一周期的密钥是相同的。那么算法的每一周期的密钥是相同的。这样的这样的弱密钥弱密钥共有共有4种：全种：全1，全，全0，先全，先全1后全后全0，先全，先全0后全后全1。相当于只有一个子密钥，而不是相当于只有一个子密钥，而不是16个。个。还有一些密钥只会产生两个不同的子密钥，而不是还有

17、一些密钥只会产生两个不同的子密钥，而不是16个不同的密钥。个不同的密钥。这样就造成两个不同的密钥会有相同的加密结果。这样就造成两个不同的密钥会有相同的加密结果。这种情况一共有这种情况一共有6对：对：01FE 01FE 01FE 01FE 和和 FE01 FE01 FE01 FE01;1FE0 1FE0 0E1F 0E1F 和和 E01F E01F F10E F10E;01E0 01E0 01F1 01F1 和和 E001 E001 F101 F101;1FFE 1FFE 0EFE 0EFE 和和 FE1F FE1F FE0E FE0E;011F 011F 010E 010E 和和 1F01 1

18、F01 0E01 0E01;E0FE E0FE F1FE F1FE 和和 FEE0 FEE0 FEF1 FEF1.上述上述“密钥对密钥对”他们对明文加密的结果是相同的。他们对明文加密的结果是相同的。同理，只有同理，只有4个子密钥的有个子密钥的有64个个 弱密钥和半弱密钥弱密钥和半弱密钥 DES 安全性若若k为弱密钥，则有为弱密钥，则有 DESk(DESk(x)=x ; DESk-1(DESk-1(x)=x即以即以k对对x加密两次或解密两次都可恢复出明文加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。其加密运算和解密运算没有区别。而对一般密钥只满足而对一般密钥只满足 DESk-1

19、(DESk(x)=DESk(DESk-1 (x)=x弱密钥下使弱密钥下使DES在选择明文攻击下的在选择明文攻击下的搜索量减半搜索量减半。 如果随机地选择密钥，则在总数如果随机地选择密钥，则在总数256个密钥中，弱密钥所占比例极小，个密钥中，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性的安全性 发现发现DES至少有至少有4个弱密钥，个弱密钥，12个半弱密钥个半弱密钥弱密钥和半弱密钥弱密钥和半弱密钥 DES算法在每次迭代时都有一个子密钥供加密用 如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2= =k1

20、6 就称给定密钥k为弱密钥弱密钥(Weak key)。DES 安全性密文与明文、密文与密钥的相关性密文与明文、密文与密钥的相关性 Meyer1978详细研究了详细研究了DES的输入明文与密文及密钥与密文之间的相关性。的输入明文与密文及密钥与密文之间的相关性。 表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出 达到这一要求所需的达到这一要求所需的迭代次数至少为迭代次数至少为5。 Konheim1981用用 2检验证明，检验证明，迭代迭代8次次后输出和输入就可认为是不相关的了。后输出和输入就可认为是不相关的了。S

21、S盒设计盒设计 DES靠靠S盒实现盒实现非线性变换非线性变换。1992年证明了年证明了“DES不成群不成群”的事实；的事实；各种各样的密码分析方法、思想各种各样的密码分析方法、思想 差分密码分析差分密码分析、线性密码分析线性密码分析 的提出，的提出， 可以说是现代分组密码可以说是现代分组密码分析史上的重大突破分析史上的重大突破密钥搜索机密钥搜索机 对对DES安全性批评意见中，较为一致的看法是安全性批评意见中，较为一致的看法是DES的密钥的密钥短短了些。了些。 IBM最初提交的建议方案采用最初提交的建议方案采用112 bits密钥，但公布密钥，但公布DES标准采用标准采用64bits密钥。密钥。

22、 有人认为有人认为NSA故意故意限制限制DES的密钥长度。的密钥长度。DES 安全性56比特密钥太短，已抵挡不住穷尽密钥搜索攻击比特密钥太短，已抵挡不住穷尽密钥搜索攻击密钥量为密钥量为256=7.21016= 72,057,594,037,927,936 1017(千万亿千万亿)个个若要对若要对DES进行密钥搜索破译，进行密钥搜索破译，分析者在得到一组明文分析者在得到一组明文-密文对条件下，可密文对条件下，可 对明文用对明文用不同的密钥加密不同的密钥加密， 直到得到的密文与已知的明文直到得到的密文与已知的明文-密文对中的相符。密文对中的相符。密钥搜索所需的时间取决于密钥搜索所需的时间取决于 密

23、钥空间的大小密钥空间的大小 执行执行一次加密一次加密所需的时间。所需的时间。 若假定若假定DES加密操作需时为加密操作需时为100 s(一般微处理器能实现一般微处理器能实现)， 则搜索整个密钥空间需时为则搜索整个密钥空间需时为7.21015秒，近似为秒，近似为2.28108年。年。 若以最快的若以最快的LSI器件，器件，DES加密操作时间可降到加密操作时间可降到5 s， 也要也要1.1104年才能穷尽密钥。年才能穷尽密钥。DES的破译分析的破译分析借助差分密码分析的思想借助差分密码分析的思想1993年年Wiener给出一个给出一个密钥搜索机密钥搜索机的详细设计方案，的详细设计方案，估计估计10

24、0万美元万美元制造一台机器，搜索一个密钥平均大约花制造一台机器，搜索一个密钥平均大约花3.5小时小时1997年年1月月28日日，RSA数据安全公司数据安全公司 在在RSA安全年会上安全年会上 悬赏悬赏一万美金一万美金 破译密钥长度为破译密钥长度为56比特的比特的DES算法。算法。美国克罗拉多州的程序员美国克罗拉多州的程序员Verser从从1997年年3月月13日起，日起，用了用了96天的时间，在天的时间，在Internet上数万名志愿者的协同工作下，上数万名志愿者的协同工作下，于于1997年年6月月17日用日用穷尽密钥搜索方法穷尽密钥搜索方法成功地找到了成功地找到了DES的密钥。的密钥。1998年年7月月17日日，电子边境基金会，电子边境基金会EFF使用一台使用一台25万美元万美元的电脑通的电脑通过穷尽密钥搜索方法在过穷尽密钥搜索方法在56小时内小时内破解了破解了56比特比特DES。1999年年的的RSA会议期间，穷尽密钥搜索时间减少到不足会议期间，穷尽密钥搜索时间减少到不足24小时小时。 DES的破译分析的破译分析事件表明：事件表明：依靠依靠Internet分布式的计算能力分布式的计算能力， 用用穷尽密钥搜索穷尽密钥搜索攻击方法攻击方法 破译破译DES已成为可能。已成为可能。早在早在19931993年年，政府就意识到，政