DES算法实例详解

目录

译自J. Orlin Grabbe的名作《DES Algorithm Illustrated》，国外许多大学将该文章作为补充材料，可作为理解DES算法的最佳入门手册。反观许多教材介绍DES时直接照搬一张流程图，图中IP等缩写符号不加解释，让人误解；许多博客则直接给出蹩脚的源码，对内部流程缺乏解读。事实上，DES在算法上并不复杂，只是流程繁多而已。此时利用一个简单的例子，手工推演一下就能轻松理解。

DES (Data Encryption Standard)算法是世界上最常用的加密算法。在很长时间内，许多人心目中“密码生成”与DES一直是个同义词。尽管最近有个叫Electronic Frontier Foundation的组织造了台价值22万的机器尝试**DES加密的数据，DES和它的变种“三重数据加密算法”仍将在*和银行中广泛应用（译注：本文年代久远，在2001年AES成为了DES的替代品）。

DES是怎样工作的？本文将通过一个简单的例子来一步步展示DES的加密流程。自DES诞生以来，许多加密算法（修改数据的方法）都采用了类似DES的手段。一旦理解了DES中的变换，你一定能够更轻松地理解这些现代加密算法中的门道。

但在此之前，不妨先了解一下DES的发展历史。

国家标准局催生了DES

1973年5月，在尼克松任期，美国国家标准局下发了红头文件，征求加密算法来保护传输过程中的数据。国家标准局等了很久一直没有人投标，一直到1974年8月6日，尼克松卸任前三天，IBM才拿出了自己家开发的一套代号LUCIFER（金星）的东西。美国安全局评估后，在1977年7月15日采用了LUCIFER的一个变种作为数据加密标准DES。

DES很快被非数字媒体采用，比如电话线中的信号加密。在那些年里，国际香料组织IFF曾用DES来加密那些用电话线传输的秘密配方。（“With Data Encryption, Scents Are Safe at IFF,” Computerworld 14, No. 21, 95 (1980)）

同时，作为*之后第二大急需加密的银行业也将DES作为广泛应用的标准，美国国家标准协会ANSI制定了整个银行业的加密规范。1980年采用的ANSI X3.92指定了DES算法的应用。

一些初步的DES例子

DES处理比特，或者说二进制数字。我们知道，每四个比特构成一个十六进制数。DES加密一组64位的信息，也就是16个16进制数。为了完成加密，DES同样使用64位长的密码。但是，秘钥中每8位被忽略掉，这样导致DES中有效的秘钥长度为56位。但是，在任何情况下，每64位一个块是DES永恒的组织方式。

比如，如果我们手上的明文是：

8787878787878787

选取了DES秘钥：

0E329232EA6D0D73

我们就能得到密文：

0000000000000000

如果对上述密文使用相同的DES秘钥

0E329232EA6D0D73

来解密的话，我们就能得到原来的明文

8787878787878787

这个例子简单明了，因为我们的明文就是64位长的，明文当然也可以是多个64位那么长。但大部分情况下，现实生活中的明文都不是64位（16个16进制位）的整数倍。

比如，对于这段文本：

Your lips are smoother than vaseline

它是38字节（76个16进制位）长的。所以在DES加密前，这段文本必须在尾部补充一些额外的字节。一旦密文被解密，这些多余的字节将被丢弃。当然，具体有多种补充的方法。在这里，我们简单地补充0在尾部，使得消息是8字节的整数倍。

这段纯文本在16进制下是：

596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A

注意这里前72个十六进制数字代表英文，但0D代表回车符，0A代表换行符，代表文本文件的结束。然后我们在这段十六进制码的尾部添加一些0，使其恰好为80个十六进制位：

596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A0000

如果我们使用相同的秘钥：

0E329232EA6D0D73

加密这段数据，我们将得到如下密文：

C0999FDDE378D7ED 727DA00BCA5A84EE 47F269A4D6438190 9DD52F78F5358499 828AC9B453E0E653

这就是可供传输或储存的秘密代码了。解密它就可以得到原文“Your lips are smoother than vaseline”。（设想一下如果克林顿的情妇加密过这些暧昧数据的话，克林顿该是有多庆幸。）

DES到底是如何工作的

DES是一个基于组块的加密算法，这意味着无论输入还是输出都是64位长度的。也就是说DES产生了一种最多2⁶⁴种的变换方法。每个64位的区块被分为2个32位的部分，左半部分L和右半部分R。（这种分割只在特定的操作中进行。）

比如，取明文M为

M = 0123456789ABCDEF

这里的M是16进制的，将M写成二进制，我们得到一个64位的区块：

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111


L = 0000 0001 0010 0011 0100 0101 0110 0111


R = 1000 1001 1010 1011 1100 1101 1110 1111

M的第一位是0，最后一位是1，我们从左读到右。

DES使用56位的秘钥操作这个64位的区块。秘钥实际上也是储存为64位的，但每8位都没有被用上（也就是第8, 16, 24, 32, 40, 48, 56, 和64位都没有被用上）。但是，我们仍然在接下来的运算中将秘钥标记为从1到64位的64个比特。不过，你也许会看到，刚刚提到的这8个在创建子秘钥的时候会被忽略掉。

举个例子，取十六进制秘钥K为

 K = 133457799BBCDFF1

我们可以得到它的二进制形式（1为0001，3为0011.依次类推，并且将每八位写成一组。这样每组的最后一位都没有被用上。）

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

第一步：创建16个子秘钥，每个长48比特

这个64位的秘钥首先根据表格PC-1进行变换。

                            PC-1

 

              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

由于上表中第一个元素为57，这将使原秘钥的第57位变换为新秘钥K+的第1位。同理，原秘钥的第49位变换为新秘钥的第2位……原秘钥的第4位变换为新秘钥的最后一位。注意原秘钥中只有56位会进入新秘钥，上表也只有56个元素。

比如，对于原秘钥：

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

我们将得到56位的新秘钥：

K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

然后，将这个秘钥拆分为左右两部分，C₀ 和 D₀，每半边都有28位。

比如，对于新秘钥，我们得到：

C0 = 1111000 0110011 0010101 0101111 


D0 = 0101010 1011001 1001111 0001111

对相同定义的C₀ 和 D₀，我们现在创建16个块C_n 和 D_n, 1<=n<=16。每一对C_n 和 D_n都是由前一对C_n-1 和 D_n-1移位而来。具体说来，对于n = 1, 2, …, 16，在前一轮移位的结果上，使用下表进行一些次数的左移操作。什么叫左移？左移指的是将除第一位外的所有位往左移一位，将第一位移动至最后一位。

                     Iteration     Number of


                      Number      Left Shifts

 

                          1          1


                          2          1


                          3          2


                          4          2


                          5          2


                          6          2


                          7          2


                          8          2


                          9          1


                         10          2


                         11          2


                         12          2


                         13          2


                         14          2


                         15          2


                         16          1

这意味着，比如说，C₃ and D₃是C₂ and D₂移位而来的，具体来说，通过2次左移位；C₁₆ and D₁₆ 则是由C₁₅ and D₁₅通过1次左移得到的。在所有情况下，一次左移就是将所有比特往左移动一位，使得移位后的比特的位置相较于变换前成为2, 3,…, 28, 1。

比如，对于原始子秘钥C₀ and D₀，我们得到：

C0 = 1111000011001100101010101111


D0 = 0101010101100110011110001111


C1 = 1110000110011001010101011111


D1 = 1010101011001100111100011110


C2 = 1100001100110010101010111111


D2 = 0101010110011001111000111101


C3 = 0000110011001010101011111111


D3 = 0101011001100111100011110101


C4 = 0011001100101010101111111100


D4 = 0101100110011110001111010101


C5 = 1100110010101010111111110000


D5 = 0110011001111000111101010101


C6 = 0011001010101011111111000011


D6 = 1001100111100011110101010101


C7 = 1100101010101111111100001100


D7 = 0110011110001111010101010110


C8 = 0010101010111111110000110011


D8 = 1001111000111101010101011001


C9 = 0101010101111111100001100110


D9 = 0011110001111010101010110011


C10 = 0101010111111110000110011001


D10 = 1111000111101010101011001100


C11 = 0101011111111000011001100101


D11 = 1100011110101010101100110011


C12 = 0101111111100001100110010101


D12 = 0001111010101010110011001111


C13 = 0111111110000110011001010101


D13 = 0111101010101011001100111100


C14 = 1111111000011001100101010101


D14 = 1110101010101100110011110001


C15 = 1111100001100110010101010111


D15 = 1010101010110011001111000111


C16 = 1111000011001100101010101111


D16 = 0101010101100110011110001111

我们现在就可以得到第n轮的新秘钥K_n（ 1<=n<=16）了。具体做法是，对每对拼合后的子秘钥C_nD_n，按表PC-2执行变换：

                              PC-2

 

                 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

每对子秘钥有56位，但PC-2仅仅使用其中的48位。

于是，第n轮的新秘钥K_n 的第1位来自组合子秘钥C_nD_n的第14位，第2位来自第17位，依次类推，知道新秘钥的第48位来自组合秘钥的第32位。

比如，对于第1轮的组合秘钥，我们有：

C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110

通过PC-2的变换后，得到：

K1 = 000110 110000 001011 101111 111111 000111 000001 110010

同理，对于其他秘钥得到：

K2 = 011110 011010 111011 011001 110110 111100 100111 100101


K3 = 010101 011111 110010 001010 010000 101100 111110 011001


K4 = 011100 101010 110111 010110 110110 110011 010100 011101


K5 = 011111 001110 110000 000111 111010 110101 001110 101000


K6 = 011000 111010 010100 111110 010100 000111 101100 101111


K7 = 111011 001000 010010 110111 111101 100001 100010 111100


K8 = 111101 111000 101000 111010 110000 010011 101111 111011


K9 = 111000 001101 101111 101011 111011 011110 011110 000001


K10 = 101100 011111 001101 000111 101110 100100 011001 001111


K11 = 001000 010101 111111 010011 110111 101101 001110 000110


K12 = 011101 010111 000111 110101 100101 000110 011111 101001


K13 = 100101 111100 010111 010001 111110 101011 101001 000001


K14 = 010111 110100 001110 110111 111100 101110 011100 111010


K15 = 101111 111001 000110 001101 001111 010011 111100 001010


K16 = 110010 110011 110110 001011 000011 100001 011111 110101

关于子秘钥的话题就到此为止了，接下来我们看看信息本身。

第二步：加密数据的每个64位区块

对于明文数据M，我们计算一个初始变换IP（Initial permutation）。IP是重新变换数据M的每一位产生的。产生过程由下表决定，表格的下标对应新数据的下标，表格的数值x表示新数据的这一位来自旧数据的第x位。

                             IP
 

            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

参照上表，M的第58位成为IP的第1位，M的第50位成为IP的第2位，M的第7位成为IP的最后一位。

比如，对M的区块执行初始变换，得到：

M = 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

这里M的第58位是1，变成了IP的第1位。M的第50位是1，变成了IP的第2位。M的第7位是0，变成了IP的最后一位。

接着讲变换IP分为32位的左半边L₀ 和32位的右半边R₀ 。

比如，对于上例，我们得到：

L0 = 1100 1100 0000 0000 1100 1100 1111 1111 


R0 = 1111 0000 1010 1010 1111 0000 1010 1010

我们接着执行16个迭代，对1<=n<=16，使用一个函数f。函数f输入两个区块——一个32位的数据区块和一个48位的秘钥区块K_n ——输出一个32位的区块。定义+表示异或XOR。那么让n从1循环到16，我们计算

L_n = R_n-1 

R_n = L_n-1 + f(R_n-1,K_n)

这样我们就得到最终区块，也就是n = 16 的 L₁₆R₁₆。这个过程说白了就是，我们拿前一个迭代的结果的右边32位作为当前迭代的左边32位。对于当前迭代的右边32位，将它和上一个迭代的f函数的输出执行XOR运算。

比如，对n = 1，我们有：

K1 = 000110 110000 001011 101111 111111 000111 000001 110010 


L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010 


R1 = L0 + f(R0,K1)

剩下的就是f函数是如何工作的了。为了计算f，我们首先拓展每个R_n-1，将其从32位拓展到48位。这是通过使用一张表来重复R_n-1中的一些位来实现的。我们称这个过程为函数E。也就是说函数E(R_n-1)输入32位输出48位。

定义E为函数E的输出，将其写成8组，每组6位。这些比特是通过选择输入的某些位来产生的，具体选择顺序按下表实现：

                    E BIT-SELECTION TABLE

 

                 32     1    2     3     4    5


                  4     5    6     7     8    9


                  8     9   10    11    12   13


                 12    13   14    15    16   17


                 16    17   18    19    20   21


                 20    21   22    23    24   25


                 24    25   26    27    28   29


                 28    29   30    31    32    1

也就是说E(R_n-1) 开头的三个比特分别来自R_n-1的第32、1和2位。E(R_n-1) 末尾的2个比特分别来自R_n-1的第32位和第1位。

比如，给定R₀ ，我们可以计算出E(R₀) ：

R0 = 1111 0000 1010 1010 1111 0000 1010 1010 


E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

（注意输入的每4位一个分组被拓展为输出的每6位一个分组。）

接着在f函数中，我们对输出E(R_n-1) 和秘钥K_n执行XOR运算：

K_n + E(R_n-1)

比如，对K₁ , E(R₀)，我们有：

K1 = 000110 110000 001011 101111 111111 000111 000001 110010 


E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 


K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111.

到这里我们还没有完成f函数的运算，我们仅仅使用一张表将R_n-1 从32位拓展为48位，并且对这个结果和秘钥K_n执行了异或运算。我们现在有了48位的结果，或者说8组6比特数据。我们现在要对每组的6比特执行一些奇怪的操作：我们将它作为一张被称为“S盒”的表格的地址。每组6比特都将给我们一个位于不同S盒中的地址。在那个地址里存放着一个4比特的数字。这个4比特的数字将会替换掉原来的6个比特。最终结果就是，8组6比特的数据被转换为8组4比特（一共32位）的数据。

将上一步的48位的结果写成如下形式：

K_n + E(R_n-1) =B₁B₂B₃B₄B₅B₆B₇B₈,

每个B_i 都是一个6比特的分组，我们现在计算

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈)

其中，S_i(B_i) 指的是第i个S盒的输出。

为了计算每个S函数S1, S2,…, S8，取一个6位的区块作为输入，输出一个4位的区块。决定S₁的表格如下：

                             S1
 

                        Column Number

Row

No.    0  1   2  3   4  5   6  7   8  9  10 11  12 13  14 15

 

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


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


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


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

如果S₁ 是定义在这张表上的函数，B是一个6位的块，那么计算S₁(B) 的方法是：B的第一位和最后一位组合起来的二进制数决定一个介于0和3之间的十进制数（或者二进制00到11之间）。设这个数为i。B的中间4位二进制数代表一个介于0到15之间的十进制数（二进制0000到1111）。设这个数为j。查表找到第i行第j列的那个数，这是一个介于0和15之间的数，并且它是能由一个唯一的4位区块表示的。这个区块就是函数S₁ 输入B得到的输出S₁(B)。比如，对输入B = 011011 ，第一位是0，最后一位是1，决定了行号是01，也就是十进制的1 。中间4位是1101，也就是十进制的13，所以列号是13。查表第1行第13列我们得到数字5。这决定了输出；5是二进制0101，所以输出就是0101。也即S₁(011011) = 0101。

同理，定义这8个函数S₁,…,S₈的表格如下所示：

                                  S1
 

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


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


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


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

                                  S2
 

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


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


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


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

                                  S3
 

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


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


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


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

                                  S4
 

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


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


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


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

                                  S5
 

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


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


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


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

                                 S6
 

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


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


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


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

                                 S7
 

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


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


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


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

                                 S8
 

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


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


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


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

例子：对于第一轮，我们得到这8个S盒的输出：

K₁ + E(R₀) = 011000 010001 011110 111010 100001 100110 010100 100111.

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈) = 0101 1100 1000 0010 1011 0101 1001 0111

函数f的最后一步就是对S盒的输出进行一个变换来产生最终值：

f = P(S₁(B₁)S₂(B₂)…S₈(B₈))

变换P由如下表格定义。P输入32位数据，通过下标产生32位输出：

                                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

比如，对于8个S盒的输出：

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈) = 0101 1100 1000 0010 1011 0101 1001 0111

我们得到

f = 0010 0011 0100 1010 1010 1001 1011 1011

那么，

R₁ = L₀ + f(R₀ , K₁ )

= 1100 1100 0000 0000 1100 1100 1111 1111 
+ 0010 0011 0100 1010 1010 1001 1011 1011 
= 1110 1111 0100 1010 0110 0101 0100 0100

在下一轮迭代中，我们的L₂ = R₁，这就是我们刚刚计算的结果。之后我们必须计算R₂ =L₁ + f(R₁, K₂)，一直完成16个迭代。在第16个迭代之后，我们有了区块L₁₆ and R₁₆。接着我们逆转两个区块的顺序得到一个64位的区块：

R₁₆L₁₆

然后对其执行一个最终的变换 IP^-1 ，其定义如下表所示：

                             IP-1

 

            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

也就是说，该变换的的输出的第1位是输入的第40位，第2位是输入的第8位，一直到将输入的第25位作为输出的最后一位。

比如，如果我们使用了上述方法得到了第16轮的左右两个区块：

L16 = 0100 0011 0100 0010 0011 0010 0011 0100 


R16 = 0000 1010 0100 1100 1101 1001 1001 0101

我们将这两个区块调换位置，然后执行最终变换：

R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100


IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101

写成16进制得到：

85E813540F0AB405

这就是明文M = 0123456789ABCDEF的加密形式C = 85E813540F0AB405。

解密就是加密的反过程，执行上述步骤，只不过在那16轮迭代中，调转左右子秘钥的位置而已。

Reference

The DES Algorithm Illustrated.pdf