Halo

A magic place for coding

0%

DES算法实现及C++实现

算法原理概述

  DES(Data Encryption Standard),是一种使用密钥加密的块密码,也就是常说的分组加密算法。从密码体系上看,DES属于对称密码体系。DES的特征是,以64位分组对数据加密,加密和解密用的是同一个算法。对数据加密的过程基本是循环移位和矩阵置换。

  DES有以下几大特点:

  1. DES是一种典型的块加密方法:它以64位为分组长度,64位一组的明文作为算法的输入,通过一系列复杂的操作,输出同样64位长度的密文。
  2. DES使用加密密钥定义变换过程,因此算法认为只有持有加密所用的密钥的用户才能解密密文。
  3. DES采用64位密钥,其中每8位含有一个校验位。因此密钥的有效程度是56位。

  DES算法过程概要:

  1. 加密过程

      $C = E_k(M) = IP^{-1}\cdot T_{16}\cdot T_{15}\cdot \dots \cdot T{1} \cdot IP(M)$

    其中,$IP$为初始置换,$IP^{-1}$是$IP$的逆置换,$T_1,T2,\cdots,T_{16}$是一系列的迭代变换。

  2. 解密过程

    $ M = D_k(M) = IP^{-1}\cdot T_{1}\cdot T_{2}\cdot \dots \cdot T{16} \cdot IP(C)$


总体结构

  DES算法的总体结构——Feistel结构

Feistel


模块分解

  根据DES的总体步骤有C++特性,我将DES算法分成下面几个模块。

① 循环左移模块。

在生成子密钥的过程中,需要对上下两部分进行循环左移的操作,位移可能是1,也可能是2,根据位数来判断。因为这一部分需要重复使用,所以把这个封装成一个模块。

② 子密钥生成模块。

算法需要根据输入的一个64位密钥K,来生成16个长度为48位的子密钥,用于轮函数。过程如下:

  1. 对K的56个非校验位实行置换PC-1,得到$C_0D_0$,其中$C_0$和$D_0$分别由PC-1置换后的前28位和后28位组成。$i=1$。

  2. 计算$C_i=LS_i(C_{i-1})$和$D_i = LS{i}(D_{i-1})$,当$i=1,2,9,16$时,$LS_i(A)$表示将二进制串A循环左移一个位置;对于其他的$i$,循环左移两个位置

  3. 对56位的$C_iD_i$实行PC-2压缩置换,得到48位的$K_i$。$i = i + 1$。

  4. 如果已经得到$K_{16}$,密钥调度过程结束;否则转2。

③ Feistel轮函数$f(R_{i-1},K_i)$

过程如下:

  1. 将长度为32位的串$R_{i-1}$作E-扩展,成为48位的串$E(R_{i-1})$;

  2. 将$E(R_{i-1})$和长度为48位的子密钥$K_i$作48位二进制串按位异或运算$K_i$又密钥K生成;

  3. 将2得到得到的结果平均分成8个分组(每个分组长度6位),各个分组分别经过8个不同的S-盒进行6-4转换,得到8个长度分别为4位的分组;

  4. 将3得到的分组结果顺序连接,得到长度为32位的串;

  5. 将4的结果经过P-置换,得到的结果作为轮函数$f(R_{i-1},K_i)$的最终32位输出。

  这里重点解释一下S-盒。S-盒是一类选择函数,用于二进制的6-4转换。Feistel轮函数使用8个S-盒$S_1,\cdots,S_8$,每个S-盒是一个4行(编号0-3),16列(编号0-15)的表,表中的每个元素是一个十进制数,取值在0-15之间,用于表示一个4位的二进制数。

  假设$S_i$的6位输入为$b_1b_2b_3b_4b_5b_6$,则由$n=(b_1b_6){10}$确定行号,由$m=(b_2b_3b_4b_5){10}$确定列号,$[s_i]_{n,m}$元素的值的二进制形式即为所要的$S_i$的输出。

④ 加密模块

  加密模块是综合上述几个模块的一个大模块。先对输入的64位数据进行初始置换IP,然后进行16轮迭代T,对迭代结果进行逆置换,最后输出结果。

⑤ 解密模块

  解密模块的步骤与加密模块一致,唯一不同的地方在于16轮迭代T的调用顺序与加密过程相反。

⑥ 格式转换模块

   为了方便数据处理,在加密过程中使用的是STL提供给的bitset数据结构,因此需要在输入时将用户输入的数据和密钥转化为bitset,在输出时需要将bitset转化为字符串。转换的规则为:每八位对应一个字符,使用ASCII来转换。

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
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
/*
DES Algorithum
Author: LiangYucheng
*/

#include <iostream>
#include <bitset>
#include <string>

using namespace std;

bitset<64> key; // 一个64位的密钥
bitset<48> subKey[16]; // 16个子密钥

/* 置换矩阵定义 */
// 初始IP置换
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};

// IP逆置换
int IP_[] = { 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};

// E-扩展规则
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};

// 8个S-盒
int S[8][4][16] = {
{ {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7},
{0, 15, 7, 4, 15, 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},
{12, 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-置换
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};

// PC-1置换
int PC1[] = { 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};

// PC-2压缩置换
int PC2[] = { 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 loop[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};


// 左移操作
bitset<28> LS(bitset<28>A, int shift) {
bitset<28> output = A;
if (shift == 1) {
for (int i = 0; i < 27; i++) {
if (i - shift < 0)
output[i - shift + 28] = A[i];
else
output[i] = A[i + shift];
}
}
if (shift == 2) {
for (int i = 0; i < 26; i++) {
if (i - shift < 0)
output[i - shift + 28] = A[i];
else
output[i] = A[i + shift];
}
}
return output;
}

// 子密钥生成
void generateSubKey() {
bitset<56> reducedKey;
bitset<28> Ci;
bitset<28> Di;
bitset<48> Ki;

// (1)对K的56个非校验位实行置换PC-1,得到C0D0,其中C0和D0分别由PC-1置换后的前28位和后28位组成。
for (int i = 0; i < 56; i++) {
reducedKey[i] = key[PC1[i] - 1];
}

// (2)计算Ci = LSi(Ci-1)和Di = LSi(Di-1),即左移
// (3)对56位的CiDi实行PC-2压缩置换,得到48位的Ki。
// (4)如果已经得到K16,密钥调度过程结束。
for (int times = 0; times < 16; times++) {
// 上下分开
for (int i = 0; i < 28; i++) {
Ci[i] = reducedKey[i];
}
for (int i = 28; i < 56; i++) {
Di[i-28] = reducedKey[i];
}
Ci = LS(Ci, loop[times]);
Di = LS(Di, loop[times]);

// 上下合并
for (int i = 0; i < 56; i++) {
if (i < 28) {
reducedKey[i] = Ci[i];
}
else {
reducedKey[i] = Di[i - 28];
}
}

// PC-2置换,得到48位的subKey
for (int i = 0; i < 48; i++) {
Ki[i] = reducedKey[PC2[i] - 1];
}

// 添加到子密钥集合中
subKey[times] = Ki;
}
}


// 轮函数
bitset<32> f(bitset<32>R, bitset<48> K) {
bitset<48> Ei;
bitset<32> result;

// (1)将长度为32位的R作E-扩展,成为48为的串
for (int i = 0; i < 48; i++) {
Ei[i] = R[E[i] - 1];
}

// (2)将Ei和长度为48位的子密钥K作48位二进制串按位异或运算。
for (int i = 0; i < 48; i++) {
Ei[i] = Ei[i] ^ K[i];
}

// (3)将(2)得到的结果平均分成8个分组(每个分组长度为6),各个分组分别经过8个不同的S-盒进行6-4转换,得到8个长度分别为4位的分组。
int j = 0; // result的下标
for (int i = 0; i < 48; i+=6) {
// input: b1b2b3b4b5b6
// n = (b1b6) 行号
// m = (b2b3b4b5) 列号
int n = Ei[i] * 2 + Ei[i + 5];
int m = Ei[i+1] * 8 + Ei[i+2] * 4 + Ei[i+3] * 2 + Ei[i+4];
int value = S[i / 6][n][m];

// (4)将(3)得到的分组结果顺序连接得到长度为32位的串
bitset<4> newValue(value); // int to binary
result[j] = newValue[3];
result[j+1] = newValue[2];
result[j+2] = newValue[1];
result[j+3] = newValue[0];
j += 4;
}

bitset<32> output = result;
// (5)将(4)的结果经过P-置换,得到的结果作为论函数f的最终32位输出。
for (int i = 0; i < 32; i++) {
output[i] = result[P[i] - 1];
}

return output;
}

// 加密
bitset<64> encrypt(bitset<64> plain) {
bitset<64> M0;
bitset<32> Li;
bitset<32> Ri;
bitset<32> temp;
bitset<64> cipher;

// 初始置换IP
for (int i = 0; i < 64; i++) {
M0[i] = plain[IP[i] - 1];
}

for (int i = 0; i< 32; i++) {
Li[i] = M0[i];
}
for (int i = 32; i < 64; i++) {
Ri[i - 32] = M0[i];
}

// 16轮迭代T
for (int times = 0; times < 16; times++) {
temp = Ri;
Ri = Li^f(Ri, subKey[times]);
Li = temp;
}

// 逆置换IP^-1
for (int i = 0; i < 32; i++) {
cipher[i] = Ri[i];
}
for (int i = 32; i < 64; i++) {
cipher[i] = Li[i - 32];
}

M0 = cipher; // 使用中间变量存储cipher,非常关键!
for (int i = 0; i < 64; i++) {
cipher[i] = M0[IP_[i] - 1];
}

return cipher;
}

// 解密
bitset<64> decrypt(bitset<64> cipher) {
bitset<64> M0;
bitset<32> Li;
bitset<32> Ri;
bitset<32> temp;
bitset<64> plain;

// 初始置换IP
for (int i = 0; i < 64; i++) {
M0[i] = cipher[IP[i] - 1];
}

for (int i = 0; i< 32; i++) {
Li[i] = M0[i];
}
for (int i = 32; i < 64; i++) {
Ri[i - 32] = M0[i];
}

// 16轮迭代T(逆序)
for (int times = 15; times >= 0; times--) {
temp = Ri;
Ri = Li^f(Ri, subKey[times]);
Li = temp;
}

// 逆置换IP^-1
for (int i = 0; i < 32; i++) {
plain[i] = Ri[i];
}
for (int i = 32; i < 64; i++) {
plain[i] = Li[i - 32];
}

M0 = plain;
for (int i = 0; i < 64; i++) {
plain[i] = M0[IP_[i] - 1];
}

return plain;
}

/*输入输出转换函数*/
// string转bitset
bitset<64> stringToBitset(const char str[8]) {
bitset<64> output;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
output[i * 8 + 7 - j] = (str[i] >> j) & 1;
}
}
return output;
}

// bitset转string
string bitsetToString(bitset<64> s) {
string output;
for (int i = 0; i < 8; i++) {
char c = '\0';
for (int j = 0; j < 8; j++) {
if (s[i*8 + j] == 1) {
c = (c << 1) | 1;
}
else {
c = c << 1;
}
}
output += (unsigned char)c;
}
return output;
}

int main() {
string str;
cout << "Please input plain(length <= 8): ";
cin >> str;
string k;
cout << "Plese input the key(length = 8): ";
cin >> k;
bitset<64> plain = stringToBitset(str.c_str());
key = stringToBitset(k.c_str());

generateSubKey();

// 加密
bitset<64> cipher = encrypt(plain);
// 解密
bitset<64> result = decrypt(cipher);
/*
cout << endl << endl;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
cout << result[i*8 + j] << " ";
}
cout << endl;
}
*/
string output = bitsetToString(result);
cout << output << endl;
return 0;
}

测试时,先加密再解密,如果最终解密结果与输入结果一致,则说明正确。

运行结果:result

总结

  DES的安全性至今仍是可靠的,通常是使用3-DES来实现数据加密。在实现过程中,注意在置换前先保存一份副本,不然置换就会错误。这里实现的DES仅支持8个字符(64位)的输入。对于多于8个字符的输入,只需要将他们分割成多个长度为8的分组,然后分组加密即可。DES的算法设计与实现分享就到这里,感谢您的支持!

Welcome to my other publishing channels