DES的C++实现

学了密码学这门课总不能白学,虽然数论部分看得头皮发麻不是很懂,但起码还是得搞懂加密算法是怎么实现的,顺便熟练一下C/C++

DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。 明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法

总体的加密流程是这样的

img

主要分以下几个步骤:

  1. IP置换
  2. 密钥置换
  3. E扩展置换
  4. S盒代替
  5. P盒置换
  6. IP末置换

IP置换

IP置换目的是将输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位

1
2
3
4
5
6
7
8
9
// 初始置换表
int 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};

即原数据块的第58位放到新数据的第1位,第50位放到第2位,……依此类推,第7位放到第64位

置换后的数据分为L0和R0两部分,L0为新数据的左32位,R0为新数据的右32位。

密钥置换

不考虑每个字节的第8位,DES的密钥由64位减至56位,每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成(注意表中没有8,16,24,32,40,48,56和64这8位)

1
2
3
4
5
6
7
8
9
// 密钥置换表,将64位密钥变成56位
int 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};

在DES的每一轮中,从56位密钥产生出不同的48位子密钥,确定这些子密钥的方式如下:

  • 将56位的密钥分成两部分,每部分28位。
  • 根据轮数,这两部分分别循环左移1位或2位。每轮移动的位数如下表:
1
2
// 每轮左移的位数
int shiftBits[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

移动后,从56位中选出48位。这个过程中,既置换了每位的顺序,又选择了子密钥,因此称为压缩置换。压缩置换规则如下表(注意表中没有9,18,22,25,35,38,43和54这8位):

1
2
3
4
5
6
7
8
9
// 压缩置换,将56位密钥压缩成48位子密钥
int 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};

E扩展置换

扩展置置换目标是IP置换后获得的右半部分R0,将32位输入扩展为48位(分为4位×8组)输出。

扩展置换目的有两个:生成与密钥相同长度的数据以进行异或运算;提供更长的结果,在后续的替代运算中可以进行压缩。

扩展置换原理如下表:

1
2
3
4
5
6
7
8
9
// 扩展置换表,将 32位 扩展至 48位
int E[] = {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};

扩展置换之后,右半部分数据R0变为48位,与密钥置换得到的轮密钥进行异或

S盒代替

 压缩后的密钥(第二步中密钥置换的结果)与扩展分组(第三步中E扩展置换的结果),异或以后得到48位的数据,将这个数据送人S盒,进行替代运算。替代由8个不同的S盒完成,每个S盒有6位输入4位输出。48位输入分为8个6位的分组,一个分组对应一个S盒,对应的S盒对各组进行代替操作。

以下是八个S盒的构造:

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
// S盒,每个S盒是4x16的置换表,6位 -> 4位
int S_BOX[8][4][16] = {
{
{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}
}
};

例如,假设S盒8的输入为110011,第1位和第6位组合为11,对应于S盒8的第3行;第2位到第5位为1001,对应于S盒8的第9列。S盒8的第3行第9列的数字为12,因此用1100来代替110011。

注意,S盒的行列计数都是从0开始

代替过程产生8个4位的分组,组合在一起形成32位数据。

P盒置换

P盒是用来给S盒输出的32位数据再一次进行置换的,该置换把输入的每位映射到输出位,任何一位不能被映射两次,也不能被略去,映射规则如下表:

1
2
3
4
5
6
7
8
9
// P置换,32位 -> 32位
int 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 };

这个时候又得到了一个32位的数据,它是由R0经过一系列变换得来的,最后它变成了L1,原来的L0变成了新的R1

继续重复以下步骤:

  1. 密钥置换
  2. E扩展置换
  3. S盒代替
  4. P盒置换

IP末置换

直到16轮以后,输出最终的左、右两半部分并未进行交换,而是两部分合并形成一个分组做为末置换的输入

末置换规则如下表:

1
2
3
4
5
6
7
8
9
// 末置换表
int IP_end[] = {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};

通过以上一系列的过程,就得到了密文

C++实现

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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
#include <iostream>
#include <fstream>
#include <bitset>
#include <string>
using namespace std;

bitset<64> key; // 64位密钥
bitset<48> subKey[16]; // 存放16轮子密钥

// 初始置换表
int IP_init[] = {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};

// 结尾置换表
int IP_end[] = {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};

/*------------------下面是生成密钥所用表-----------------*/

// 密钥置换表,将64位密钥变成56位
int 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};

// 压缩置换,将56位密钥压缩成48位子密钥
int 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};

// 每轮左移的位数
int shiftBits[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

/*------------------下面是密码函数 f 所用表-----------------*/

// 扩展置换表,将 32位 扩展至 48位
int E[] = {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};

// S盒,每个S盒是4x16的置换表,6位 -> 4位
int S_BOX[8][4][16] = {
{
{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}
}
};

// P置换,32位 -> 32位
int 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 };

/**********************************************************************/
/* */
/* 下面是DES算法实现 */
/* */
/**********************************************************************/

/**
* 密码函数f,接收32位数据和48位子密钥,产生一个32位的输出
*/
bitset<32> f(bitset<32> R, bitset<48> k)
{
bitset<48> expandR;
// 第一步:扩展置换,32 -> 48
for(int i=0; i<48; ++i)
expandR[47-i] = R[32-E[i]];
// 第二步:异或
expandR = expandR ^ k;
// 第三步:查找S_BOX置换表
bitset<32> output;
int x = 0;
for(int i=0; i<48; i=i+6)
{
int row = expandR[47-i]*2 + expandR[47-i-5];
int col = expandR[47-i-1]*8 + expandR[47-i-2]*4 + expandR[47-i-3]*2
+ expandR[47-i-4];
int num = S_BOX[i/6][row][col];
bitset<4> binary(num);
output[31-x] = binary[3];
output[31-x-1] = binary[2];
output[31-x-2] = binary[1];
output[31-x-3] = binary[0];
x += 4;
}
// 第四步:P-置换,32 -> 32
bitset<32> tmp = output;
for(int i=0; i<32; ++i)
output[31-i] = tmp[32-P[i]];
return output;
}

/**
* 对56位密钥的前后部分进行左移
*/
bitset<28> leftShift(bitset<28> k, int shift)
{
bitset<28> tmp = k;
for(int i=27; i>=0; --i)
{
if(i-shift<0)
k[i] = tmp[i-shift+28];
else
k[i] = tmp[i-shift];
}
return k;
}

/**
* 生成16个48位的子密钥
*/
void generateKeys()
{
bitset<56> realKey;
bitset<28> left;
bitset<28> right;
bitset<48> compressKey;
// 去掉奇偶标记位,将64位密钥变成56位
for (int i=0; i<56; ++i)
realKey[55-i] = key[64 - PC_1[i]];
// 生成子密钥,保存在 subKeys[16] 中
for(int round=0; round<16; ++round)
{
// 前28位与后28位
for(int i=28; i<56; ++i)
left[i-28] = realKey[i];
for(int i=0; i<28; ++i)
right[i] = realKey[i];
// 左移
left = leftShift(left, shiftBits[round]);
right = leftShift(right, shiftBits[round]);
// 压缩置换,由56位得到48位子密钥
for(int i=28; i<56; ++i)
realKey[i] = left[i-28];
for(int i=0; i<28; ++i)
realKey[i] = right[i];
for(int i=0; i<48; ++i)
compressKey[47-i] = realKey[56 - PC_2[i]];
subKey[round] = compressKey;
}
}

/**
* 工具函数:将char字符数组转为二进制
*/
bitset<64> charToBitset(const char s[8])
{
bitset<64> bits;
for(int i=0; i<8; ++i)
for(int j=0; j<8; ++j)
bits[i*8+j] = ((s[i]>>j) & 1);
return bits;
}

/**
* DES加密
*/
bitset<64> encrypt(bitset<64>& plain)
{
bitset<64> cipher;
bitset<64> currentBits;
bitset<32> left;
bitset<32> right;
bitset<32> newLeft;
// 第一步:初始置换IP
for(int i=0; i<64; ++i)
currentBits[63-i] = plain[64-IP_init[i]];
// 第二步:获取 Li 和 Ri
for(int i=32; i<64; ++i)
left[i-32] = currentBits[i];
for(int i=0; i<32; ++i)
right[i] = currentBits[i];
// 第三步:共16轮迭代
for(int round=0; round<16; ++round)
{
newLeft = right;
right = left ^ f(right,subKey[round]);
left = newLeft;
}
// 第四步:合并L16和R16,注意合并为 R16L16
for(int i=0; i<32; ++i)
cipher[i] = left[i];
for(int i=32; i<64; ++i)
cipher[i] = right[i-32];
// 第五步:结尾置换IP-1
currentBits = cipher;
for(int i=0; i<64; ++i)
cipher[63-i] = currentBits[64-IP_end[i]];
// 返回密文
return cipher;
}

/**
* DES解密
*/
bitset<64> decrypt(bitset<64>& cipher)
{
bitset<64> plain;
bitset<64> currentBits;
bitset<32> left;
bitset<32> right;
bitset<32> newLeft;
// 第一步:初始置换IP
for(int i=0; i<64; ++i)
currentBits[63-i] = cipher[64-IP_init[i]];
// 第二步:获取 Li 和 Ri
for(int i=32; i<64; ++i)
left[i-32] = currentBits[i];
for(int i=0; i<32; ++i)
right[i] = currentBits[i];
// 第三步:共16轮迭代(子密钥逆序应用)
for(int round=0; round<16; ++round)
{
newLeft = right;
right = left ^ f(right,subKey[15-round]);
left = newLeft;
}
// 第四步:合并L16和R16,注意合并为 R16L16
for(int i=0; i<32; ++i)
plain[i] = left[i];
for(int i=32; i<64; ++i)
plain[i] = right[i-32];
// 第五步:结尾置换IP-1
currentBits = plain;
for(int i=0; i<64; ++i)
plain[63-i] = currentBits[64-IP_end[i]];
// 返回明文
return plain;
}


/**********************************************************************/
/* 测试: */
/* 1.将一个 64 位的字符串加密, 把密文写入文件 a.txt */
/* 2.读取文件 a.txt 获得 64 位密文,解密之后再写入 b.txt */
/**********************************************************************/

int main() {
string s = "ABCDEFGH";
string k = "12345678";
bitset<64> plain = charToBitset(s.c_str());
key = charToBitset(k.c_str());
// 生成16个子密钥
generateKeys();
// 密文写入 a.txt
bitset<64> cipher = encrypt(plain);

cout<<(char*)&plain<<endl;
cout<<(char*)&cipher<<endl;


fstream file1;
file1.open("D://a.txt", ios::binary | ios::out);
file1.write((char*)&cipher,sizeof(cipher));
file1.close();

//读文件 a.txt
bitset<64> temp;
file1.open("D://a.txt", ios::binary | ios::in);
file1.read((char*)&temp, sizeof(temp));
file1.close();

//解密,并写入文件 b.txt
bitset<64> temp_plain = decrypt(temp);
file1.open("D://b.txt", ios::binary | ios::out);
file1.write((char*)&temp_plain,sizeof(temp_plain));
file1.close();

return 0;
}

参 考

https://www.cnblogs.com/songwenlong/p/5944139.html

https://songlee24.github.io/2014/12/06/des-encrypt/