DES

DES

简介

1975年IBM公司颁布的算法，在当时被美国选为国家标准并沿用至今天

DES多用于加密商业部门的非机密的敏感数据

特点：

分组密码：明文、密文、密钥的分组长度都是64位

能够加密任何形式的计算机数据

对合运算，加密和解密共用一套算法

基本结构输入Feistel结构

理论基础

DES算法可分为密钥生成和加/解密过程两个阶段，整体工作流程如下图：

image-20211205170307869

密钥生成

DES算法共有16轮加/解密迭代，每一轮都需要单独的子密钥，因此需要生成16个子密钥：

image-20211205170456114

置换选择1

输入：64bit密钥

输出：28位C0, 28位D0

过程：从64位密钥中去掉每个字节的第8位，奇偶校验位，把剩下的56位按照规则打乱重排，将前28位作为C0，后28位作为D0

循环左移

每一轮根据表格循环不同的位数，注意，如果数据摆放的方式不同，这里的循环左移可能变成循环右移，需要参考具体示例来决定

置换选择2

输入：28位Ci, 28位Di

输出：48位子密钥

过程：将Ci和Di合并成56位中间数据，从中选择48位的子密钥Ki

加密算法

初始置换IP

输入：64位明文

输出：32位L0，32位R0

过程：按照规则将明文转化为L0，R0

加密函数F

输入：32为R和48位子密钥

输出：32位f

具体过程如下图：

image-20211205174408085

选择运算

输入：32位A

输出：48位中间结果

过程：根据规则扩展

模2相加

输入：48位中间结果，48位子密钥

输出：48位

过程：异或

S盒变换

输入：48位

输出：32位

过程：将48位输入分成8份，每份6bit，设为b1b2b3b4b5b6，其中b1b6组成行号，b2b3b4b5组成列号，使用行列到Si盒中查找相应的值作为4bit输出。注意，输出的结果很可能是逆序存放的，即4bit的高位放到最终输出的低位

置换运算P

输入：32位

输出：32位

过程：按照规则取数

解密算法

整体流程和加密相同，但是子密钥是反过来使用的，即最先使用K16，最后使用K1

具体实现

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
// main.c

#include<stdio.h>
#include"des.h"

int main()
{
    char* key_str = "0011000100110010001100110011010000110101001101100011011100111000";
    char* M_str   = "0011000000110001001100100011001100110100001101010011011000110111";

    uint64_t key = get_key(key_str);
    uint64_t M = get_M(M_str);

    uint64_t C = des_encode(M, key);
    printf("C:\n");
    output_bin(C, 64);
    printf("\n");

    uint64_t plain = des_decode(C, key);
    printf("M:\n");
    output_bin(plain, 64);
    printf("\n");

    printf("M == M ? %d\n", M == plain);

    return 0;
}
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
// des.h
#ifndef DES_H
#define DES_H

typedef unsigned long long uint64_t;
typedef unsigned int       uint32_t;
typedef unsigned char      uint8_t;

// des加密
uint64_t des_encode(uint64_t M, uint64_t key);

// des解密
uint64_t des_decode(uint64_t C, uint64_t key);

// 获取密钥
uint64_t get_key(char* str);

// 获取明文
uint64_t get_M(char* str);

// 输出10进制数的二进制表示
// k: 二进制的位数
void output_bin(uint64_t dec, uint8_t k);

#endif
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
// des.c
#include<stdio.h>
#include"des.h"
#include"table.h"

// 获得byte8第p位的bit
// eg: byte=0100 0010, p=1, bit=1; p=2, bit=0
uint8_t get_bit(uint64_t byte8, uint8_t p)
{
    return (byte8 >> p) & 0x1;
}

// 设置byte8第p位为 bit
void set_bit(uint64_t* byte8, uint8_t p, uint8_t bit)
{
    uint64_t bit_p = get_bit(*byte8, p);
    *byte8 ^= bit_p << p;
    *byte8 |= (uint64_t)bit << p;
}

// 输出k位64bit十进制数的二进制表示
// output: 0bit->(k-1)bit
void output_bin(uint64_t dec, uint8_t k)
{
    for(int i = 0; i < k; ++i)
    {
        printf("%d", (int)get_bit(dec, i));
        if((i + 1) % 8 == 0)printf(" ");
    }
}

// len(str) == 64
// str: 0bit->63bit
uint64_t get_key(char* str)
{
    uint64_t key = 0;
    for(int i = 0; i < 64; ++i)
    {
        uint8_t ch = str[i];
        set_bit(&key, i, ch);
    }
    return key;
}

// 获取明文
uint64_t get_M(char* str)
{
    uint64_t M = 0;
    for(int i = 0; i < 64; ++i)
    {
        uint8_t ch = str[i];
        set_bit(&M, i, ch);
    }
    return M;
}

// 置换选择1
void swap_sel1(uint64_t key, uint64_t* C0, uint64_t* D0)
{
    for(int i = 0; i < 28; ++i)
    {
        set_bit(C0, i, get_bit(key, MatC0[i] - 1));
        set_bit(D0, i, get_bit(key, MatD0[i] - 1));
    }
}

// 循环左移 011(1) -> 110, 在算法中体现为右移
// d: 要移动的数字
// k: 该数字的长度
// l: 移动的长度
uint64_t rol_shift_l(uint64_t d, uint8_t k, uint8_t l)
{
    for(int i = 0; i < l; ++i)
    {
        uint8_t bit = get_bit(d, 0);
        d >>= 1;
        set_bit(&d, k - 1, bit);
    }
    return d;
}

// 生成下一轮子密钥
uint64_t cal_K(uint64_t* Ci, uint64_t* Di, uint32_t it)
{
    uint64_t K = 0;

    *Ci = rol_shift_l(*Ci, 28, Rol[it]);  // 0~23
    *Di = rol_shift_l(*Di, 28, Rol[it]);  //24~47

    // 置换选择2
    for(int i = 0; i < 48; ++i)
    {
        uint32_t idx = MatPC2[i] - 1;
        uint8_t bit;
        if(idx < 28)
        {
            bit = get_bit(*Ci, idx);
        }
        else
        {
            idx -= 28;
            bit = get_bit(*Di, idx);
        }

        set_bit(&K, i, bit);
    }

    return K;
}

// 初始置换IP
void IP_swap(uint64_t M, uint32_t* L, uint32_t* R)
{
    for(int i = 0; i < 64; ++i)
    {
        if(i < 32)
        {
            set_bit((uint64_t*)L, i, get_bit(M, IP[i] - 1));
        }
        else
        {
            set_bit((uint64_t*)R, i - 32, get_bit(M, IP[i] - 1));
        }
    }
}

// IP逆置换
uint64_t IPinv_swap(uint32_t R, uint32_t L)
{
    uint64_t C = 0;
    
    for(int i = 0; i < 64; ++i)
    {
        int idx = IP_inv[i] - 1;
        if(idx < 32)
        {
            set_bit(&C, i, get_bit(R, idx));
        }
        else
        {
            idx -= 32;
            set_bit(&C, i, get_bit(L, idx));
        }
    }
    return C;
}

// 选择运算E
uint64_t E(uint32_t R)
{
    uint64_t mid;

    for(int i = 0; i < 48; ++i)
    {
        set_bit(&mid, i, get_bit(R, ET[i] - 1));
    }

    return mid;
}

// S盒变换
uint32_t S(uint64_t in48)
{
    uint32_t out32 = 0;
    uint64_t row = 0, col = 0;

    for(int i = 0; i < 8; ++i)
    {
        // 取出6*i-> 6*i+5位
        // row: b1b6
        set_bit(&row, 1, get_bit(in48, 6*i  ));
        set_bit(&row, 0, get_bit(in48, 6*i+5));

        // col: b2b3b4b5
        set_bit(&col, 3, get_bit(in48, 6*i+1));
        set_bit(&col, 2, get_bit(in48, 6*i+2));
        set_bit(&col, 1, get_bit(in48, 6*i+3));
        set_bit(&col, 0, get_bit(in48, 6*i+4));

        uint32_t si = S_Box[i][row][col];
        for(int j = 0; j < 4; ++j)
        {
            set_bit((uint64_t*)&out32, 4*i+j, get_bit((uint64_t)si, 3 - j));
        }
    }

    return out32;
}

uint32_t P(uint32_t s)
{
    uint32_t p = 0;
    for(int i = 0; i < 32; ++i)
    {
        set_bit((uint64_t*)&p, i, get_bit((uint64_t)s, PT[i] - 1));
    }
    return p;
}

// F函数
uint32_t F(uint32_t R, uint64_t key48)
{
    // 选择运算
    uint64_t mid = E(R);
    // 模2相加
    uint64_t xor = mid ^ key48;
    // S盒
    uint32_t s = S(xor);
    // 置换运算P
    uint32_t p = P(s);

    return p;
}



uint64_t des_encode(uint64_t M, uint64_t key)
{
    // IP置换
    uint32_t L = 0, R = 0;
    IP_swap(M, &L, &R);

    // 置换选择1
    uint64_t C = 0, D = 0;
    swap_sel1(key, &C, &D);
    // 轮函数
    for(int it = 0; it < 16; ++it)
    {
        uint64_t key48 = cal_K(&C, &D, it);
        uint32_t f = F(R, key48);

        uint32_t lastL = L;
        L = R;
        R = lastL ^ f;
    }

    // IP逆置换
    uint64_t cipher = IPinv_swap(R, L);
    return cipher;
}

// des解密
uint64_t des_decode(uint64_t cipher, uint64_t key)
{
    // IP置换
    uint32_t L = 0, R = 0;
    IP_swap(cipher, &L, &R);

    // 置换选择1
    uint64_t C = 0, D = 0;
    uint64_t keys[16] = {0};
    swap_sel1(key, &C, &D);
    // 轮密钥
    for(int it = 0; it < 16; ++it)
    {
        keys[it] = cal_K(&C, &D, it);
    }

    // 轮函数
    for(int it = 15; it >= 0; --it)
    {
        uint32_t f = F(R, keys[it]);

        uint32_t lastL = L;
        L = R;
        R = lastL ^ f;
    }

    // IP逆置换
    uint64_t M = IPinv_swap(R, L);
    return M;
}
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
// table.h

#ifndef TABLE_H
#define TABLE_H

#include"des.h"

uint32_t MatC0[7 * 4] = 
{
57, 49, 31, 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,
};

uint32_t MatD0[7 * 4] = 
{
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,
};

// 置换选择2表格
uint32_t MatPC2[6 * 8] =
{
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 
};

//  移位表
uint32_t Rol[16] =
{
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};

// IP置换表
uint32_t IP[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 
};
// IP-1置换表
uint32_t IP_inv[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 
};

// E扩展表
uint32_t ET[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
};

 // S盒
uint32_t S_Box[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
};

 //P置换表
uint32_t PT[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
};

#endif
密码学
#DES #分组密码
DES
http://example.com/2023/01/10/DES/
作者
Chen Shuwen
发布于
2023年1月10日
许可协议