对称密钥密码学中的DES

概念

密的人与解密的人用的密钥是一样的。这种加密方式被称为对称密钥加密。

对称密钥加密的工作原理

对称密钥加密的工作机制首先参考下图。对于送信的一方，使用公共密钥加密明文之后传输给受信一方，受信一方用同一个公共密钥解密密文拿到明文

https://img-blog.csdnimg.cn/20191022212700782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvcmFOZQ==,size_16,color_FFFFFF,t_70

DES算法

DES是有IBM公司研制的一种对称加密算法，美国国家标准局于1977年公布把它作为非机要部门使用的数据加密标准。

DES是一个分组加密算法，就是将明文分组进行加密，每次按顺序取明文一部分，一个典型的DES以64位为分组，加密解密用算法相同。它的密钥长度为56位，因为每组第8位是用来做奇偶校验，密钥可以是任意56位的数，保密性依赖于密钥。因此正常工作的密钥只有56位 img

初始置换IP

始置换是固定公开的函数，因此没有密码的意义。

img

初始置换IP是DES的第一步密码变换。初始置换的作用在于将64位明文打乱重排，并分成左右两半。左边32位作为L0，右边32位作为R0。

进行这步主要是为了起到混淆作用。

而在DES算法中，主要执行的是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个元素。

DES到底是如何工作的

比如，对于原秘钥：

  1. K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

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

  1. K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

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

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

  1. C0 = 1111000 0110011 0010101 0101111
  2. D0 = 0101010 1011001 1001111 0001111

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

  1. C0 = 1111000011001100101010101111
  2. D0 = 0101010101100110011110001111
  3. C1 = 1110000110011001010101011111
  4. D1 = 1010101011001100111100011110
  5. C2 = 1100001100110010101010111111
  6. D2 = 0101010110011001111000111101
  7. C3 = 0000110011001010101011111111
  8. D3 = 0101011001100111100011110101
  9. C4 = 0011001100101010101111111100
  10. D4 = 0101100110011110001111010101
  11. C5 = 1100110010101010111111110000
  12. D5 = 0110011001111000111101010101
  13. C6 = 0011001010101011111111000011
  14. D6 = 1001100111100011110101010101
  15. C7 = 1100101010101111111100001100
  16. D7 = 0110011110001111010101010110
  17. C8 = 0010101010111111110000110011
  18. D8 = 1001111000111101010101011001
  19. C9 = 0101010101111111100001100110
  20. D9 = 0011110001111010101010110011
  21. C10 = 0101010111111110000110011001
  22. D10 = 1111000111101010101011001100
  23. C11 = 0101011111111000011001100101
  24. D11 = 1100011110101010101100110011
  25. C12 = 0101111111100001100110010101
  26. D12 = 0001111010101010110011001111
  27. C13 = 0111111110000110011001010101
  28. D13 = 0111101010101011001100111100
  29. C14 = 1111111000011001100101010101
  30. D14 = 1110101010101100110011110001
  31. C15 = 1111100001100110010101010111
  32. D15 = 1010101010110011001111000111
  33. C16 = 1111000011001100101010101111
  34. 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

同理：

  1. K2 = 011110 011010 111011 011001 110110 111100 100111 100101
  2. K3 = 010101 011111 110010 001010 010000 101100 111110 011001
  3. K4 = 011100 101010 110111 010110 110110 110011 010100 011101
  4. K5 = 011111 001110 110000 000111 111010 110101 001110 101000
  5. K6 = 011000 111010 010100 111110 010100 000111 101100 101111
  6. K7 = 111011 001000 010010 110111 111101 100001 100010 111100
  7. K8 = 111101 111000 101000 111010 110000 010011 101111 111011
  8. K9 = 111000 001101 101111 101011 111011 011110 011110 000001
  9. K10 = 101100 011111 001101 000111 101110 100100 011001 001111
  10. K11 = 001000 010101 111111 010011 110111 101101 001110 000110
  11. K12 = 011101 010111 000111 110101 100101 000110 011111 101001
  12. K13 = 100101 111100 010111 010001 111110 101011 101001 000001
  13. K14 = 010111 110100 001110 110111 111100 101110 011100 111010
  14. K15 = 101111 111001 000110 001101 001111 010011 111100 001010
  15. K16 = 110010 110011 110110 001011 000011 100001 011111 110101

加密数据的每个64位区块

对于明文数据M，我们计算一个初始变换IP（Initial permutation）。

img

参照上表，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

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

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运算。

我们拿前一个迭代的结果的右边32位作为当前迭代的左边32位。对于当前迭代的右边32位，将它和上一个迭代的f函数的输出执行XOR运算。

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

  1. K1 = 000110 110000 001011 101111 111111 000111 000001 110010
  2. L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010
  3. R1 = L0 + f(R0,K1)

下的就是f函数是如何工作的了。为了计算f，我们首先拓展每个*Rn-1*，将其从32位拓展到48位。

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

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*) ：

  1. R0 = 1111 0000 1010 1010 1111 0000 1010 1010
  2. E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

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

Kn* + E(****Rn-1*)

  1. K1 = 000110 110000 001011 101111 111111 000111 000001 110010
  2. E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
  3. 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盒的输出

那么如何将6位转换成九位，先将这8位数，s1，s2，s3。。。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

计算S(B)* 的方法是：B的第一位和最后一位组合起来的二进制数决定一个介于0和3之间的十进制数（或者二进制00到11之间）。设这个数为i。B的中间4位二进制数代表一个介于0到15之间的十进制数（二进制0000到1111）。设这个数为j。查表找到第i行第j列的那个数，这是一个介于0和15之间的数，并且它是能由一个唯一的4位区块表示的。这个区块就是函数S* 输入B得到的输出*S(B)*。

例子：对于第一轮，我们得到这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

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

根据这个改变我们得到

*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 ，其定义如下表所示：

​ 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轮的左右两个区块：

  1. L16 = 0100 0011 0100 0010 0011 0010 0011 0100
  2. 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。