数据加密标准DES.doc

数据加密标准DES1977年1月，美国政府将IBM研制的一种乘积密码宣布为国家的数据加密标准。这个标准的确立刺激了很大一批厂商去实现加密算法的硬件化，以提高处理速度。这种密码术的核心是乘积变换，在硬件产业中常常简称为 DES（Data Encryption Standard）。这样一来，由于可以得到便宜高速的硬件，所以反过来也鼓励了许多其他用户采纳DES。1DES算法描述现在我们来说明DES算法，它的过程如图92所示。对明文按64位分组，每组明文经初始排列（第1步），通过子密钥K1-K16进行16次乘积变换（第2步），再通过最终排列（第3步）得到64位密文。图9-2 DES算法过程图16次乘积变换的目的是使明文增大其混乱性和扩散性，使得输出不残存统计规律，使破译者不能从反向推算出密钥。第1步：初始排列（IP）IP（Initial Permutation）取排数据的方法如表9-2所示，其中的数据表示明文的位标（164）。例如，58指该组明文中的第58位，50指该组明文中的第50位，其他类推。第l步初始排列的目的是将明文的顺序打乱。表92 初始排列法（IP）例12-1明文X=0123456789ABCDEF（十六进制形式），写成二进制形式，共64位：X=0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111经过初始排列（IP）后，结果变成：1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010即写成十六进制形式是：CC00CCFFFOAAFOAA。第2步：乘积变换把通过第1步得出的64位一分为二，用L0表示前32位，R0表示后32位，那么在上例中有：L0CC00CCFF R0FOAAFOAA其16次乘积变换的过程可以用图93表示。其中K1K16为16次变换所采用的密钥。每一个密码函数 f（Ri-1，Ki）（i 1，16）都是通过3个子过程（扩展置换，压缩代换，P排列）得到的。由于16次变换过程是类似的，我们只要对其中的一个展开讨论就行了。在上面的例子中，我们不妨看一下i=1（第1次变换）的情况。其具体过程如图9-4所示。图9-3 16乘积变换过程（1）扩展置换扩展置换又称E（Expand）函数，是一个与密钥无关的纯移位变换，它把32位扩展成48位。将32位分成4位一组，共8组，记作a 1(1)a4(1), a1(2)a4(2),a1(8)a4(8) 。每组扩展成6位，共48位，记作b1(1)b6(1), b1(2)b6(2),b1(8)b6(8) 。其扩展公式可以表示成：当j=l时,有bl(1)=a4(8)，j=8时有b6(8)=a1(1)，也就是：图9-4 第1次变换的过程例12-1中，R0=F0AAF0AA，经过扩展置换就变成了：把扩展置换的结果与子密钥进行异或，16个子密钥的顺序是第i次变换用子密钥Ki。我们不妨先假设子密钥K1=0B02679B49A5，则7A15557A1555 0B02679B49A5=711732E15CF0。（2）压缩替换压缩替换也称压缩编码（compressed encoding），通过压缩替换将输入的48位变换为32位输出，其主要方法是利用替换盒（substitution box），简称S盒。S盒是指这样的函数，它把6个输入位映射为4个输出位。作为一个密码表，它是由015组成的4行16列的随机数表，此密码表就是S盒。一个S盒中有4个替换表（行编号为0，1，2，3）。因为48位分成6位一组，共分8组，故应有8个不同的S盒，记为S1，S2 ，S8，它们的构成见表9-3。表9-3 S盒的构成我们以Sl为例来看一看如何由6位生成4位。把输入6位中的头尾两位合起来构成的两位二进制数表示行数，中间4位二进制数表示列数，在S1盒中查找对应的数，该数化成二进制形式就是输出的4位。如果输入为101100，那么在Sl中查到2行6列所对应的数为2，即0010，故其输出的4位为0010，可写成或写成。整个压缩替换可用图95表示。图9-5 压缩替换前面的例子经第1子过程后，得711732E15CF0H（48位），分成011100，010001，011100,110010，111000，010101，110011和110000 8个组，经压缩替换后得到：即经压缩替换的结果是用十六进制表示的0C216D50，或32位二进制。（3） P排列P排列也称换位表变换，将压缩替换后得到的32位按表94所示顺序重新排列的32位，即密码函数。表9-4 P排列在前面的例子中，经压缩替换后的32位是：0000 1100 0010 0001 0110 1101 0101 0000即有：故 。最后，得到Ll、Rl后，再重复上述乘积变换（共16次），得L16、R16组成64位。第3步：最终排列它是初始排列的逆变换，即（IP）1，其排列顺序可用表9-5示意。联合R16L16，共64位，经（IP）1操作后就能得到该组的密文。表95 （IP）12DES算法密钥的生成过程取64位作为初始密钥（或称主密钥），每8位中有1位奇偶检验位，故主密钥实质上只有56位，经过排列选择1，简称PC1（PC是permutation choose的缩写），分成C0和D0两部分，各28位。将C0、D0各循环左移1位得到C 1、D1，再经过排列选择2（PC2）得到了密钥K1；对C1、D1；作循环左移位后得到C2、D2，经过PC2得到子密钥K2；直到产生子密钥K16，其过程如图96所示。图96 密钥生成过程其中LSi表示第i次循环左移的位数。初始密钥K去掉第8，16，24，32，40，48，56，64位后余下56位，对这56位 通过PC1作重新排列，用以确定C0的顺序如下：用以确定D0的顺序如下：其中的顺序号均指初始密钥K的位置标号。由Ci、Di经循环左移位后得到Cil、Dil，为了保证经16次移位后能恰好循环移动28位，使C16=C0、D16=D0， 故各次的移位数不全相等，具体的移位数LSi在表9-6中给出。表96 左移位数表为了更清楚地说明密钥生成过程，我们把经PC1处理后得到的C0、DO，经LS 1次循环左移后的C1、Dl，经LS2次循环左移后的C2、D2，经 LS3次循环左移后的C3、D3的情况列在表97中，表的第1行表示C、D的位标，表的第2行以后 的数都是初始密钥K中的位标，其值只能是0或1。表9-7 CiDi变化表图9-6中的PC2是从56位（Ci，Di）中重新排列选择出48位的子集，该子集就是初始密钥K的子密钥Ki，PC2的置换表如下。表中的数值是C、D的位标。对Ci、 Di通过PC2处理就产生Ki（去掉Ci、Di的第 9、 18、22、25、35、38、43、54位后的重新排列）。为了使Ki与初始密钥K的位标相对应，表98给出K1 、K2、K3与 Ci、Di的位标及K的位标的对应表，其中第1行是Ki的位标，从l到48；第2行是PC2的选择，其数值是Ci、Di的位标，从1到56； 第3行开始的数值是初始密钥K中的位标，从l到63。当然，子密钥Ki的最后值只是由0和1组成的一个48位的二进制序列。类似地，也有K4K16与Ci、Di的位标及K的位标的对应关系。 由主密钥K产生密钥K1K16的全过程也可以用图9-7来表示。表9-8 位标对应表图9-7 由主密钥K产生密钥K1一K16的全过程例12-2 取密钥K（64位）K = 0000 0001 * 0010 0011 * 0100 0101 * 0110 0111 * 1000 100l * 1010 1011 * 1100 110l * 1110 1111 *其中标上*号的位是奇偶校验位。去掉校验位后经过PC1选择得C0、D0（56位），分别为：C0 = 1111 0000 1100 1100 1010 1010 0000D0 = 1010 1010 1100 1100 1111 0000 0000循环左移LS1（=1）位后得C1、D1：C1 1110 0001 1001 1001 0101 0100 0001D1 0101 0101 1001 1001 1110 0000 0001C1、D1经 PC2选择后得K1（48位）如下：K1 0000 1011 0000 0010 0110 0111 1001 1011 0100 1001 1010 0101用十六进制形式书写，有K1 = 0B02679B49A5。因为Ki是由主密钥通过一些指定的移位、排列选择得到的，因此只要对用户给出主密钥即可。3解密运算由于模2加法的特性和最终排列与初始排列的可逆性，解密运算与加密运算一样，只是所取子密钥的顺序不同。 加密时候的顺序是：；解密时的顺序则为：因此，我们可以把加密和解密过程统一画在图9-6所示的流程图中。虽然DES算法如此复杂，但它基本上还是采用一个64比特字符的单字母表替换密码。当明文是64个0并且密钥也是56个0时， 利用DES算法所得的密文将是:8CA64DE9C1B123A7（十六进制）。增强DES（或任一密码）的一种办法是：根据一定义良好的规则（例如，每第n个字符有效，其他字符无效） 在明文中插入随机字符。此外，还可根据另一条规则在两条真正的报文之间插入一些假报文，这称为空密码（null cipher）。空密码要浪费一些带宽，但不容易被破译，因为真正的字符和报文位置是严格保密的，而且随密钥的改变而变化。值得一提的是，对于租用的专用线路，只要有空闲就可传输一些无用的报文。图9-8 DES算法的加密、解密流程图4流加密另一种加大DES密码分析难度的办法是把它当作一个流密码来进行操作，如图9-9所示， 而不是我们迄今为止一直在讨论的块加密。当使用一个密码时，发送者和接收者都让他们的DES处于加密方式进行操作。 各DES芯片有一个64位输入寄存器（移位寄存器），还有一个64位输出寄存器（非移位寄存器）。当一个明文字符到达时，它与输出寄存器O1（O2到O8未用）的8个比特相异或，所生成的字符被传送给接收方， 同时将该字符移入输入寄存器，它把I8顶出。于是DES芯片开始工作，为下一输入计算输出。在接收端，收到的字符首先与O1相异或（产生出明文）。然后把所收到字符移入I1， 如果收发双方芯片的输入寄存器内容最初相同，那么它们将永远保持一致。这也就是说收发双方的O1始终相同。 由于进入发送端的明文与之作异或操作的字符相同于进入接收器的密文与之作异或操作的字符（即都是O1中的字符）， 因此，接收器的输出即为最初的明文。流加密有价值的特征是O1依赖于明文的整个历史， 因此明文中重复的字组不会被生成为加密文中重复的字组。流加密也非常适用于终端，因为这样不必在发送加密文之前收齐8个字符， 每敲击一次键盘就可以立即生成加密输出。5 对DES算法的评价DES开创了算法全部公开的先例。有