计算机数据加密标准DES分析

为了建立适用于计算机系统的商用密码，美国商业部国家标准局（National Bureau of Standards，NBS）于1973年5月和1974年8月两次发布通告，向社会征求密码算法。在征得的算法中，由IBM公司提出的算法lucifer中选。1975年3月，NBS向社会公布了此算法，以求得公众的评论。此算法于1976年11月被美国政府采用，随后被美国国家标准局和美国国家标准协会ANSI（American National Standard Institute）承认，并于1977年1月以数据加密标准DES（Data Encryption Standard）的名称正式向社会公布。DES曾是现代社会使用最广泛的加密方法之一，尽管现在被证明是不安全的，但仍然是一种非常重要的现代密码系统。

DES是一个分组加密算法，它以64位为分组对数据加密，64位一组的明文从算法的一端输入，64位的密文从另一段输出。同时，DES也是一个对称算法：加密和解密用的是同一个算法。在DES算法中，密钥通常表示为64位的数，但由于每个第8位都用作奇偶校验，因此，DES的密钥长度为56位，可以是任意的56位的数，而且可在任意的时候改变。

DES基于加密的两个基本技术——混乱和扩散，采用先替换后置换的方法，基于密钥作用于明文（一次替换和置换称为一轮），对64位明文分组进行操作，首先通过一个初始置换，将明文分成左右两个部分，各32位长。然后，再进行16轮（Round）完全相同的运算，这些运算被称为函数f，在运算过程中数据与密钥结合。在经过16轮运算之后，左、右半部分合在一起经过一个末置换（初始置换的逆置换），算法就完成了。

在每一轮中，密钥位移位，然后再从密钥的56位中选出48位。通过一个扩展置换将数据的右半部分从32位扩展成48位，并通过一个异或操作与48位密钥结合，通过8个S盒（SBOX）将这48位替代成新的32位数据，再将其置换一次。这四步运算构成了函数f。然后，通过另一个异或运算，将函数 f 的输出与左半部分结合，其结果作为新的左半部分。将该操作重复16次，便实现了DES的全部16轮运算。其中，一轮DES运算的具体过程如图8.2所示。

假设Bi是第i次迭代的结果，Li和Ri是Bi的左半部分和右半部分，Ki是第i轮的48位密钥，且f是实现代替、置换及密钥异或等运算的函数，那么每一轮就是：

Li=Ri−1

Ri=Li-1⊕f (Ri−1, Ki)

基于以上描述，则DES算法具体可描述如下：

步骤1（初始置换）：首先，用一个固定初始置换P来置换明文x的比特，得到的64比特的结果被分成两个部分L0和R0，均为32比特。

图8.2　一轮DES运算的具体过程

初始置换在第一轮运算之前进行，初始置换将对输入分组实施如下变换：

58，50，42，34，26，18，10，2，60，52，44，36，28，20，12，4

62，54，46，38，30，22，14，6，64，56，48，40，32，24，16，8

57，49，41，33，25，17，9，1，59，51，43，35，27，19，11，3

61，53，45，37，29，21，13，5，63，55，47，39，31，23，15，7

显然，上述初始置换将把明文的第58位换到第1位的位置，把第50位换到第2位的位置，把第42位换到第3位的位置，依此类推。

初始置换和对应的末置换并不影响DES的安全性，它们的主要目的是更容易地将明文和密文数据以字节大小放入到DES芯片之中。

步骤2（DES运算）：然后，基于得到的L0和R0，再进行16轮DES运算，针对第

i（1≤i≤16）轮DES运算，Li与Ri可通过下式计算得到：

Li=Ri−1

Ri= Li-1⊕f (Ri−1, Ki)

其中，⊕表示异或运算，且：

f (Ri−1, Ki)=P(S(E(Ri−1)⊕Ki))

其中，E表示扩展置换（Expansion）；S表示S盒替换；P表示P盒置换。每一轮的密钥K1, K2,…, K16均为48位的比特流，可由密钥函数K计算得到。

步骤2.1（扩展置换）：扩展置换E(Ri-1)通过如下方式将右半部分Ri-1从32位扩展成48位，其目的是产生与密钥同长度（48位）的数据以进行异或运算：

3212345

456789

8910111213

121314151617

161718192021

202122232425

242526272829

28293031321

对于一个32比特的位串b1b2…b32，其对应的48位输出为b32b1b2b3b4b5b4…b1。

步骤2.2（密钥置换）：由于在DES的密钥中，每个字节第8位作为奇偶校验以确保密钥不发生错误，因此，可以不考虑每个字节的第8位，故DES的密钥由64位减至了如下的56位：

57，49，41，33，25，17， 9， 1，58，50，42，34，26，18

10， 2，59，51，43，35，27，19，11， 3，60，52，44，36

63，55，47，39，31，23，15， 7，62，54，46，38，30，22

14， 6，61，53，45，37，29，21，13， 5，28，20，12， 4

针对上述56位的密钥，在每一轮中，需要通过密钥位移位，从密钥的56位中选出48位来作为该轮的子密钥。在第i（1≤i≤16）轮中，子密钥Ki是通过如下方法来确定的：

（1）首先，56位密钥被分成两部分，每部分28位。

（2）然后，根据轮数，这两部分分别循环左移1位或2位，其中，每轮移动的位数如下所示：

轮　1　2　3　4　5　6　7　8　9　10 11　12　13　14　15　16

位数　1　1　2　2　2　2　2　2　1　 2　 2　 2　 2　 2　 2　 1

（3）最后，再基于以下压缩置换（Compression Permutation），从移动后得到的56位之中选出48位来作为该轮的子密钥：

14，17，11，24， 1， 5， 3，28，15， 6，21，10

23，19，12， 4，26， 8，16， 7，27，20，13， 2

41，52，31，37，47，55，30，40，51，45，33，48

44，49，39，56，34，53，46，42，50，36，29，32

显然，由上述压缩置换可以看出，在每一轮中，移动后得到的第33位的那一位在输出时被移到了第35位，而处于第18位的那一位则被忽略了。

步骤2.3（S盒替换）：在第i轮中，将基于上述压缩置换所得到的子密钥Ki与扩展数据进行异或运算之后，首先，将结果分成8个6位的比特流B=B1B2…B8，然后，再将其送入如下所示的8个S盒 S1，S2，…，S8之中，其中，每个S盒都包含6位输入和4位输出：

假定将某个S盒的6位输入标记为b1、b2、b3、b4、b5、b6，则b1和b6组合构成了一个2位数，从0到3，它对应着该S盒中的一行；从b2到b5构成了一个4位数，从0到15，对应着该S盒中的一列。

例如：S2假设输入为111010，则b1b6=10（十进制为2，即对应的为S2中的第2行），b2b3b4b5=1101（十进制为13，即对应的为S2中的第13列），则输出为0011（由于S2的第2行第13列为3），这里，S盒中行与列的计数分别为第0～3行和第0～15列。

步骤2.4（P盒置换）：接下来，需要将经过S盒替换运算得到的32位输出依照P盒进行置换。该置换把每个输入位映射到输出位，任一位不能被映射两次，也不能被略去。P盒置换的具体描述如下所示：

16， 7，20，21，29，12，28，17， 1，15，23，26， 5，18，31，10

2， 8，24，14，32，27， 3， 9，19，13，30， 6，22，11， 4，25

由上述P盒置换可知，经过S盒替换运算得到的32位之中，第21位被移到了第4位，同时，第4位则被移到了第31位。

步骤2.5：最后，将P盒置换的结果与最初的64位分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。

步骤3（末置换）：末置换是初始置换的逆过程。DES在最后一轮后，左半部分和右半部分并未交换，而是将两部分并在一起形成一个分组作为末置换的输入，然后，对R16与L16使用初始置换P的逆置换（即末置换）即可获得密文。其中，末置换的具体描述如下所示：

40，8，48，16，56，24，64，32，39，7，47，15，55，23，63，31，

38，6，46，14，54，22，62，30，37，5，45，13，53，21，61，29

36，4，44，12，52，20，60，28，35，3，43，11，51，19，59，27

34，2，42，10，50，18，58，26，33，1，41，9，49，17，57，25

步骤4（DES的解密）：注意到DES算法具有下列属性：

Ri−1= Li

Li−1= Ri⊕f(Ri−1, Ki)

因此，以相反顺序使用密钥K16, K15, …, K1，所得到的输出即为明文。

当DES被提议为标准时，就招致了很多批评与攻击，有些研究人员反对该系统是因为其密钥空间较小，还有的批评则是针对S-Box，一些人甚至认为DES有隐藏的陷门（Trapdoors）可让美国国家安全局NSA（National Security Agency）用于解密消息。另外，还出现了很多攻击DES的方法，但其中大部分的方法都是已知明文攻击或选择明文攻击。在所有攻击DES的方法之中，一种著名的攻击方法叫作差分密码分析（Differential Cryptanalysis）法，该方法是由Biiham和Shamir发明的。尽管S-Box具有均衡的输出（每个可能的输出出现4次，每行一次），但不同输入的输出却是非均匀分布的。

例如：假设(Z2)6中有64对数，对任意1≤i≤j≤64，有Bj⊕B′j = Bi⊕B′i（即每一对的差分相同），但S-Box S(Bi)⊕S(B′i)的输出差分就为非均匀分布的，因此，可在每一轮中找出具有较高概率在输出对（Output Pairs）中引起某些差异性的输入对（Input Pairs）中的差异性。基于这一事实，即可利用选择明文攻击来得到有关密钥的信息。Biham和Shamir在1990年指出，使用差分破译仅需要247个输入，少于蛮力密钥搜索所要求的256个密钥。

另一种针对DES的攻击方法称为线性密码分析（Linear Cryptanalysis），是由Matsui发明的，该方法主要是通过检查明文与密文的“比特和”来找出密钥的“比特和”信息，这里“和”表示异或（XOR）。Matsui的针对DES的已知明文攻击需要研究243个加密文本。尽管差分破译与线性破译并没有真正破解DES，但它们都是相当重要的攻击方法，确实可以破解任何分组密码。

另一方面，人们试图建立高效的密钥蛮力搜索机器来破解DES，在1998年，电子边界基金EFF（Electronic Frontier Foundation）组织使用定制的芯片和一台个人计算机建立了一个DES破解者（DES Craker），在花费了250000美元和一年的时间的建造之后，DES破解者在56个小时内成功破解了一个消息。在1999年，通过借助一个由100000台个人计算机与EFF机器连成的网络，此结果被缩短到了22小时。