DES算法工作原理

1、3 DES算法的原理研究3.1 DES算法的产生与发展DES是在1970年代中期由美国IBM公司发展出来的，且被美国国家标准局（NBS）公布为数据加密标准的一种分组加密法。1972年，NBS制定了一个保护计算机和通信开发计划，准备开发一个标准的密码算法，来规范密码技术应用的混乱局面。1973年5月15日，NBS公开征集保密传输系统中计算机数据密码算法，由于此前公众对密码知识的缺乏，提交的方案均不理想。1974年8月27日，NBS再次发表征集公告，IBM公司提交了个良好的候选算法。该算法是LUCIFFER密码算法的改进，是由Host Feistel 1971年设计的。1975年3月17日，NBS

2、在联邦记事上公布了这一算法的细节。1981年，美国国家标准研究所批准DES作为私营部门的数据加密标准3。3.2 DES算法的基本原理3.2.1 DES算法的总结构DES是一个分组加密算法，它以64位为分组对数据加密，所用的加解密密钥也是64位大小，其中8个位用来做奇偶校验，所以实际用来加解密的密钥为56位。DES算法加密与解密所用的算法除了子密钥的顺序不同之外，其他的部分则是完全相同的。其加密/解密结构如图3.1所示。在结构图最上方的64位输入可以是明文也可以是密文，视加密或解密而定，加密与解密的不同之处在于最右面密钥的顺序不同，加密的子密钥顺序为K1，K2，K16，而解密的子密钥顺序为K16

3、，K15，K1。在进行加密或解密时，首先对输入的内容进行初始置换，然后分为L0和R0两部分，R0和子密钥K1进行f函数运算与L0异或后作为下一轮的R1，而R0作为下一轮的L1，如此运作16轮，再进行初始置换的逆置换，得到64位输出5。图 3.1 DES的加密/解密结构3.2.2 DES算法的基本运算（1） 初始置换IP和初始逆置换IP-1初始置换和初始逆置换为互逆运算，初始置换发生在加/解密运算前，初始逆置换发生在加/解密运算后。初始置换和初始逆置换的变换分别如表3.1和表3.2所示。这里表格的数字是指数据所在的位置。表3.1 初始置换IP585042342618102605244362820

4、12462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157表3.2 初始逆置换IP-140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2） E-扩展运算经过初始置换后，L0和R0分别为32位，而子密钥为48位，因此右部分输入数据要经过扩展运算后才能和子密钥进行异或操作。扩展运算首先

5、将32位数据分成8块，每块4位，然后将每个4位块扩展为6位块。扩展时，重复4位块的第一位和第四位，操作是块间交叉进行的，第一位和最后一位循环交叉，第二位和第三位原样定出。表3.3给出了扩展后输出位对应的输入位。表3.3 E-扩展运算3212345456789891011121312131415161716171819202120212223242524252627282928293031321（3） S盒运算S盒运算有8个S盒构成，每个S盒有6位输入，4位输出。每个S盒输入的第一位和最后一位组成一个2位的二进数用来选择S盒的行，剩下的中间四位用来选择S盒的列，选择的行和列的交叉位置对应的数即为

6、输出的十进制，转换后为4位二进制输出。其中具体S盒如表3.4所示。表3.4 S盒S11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S21518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S3100914631551131271142813709346102851412115113649815301112125101471101306987415

7、143115212S4713143069101285111241513811565034721211014910690121171315131452843150610113894511127214S5212417101168531513014914112124713150151039864211110137815912563014181271142136150910453S61211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S7411214150813312975106

8、1130117491101435122158614111312371410156805926111381410795015142312S81328461511110931450127115138103741256110149271141912142061013153582114741081315129035611（4）P-置换所有S盒的输出组成32位数据，P-置换是对这32位数进行变换，P-置换只进行简单置换不进行扩展和压缩。P-置换如表3.5所示。表3.5 置换函数P16172021291228171152326518311028241432273919133062211425在DES算法基

9、本运算中，其中E扩展运算、S盒和P置换又叫f函数，f函数是DES算法最重要的部分，数据加/解密基本上都属于f函数。3.2.3 子密钥生成器在整个DES算法中，输入的密钥为64位，而实际每一轮加/解密中所用到的密钥为48位子密钥，因此，在DES算法中，除了基本运算外还要有子密钥生成器，对密钥进行运算得到所用的子密钥。子密钥的生成过程如下：首先通过密钥置换表PC-1（表3.6）对64位密钥进行置换，去掉8位校验位留下真正需要的56位初始密钥。然后将初始密钥分为两个28位分组C0和D0，每个分组根据循环移位表（表3.7）循环1位或2位，得到C1和D1，C1和D1作为下一轮输入循环，同时C1和D1组成

10、56位数据作为置换PC-2（表3.8） 的输入，产生48位密钥K1，K2到K16采用相同的方法产生，子密钥生成算法如图3.2所示。表3.6 置换选择PC-157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124表3.7 循环移位函数轮数12345678910111213141516位数1122222212222221表3.8 置换选择PC-2141711241532815621102319124268167272013241523137475

11、5304051453348444939563453464250362932图3.2 子密钥生成算法3.3 DES算法的安全性分析DES运用了置换、替换、代数等多种密码技术，算法结构紧凑，条理清楚，而且加密与解密算法类似，便于工程实现。从DES诞生之日起，人们对它的安全性就争论不休，主要表现在以下几点。(1)弱密钥和半弱密钥所谓的弱密钥是指在所有可能的密钥中，有某几个特别的密钥，会降低DES的安全性，弱密钥产生的原因是由于子密钥产生过程的设计不当所导致的。由子密钥产生过程看，假设某个初始密钥经过密钥置换PC-1之后使C0和D0的内容成为全是0或全是1的数据。如此一来，不管以后的每一轮中如何变化，

12、产生的子密钥都是相同的，这样将大大降低DES的安全度。弱密钥的另外一个特性对弱密钥而言，其加密和解密的过程是一模一样的。DES加密和解密唯一的不同在于子密钥的使用顺序是相反的，对弱密钥而言，所有子密钥是相同的，所以加密和解密也就完全一样了。半弱密钥是指产生的子密钥只有两种可能，每一种可能的子密钥刚好出现8次。虽然DES存在有弱密钥和半弱密钥，但这并不是较大的安全问题，弱密钥和半弱密钥的数量与密钥总量相比是微不足道的。如果随机地选择密钥，那么选中这些弱密钥和半弱密钥的概率可以忽略不计。而且，也可以在密钥产生时进行检查，保证不使用弱密钥或半弱密钥作为DES的密钥。(2)S盒的设计准则S盒是DES加

13、密系统的重要部分，由于种种原因，在1990年以前S盒的设计准则一直没有公布，因此一些人猜测是否设计者故意在S盒设计上留下一些陷门，以便他们能轻易地破解出别人的密文，直到差分密码分析方法发表后S盒设计准则才公布，公布的S盒设计准则为如下几个。a.S盒的第一行是整数0，15的一个置换；b.一个S盒是它输入的线性或仿射函数；c.S盒的一个输入比特至少要引起两比特的输出改变；d.固定输入的最左边和最右边的2个比特，变换中间4个比特，每个可能的4比特输出只能得到一次；e.两个输入仅中间2个比特不同，则输出至少有2个比特不同；f.何一个S盒，如果两个输入的前两不同，而最后两位相同，两个输出必须不同；g.何

14、一个S盒，如果固定一个输入比特保持不变而使其他5比特输入变化，观察一个固定输出比特的值，使这个输出比特为D的输入的数目与使这个输出比特为I的输入的数目总数接近相等；h.相同且非零的差分的32对输入中，至多有8对具有相同的输出差分。目前为止，S盒的设计准则还没有完全公开，仍然不知道S盒的构造中是否使用了进一步的设计准则，这也使得人们的猜测无法得到消除，关于S盒的争议仍在继续。(3)密钥长度在对DES的安全性分析中，密钥长度是重要的一部分，DES的56位密钥面临的一个严峻而现实的问题是：国际互联网形成的分布式超级计算能力的攻击。1997年1月28日，美国RSA数据安全公司在Internet上开展了一个项“秘密密钥挑战”的比赛，悬赏一万美元来破解一段DES密文。竞赛发布后的第140天美国盐湖城的Micha