算法科普：神秘的 DES 加密算法

1 前言

DES 算法是一种常见的分组加密算法，由IBM公司在1971年提出。DES 算法是分组加密算法的典型代表，同时也是应用最为广泛的对称加密算法。本文将详细讲述DES 的原理以及实现过程。

1.1 明文

明文是指没有经过加密的数据。一般而言，明文都是等待传输的数据。由于没有经过加密，明文很容易被识别与破解，因此在传输明文之前必须进行加密处理。

1.2 密文

密文只是明文经过某种加密算法而得到的数据，通常密文的形式复杂难以识别及理解。

1.3 密钥

密钥是一种参数，它是在明文转换为密文或将密文转换为明文的算法中输入的参数。

1.4 对称加密

通信双方同时掌握一个密钥，加密解密都是由一个密钥完成的（即加密密钥等于解密密钥，加解密密钥可以相互推倒出来）。双方通信前共同拟定一个密钥，不对第三方公开。

1.5 分组密码

分组密码是将明文分成固定长度的组，每一组都采用同一密钥和算法进行加密，输出也是固定长度的密文。

2 DES 加密算法

2.1 分组长度

DES 加密算法中，明文和密文为 64 位分组。密钥的长度为 64 位，但是密钥的每个第八位设置为奇偶校验位，因此密钥的实际长度为56位。

2.2 加密流程

DES 加密算法大致分为 4 个步骤：
（1）初始置换
（2）生成子密钥
（3）迭代过程
（4）逆置换

整个过程流程图：

加密流程

3 初始置换

初始置换是将原始明文经过IP置换表处理。置换过程如图：

例如：
输入64位明文数据M（64位）：
明文M（64位）=
0110001101101111011011010111000001110101011101000110010101110010
选取密钥K（64位）：
密钥K（64位）=
0001001100110100010101110111100110011011101111001101111111110001

IP置换表：

58,50,42,34,26,18,10,02,
60,52,44,36,28,20,12,04,
62,54,46,38,30,22,14,06,
64,56,48,40,32,24,16,08,
57,49,41,33,25,17,09,01,
59,51,43,35,27,19,11,03,
61,53,45,37,29,21,13,05,
63,55,47,39,31,23,15,07,

IP置换表中的数据指的是位置，例如58指将M第58位放置第1位。

M经过IP置换后为M’

M’（64位） =
1111111110111000011101100101011100000000111111110000011010000011
取M’的前32位作为L0，则有
L0（32位）= 11111111101110000111011001010111
取M’的后32位作为R0，则有
R0（32位）= 00000000111111110000011010000011

4 生成子密钥

DES 加密共执行16次迭代，每次迭代过程的数据长度为48位，因此需要16个48位的子密钥来进行加密，生成子密钥的过程如下：

以第3节的例子说明子密钥的计算过程：

（1）第一轮置换：

密钥 K = 0001001100110100010101110111100110011011101111001101111111110001需经过PC-1表置换，即执行置换选择1过程。
PC-1表为：

57,49,41,33,25,17,09
01,58,50,42,34,26,18
10,02,59,51,43,35,27
19,11,03,60,52,44,36
63,55,47,39,31,23,15
07,62,54,46,38,30,22
14,06,61,53,45,37,29
21,13,05,28,20,12,04

PC-1表为8行7列的表，密钥K经PC-1后变为56位数据K’。

K’（56位）= 11110000110011001010101011110101010101100110011110001111
取K’的前28位作为C0，则有
C0（28位）= 1111000011001100101010101111
取K’的后28位作为D0，则有
D0（28位）= 0101010101100110011110001111
获得C0，D0后进行左移操作需要查询移动位数表：

每轮移动移动位数表如下：

轮数 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

进行第一轮移位，轮数为1，查表得左移位数为1。

C0左移1位为C1：
C1（28位） = 1110000110011001010101011111
D0左移1位为D1：
D1（28位） = 1010101011001100111100011110
将C1和D1合并后，经过PC-2表置换得到子密钥K1，PC-2表中去除了第9，18，22，25，35，38，43，54位。

PPC-2表为6X8的表，PC-2表如下：

14,17,11,24,01,05,
03,28,15,06,21,10,
23,19,12,04,26,08,
16,07,27,20,13,02,
41,52,31,37,47,55,
30,40,51,45,33,48,
44,49,39,56,34,53,
46,42,50,36,29,32

由于PC-2表为6X8的表，经PC-2置换后的数据为48位，置换后得到密钥K1，
K1（48位）= 000110110000001011101111111111000111000001110010

（2）第二轮置换

C1和D1再次左移，轮数 = 2，查表得左移位数 = 1，则C1和D1左移1位得到C2和D2。

C2（28位）= 1100001100110010101010111111
D2（28位）= 0101010110011001111000111101
C2和D2合并后为56位，经过PC-2表置换得到密钥K2（48位）
K2（48位）= 011110011010111011011001110110111100100111100101
依次类推，得到K3-K16子密钥，注意Ci和Di左移的位数。

C3（28位） = 0000110011001010101011111111
D3（28位） = 0101011001100111100011110101
K3（48位） = 010101011111110010001010010000101100111110011001

C4（28位） = 0011001100101010101111111100
D4（28位） = 0101100110011110001111010101
K4（48位） = 011100101010110111010110110110110011010100011101

C5（28位） = 1100110010101010111111110000
D5（28位） = 0110011001111000111101010101
K5（48位） = 011111001110110000000111111010110101001110101000

C6（28位） = 0011001010101011111111000011
D6（28位） = 1001100111100011110101010101
K6（48位） = 011000111010010100111110010100000111101100101111

C7（28位） = 1100101010101111111100001100
D7（28位） = 0110011110001111010101010110
K7（48位） = 111011001000010010110111111101100001100010111100

C8（28位） = 0010101010111111110000110011
D8（28位） = 1001111000111101010101011001
K8（48位） = 111101111000101000111010110000010011101111111011

C9（28位） = 0101010101111111100001100110
D9（28位） = 0011110001111010101010110011
K9（48位） = 111000001101101111101011111011011110011110000001

C10（28位） = 0101010111111110000110011001
D10（28位） = 1111000111101010101011001100
K10（48位） = 101100011111001101000111101110100100011001001111

C11（28位） = 0101011111111000011001100101
D11（28位） = 1100011110101010101100110011
K11（48位） = 001000010101111111010011110111101101001110000110

C12（28位） = 0101111111100001100110010101
D12（28位） = 0001111010101010110011001111
K12（48位） = 011101010111000111110101100101000110011111101001

C13（28位） = 0111111110000110011001010101
D13（28位） = 0111101010101011001100111100
K13（48位） = 100101111100010111010001111110101011101001000001

C14（28位） = 1111111000011001100101010101
D14（28位） = 1110101010101100110011110001
K14（48位） = 010111110100001110110111111100101110011100111010

C15（28位） = 1111100001100110010101010111
D15（28位） = 1010101010110011001111000111
K15（48位） = 101111111001000110001101001111010011111100001010

C16（28位） = 1111000011001100101010101111
D16（28位） = 0101010101100110011110001111
K16（48位） = 110010110011110110001011000011100001011111110101

5 迭代过程

设Li（32位）和Ri（32位）为第i次迭代结果的左半部分与右半部分，子密钥Ki为第i轮的48位加密密钥。定义运算规则：

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

整个迭代过程如下图：

5.1 扩展置换E

右半部分Ri的位数为32位，而密钥长度Ki为48位，为了能够保证Ri与Ki可以进行异或运算需要对Ri位数进行扩展，用于扩展置换表E如下：

扩展置换表E：

32,01,02,03,04,05,
04,05,06,07,08,09,
08,09,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,01

例如：
L0（32位） = 11111111101110000111011001010111
R0（32位） = 00000000111111110000011010000011
R0（32位）经过扩展置换后变为48位数据：
E(R0)（48位） = 100000000001011111111110100000001101010000000110

将E(R0)（48位）与K1（48位）作异或运算

100000000001011111111110100000001101010000000110
  000110110000001011101111111111000111000001110010
= 100110110001010100010001011111001010010001110100

得到：
E(R0)^K1（48位） = 100110110001010100010001011111001010010001110100

5.2 S-盒替代

代替运算由8个不同的代替盒（S盒）完成。每个S盒有6位输入，4位输出。代替运算流程如下：

S-盒1：

14,04,13,01,02,15,11,08,03,10,06,12,05,09,00,07,
00,15,07,04,14,02,13,01,10,06,12,11,09,05,03,08,
04,01,14,08,13,06,02,11,15,12,09,07,03,10,05,00,
15,12,08,02,04,09,01,07,05,11,03,14,10,00,06,13,

S-盒2：

15,01,08,14,06,11,03,04,09,07,02,13,12,00,05,10,
03,13,04,07,15,02,08,14,12,00,01,10,06,09,11,05,
00,14,07,11,10,04,13,01,05,08,12,06,09,03,02,15,
13,08,10,01,03,15,04,02,11,06,07,12,00,05,14,09,

S-盒3：

10,00,09,14,06,03,15,05,01,13,12,07,11,04,02,08,
13,07,00,09,03,04,06,10,02,08,05,14,12,11,15,01,
13,06,04,09,08,15,03,00,11,01,02,12,05,10,14,07,
01,10,13,00,06,09,08,07,04,15,14,03,11,05,02,12,

S-盒4：

07,13,14,03,00,06,09,10,01,02,08,05,11,12,04,15,
13,08,11,05,06,15,00,03,04,07,02,12,01,10,14,09,
10,06,09,00,12,11,07,13,15,01,03,14,05,02,08,04,
03,15,00,06,10,01,13,08,09,04,05,11,12,07,02,14,

S-盒5：

02,12,04,01,07,10,11,06,08,05,03,15,13,00,14,09,
14,11,02,12,04,07,13,01,05,00,15,10,03,09,08,06,
04,02,01,11,10,13,07,08,15,09,12,05,06,03,00,14,
11,08,12,07,01,14,02,13,06,15,00,09,10,04,05,03,

S-盒6：

12,01,10,15,09,02,06,08,00,13,03,04,14,07,05,11,
10,15,04,02,07,12,09,05,06,01,13,14,00,11,03,08,
09,14,15,05,02,08,12,03,07,00,04,10,01,13,11,06,
04,03,02,12,09,05,15,10,11,14,01,07,06,00,08,13,

S-盒7：

04,11,02,14,15,00,08,13,03,12,09,07,05,10,06,01,
13,00,11,07,04,09,01,10,14,03,05,12,02,15,08,06,
01,04,11,13,12,03,07,14,10,15,06,08,00,05,09,02,
06,11,13,08,01,04,10,07,09,05,00,15,14,02,03,12,

S-盒8：

13,02,08,04,06,15,11,01,10,09,03,14,05,00,12,07,
01,15,13,08,10,03,07,04,12,05,06,11,00,14,09,02,
07,11,04,01,09,12,14,02,00,06,10,13,15,03,05,08,
02,01,14,07,04,10,08,13,15,12,09,00,03,05,06,11,

S盒的计算规则：
例如：若S-盒1的输入为110111，第一位与最后一位构成11，十进制值为3，则对应第3行，中间4位为1011对应的十进制值为11，则对应第11列。查找S-盒1表的值为14，则S-盒1的输出为1110。8个S盒将输入的48位数据输出为32位数据。

按照S-盒的计算过程，将
E(R0)^K1（48位）= 100110110001010100010001011111001010010001110100，通过 S- 盒替换得到的S盒输出为10001011110001000110001011101010（32位）。

5.3 P-盒置换

将S-盒替代的输出结果作为P-盒置换的输入。P-盒置换表如下：

16,07,20,21,29,12,28,17,01,15,23,26,05,18,31,10,
02,08,24,14,32,27,03,09,19,13,30,06,22,11,04,25,

将S盒输出10001011110001000110001011101010（32位）经过P盒置换，P-盒置换输出01001000101111110101010110000001

令扩展置换E、S-盒替代、P盒置换的过程作为函数f。

第一次迭代过程f(R0,K1)为：
f(R0,K1) = 01001000101111110101010110000001

计算L1（32位）= R0 = 00000000111111110000011010000011
计算R1（32位）= L0 ^ f(R0,K1)
  11111111101110000111011001010111
  01001000101111110101010110000001
= 10110111000001110010001111010110

R1（32位） = 10110111000001110010001111010110。
将L1与R1作为输入，继续执行迭代过程f。直至输出L16与R16。

经过16次迭代后输出:

L16（32位）= 00110000100001001101101100101000
R16（32位）= 10110001011001010011000000011000

6 逆置换

将初始置换进行16次的迭代，即进行16层的加密变换，得到L16和R16，将此作为输入块，进行逆置换得到最终的密文输出块。逆置换是初始置换的逆运算。从初始置换规则中可以看到，原始数据的第1位置换到了第40位，第2位置换到了第8位。则逆置换就是将第40位置换到第1位，第8位置换到第2位。以此类推，逆置换规则表如下

40,08,48,16,56,24,64,32,
39,07,47,15,55,23,63,31,
38,06,46,14,54,22,62,30,
37,05,45,13,53,21,61,29,
36,04,44,12,52,20,60,28,
35,03,43,11,51,19,59,27,
34,02,42,10,50,18,58 26,
33,01,41,09,49,17,57,25,

逆置换过程图：

将L16与R16构成64位数据，经过逆置换表输出密文为：

密文：0101100000001000001100000000101111001101110101100001100001101000

7 结语

DES 加密算法为最为常见的分组加密算法。其主要思想在于数据位的置换与移位过程，通过16次的迭代加密与最终的逆置换得出最终的密文。DES 的解密方式只需按照加密的逆过程求解即可。由于DES 加密过程的算法是公开的，所以密钥K的保密就显得尤为重要，只有发送方与接收方采用相同的密钥进行加密解密才能获取明文数据。