算法科普：神秘的 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);
整个迭代过程如下图：
img
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,