译自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产生了一种最多264种的变换方法。每个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
然后,将这个秘钥拆分为左右两部分,C0 和 D0,每半边都有28位。
比如,对于新秘钥,我们得到:
- C0 = 1111000 0110011 0010101 0101111
- D0 = 0101010 1011001 1001111 0001111
对相同定义的C0 和 D0,我们现在创建16个块Cn 和 Dn, 1<=n<=16。每一对Cn 和 Dn都是由前一对Cn-1 和 Dn-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
这意味着,比如说,C3 and D3是C2 and D2移位而来的,具体来说,通过2次左移位;C16 and D16 则是由C15 and D15通过1次左移得到的。在所有情况下,一次左移就是将所有比特往左移动一位,使得移位后的比特的位置相较于变换前成为2, 3,…, 28, 1。
比如,对于原始子秘钥C0 and D0,我们得到:
- 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轮的新秘钥Kn( 1<=n<=16)了。具体做法是,对每对拼合后的子秘钥CnDn,按表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轮的新秘钥Kn 的第1位来自组合子秘钥CnDn的第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位的左半边L0 和32位的右半边R0 。
比如,对于上例,我们得到:
- 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位的秘钥区块Kn ——输出一个32位的区块。定义+表示异或XOR。那么让n从1循环到16,我们计算
Ln = Rn-1
Rn = Ln-1 + f(Rn-1,Kn)
这样我们就得到最终区块,也就是n = 16 的 L16R16。这个过程说白了就是,我们拿前一个迭代的结果的右边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,我们首先拓展每个Rn-1,将其从32位拓展到48位。这是通过使用一张表来重复Rn-1中的一些位来实现的。我们称这个过程为函数E。也就是说函数E(Rn-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(Rn-1) 开头的三个比特分别来自Rn-1的第32、1和2位。E(Rn-1) 末尾的2个比特分别来自Rn-1的第32位和第1位。
比如,给定R0 ,我们可以计算出E(R0) :
- R0 = 1111 0000 1010 1010 1111 0000 1010 1010
- E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
(注意输入的每4位一个分组被拓展为输出的每6位一个分组。)
接着在f函数中,我们对输出E(Rn-1) 和秘钥Kn执行XOR运算:
Kn + E(Rn-1)
比如,对K1 , E(R0),我们有:
- 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函数的运算,我们仅仅使用一张表将Rn-1 从32位拓展为48位,并且对这个结果和秘钥Kn执行了异或运算。我们现在有了48位的结果,或者说8组6比特数据。我们现在要对每组的6比特执行一些奇怪的操作:我们将它作为一张被称为“S盒”的表格的地址。每组6比特都将给我们一个位于不同S盒中的地址。在那个地址里存放着一个4比特的数字。这个4比特的数字将会替换掉原来的6个比特。最终结果就是,8组6比特的数据被转换为8组4比特(一共32位)的数据。
将上一步的48位的结果写成如下形式:
Kn + E(Rn-1) =B1B2B3B4B5B6B7B8,
每个Bi 都是一个6比特的分组,我们现在计算
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
其中,Si(Bi) 指的是第i个S盒的输出。
为了计算每个S函数S1, S2,…, S8,取一个6位的区块作为输入,输出一个4位的区块。决定S1的表格如下:
- 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
如果S1 是定义在这张表上的函数,B是一个6位的块,那么计算S1(B) 的方法是:B的第一位和最后一位组合起来的二进制数决定一个介于0和3之间的十进制数(或者二进制00到11之间)。设这个数为i。B的中间4位二进制数代表一个介于0到15之间的十进制数(二进制0000到1111)。设这个数为j。查表找到第i行第j列的那个数,这是一个介于0和15之间的数,并且它是能由一个唯一的4位区块表示的。这个区块就是函数S1 输入B得到的输出S1(B)。比如,对输入B = 011011 ,第一位是0,最后一位是1,决定了行号是01,也就是十进制的1 。中间4位是1101,也就是十进制的13,所以列号是13。查表第1行第13列我们得到数字5。这决定了输出;5是二进制0101,所以输出就是0101。也即S1(011011) = 0101。
同理,定义这8个函数S1,…,S8的表格如下所示:
- 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盒的输出:
K1 + E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111.
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
函数f的最后一步就是对S盒的输出进行一个变换来产生最终值:
f = P(S1(B1)S2(B2)…S8(B8))
变换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盒的输出:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
我们得到
f = 0010 0011 0100 1010 1010 1001 1011 1011
那么,
R1 = L0 + f(R0 , K1 )
= 1100 1100 0000 0000 1100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100
在下一轮迭代中,我们的L2 = R1,这就是我们刚刚计算的结果。之后我们必须计算R2 =L1 + f(R1, K2),一直完成16个迭代。在第16个迭代之后,我们有了区块L16 and R16。接着我们逆转两个区块的顺序得到一个64位的区块:
R16L16
然后对其执行一个最终的变换 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轮迭代中,调转左右子秘钥的位置而已。
今天的文章des算法最简单例子_十大经典算法分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/78946.html