cdcq的密码学教程一——手把手教你DES的原理和实现

发表于2022-01-06更新于2023-04-30阅读次数

一、前言

如果你开始学习 DES 的算法细节，那么你可能会像我第一次看 DES 一样，大呼“这是什么鬼？？”。确实，DES 的繁琐程度要远超 RSA 这种通过优美的数学原理定义的算法，而且 DES 的各种不知道怎么冒出来的盒子看上去也不像 RSA 那么有道理。但是如果你了解了 DES 的每一个部分的作用，并且亲自动手实现它，那么这个经典的算法就不再像看上去的那么复杂。

这篇文章就详细地介绍了 DES 每一个部分的实现，并且一步步补充代码。DES 的代码非常基础，任何一个会写 C 语言的人都能在看完之后完整地写出来，所以我鼓励读者一定要动手做一做。希望每一个看到这篇文章的人都能学会 DES （虽然它已经不再安全了）。

二、DES 的设计原则

DES 被设计用来使用一个 64 bit 的密钥加密一个 64 bit 的明文，并且得到一个 64 bit 的密文。如果你想理解 DES ，就必须搞清楚一个问题：现代密码学理论告诉我们，给一个明文字节流异或上一个长度相等的，并且足够随机的密钥字节流，那么这个明文无论如何都不可能被恢复。因为任何一个明文都有等概率的可能随机到合适的密钥，使得异或后的结果恰好等于密文。那么为什么不直接用密钥异或上明文来加密，而是要设计复杂的加密算法呢？答案是混淆和扩散。混淆就是指密文和明文之间几乎没有关系，而扩散则是指明文的一个微小改动都会使密文发生很大的变化。

设想这样一个场景，Bob 正准备发送一条内容为 “connect at port 80” 的消息，并且使用相等长度的密钥异或，那么攻击者只需要在第 17 和 18 字节异或上合适的值，就可以把消息改成 “connect at port 22” ！同样的，如果 Bob 把消息换成了 “connect at port 25” ，攻击者也可以知道连接的端口发生了变化。因此一个良好的加密算法必须满足混淆和扩散的性质，而在 DES 中使用则 S 盒来实现混淆，使用 P 盒来实现扩散。

此外，DES 使用比特替换来实现加密的另一个原因是便于硬件实现。例如 RSA 需要进行大整数运算，这很难用汇编直接实现，而比特替换就简单多了，只需要查表就行。比特替换还有很多优点，比如运算速度更快，这不仅是因为操作简单，而且是因为在整个 DES 中没有任何分支结构，这对 CPU 的流水线运行相当有利。所以 DES 常常用于大量数据的加密，而 RSA 作为公钥密码则主要用于密钥交换。

（图 1 - CPU 的流水线结构）

现在你已经知道了 DES 为什么要被设计成这个样子，我们就可以开始了解算法了。

三、DES 的基本流程

DES 使用一种叫做 Feistel 结构的流程来加密。Feistel 结构分成很多轮，每一轮都将 64 bit 输入分开考虑，分成各 32 bit 的左半部分 LL 和右半部分 RR（这里需要强调，在 DES 中最左位是最高为，最右位是最低位，也就是第 0 位）。有一个轮函数 FF 执行每一轮的操作，轮函数对每一轮都是相同的，此外每一轮还有一个不同的轮密钥 keyikey_i 。每一轮将 RR 和 keyikey_i 输入到轮函数中，得到的结果 F(R,keyi)F(R, key_i) 与 LL 异或，就得到这一轮输出的右半部分 rr ，RR 原封不动作为这轮输出的左半部分 ll 。说起来很抽象，但是画成示意图就很容易懂了。

（图 2 - Feistel 结构的一轮）

这样的过程总共会执行 16 轮，每一轮的输入都是上一轮的输出。在最后一轮之后还需要再额外将 ll 和 rr 交换一次才能得到 Feistel 结构的输出。这个交换操作看上去很多余，但我们如果将一个轮函数的输出交换一下，然后再输入到另一个轮函数中，就能发现为什么要这样做。

（图 3 - 将 Feistel 结构首尾相连）

我们写出轮函数输出的表达式 l=Rl = R 和 r=L⊕F(R)r = L \oplus F(R) （省略了 keyikey_i ，但不影响计算），然后再带入到另一个轮函数中，再交换，就得到 r2=r⊕F(l)=L⊕F(R)⊕F(R)=Lr_2 = r \oplus F(l) = L \oplus F(R) \oplus F(R) = L 和 l2=l=Rl_2 = l = R ！也就是说经过了两次相同的变换，又得到了最开始的输入。如果你愿意多费点功夫，写出更多轮的话，只要第二遍执行时把轮密钥倒序使用就能得到相同的结果。这就是 Feistel 结构加密和解密完全相同的原因。这个加解密过程完全相同的特性同样非常利于物理实现。

但 Feistel 并不是 DES 的全部，在 Feistel 之前，要先对明文做一个初始置换 FP 才能输入 Feistel 结构，而在 Feistel 结构之后还需要做一个末尾置换 IP 才能得到密文。这样做是为了让扩散程度更强，让算法更难分析。此外还需要一个密钥生成算法 KeyGen 来将 DES 的密钥扩展为每一轮的轮密钥。接下来我们就来详细介绍每一个部分的实现。

四、轮函数

如果你学过现代密码学的理论，就能意识到轮函数其实是一个 PRF （伪随机函数），它的目的就是根据输入生成一个随机程度很高的比特串，将这个比特串异或到另一个比特串上就实现了加密。

轮函数又分为 4 个过程：明文扩展、轮密钥加、S 盒和 P 盒。

（图 4 - 轮函数）

4.1 明文扩展算法和轮密钥加

明文扩展算法的功能是将一个 32 bit 的输入扩展成一个 48 bit 的比特串，以适应 48 bit 的轮密钥。具体的做法很简单，给出一个置换表 e ，其中 e[i] 表示输出的第 i 个比特应该和输入的第 e[i] 个比特一样，也就是说从输入中取出一些比特，再按顺序拼起来。

首先我们写一个函数实现查表的功能：

1
2
3
4
5
6
7
Bytes Permutate(Bytes a, int b[], int m, int n) {
    Bytes c = 0;
    for (int i = 0; i < n; i++) {
        c = c << 1 | (a >> (m - b[i] - 1) & 1);
    }
    return c;
}

在我的代码中，我把 unsigned long long 定义成了 Bytes ，来表示一个 64 bit 的比特串。参数 m 和 n 指示出了这个函数的输入和输出的位数，这在阅读代码的时候非常有用。顺带一提，后面我们会频繁使用到这个函数。

明文扩展时，只需要先定义好扩展表 e ，然后执行查表函数就可以了：

1
2
3
4
5
6
7
8
9
10
11
Bytes Expand(Bytes a) {
    static int e[48] = {
        31,  0,  1,  2,  3,  4,  3,  4, 
         5,  6,  7,  8,  7,  8,  9, 10, 
        11, 12, 11, 12, 13, 14, 15, 16, 
        15, 16, 17, 18, 19, 20, 19, 20, 
        21, 22, 23, 24, 23, 24, 25, 26, 
        27, 28, 27, 28, 29, 30, 31,  0
    };
    return Permutate(a, e, 32, 48);
}

其中 e 数组被定义为 static ，这样相当于一个只能在函数中使用的全局变量，只需要初始化一次。可以看到毕竟要把 32 bit 映射到 48 bit ，有一些比特重复使用了。此外，这个扩展算法也为 S 盒的输入提供了扩散性。

轮密钥加则是将 48 bit 的轮密钥和扩展后的 48 bit 串异或起来，结果会送到 S 盒进行处理。这一步虽然简单，但 DES 的保密性就来自这一步，其他的步骤只是在增强分析的难度。

4.2 S 盒

S 盒是 DES 中最奇怪也是最精髓的地方。总共有 8 个 S 盒，每一个 S 盒的输入都是 6 bit ，而输出却是 4 bit 。8 个 S 盒按顺序分别处理输入串的一块，就将一个 48 bit 的串映射到 32 bit 。具体到每一个 S 盒，它会给出一个大小为 64 的表，表中每一个元素都是 4 bit 的比特串。输入会以第 1, 6, 2, 3, 4, 5 的顺序重排序，然后输出表中对应位置的值（这里补充强调一点，在 DES 的分析中习惯从 1 开始计数，而在代码中为了方便则从 0 开始）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Bytes S(Bytes a) {
    static Byte s_box[8][64] = {
        {
            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
        },
        ...
    };
    Bytes res = 0;
    static Bytes p[6] = {0, 5, 1, 2, 3, 4};
    for (int i = 0; i < 8; i++) {
        Bytes b = a >> (7 - i) * 6 & ((1 << 6) - 1);
        b = Permutate(b, p, 6, 6);
        res = res << 4 | s_box[i][b];
    }
    return res;
}

代码中省略了 S 盒的具体内容，毕竟一个 8 * 64 的表实在是太大了，不便于阅读，需要实现的读者可以自己去查找 DES 的 S 盒并填入。代码循环枚举了 8 个 S 盒，首先从输入中提取出这个 S 盒对应的块，经过查表函数重排序后将 S 盒中的查找结果填入输出比特串。

值得一提的是 DES 使用的 S 盒是经过精心设计来满足安全性的。这里有一则小故事，来自阮行止的博客 https://www.ruanx.net/des/ ：

DES 提出的时候，由于 S 盒来历不明，以及传说 NSA 唆使 IBM 公司把有效密钥长度从 64 位减少到 56 位，DES 被怀疑有 NSA 留下的后门。直到上世纪 90 年代， “差分密码攻击”被公开提出，相关质疑终于消解 —— DES 的 S 盒，恰到好处地提供了对差分密码攻击的超强防御能力；而如果采用随机的 S 盒，抗差分密码攻击的能力则大大减弱。事实上，IBM 的研究员们早在 70 年代就已经发现了差分密码攻击方法，并针对此攻击方式特殊构建了 S 盒。出于国家安全的考虑，NSA 要求 IBM 保守秘密，于是差分密码攻击方法在二十余年后才得以重新被其他人发现。

（阮老师的这篇博客写得很好，我就是根据这篇文章学习 DES 的，读者也可以进行参考）

Update, 来自 shallow 的指正：

“我听过的故事好像不是这样的，是 NSA 在差分攻击提出的两年前要求换个算法，别用 DES 了，然后两年后知道 NSA 这么说的原因是因为差分攻击。毕竟 DES 的有一个 S 盒的差分特性真的很离谱。并且不公开设计细节其实也是不合理的，像算法中的常数，都是很有可能留后门的。比如 SHA256 的结构，如果能够自己挑选常数 IV ，可以设计出只有自己能找到碰撞，而别人能找到碰撞的概率可忽略的哈希函数。所以那些常数要么是什么圆周率后面几位，或者直接 123456 啥的，像 MD5 是12345678 ，AES 的 S 盒是一个有限域线性式子算出来的。”

4.3 P 盒

虽然 P 盒被称为“盒”，但 P 盒和明文扩展算法很像，都是查表替换，只不过 P 盒是一个一一替换，作用在于最大限度的提供扩散性质：

1
2
3
4
5
6
7
8
9
Bytes P(Bytes a) {
    static int p[32] = {
        15,  6, 19, 20, 28, 11, 27, 16, 
         0, 14, 22, 25,  4, 17, 30,  9, 
         1,  7, 23, 13, 31, 26,  2,  8, 
        18, 12, 29,  5, 21, 10,  3, 24
    };
    return Permutate(a, p, 32, 32);
}

有了这些我们就可以写出轮函数和 Feistel 的一轮操作了：

1
2
3
4
5
6
7
8
9
10
11
12
Bytes Round(Bytes a, Bytes subkey) {
    Bytes t = Expand(a) ^ subkey;
    t = S(t);
    t = P(t);
    return t;
}

Bytes Feistel(Bytes a, Bytes subkey) {
    Bytes l = a >> 32;
    Bytes r = a ^ l << 32;
    return r << 32 | (l ^ Round(r, subkey));
}

五、初始置换和末尾置换

FP 和 IP 本质也是两个 P 盒，但这两个盒子还有一个特点：互为逆操作。这样就才能保证加密操作和解密操作是完全一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Bytes IP(Bytes a) {
    static int ip[64] = {
        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, 
        56, 48, 40, 32, 24, 16,  8,  0, 
        58, 50, 42, 34, 26, 18, 10,  2, 
        60, 52, 44, 36, 28, 20, 12,  4, 
        62, 54, 46, 38, 30, 22, 14,  6
    };
    return Permutate(a, ip, 64, 64);
}

Bytes FP(Bytes a) {
    static int fp[64] = {
        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, 
        32,  0, 40,  8, 48, 16, 56, 24
    };
    return Permutate(a, fp, 64, 64);
}

Update, 来自 shallow 的指正：

“不是的，IP 和 FP 其实只是一个标准而已，与安全性完全无关，因为 IP 和 FP 是完全公开的，大家都能做，所以这个步骤其实大可删了。比如 SM4 其实就没有这一步。”

我本来以为只是在选择明文攻击里没有用，但其实其他情况只要在分析明文的时候也做一下变换就完全一样了。

六、密钥扩展算法

首先要说的一点是，虽然 DES 的密钥长度为 64 bit ，但其中有效密钥只有 56 bit ，其余的 8 个 bit 是校验位。

密钥扩展首先采用选择置换 1 ，从 64 bit 密钥中选取 56 bit 有效密钥：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Bytes PC1(Bytes key) {
    static int pc1_l[28] = {
        56, 48, 40, 32, 24, 16,  8,  0, 
        57, 49, 41, 33, 25, 17,  9,  1, 
        58, 50, 42, 34, 26, 18, 10,  2, 
        59, 51, 43, 35
    };
    static int pc1_r[28] = {
        62, 54, 46, 38, 30, 22, 14,  6, 
        61, 53, 45, 37, 29, 21, 13,  5, 
        60, 52, 44, 36, 28, 20, 12,  4, 
        27, 19, 11, 3
    };
    return Permutate(key, pc1_l, 64, 28) << 28 | Permutate(key, pc1_r, 64, 28);
}

这里我把 PC1 盒分成左右两个部分写了，其实和写在一起没有区别。在 Python 里边可以分别求出左右两半方便后续操作，我用的 c++ ，所以最后还是合并在一起返回。

接下来执行 16 轮，每一轮先分别把左右两个部分循环左移 1 或 2 位，然后再经过选择置换 2 求出这一轮的轮密钥：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Keygen(Bytes key, Bytes keys[]) {
    key = PC1(key);
    Bytes l = key >> 28;
    Bytes r = key ^ l << 28;
    int offset[16] = {
         1,  1,  2,  2,  2,  2,  2,  2, 
         1,  2,  2,  2,  2,  2,  2,  1
    };
    for (int i = 0; i < 16; i++) {
        l = Rotate(l, offset[i]);
        r = Rotate(r, offset[i]);
        keys[i] = PC2(l << 28 | r);
    }
}

其中 Rotate 是循环左移，PC2 又是一个选择置换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Bytes Rotate(Bytes a, int n) {
    for (int i = 0; i < n; i++)
        a = (a << 1 | (a >> 27 & 1)) & ((1 << 28) - 1);
    return a;
}

Bytes PC2(Bytes key) {
    static int pc2[48] = {
        13, 16, 10, 23,  0,  4,  2, 27, 
        14,  5, 20,  9, 22, 18, 11,  3, 
        25,  7, 15,  6, 26, 19, 12,  1, 
        40, 51, 30, 36, 46, 54, 29, 39, 
        50, 44, 32, 47, 43, 48, 38, 55, 
        33, 52, 45, 41, 49, 35, 28, 31
    };
    return Permutate(key, pc2, 56, 48);
}

这样我们就得到了 16 个子密钥，每一个长度都是 48 bit ，它们各不相同。生成这些子密钥的目的是使加密过程更复杂，更难以分析。

七、完整的 DES 代码

最后我们把所有过程拼起来，就可以得到完整的代码实现。代码还附带了一些测试数据，供读者自己实践时参考。

代码中的易错点：

  1. 注意序号和顺序的差异，在分析时从 1 开始，第 1 位表示最高位，而在程序中则从第 0 位开始，第 0 位仍然表示最高位，但编程语言可不会默认第 0 位是最高位，要手动变换。

  2. 注意位运算的优先级，如果记不住又不想带太多括号的话就勤查表吧。

  3. 最后输出时要把左右部分交换再执行 IP 盒，交换的操作容易忘记。

  4. 记得解密时把轮密钥顺序翻转哦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <iostream>
#include <cstdio>
#include <algorithm>

typedef unsigned char Byte;
typedef unsigned long long Bytes;

Bytes Permutate(Bytes a, int b[], int m, int n) {
    Bytes c = 0;
    for (int i = 0; i < n; i++) {
        c = c << 1 | (a >> (m - b[i] - 1) & 1);
    }
    return c;
}

Byte Permutate(Byte a, Byte b[], int m, int n) {
    Byte c = 0;
    for (int i = 0; i < n; i++) {
        c = c << 1 | (a >> (m - b[i] - 1) & 1);
    }
    return c;
}

Bytes IP(Bytes a) {
    static int ip[64] = {
        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, 
        56, 48, 40, 32, 24, 16,  8,  0, 
        58, 50, 42, 34, 26, 18, 10,  2, 
        60, 52, 44, 36, 28, 20, 12,  4, 
        62, 54, 46, 38, 30, 22, 14,  6
    };
    return Permutate(a, ip, 64, 64);
}

Bytes FP(Bytes a) {
    static int fp[64] = {
        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, 
        32,  0, 40,  8, 48, 16, 56, 24
    };
    return Permutate(a, fp, 64, 64);
}

Bytes PC1(Bytes key) {
    static int pc1_l[28] = {
        56, 48, 40, 32, 24, 16,  8,  0, 
        57, 49, 41, 33, 25, 17,  9,  1, 
        58, 50, 42, 34, 26, 18, 10,  2, 
        59, 51, 43, 35
    };
    static int pc1_r[28] = {
        62, 54, 46, 38, 30, 22, 14,  6, 
        61, 53, 45, 37, 29, 21, 13,  5, 
        60, 52, 44, 36, 28, 20, 12,  4, 
        27, 19, 11, 3
    };
    return Permutate(key, pc1_l, 64, 28) << 28 | Permutate(key, pc1_r, 64, 28);
}

Bytes PC2(Bytes key) {
    static int pc2[48] = {
        13, 16, 10, 23,  0,  4,  2, 27, 
        14,  5, 20,  9, 22, 18, 11,  3, 
        25,  7, 15,  6, 26, 19, 12,  1, 
        40, 51, 30, 36, 46, 54, 29, 39, 
        50, 44, 32, 47, 43, 48, 38, 55, 
        33, 52, 45, 41, 49, 35, 28, 31
    };
    return Permutate(key, pc2, 56, 48);
}

Bytes Rotate(Bytes a, int n) {
    for (int i = 0; i < n; i++)
        a = (a << 1 | (a >> 27 & 1)) & ((1 << 28) - 1);
    return a;
}

void Keygen(Bytes key, Bytes keys[]) {
    key = PC1(key);
    Bytes l = key >> 28;
    Bytes r = key ^ l << 28;
    int offset[16] = {
         1,  1,  2,  2,  2,  2,  2,  2, 
         1,  2,  2,  2,  2,  2,  2,  1
    };
    for (int i = 0; i < 16; i++) {
        l = Rotate(l, offset[i]);
        r = Rotate(r, offset[i]);
        keys[i] = PC2(l << 28 | r);
    }
}

Bytes S(Bytes a) {
    static Byte s_box[8][64] = {
        {
            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
        }, {
            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
        }, {
            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
        }, {
             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
        }, {
             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
        }, {
            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
        }, {
             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
        }, {
            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
        }
    };
    Bytes res = 0;
    static Byte p[6] = {0, 5, 1, 2, 3, 4};
    for (int i = 0; i < 8; i++) {
        Byte b = a >> (7 - i) * 6 & ((1 << 6) - 1);
        b = Permutate(b, p, 6, 6);
        res = res << 4 | s_box[i][b];
    }
    return res;
}

Bytes P(Bytes a) {
    static int p[32] = {
        15,  6, 19, 20, 28, 11, 27, 16, 
         0, 14, 22, 25,  4, 17, 30,  9, 
         1,  7, 23, 13, 31, 26,  2,  8, 
        18, 12, 29,  5, 21, 10,  3, 24
    };
    return Permutate(a, p, 32, 32);
}

Bytes Expand(Bytes a) {
    static int e[48] = {
        31,  0,  1,  2,  3,  4,  3,  4, 
         5,  6,  7,  8,  7,  8,  9, 10, 
        11, 12, 11, 12, 13, 14, 15, 16, 
        15, 16, 17, 18, 19, 20, 19, 20, 
        21, 22, 23, 24, 23, 24, 25, 26, 
        27, 28, 27, 28, 29, 30, 31,  0
    };
    return Permutate(a, e, 32, 48);
}

Bytes Round(Bytes a, Bytes subkey) {
    Bytes t = Expand(a) ^ subkey;
    t = S(t);
    t = P(t);
    return t;
}

Bytes Feistel(Bytes a, Bytes subkey) {
    Bytes l = a >> 32;
    Bytes r = a ^ l << 32;
    return r << 32 | (l ^ Round(r, subkey));
}

Bytes DES(Bytes m, Bytes key, bool decrypt, int round) {
    Bytes keys[16] = {0};
    Keygen(key, keys);
    if (decrypt) {
        for (int i = 0; i < 8; i++)
            std::swap(keys[i], keys[15 - i]);
    }
    Bytes c = IP(m);
    for (int i = 0; i < round; i++)
        c = Feistel(c, keys[i]);
    Bytes l = c >> 32;
    Bytes r = c ^ l << 32;
    return FP(r << 32 | l);
}

Bytes Encrypt(Bytes m, int round) {
    return DES(m, 0xcafababedeadbeafULL, 0, round);
}

void test() {
    printf("Test rotate: ");
    if (Rotate(167772165, 2) == 134217750) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
    printf("Test IP: ");
    if (IP(81985529216486895ULL) == 14699974583363760298ULL) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
    printf("Test PC1: ");
    if (PC1(1383827165325090801ULL) == 67779029043144591ULL) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
    printf("Test keygen: ");
    Bytes keys[16] = {0};
    Keygen(1383827165325090801ULL, keys);
    if (keys[15] == 223465186400245ULL) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
    printf("Test S box: ");
    if (S(178261171038007ULL) == 3725222752ULL) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
    printf("Test round: ");
    if (Round(3707429454ULL, 141493528337059ULL) == 3207079049ULL) {
        printf("OK.\n");
    } else {
        printf("GG!\n");
    }
}

int main() {
    test();
    Bytes m = 0x11aabbccddeeff01ULL;
    Bytes k = 0xcafababedeadbeafULL;
    Bytes c = DES(m, k, 0, 16);
    printf("%016llx\n", c);
    printf("%016llx\n", DES(c, k, 1, 16));
    return 0;
}

八、总结

在这篇文章中，我带领着各位读者自顶向下地深入 DES 的算法细节。在了解了算法每一个部分的作用和原理，并亲自动手实现过之后，我们会发出这样的感慨：“原来 DES 也是如此地精妙！”。但 DES 的趣味并没有在此终结，下一篇文章我将带领大家学习 DES 的差分攻击，继续感受密码学算法的无穷魅力。