DES算法全解

一、什么是DES算法

  • DES是(Data Encryption Standard)的缩写,为密码体制中的对称密码体制,又被称为美国数据加密标准。
  • DES是一种分组密码。明文,密文,密钥的分组长度都是64位。
  • DES是面向二进制的密码算法。因而能够加解密任何形式的计算机数据。
  • DES是对合运算,因而加密和解密共用同一算法,从而使工程实现的工作量减半
  • DES的密码结构属于Feistel结构

二、DES的加密过程

  1. 64位秘钥经子秘钥产生算法产生出16个子秘钥:$K1,K_2,…,K{16}$, 分别供第一次,第二次,… ,第十六次加密迭代使用。
  2. 64位明文首先经过初始置换$IP(Initial\quad permutation)$,将数据打乱重新排列并分成左右两半,左边32位构成$L_0$,右边32位构成$R_0$。
  3. 由加密函数$f$实现子密钥$K_1$对$R_0$的加密,结果为32位的数据组$f(R_0,K_1)$。$f(R_0,K_1)$再与$L_0$模2相加,又得到一个有32位的数据组$L_0\bigoplus f(R_0,K_1)$。以$L_0\bigoplus f(R_0,K_1)$作为第二次加密迭代的$R_1$,以$R_0$作为第二次加密迭代的$L_1$。至此,第一次加密迭代结束。
  4. 第二次加密迭代至第十六次加密迭代分别用子密钥$K2,…,K{16}$进行,其过程与第一次加密迭代相同。
  5. 第十六次加密迭代结束后,产生一个64位的数据组。以其左边32位作为$L{16}$,以其右边32位作为$R{16}$,两者合并在经过逆初始置换$\color{red}{IP^{-1} }$,将数据重新排列,便得到64位密文。至此加密过程全部结束。

三、DES的算法细节

下面我们详细的介绍算法细节。

1. 创建16个子秘钥,每个长48比特

创建子密钥过程大致流程图如下:

流程

64位秘钥我们已经给出,现在依次介绍置换选择1,,置换选择2,循环左移。

  1. 置换选择1

    • 64位秘钥分为8个字节,每个字节的前7位是真正的秘钥位,第8位是奇偶校验位。奇偶校验位可以从前7位秘钥位计算得出,不是随机的,因而不起秘钥的作用。奇偶校验位的作用在于可检测秘钥中是否有错误,确保秘钥的完整性,因此,DES真正的秘钥只有56位。

    • 置换选择1的作用,一是从64位秘钥中去掉8个奇偶校验位,二是把其余56位秘钥位打乱重新排,且将前28位作为$C_0$,后28位作为$D_0$。

    • 置换选择1规定:$C_0$的各位依次为原秘钥中的第57,49,…,1,…,44,36位。$D_0$的各位依次为原秘钥中的第63,55,…,7,…,12,4位,具体矩阵如下:

      CBCEA409-810F-4561-8D56-F37A664CD81D.png

例:秘钥为12345678

以ASCLL码的形式转化为二进制:

1
00110001 00110010 00110011 00110100 00110101 00110110 00110111 00111000

那么,此秘钥置换选择1后的结果为:

置换选择1:

1
00000000 00000000 11111111 11110110 01100111 1001000 00001111

$C_0$

1
0000000000000000111111111111

$D_0$

1
0110011001111000100000001111
  1. 置换选择2
    • 将$C_i$和$D_i$合并成一个56位的中间数据,置换选择2从中选择出一个48位的子密钥$K_i$。置换选择2的矩阵如下图
    • 置换选择2规定子密钥$K_i$中的第1,2,…,48位依次是这个56位中间数据中的第14,17,…,5,3,…,29,32位。

置换选择2

  1. 循环左移:将密钥(除第一位)整体左移一位,将第一位移动至最后一位。循环左移位数表如下:循环左移位数表

16轮子密钥生成结果如下:

2. 明文初始变换

初始置换$IP$是DES的第一步密码变换,初始置换的作用在于将64位明文打乱重排,并陈诚左右两半,左边32位作为$L_0$,右边32位作为$R_0$。供后面的加密迭代使用。初始置换$IP$的矩阵如下:(道理同上)

初始置换IP

3. 加密函数

加密函数是DES的核心部分。它的作用是在第$i$次加密迭代中用子密钥$Ki$对$R{i-1}$进行加密。

在第$i$次迭代加密中选择运算$E$对32位的$R{i-1}$的各位进行选择和排列,产生一个48位的结果,此结果与子密钥$K_i$模2相加,然后送入代替函数组$S$。代替函数组由8个代替函数(也称S盒子)组成,每个S盒子有6位输入,产生4位的输出。8个S盒子的输出合并,结果得到一个32位的数据组。此数据组在经过置换运算P,将其各位打乱重排,置换运算P的输出便是加密函数的输出$f(R{i-1},K_i)$。

  1. 选择运算E对32位的数据组A的各位进行选择和排列,产生一个48位的结果。他是一种扩展运算,其矩阵如图:

    选择运算

  2. 代替函数组S由8个代替函数(也称S盒子)组成,8个S盒分别记为,$S_1,S_2,…,S_8$。代替函数组的输入时一个48位的数据,从第一位到第48位依次加到8个S盒的输入端,每个S盒有一个代替矩阵,规定了其输出与输入的代替规则。代替矩阵有4行16列,每行都是0到15这16个数字,但每行的数字排列都不同,而且8个代替矩阵彼此也不同,每个S盒有6位输入,产生4位的输出。S盒运算的结果是用输出数据代替了输入数据,所以称其为代替函数。

    S盒的代替规则:S盒的六位输入中,第一位和第六位组成二进制数并转化为十进制数代表选中的行号,其余四位组成二进制数并转化为十进制数代表选中的列号。那么被选中的那个数就是要输出的数(转化为二进制)。

    ​ 以$S1$为例,如果输入的是101011,第一位与第六位组成行号 $11{(2)} = 3{(10)}$ ,选中第三行,其余四位组成列号 $0101{(2)} = 5_{(10)}$,选中第五列,交点数字是9,则$S_1$的输出是1001。

  3. 置换运算$P$:置换运算吧S盒输出的32位数据打乱重排,得到32位的加密函数输出。用P置换来提供扩散,把S盒的混淆作用扩散开来。此时,$R{i-1}$变成$L{i}$,$L_i$再和置换运算P得出来的32位数据做$\bigoplus$运算,得到$R_i$。置换矩阵如图:

  4. 逆初始置换$IP^{-1}$:是初始置换的逆置换,它把第十六次加密迭代的结果打乱重排(这里$R{16}$与$L{16}$互换),形成64位密文。至此,加密过程完全结束。

672C1E7DBC59E27A94DF29AF58498D4B.jpg

4C5C280892CC879204AC6F800285FC99.jpg

930EEC1CD39D6D844DFD3167F84CFBC4.jpg

3AF7BA7A091100A2732266480E846A0A.jpg

4. 解密过程

​ 由于DES是对合运算,所以解密和加密可共用同一个运算,只是子密钥使用的顺序不同。把64位密文当做明文输入,而且第一次解密迭代是用子密钥$K_{16}$,第十六次解密迭代使用子密钥$K_1$,最后的输出便是64位明文。

代码如下:

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
//
// main.cpp
// DES算法
//
// Created by CharlesYan on 2021/4/13.
//

#include <iostream>
#include <stdio.h>
#include<stdlib.h>
using namespace std;
//16-wheel secret key structural body
struct Secret_Key{
int subKey[56] = {};
int C[28];
int D[28];
}Secret_KeyOf16[17];//save the 16-wheel sercet key,and the zero flag in order to save the first substitution selection.

// save the process of encryption
struct Encryption{
int select_Operation[48];
int secretKey_Operation[48];
int boxOf_S[32];
int L[32];
int R[32];
}Encryption_Pro[17];

int result_Secret[64] = {};



//substitution selection table 1(置换选择1)
static int subSelect_table1[56] = {
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
};
//substitution selection table 2(置换选择2)
static int subSelect_table2[48]={
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
};
//Move left shift bits table(循环左移位数表)
static int moveLeft_table[17] = {0,1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
//initial substitution IP
static int init_subIP[64] = {
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
};
//selection operation E
static int sel_E[48] = {
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
};
// Box of S 3D array
static int BoxOf_S[8][4][16]={
//S1
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,
//S2
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,
//S3
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,
//S4
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,
//S5
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,
//S6
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,
//S7
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,
//S8
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
};
//substitution IP
static char P_Table[32]={
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
};

const int IPR_Table[64]={
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
};


//Convert an 8-byte key or plaintext to 64-bit binary
int* ChangeToBit(char code[],int n);
//Subfunction:change Byte to 8-bit binary
int * Change_bit(int a);
//create 16-wheel secret key and save them to Secret_KeyOf16
void set_16wheelKey(int *bit_SecretKey);
//the first step of encryption,set R0, as we know, we will not need L0 later.
void first_StepEncryption(int *bit_PlainText);
//encryption, return the result of encryption
void other_StepEncrtption(int flag);
//Box of S operation
void Box_operation(int *a,int n);
// Box of S change byte to bit
int * Change_bit_S(int a);
//IPR_table operation
void IPR_Operation(int result[]);
void print(int flag);
void Pri_ChangeToByte(int secretKey[]);
int main() {
char my_Plaintext[9] = {};//save plaintext and the last one is '\0'
char my_SecretKey[9] = {};//save secretkey
cout<<"Please input the plaintext of 8 byte:"<<endl;
cin.get(my_Plaintext,9);
cin.get();// getchar();
cout<<"Please input the secret key of 8 byte"<<endl;
cin.get(my_SecretKey,9);
printf("\n");
//8-byte SecretKey turn into 64-bit binary
int *bit_SecretKey = ChangeToBit(my_SecretKey, 8);
//create 16-wheel secret key.
set_16wheelKey(bit_SecretKey);
//8-byte SecretKey turn into 64-bit binary
int *bit_Plaintext = ChangeToBit(my_Plaintext, 8);

//Encryption
first_StepEncryption(bit_Plaintext);
other_StepEncrtption(0);//the 0 is meant encryption
IPR_Operation(result_Secret);
print(0);

//Decryption
first_StepEncryption(result_Secret);
other_StepEncrtption(1);//the 1 is meant decryption.
IPR_Operation(result_Secret);
print(0);
Pri_ChangeToByte(result_Secret);
}
int* ChangeToBit(char code[],int n){
static int BinaryText[64] = {};
int k = 0;
for (int i = 0; i<n; i++) {
int *temp =Change_bit(code[i]);
for (int j = 0; j<n; j++) {
BinaryText[k++] = temp[j];
}
}

return BinaryText;
}
int * Change_bit(int a){
static int flag[8] = {};
int k = 7;
while (a/2!=0) {
flag[k--] = a % 2;
a = a / 2;
}
flag[k] = 1;
return flag;
}
int * Change_bit_S(int a){
static int flag[4] = {0};
int k = 0;
while (a/2!=0) {
flag[k++] = a % 2;
a = a / 2;
}
if(a == 1)
flag[k] = 1;
return flag;
}
void set_16wheelKey(int *bit_SecretKey){
//substitution selection 1
for (int i = 0; i<56; i++) {
Secret_KeyOf16[0].subKey[i] = bit_SecretKey[subSelect_table1[i]-1];
}
//C0 D0
for (int i = 0; i<28; i++) {
Secret_KeyOf16[0].C[i] = Secret_KeyOf16[0].subKey[i];
Secret_KeyOf16[0].D[i] = Secret_KeyOf16[0].subKey[i+28];
}
for (int i = 1 ; i<17; i++) {
if(moveLeft_table[i] == 1){
for (int j = 0; j<27; j++) {
Secret_KeyOf16[i].C[j] = Secret_KeyOf16[i-1].C[j+1];
Secret_KeyOf16[i].D[j] = Secret_KeyOf16[i-1].D[j+1];
}
Secret_KeyOf16[i].C[27] = Secret_KeyOf16[i-1].C[0];
Secret_KeyOf16[i].D[27] = Secret_KeyOf16[i-1].D[0];
}else{
for (int j = 0; j<26; j++) {
Secret_KeyOf16[i].C[j] = Secret_KeyOf16[i-1].C[j+2];
Secret_KeyOf16[i].D[j] = Secret_KeyOf16[i-1].D[j+2];
}
Secret_KeyOf16[i].C[26] = Secret_KeyOf16[i-1].C[0];
Secret_KeyOf16[i].C[27] = Secret_KeyOf16[i-1].C[1];
Secret_KeyOf16[i].D[26] = Secret_KeyOf16[i-1].D[0];
Secret_KeyOf16[i].D[27] = Secret_KeyOf16[i-1].D[1];
}
}
//subKey1 ... subKey16
for (int i = 1; i<17; i++) {
int flag[56] = {};
for (int j = 0; j<28; j++) {
flag[j] = Secret_KeyOf16[i].C[j];
flag[j+28] = Secret_KeyOf16[i].D[j];
}
for (int j = 0; j<48; j++) {
Secret_KeyOf16[i].subKey[j] = flag[subSelect_table2[j]-1];
}
}
//print the result of secret key.
for (int i = 1; i<17; i++) {
printf("N = %d\n",i);
printf("C%d:",i);
for (int j = 0; j<28; j++) {
printf("%d",Secret_KeyOf16[i].C[j]);
}
printf("\n");
printf("D%d:",i);
for (int j = 0; j<28; j++) {
printf("%d",Secret_KeyOf16[i].D[j]);
}
printf("\n");
printf("子密钥%d:",i);
for (int j = 0; j<48; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Secret_KeyOf16[i].subKey[j]);
}
printf("\n\n");
}
}
void first_StepEncryption(int *bit_PlainText){
for (int i = 0; i<32; i++) {
Encryption_Pro[0].L[i] = bit_PlainText[init_subIP[i]-1];
Encryption_Pro[0].R[i] = bit_PlainText[init_subIP[i+32]-1];
}
}
void other_StepEncrtption(int flag){
for (int i = 1; i<17; i++) {
for (int j = 0; j<48; j++) {
//selection
Encryption_Pro[i].select_Operation[j] = Encryption_Pro[i-1].R[sel_E[j]-1];
//secretion operation
if(flag == 0)
Encryption_Pro[i].secretKey_Operation[j] =Secret_KeyOf16[i].subKey[j]^Encryption_Pro[i].select_Operation[j];
else
Encryption_Pro[i].secretKey_Operation[j] =Secret_KeyOf16[17-i].subKey[j]^Encryption_Pro[i].select_Operation[j];
}
// Box of S
Box_operation(Encryption_Pro[i].secretKey_Operation,i);
// XOR operation
for (int j = 0; j<32; j++) {
Encryption_Pro[i].L[j] = Encryption_Pro[i-1].R[j];
Encryption_Pro[i].R[j] = Encryption_Pro[i-1].L[j]^Encryption_Pro[i].boxOf_S[P_Table[j]-1];
}
}
}
void Box_operation(int *a,int n){
int sum = 0;
for (int i = 0; i<48; i += 6) {
int flag1 = BoxOf_S[i/6][a[i]*2+a[i+5]][a[i+1]*8+a[i+2]*4+a[i+3]*2+a[i+4]];
int flag[4] = {0};
int k = 0;
while (flag1/2!=0) {
flag[k++] = flag1 % 2;
flag1 = flag1 / 2;
}
if(flag1 == 1)
flag[k] = 1;
for (int j = 3; j>=0; j--) {
Encryption_Pro[n].boxOf_S[sum++] = flag[j];

}

}
}
void IPR_Operation(int result[]){
int temp[64] = {};
for (int i = 0;i<32 ; i++) {
temp[i] = Encryption_Pro[16].R[i];
temp[32+i] = Encryption_Pro[16].L[i];
}
for (int i = 0 ; i<64; i++) {
result[i] = temp[IPR_Table[i]-1];
}
}
void print(int flag){
for (int i = 1; i < 17 ; i++) {
printf("\nN = %d\n",i);
printf("选择运算:");
for (int j = 0; j<48; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Encryption_Pro[i].select_Operation[j]);
}
printf("\n子密钥加:");
for (int j = 0; j<48; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Encryption_Pro[i].secretKey_Operation[j]);
}
printf("\nS盒:");
for (int j = 0; j<32; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Encryption_Pro[i].boxOf_S[j]);
}
printf("\nL:");
for (int j = 0; j<32; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Encryption_Pro[i].L[j]);
}
printf("\nR:");
for (int j = 0; j<32; j++) {
if(j%8 == 0 && j) printf(" ");
printf("%d",Encryption_Pro[i].R[j]);
}
printf("\n");
}
printf("\n");
if(flag == 0)
cout<<"the result of secret text: "<<endl;
else
cout<<"the result of plain text: "<<endl;
for (int i = 0; i<64; i++) {
if (i%8 == 0 && i != 0) printf(" ");
printf("%d",result_Secret[i]);
}
printf("\n");
}
void Pri_ChangeToByte(int secretKey[]){
char temp[8] = {};
int k = 0;
for (int i = 0; i<64; i+=8) {
int sum = 0;
for (int j = i; j<i+8; j++) {
sum += secretKey[j] * pow(2,7-j%8);
}
temp[k++] = sum;
}
cout<<"the plaintext of 8 byte is :"<<endl;
for (int i = 0; i<8; i++) {
printf("%c",temp[i]);
}
printf("\n");
}