DES算法的实现及安全性分析

DES算法的实现及安全性分析专业班级：计算机科学与技术1班姓名：廖孜孜学号：120103011126完成日期：2015年5月17日2引言如果一个密码体制的加密密钥等于脱密密钥，或者其中一个很容易推出另一个，则称此密码体制为单密钥密码体制，也称为对称密码体制或传统密码体制。最具有代表性的近代传统密码体制是DES（数据加密标准）。为了适应社会对计算机数据安全保密越来越高的要求，美国国家标准局（NBS）于1973年向社会公开征集一种用于政府部门及民间进行计算机数据加密算法，许多公司提出了自己的加密算法，最后选中了IBM公司提出的一种加密算法。经过一段时间的试用与征求意见，美国国家标准局于1977年公布了由IBM公司研制的一种加密算法，批准把它作为非机要部门使用的数据加密标准，简称DES，DES是DataEncryptionStandard的缩写。自从公布以来，它一直超越国界成为国际上商用保密通信和计算机通信的最常用的加密算法。原先规定使用期10年，可能是DES尚未受到严重的威胁，更主要的是新的数据加密标准还没有完成，或意见未一致，所以当时的美国政府宣布延长它的使用期。因而DES超期服役了很长时间，20年来它一直活跃在国际上保密通信的舞台上，扮演了十分突出的角色。进入20世纪九十年代后以色列的密码学家Shamir等人提出了一种“差分分析法”，以后日本人又提出类似的方法，这才正式有一种称得上对它的攻击的方法。严格地说，Shamir的“差分分析法”也只有理论上的价值，至少目前为止是这样的。又如，后来的“线性逼近法”，它是一种已知明文攻击法，需要2的43次方也就是4.398×10的12次方对明文-密文对，在这样强的要求条件下，有十多台工作站协同作战，还需要十天的时间。在这以前已有人建议造专用装置来对付它，其基本想法无非是借用硬件来实现对所有密钥的遍历搜索。当时估计一天可以搜索到一个密钥。技术的进步使得搜索的时间进一步缩短，使DES受到了威胁，但DES毕竟辉煌过。它的思想还是值得借鉴。DES算法概述DES是一个对称算法：加密和解密用的是同一算法（除密钥编排不同以外），既可用于加密又可用于解密。它的核心技术是：在相信复杂函数可以通过简单函数迭代若干圈得到的原则下，利用F函数及对合等运算，充分利用非线性运算。DES以64位为分组对数据加密。每组64位，最后一组若不足64位，以“0”补齐。密钥通常表示为64位的数，但每个第8位都用作奇偶校验，可以忽略，所以密钥的长度为56位，密钥可以是任意的56位的数，且可在任意的时候改变。其中极少量的数被认为是弱密钥，但能容易地避开它们，所有的保密性依赖于密钥。DES算法的基本思想DES对64位的明文分组进行操作。通过一个初始置换，将明文分组分成左半部分（L0）和右半部分(R0)，各32位长。R0与子密钥K1进行F函数的运算，输出32位的数，然后与L0执行异或操作得到R1,L1则是上一轮的R0,如此经过16轮后，左、右半部分合在一起，经过一个末置换（初始置换的逆置换），这样该算法就完成了。DES算法剖析DES算法的加密由四部分完成，分别为：初始置换函数IP、子密钥的生成、密码函数F、末置换函数。初始置换函数IP接受长度为64位的明文输入，末置换函数IP一1输出64位的密文。在子密钥的获取过程中，通过密钥置换Pc—l获取从Kl到K16共16个子密钥，这16个子密钥分别顺序应用于密码函数的16次完全相同的迭代运算中。3DES的解密算法与加密算法完全相同，只需要将密钥的应用次序与加密时相反应用即可。即解密过程是初始置换函数IP接受长度为64比特的密文输入，将16个子密钥按照K16到K1的顺序应用与函数F的16轮迭代运算中，然后将迭代的结果经由末置换函数IP．1得到64位的明文输出。DES算法运算过程DES主要采用置换和移位运算来实现加解密，接下来深入剖析DES每个部分运算的实现过程。（1）初始置换函数IP64位的明文分组x首先经过一个初始置换函数IP进行置换运算，产生一个64位的输出x0，该输出被分成两个分别为32位的左半部分L0和右半部分RO，用于F函数的16轮迭代运算的首次迭代的初始输入。初始置换函数IP实际上就是一张8x8(8行8列)的迭代表，如表I所示。明文分组中的64位按照表中的规定重新进行排序，其排列顺序为从左到右，从上到下。按表I所示，明文中的第58位被放置在xO的第1位，第50位防止在第2位，依次类推。IP:初始置换表（2）获取子密钥Ki子密钥的获取主要通过置换和移位运算来实现。DES加密算法的密钥长度为56位，由用户提供，是DES算法的输入之一。但用户输入的密钥是64位的，按8行8列从左到右从上到下地排列，其中，每行的第8位用于奇偶校验。在DES加密算法中，子密钥获取过程中，DES经过一系列的置换和移位运算，得到Kl到K16共16个子密钥，每个子密钥长48位。其实现过程如下：首先将输入的64位密钥去掉最后一列的8个校验位，然后用密钥置换函数PC-l对剩下的56位密钥进行置换。585042342618102605244362820124625446383022146645648403224168574941332517915951433527191136153453729211356355473931231574PC-1：用户输入的64位密钥中，第8、16、24、32、40、48、56、64共8个校验位被去掉。剩余的56位按表2所示排放：第57位放在第1位，第49位放在第2位，依次类推。经过PC-l置换后，将其置换的输出再分为前28位C0和后28位D0和两部分，上一轮置换得到的输出的两部分经过循环左移I位或2位后，每轮按表3进行移位，然后将两部分合并成56位，之后经过压缩置换PC-2后得到当前这轮置换的48位子密钥。根据轮数，Ci和Di分别经过LSi循环左移1位或2位。16次循环左移的位数依据下列规则进行：每轮移动的位数压缩置换PC-2PC-2置换为压缩置换，即置换后的输出数据的位数要比置换前输入的位数要少，即某些位的数据在置换的过程中被去掉了。由表4可知，在压缩置换过程中，原来的7行8列共58位数据被压缩成8行6列的48位数据。在压缩置换过程中，第9、18、22、25、35、38、43、54共8位数据被丢掉。同时，将上一轮移位后得到的两部分再按上面的每轮移动的位数进行移位，作为下一个子密钥产生的PC-2置换的输入。依次经过16次循环左移和16次置换得到16个子密钥。子密钥的产生流图：57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124迭代顺序12345678910111213141516左移位数112222221222222114171124153281562110231912426816727201324152313747553040514533484449395634534642503629325（3)DES的迭代过程DES算法有16次迭代，迭代如图所示。从图中可得到Li=Ri-1，Ri=Li-1⊕F(Ri-1,Ki),i=1,2,3…15,16。K1K1664位密钥PC-1C0D0LS1LS1C1D1PC-2LS16LS16C16D16PC-256位密钥子密钥的产生6F函数的实现原理是将Ri-1进行扩展置换后其结果与Ki进行异或，并把输出内容执行S盒替代与P盒转换后得到F(Ri-1,Ki),其原理如下所示。TIPL0R1=L0○+f(R0,k1)L15=R11R0R16=L15○+f(R15,k16)L16=R15R2=L1○+f(R1,k2)R15=L11○+f(R11,k15)L1=R0L2=R1fffIP-1DES第16圈的加密过程k11k2k37扩展置换也叫做E盒，它将数据右半部分从32位扩展到48位，改变了位的次序，重复了某些位,比原输入长了16位，数据位仍取决于原输入。扩展置换的48位输出按顺序分成8组，每组6位，分别输入8个S子盒，每个子盒输出4位，共32位。假设将S盒的6位的输入标记为b1、b2、b3、b4、b5、b6，则b1和b6组合构成了一个2位的数，从0到3，它对应着S表中的一行。从b2到b5构成了一个4位的数，从0到15，对应着表中的一列，行列交汇处的数据就是该S盒的输出。每个S盒可被看作一个4位输入的代替函数：b2到b5直接输入，输出结果为4位，b1和b6位来自临近的分组，它们从特定的S盒的④个代替函数中选择一个。这是该算法的关键步骤，所有其他的运算都是线性的，易于分析，而S盒是非线性的，它比DES其他任何一步提供了更好的安全性。P盒转换是把每个输入位映射到输出位，任意一位不能被映射两次，也不能被略去。(4)末置换E:P：将(3)中8个6位数据的置换结果连在一起，形成一个32位的输出，输出结果再通过一个P盒置换产生一个32位的输出。P盒置换如上表所示。最后，P盒置换的结果与左半部分进行异或运算，然后将左右两半部分交换。之后进入下一轮迭代。在完16720212912281711523265183110282414322739191330622114253212345456789891011121312131415161716171819202120212223242524252627282928293031321F(Ri-1,Ki)S1S2S3S4S5S6S7S8扩展置换Ki(48位)Ri-1(32位)48位P盒转换32位F函数的功能结构8成完全相同的16轮运算后，将得到的两部分数据合在～起，再经过一个末置换函数IP-1即可得到64位的密文。IP-1：DES的主要解密成果DES的安全性完全依赖于所用的密钥，自从DES作为标准起，人们对它的安全性就有激烈的争论，下面简要介绍20年来对DES的一些主要研究成果。（1）互补性DES具有性质：若明文组x逐位取补得x—密钥k逐位取补得k—，且y=DESk(x),则y—=DESk(x—)，其中y—是y的逐位取补。这种特征称为算法上的互补性。这种互补性表明在选择明文攻击下仅需试验其可能的256个密钥的一半255个即可。另外，互补性告诫人们不要使用互补密钥。（2）弱密钥和半弱密钥大多数密码都有明显的“坏”密钥，DES也不例外。若DESk（·）=DESk-1（·），即如果k确定的加密函数与解密函数一致，则称k是一个弱密钥。DES至少有4个弱密钥，因为在产生密钥时，初始密钥被分成了两半，每半各自独立的移位，如果每一半的所有位都是0或1，那么密钥方案中的所有密钥都是相同的，即k1=k2=...=k16，这样DESk（·）=DESk-1（·）。易知，这样的情况至少有4种可能，很可能不存在其它弱密钥。若存在一个不同的密钥k＇使DESk＇（·）=DESk-1（·），则称k是一个半弱密钥。此时我们也称密钥k和k＇是对合的。半弱密钥的特点是成对地出现。DES至少有12个半弱密钥，因为产生C0=[1010...10]和D0=[00...0]或[11...1]或[1010...10]或[0101...01]的密钥与产生C0=[0101...01]和D0=[00...0]或[11...1]或[0101...01]或[1010...10]的密钥时互为对合的，同样地与C0=[0101...01],D0=[1010...10]或D0=[0101...01]的密钥也是互为对合的，这样就至少有(4×4＋4×2)／2=12个半弱密钥，好像不存在另外的半弱的密钥。弱密钥和半弱密钥直接引起的唯一“危险”是对多重加密，当选用弱密钥时，第二次加密使第一次加密复原。如果随机地选择密钥，则在总数256个密钥中，弱密钥和半弱密钥所占的比例极小，因此，弱密钥和半弱密钥的存在不会危及到DES的安全性。408481656246432397471555236331386461454226230375451353216129