DES算法实例详解

　

des

目录

• 国家标准局催生了DES
• 一些初步的DES例子
• DES到底是如何工作的
• 第一步：创建16个子秘钥，每个长48比特
• 第二步：加密数据的每个64位区块
• Reference

译自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,”Computerworld14, 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进制位）的整数倍。

比如，对于这段文本：

Yourlipsaresmootherthanvaseline

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

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

596F7572206C6970732061726520736D6F6F74686572207468616E20766173656C696E650D0A

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

596F7572206C6970732061726520736D6F6F74686572207468616E20766173656C696E650D0A0000

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

0E329232EA6D0D73

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

C0999FDDE378D7ED727DA00BCA5A84EE47F269A4D64381909DD52F78F5358499828AC9B453E0E653

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

DES到底是如何工作的

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

比如，取明文M为

M=0123456789ABCDEF

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

M=0000000100100011010001010110011110001001101010111100110111101111
L=00000001001000110100010101100111
R=10001001101010111100110111101111

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

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

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

PC-1
5749413325179
1585042342618
1025951433527
1911360524436
63554739312315
7625446383022
1466153453729
211352820124

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

比如，对于原秘钥：

K=0001001100110100010101110111100110011011101111001101111111110001

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

K+=11110000110011001010101011110101010101100110011110001111

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

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

C0=1111000011001100101010101111
D0=0101010101100110011110001111

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

IterationNumberof
NumberLeftShifts
11
21
32
42
52
62
72
82
91
102
112
122
132
142
152
161

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

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

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
1417112415
3281562110
2319124268
1672720132
415231374755
304051453348
444939563453
464250362932

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

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

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

C1D1=11100001100110010101010111111010101011001100111100011110

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

K1=000110110000001011101111111111000111000001110010

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

K2=011110011010111011011001110110111100100111100101
K3=010101011111110010001010010000101100111110011001
K4=011100101010110111010110110110110011010100011101
K5=011111001110110000000111111010110101001110101000
K6=011000111010010100111110010100000111101100101111
K7=111011001000010010110111111101100001100010111100
K8=111101111000101000111010110000010011101111111011
K9=111000001101101111101011111011011110011110000001
K10=101100011111001101000111101110100100011001001111
K11=001000010101111111010011110111101101001110000110
K12=011101010111000111110101100101000110011111101001
K13=100101111100010111010001111110101011101001000001
K14=010111110100001110110111111100101110011100111010
K15=101111111001000110001101001111010011111100001010
K16=110010110011110110001011000011100001011111110101

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

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

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

IP
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157

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

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

M=0000000100100011010001010110011110001001101010111100110111101111
IP=1100110000000000110011001111111111110000101010101111000010101010

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

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

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

L0=11001100000000001100110011111111
R0=11110000101010101111000010101010

我们接着执行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=000110110000001011101111111111000111000001110010
L1=R0=11110000101010101111000010101010
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位。这些比特是通过选择输入的某些位来产生的，具体选择顺序按下表实现：

EBIT-SELECTIONTABLE
3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321

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

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

R0=11110000101010101111000010101010
E(R0)=011110100001010101010101011110100001010101010101

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

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

K_n+E(R_n-1)

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

K1=000110110000001011101111111111000111000001110010
E(R0)=011110100001010101010101011110100001010101010101
K1+E(R0)=011000010001011110111010100001100110010100100111.

到这里我们还没有完成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
ColumnNumber
Row
No.0123456789101112131415
01441312151183106125907
10157414213110612119538
24114813621115129731050
31512824917511314100613

如果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
1441312151183106125907
0157414213110612119538
4114813621115129731050
1512824917511314100613
S2
1518146113497213120510
3134715281412011069115
0147111041315812693215
1381013154211671205149
S3
1009146315511312711428
1370934610285141211151
1364981530111212510147
1101306987415143115212
S4
7131430691012851112415
1381156150347212110149
1069012117131513145284
3150610113894511127214
S5
2124171011685315130149
1411212471315015103986
4211110137815912563014
1181271142136150910453
S6
1211015926801334147511
1015427129561131401138
9141552812370410113116
4321295151011141760813
S7
4112141508133129751061
1301174911014351221586
1411131237141015680592
6111381410795015142312
S8
1328461511110931450127
1151381037412561101492
7114191214206101315358
2114741081315129035611

例子：对于第一轮，我们得到这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
1672021
29122817
1152326
5183110
282414
322739
1913306
2211425

比如，对于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₁₆andR₁₆。接着我们逆转两个区块的顺序得到一个64位的区块：

R₁₆L₁₆

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

IP-1
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725

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

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

L16=01000011010000100011001000110100
R16=00001010010011001101100110010101

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

R16L16=0000101001001100110110011001010101000011010000100011001000110100
IP-1=1000010111101000000100110101010000001111000010101011010000000101

写成16进制得到：

85E813540F0AB405

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

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

Reference

The DES Algorithm Illustrated.pdf

相关阅读

十大滤波算法程序大全：C语言版和arduino版(精心整理)

一、arduino版1、限幅滤波法（又称程序判断滤波法）2、中位值滤波法3、算术平均滤波法4、递推平均滤波法（又称滑动平均滤波法）5、中位值

textteaser算法学习

今天简单来介绍和实现textteaser摘要算法：统计指标：1）句子长度，长度为某个长度的句子为最理想的长度，依照距离这个长度的远近来打分。2

自动排课算法总结

自动排课算法总结 http://blog.csdn.net/Sinde1992/article/details/50321225 零.与遗传算法的比较 遗传的优点: 全局寻优能力强,

简洁明了的克鲁斯卡尔算法求解

小试牛刀–++克鲁斯卡尔算法++ 考研资料书本定义：克鲁斯卡尔算法思想：每次找出侯选边中权值最小的边，就将该边并入生成树中。重复

百度烽火算法升级，持续打击网络劫持问题

网站劫持对用户伤害极大，严重危害搜索用户的网络安全。一直以来，网站劫持问题都是百度搜索重点关注和严厉打击的问题之一。网站劫持