DES 加密解密

前言

徐旭东老师说过学者就应该对知识抱有敬畏之心,所以我的博客的标题总喜欢加上“简单”二字,就是为了提醒自己,自己所学知识只是皮毛,离真理还远矣。

DES 算法

DES算法是密码体制中的对称密码体制,明文按64位进行分组,密钥长64位(其中有8位是奇偶校验位,不参与 DES 运算),参数有三个:key、data、mode。即要加密或者解密的数据、密钥、加密还是解密。

考虑到算法注重的是性能,且不涉及面向对象的思维,所以一开始选择 C 语言开发,但是为了良好的交互界面,所以最终选择了 MFC。

基础知识

DES 算法是对二进制数进行各种操作从而达到加密解密的作用,所以了解编码、字符和二进制数的概念非常重要。这也算是这个作业的意外收获吧~

首先一个字节对应一个8位的二进制数。

编码英文字符(单位:字节)中文字符(单位:字节)备注
ASCII1(有时候7位二进制数)不能满足其他国家需求
GB231212为了显示中文制定(属于 ANSI 编码,其他国家皆有自己的标准)
GBK12支持人名、古汉语等方面出现的罕用字,如:溙
Big512支持繁体字
GB1803012支持藏文、蒙文、维吾尔文等主要的少数民族文字
UTF-16(标准的 Unicode)22为了适应全球化,超出范围的使用两个UTF-16即4字节
UTF-8(Unicode 的一种,变长编码)12-4(大部分占3个字节)保留 ASCII 字符的编码,存英文时节省空间

加密流程

1、输入64位的明文,按照以下 IP 置换表对明文进行置换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int IP_Table[64] = {    //64位明文初始置换 表IP
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
};

//IP置换
int IP_Substitute(Type data[64]){
Type temp[64];
for (int i = 0; i < 64; i++){
temp[i] = data[IP_Table[i]];
}
memcpy(data, temp, 64);
return 0;
}

得到置换后的64位数据分成两份各32位,即 L0 和 R0( R0 也是下一轮的L1)。

2、32位的 R0 通过以下 E 位选择表扩充置换成48位:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int E_Table[48] = {    //32位R扩充置换成48位 表E
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
};

//32位R扩展置换成48位
Int E_Substitute(Type data[48]){
Type temp[48];
for (int i = 0; i < 48; i++){
temp[i] = data[E_Table[i]];
}
memcpy(data, temp, 48);
return 0;
}

R0 由32位扩充置换成48位,等待和子密钥进行运算。

3、输入64位的密钥,通过以下 PC_1 置换选择表去除第8,16,24,32,48,56,64位,即去除奇偶校验位后置换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int PC_1_Table[56] = {    //64位密钥置换压缩成56位 表1
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,
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
};

//64位密钥置换压缩成56位
int PC1_Compress(Type key[64], Type temp[56]){
for (int i = 0; i < 56; i++){
temp[i] = key[PC_1_Table[i]];
}
return 0;
}

得到56位的密钥分成两份,各28位,即 C0 和 D0。

4、C0 和 D0 分别按照循环左移表进行左移:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//循环左移次数
int MOVE[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };

//循环左移
int LEFT_Shift(Type data[56], int time){
Type temp[56];

//保存将要循环移动到右边的位
memcpy(temp, data, time);
memcpy(temp + time, data + 28, time);

//前28位移动
memcpy(data, data + time, 28 - time);
memcpy(data + 28 - time, temp, time);

//后28位移动
memcpy(data + 28, data + 28 + time, 28 - time);
memcpy(data + 56 - time, temp + time, time);

return 0;
}

即左移一次得到 C1 和 D1,然后 C1 和 D1 左移1次得到 C2 和 D2,然后 C2 和 D2 左移2次得到 C3 和 D3,依次类推最后得到16个56位的密钥。这16个密钥再按照以下 PC_2 表进行置换压缩:

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
int PC_2_Table[48] = {    //56位子密钥置换压缩成48位 表2
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, 46, 43, 48, 38, 55,
33, 52, 45, 41, 49, 35, 28, 31
};

//56位的子密钥置换压缩成48位
int PC2_Compress(Type key[56], Type temp[48]){
for (int i = 0; i < 48; i++){
temp[i] = key[PC_2_Table[i]];
}
return 0;
}

//生成16个子密钥
int MAKE_SubKeys(Type key[64], Type subKeys[16][48]){
Type temp[56];
PC1_Compress(key, temp);//PC1置换
for (int i = 0; i < 16; i++){//16轮跌代,产生16个子密钥
LEFT_Shift(temp, MOVE[i]);//循环左移
PC2_Compress(temp, subKeys[i]);//PC2置换,产生子密钥
}
return 0;
}

最终得到16个48位的子密钥:K1~K16。

5、R0 和 K0 进行异或运算得到48位的新的 R0 (8行6列),然后通过 S1~S8
表进行压缩(每行分别对应一个 S 表),最终压缩成8行4列,即32位,例如第一行:011010,第1和第6列组成00(十进制中的0),则对应 S1 表中第一行;中间4列组成1101(十进制中的13),则对应第14列,也就是9,最终011010被替换成1001,所以很明显 S 表中的数最大不会超过15。

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
//count=48:R与子密钥异或运算、count=32:R与L异或运算
int XOR(Type R[48], Type L[48], int count){
for (int i = 0; i < count; i++){
R[i] ^= L[i];
}
return 0;
}

int S[8][4][16] =
{ //8行6列R压缩成8行4列 S盒
//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 }
}
};

压缩后得到新的32位的 R0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//S盒置换
int SBOX(Type data[48]){
int line, row, output;
int cur1, cur2;
for (int i = 0; i < 8; i++){
cur1 = i * 6;
cur2 = i << 2;

//计算在S盒中的行与列
line = (data[cur1] << 1) + data[cur1 + 5];
row = (data[cur1 + 1] << 3) + (data[cur1 + 2] << 2)
+ (data[cur1 + 3] << 1) + data[cur1 + 4];
output = S[i][line][row];

//化为2进制
data[cur2] = (output & 0X08) >> 3;
data[cur2 + 1] = (output & 0X04) >> 2;
data[cur2 + 2] = (output & 0X02) >> 1;
data[cur2 + 3] = output & 0x01;
}
return 0;
}

6、R0 通过32位的置换表 P 置换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int P_Table[32] = {    //32位R置换函数 表P
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
};

//32位的R进行P置换
int P_Substitute(Type data[32]){
Type temp[32];
for (int i = 0; i < 32; i++){
temp[i] = data[P_Table[i]];
}
memcpy(data, temp, 32);
return 0;
}

得到新的 R0 和 L0 进行异或运算(目前为止前面除了K2到K16,其他值都用上了)得到 R1(也就是下一轮的 L2 );将一开始的 R0 赋值给 L1。于是得到了 L1 和 R1 ,使用 K1 循环上面的运算,知道把子密钥全部使用完。最终的得到 L16 和 R16,合并得到64位的密文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//count=48:R与子密钥异或运算、count=32:R与L异或运算
int XOR(Type R[48], Type L[48], int count){
for (int i = 0; i < count; i++){
R[i] ^= L[i];
}
return 0;
}

//交换
int Swap(Type left[32], Type right[32]){
Type temp[32];
memcpy(temp, left, 32);
memcpy(left, right, 32);
memcpy(right, temp, 32);
return 0;
}

7、得到的密文通过 IP_1 逆置换表置换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int IP_1_Table[64] = {    //64位密文逆初始置换 表IP^-1
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
};

//IP逆置换
int IP_1_Substitute(Type data[64]){
Type temp[64];
for (int i = 0; i < 64; i++){
temp[i] = data[IP_1_Table[i]];
}
memcpy(data, temp, 64);
return 0;
}

置换后得到最终的加密结果,64位的密文。

解密流程:

由于加密的算法过程几乎是对称的,所以解密过程和加密过程几乎一样,只是在 R 和16个子密钥进行与或运算时,应该是从K16到K1。

图形界面:

Visual Studio->文件->新建->项目->MFC 应用程序,基于对话框:

给 Button 添加响应函数:

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
void CDESDlg::OnBnClickedOk()
{
// TODO: 在此添加控件通知处理程序代码
CString Spath, Dpath, Kpath;
GetDlgItemText(Source_path, Spath);
GetDlgItemText(Destination_path, Dpath);
GetDlgItemText(Key_path, Kpath);

char *Cspath = NULL, *Cdpath = NULL, *Ckpath = NULL;
bool correct = true;
if (!Spath.GetLength() || !Dpath.GetLength() || !Kpath.GetLength()){
MessageBox(_T("请选择文件!"));
correct = false;
}
else{
Cspath = (LPSTR)(LPCTSTR)Spath;
Cdpath = (LPSTR)(LPCTSTR)Dpath;
Ckpath = (LPSTR)(LPCTSTR)Kpath;
}

if (correct){
int state;
state = IsDlgButtonChecked(Encrypt);

clock_t a, b;
CString time;

if (state) {
a = clock();
DES_Encrypt(Cspath, Ckpath, Cdpath);
b = clock();
time.Format(_T("加密成功,耗时%lu毫秒。"), b - a);
MessageBox(time);
}
else {
a = clock();
DES_Decrypt(Cspath, Ckpath, Cdpath);
b = clock();
time.Format(_T("解密成功,耗时%lu毫秒。"), b - a);
MessageBox(time);
}
}
}
疏影横斜水清浅,暗香浮动月黄昏