DES算法详细介绍

1973年5月15日，美国国家标准局（现在美国国家标准技术研究所（NIST）在联邦注册报上发表一则启事，公开征集用来保护传输和静止存储中的计算机数据的密码算法，这一举措最终导致了数据加密标准DES的出现。DES采用分组乘积密码体制，它是由IBM开发，是对早期被称为Lucifer密码体制的改进。DES在1975年3月17日首次在联邦记录中公布，而且声明对比算法征求意见。到1977年2月15日拟议中的DES被采纳为“非密级”应用的一个联邦标准。最初预期DES作为一个标准只能使用10~15年，然而，出于种种原因，可能是DES还没有受到严重的威胁，事实证明了DES要长寿得多。在其被采用后，大约每隔5年被评审一次。DES的最后一次评审是在1999年1月。但是，随着计算机计算能力的提高，由于DES的密钥过短，仅有56位，对DES的成功攻击也屡见报端。例如：1999年1月，RSA数据安全公司宣布：该公司所发起的对56位DES的攻击已经由一个称为电子边境基金（EFF）的组织，通过互联网上的100000台计算机合作在22小时15分钟内完成。在这种情况下，对于替代DES的要求日益增多。最终，NIST于1997年发布公告，征集新的数据加密标准作为联邦信息处理标准以代替DES。新的数据加密标准称为AES，关于AES的讨论将放在后面的4.5节。尽管如此，DES的出现是现代密码学历史上非常重要的事件。它对于我们分析掌握分组密码的基本理论与设计原理仍然具有重要的意义。4.1.1DES算法描述DES是一个16轮的Feistel型结构密码，它的分组长度为64比特，用一个56比特的密钥来加密一个64比特的明文串，输出一个64比特的密文串。其中，使用密钥为64比特，实用56比特，另8位用作奇偶校验。加密的过程是先对64位明文分组进行初始置换，然后分左、右两部分分别经过16轮迭代，然后再进行循环移位与变换，最后进行逆变换得出密文。加密与解密使用相同的密钥，因而它属于对称密码体制。图4-3给出了DES过程框图。假设输入的明文数据是64比特。首先经过初始置换IP后把其左半部分32比特记为L0，右半部分32比特记为R0，即成了置换后的输入；然后把R0与密钥产生器产生的子密钥k1进行运算，其结果计为f(R0,k1);再与L0进行摸2加得到L0○+f(R0,k1),把R0记为L1放在左边，而把L0○+f(R0,k1)记为R1放在右边，从而完成了第一轮迭代运算。在此基础上，重复上述的迭代过程，一直迭代至第16轮。所得的第16轮迭代结果左右不交换，即L15○+f(R15,k16)记为R16,放在左边，而R15记为L16放在右边，成为预输出，最后经过初始置换的逆置换IP-1运算后得到密文。下面详细介绍DES加密过程中的基本运算：（1）DES中的初始置换IP与初始逆置换IP-1表4-1给出了初始置换IP与初始逆置换IP-1。对于要加密的明文串64比特，初始置换IP把原来输入的第58位置换为第1位，原输入的第50位置换为第2位，……,把原输入的第7位置换为第64位，即最后一位。同样的初始置换是以预输出作为它的输入，该置换的输出以预输出块的第40位作为它的第1位，……,而以25位作为它的最后一位。图4-3DES框图表4-1初始置换IP与初始逆置换（2）密码函数f函数f:{0,1}32{0,1}48{0,1}32的输入是一个32比特串(当前状态的右半部)和子密钥。密钥编排方案),...,,(3221kkk由16个48比特的子密钥组成，这些子密钥由56比特的种子密钥k导出。每个ki都是由k置换选择而来（子密钥的产生过程将在后面详细说明）。图4-4给出了函数f的示意图。它主要包含一个应用S盒的替代以及其后跟随的一个固定置换P。密码函数f是整个加密的关键部分，它包含了如下四种功能：i)扩展函数E扩展函数E的功能就是将一个32位的输入块扩展为48位的输出块，而这48位的输出块再分成8个6位的块。它是按照表4-2依次选择它所输入中的位而取得的。从表4-2可知，E(R)的前面3位是R的32，1，2位置上的值，而E(R)的最后2位是R的32，1位的值。RkE(R)○+○EB1B2B3B4B5B6B7B8B1B1B1B1B1B1S2S111S5S111S4S111S3S111S6S111S7S111S8S111S1C1C2C3C4C5C6C7C8○Pf(R,k)图4-4DES的f函数ii)模2加法模2加功能就是将E(R)的各个位与密钥k的各位逐位作模2加，以得到输出bi,具体运算如下：),...,,()(3221aaaERE13132132,...,,aaaaaa'48'3'2'1,...,aaaa48,...2,1,''ikabiii表4-2E比特选择表3212345456789891011121312131415161716171819202120212223242524252627282928293031321iii)S盒运算在密码函数f(R,k)中有8个S盒，称为8个不同的选择函数，分别用),...,,(821SSS表示，参见表4-3。每个S盒都是将6位作为输入，得到一个4位块作为输出。以S1为例，若B是6位的一个块，则S1(B)计算如下：B的第一和最后一位表示从0到3之间的二进制数，令该数为i；而B的中间4位表示从0到15之间的二进制数，令该数为j；在该表S1中查第i行j列的数，它是从0到15之间的一个数，且唯一地由4位块代表，则该块就是输入B的S1的输出S1(B)例如对于输入为101000而言，行是10，即第2行。而列是由0100确定，即第5列，S1盒的第2行与第5列的交叉处即为B，因而输出为1101，因此1101就是S盒S1在输入为101000时的输出。在f(R,k)的计算中，它将由模2加运算得到的4821,...,,bbb按每6个一组共分为8组，顺序记为821,...,,BBB它们分别经过8个选择函数Si运算变成3221,...,,CCC即S1(B1)S2(B2)…S8(B8)=3221,...,,CCCiv)置换函数P置换函数P是通过输入块的位，从32位输入中得到32位的输出。置换函数P由表4-4给出。由该表确定的函数P的输出P(C)，是通过C的第16位为P(C)的第1位，取第7位为P(C)的第2位，……,取第25为P(C)的第32位。表4-3S-盒表4-4置换函数P现在我们就令821,...,,SSS为8个不同的选择函数，P为置换函数，E为扩展函数。为了计算f(R,k)，先规定821,...,,BBB每个为6位块，且821,...,,BBB=k○+E(R),于是有f(R,k)=)](),...,()([882211BSBSBSP因此，在f(R,k)的计算中将k○+E(R)分成8个块，即每块6位（即Bi）,然后每个Bi取作Si的一个输入就得到每个都为4位的8个块Si(Bi)(i=1,2,…,8)的输出，再将此8块连接成32位的整块。这个整块就构成了P的输出，经P置换，即为f(R,k)的输出。（3）子（轮）密钥的生成过程在DES中，每一轮迭代都使用了一个轮密钥。轮密钥是从用户输入的密钥k（64位）产生的。实用密钥是56位，另8位是奇偶校验位：输出密钥k的第8,16,…,64位为奇偶校验位（每一字节的最后一位），这些位的值使得每个字节恰好包含了奇数个1，这样如果输入密钥中某个字节中存在一个错误，奇偶校验可以帮助查到这些错误。图4-5给出了子密钥的生成示意图，具体的子密钥生成过程描述如下：1）输入的密钥k先经过一个置换（称为“置换选择1”）进行重排。置换结果（56位）被当成两个28比特的量C0与D0,其中C0是置换结果的前28位，而D0是置换结果的后28位。图4-5子密钥的生成置换选择1如表4-5所示。注意到，在置换选择1中不出现第8，16，24，32，40，48，6，4位，因此实际64位的密钥k在经过置换选择1后，奇偶校验位被删除掉而仅保留下有效的56位密钥。置换选择1与初始置换IP的含义类似。例如，置换结果C0的第7位是输入密钥k的第9位，而置换结果D0的第10位是输入密钥的第54位。表4-5置换选择12）在计算第i轮迭代所需要的子密钥时，首先对Ci-1与Di-1进行循环左移，分别得到Ci与Di。循环的次数取决于i的值：如果i=1，2，9和16，循环左移的次数是1；否则循环左移的次数等于2。这些经过移位的值将作为下一个循环的输入。然后，以CiDi作为另外一个由DES算法固定的置换选择（称为“置换选择2”）的输入，所得到的置换结果即为第i轮迭代所需要的子密钥ki。表4-6置换选择2表4-6给出了置换选择2，它表示从56比特（即Ci与Di）选择出48位进行输出。前面说过，DES的解密过程与加密过程共用了同样的计算过程。两者的不同之处仅在于解密时子密钥ki的使用顺序与加密时相反。如果加密的子密钥k1，k2,…,k16,那么，解密时子密钥的使用顺序为与k16，k15,…,k1。即：用DES解密时，将以64位密文作为输入，第一轮迭代使用子密钥k16；第二轮迭代使用子密钥k15,…,第16轮迭代使用子密钥k1,其他运算与加密时一样，最后输出的便是64位明文。严格说来，DES中解密过程的正确性是由Feistel密码结构的性质决定的。读者可以回顾一下，以便得到DES加密过程与解密过程互逆性的证明。