简述

DES 的代码网上一找一大堆,神奇的是用相同的明文和密钥加密出来的结果不一样,而且它们还都能解密出明文。这就有那么点尴尬了,本来是不打算写的,了解原理就好了(非常懒),然后就很不甘心地写了起来,虽然基本上就是在搬运代码(?)

实现的 DES 算法:

  • 分组长度为 64 位,明文密文长度相同
  • 密钥长度 64 位,有效密钥 56 位
    • 8、16、24、40、48、56 和 64 位是奇偶校验位
  • 明文密钥大于 64 位只取前 64 位

加密 / 解密

加解密只是密钥使用顺序不同

  • 初始置换
  • 16 轮迭代
  • 逆初始置换

DES 结构

DES 使用了 Feistel 网络结构

  • Feistel 网络(Feistel Network)结构是一种应用于分组密码的对称密钥
  • Feistel 的优点在于加解密相似性,它只需要一个逆转的密钥编排算法,其加解密算法部分几乎完全相同。因此在实施过程中,对编码量和线路传输的要求都几乎减半

实验代码

DES 算法的具体过程参考:DES 加密算法的 C++ 实现

des.h

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
#pragma once

#include <bitset>
#include <string>
#include <iostream>
using namespace std;

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

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

// 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,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盒置换表
int P[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
};

// 密钥置换选择表,64位变56位
int PC_1[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
};
// 密钥置换选择表,56位变48位
int PC_2[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
};
//密钥位移次数
int shift[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };

des.cpp

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
#include "des.h"

// 将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[7*(i+1) - j + i] = (s[i] >> j) & 1;
}

return bits;
}
// 将二进制转为string数组
string bitsetTochar(bitset<64> b) {
bitset<8> temp;
char ch[9];
for (int i = 0, j = 0; i < 64; i++) {
temp[i % 8] = b[i];
if ((i + 1) % 8 == 0) {
ch[j] = char(temp[7] + temp[6] * 2 + temp[5] * 4
+ temp[4] * 8 + temp[3] * 16 + temp[2] * 32
+ temp[1] * 64 + temp[0] * 128);
j++;
}
}
ch[8] = '\0';
return string(ch);
}


// 轮函数F
bitset<32> F(bitset<32> LR, bitset<48> K) {
// 扩展置换E,将32位输入变成48位输出
bitset<48> LR48;
for (int i = 0; i < 48; i++) {
LR48[i] = LR[E[i] - 1];
}
// 密钥加,异或
LR48 = LR48 ^ K;
// 密钥加非线性代换(S盒),48位输入变32位输出
bitset<32> LR32;
for (int i = 0, j = 0; i <48; i += 6, j += 4) {
int row = LR48[i] * 2 + LR48[i + 5];//行
int col = LR48[i + 1] * 8 + LR48[i + 2] * 4
+ LR48[i + 3] * 2 + LR48[i + 4];//列
int num = S[i / 6][row][col];
// 这里比较神奇,数据是倒过来的
bitset<4> temp(num);
LR32[j] = temp[3];
LR32[j + 1] = temp[2];
LR32[j + 2] = temp[1];
LR32[j + 3] = temp[0];
}
// 线性置换(P盒)
bitset<32> newLR32;
for (int i = 0; i < 32; i++) {
newLR32[i] = LR32[P[i] - 1];
}

return newLR32;
}


// 循环左移
bitset<28> Left(bitset<28> LR, int step) {
bitset<28> newLR;
for (int i = 0; i < 28; i++) {
newLR[i] = LR[(i + step) % 28];
}
return newLR;
}
// 生成16个子密钥
void GenerateSubkeys() {
// 56位有效密钥
int i, j;
bitset<56> newkey;
for (i = 0; i < 56; i++) {
newkey[i] = key[PC_1[i] - 1];
}
// 分成2个28位数据
bitset<28> L;
bitset<28> R;
for (i = 0; i < 28; i++) {
L[i] = newkey[i];
R[i] = newkey[i + 28];
}
// 循环左移生成子密钥
for (i = 0; i < 16; i++) {
L = Left(L, shift[i]);
R = Left(R, shift[i]);
for (j = 0; j < 28; j++) {
newkey[j] = L[j];
newkey[j + 28] = R[j];
}
for (j = 0; j < 48; j++) {
subkey[i][j] = newkey[PC_2[j] - 1];
}
}
}


// DES加密算法,64位明文转64位密文
bitset<64> des(bitset<64>& plain) {
// 初始置换
int i;
bitset<64> newplain;
for (i = 0; i < 64; i++) {
newplain[i] = plain[IP[i] - 1];
}
// 分成左右两组
bitset<32> L;
bitset<32> R;
for (i = 0; i < 32; i++) {
L[i] = newplain[i];
R[i] = newplain[i + 32];
}
// 16轮迭代
bitset<32> newL;
for (i = 0; i < 16; i++) {
newL = R;
R = L ^ F(R, subkey[i]);
L = newL;
}
// 合并成一组
bitset<64> encrypt;
for (i = 0; i < 32; i++) {
encrypt[i] = R[i];
encrypt[i + 32] = L[i];
}
// 逆初始置换
bitset<64> encryption;
for (i = 0; i < 64; i++) {
encryption[i] = encrypt[IP_1[i] - 1];
}

return encryption;
}

// DES解密算法,64位密文转64位明文
bitset<64> re_des(bitset<64>& encription) {
// 初始置换
int i;
bitset<64> newencription;
for (i = 0; i < 64; i++) {
newencription[i] = encription[IP[i] - 1];
}
// 分成左右两组
bitset<32> L;
bitset<32> R;
for (i = 0; i < 32; i++) {
L[i] = newencription[i];
R[i] = newencription[i + 32];
}
// 16轮迭代
bitset<32> newL;
for (i = 15; i >= 0; i--) {
newL = R;
R = L ^ F(R, subkey[i]);
L = newL;
}
// 合并成一组
bitset<64> replain;
for (i = 0; i < 32; i++) {
replain[i] = R[i];
replain[i + 32] = L[i];
}
// 逆初始置换
bitset<64> plain;
for (i = 0; i < 64; i++) {
plain[i] = replain[IP_1[i] - 1];
}

return plain;
}

// 比较加密后串位的不同
int compare(bitset<64>a, bitset<64>b) {
int i, j;
for (i = 0, j = 0; i < 64; i++) {
if (a[i] != b[i])
j++;
}
return j;
}

/************** 入口 **************/
int main() {
string s = "ckjckjck";
string k = "87876565";
bitset<64> plain = charTobitset(s.c_str());
key = charTobitset(k.c_str());
GenerateSubkeys();
bitset<64> encription = des(plain);
bitset<64> message = re_des(encription);

cout << "明文:" << s << endl;
cout << "明文二进制:" << plain << endl;

cout << "密钥:" << k << endl;
cout << "密钥二进制:" << key << endl;

cout << "加密后结果:" << encription << endl;

cout << "解密后明文:" << message << endl;
cout << "解密后明文:" << bitsetTochar(message) << endl;

//cout << compare(plain, message) << endl;

return 0;
}

结语

快要 2 年前的东西了,写文章基本上只有代码是我不爱看的类型之一(没想到当年自己还这么干过)。