embox

1
/**
2
 * @file
3
 * @brief  Data Encryption Standard (DES)
4
 *
5
 * @date Sep 17, 2022
6
 * @author Anton Bondarev
7
 */
8

9
#include <stdint.h>
10
#include <assert.h>
11
#include <string.h>
12

13
#include "des.h"
14

15
#define DES_BITMAP_SIZE      64
16

17
/*
18
 * Tables bellow can be verified on wikipedia:
19
 * http://en.wikipedia.org/wiki/DES_supplementary_material
20
 */
21

22
static const uint8_t initial_permutation [DES_BITMAP_SIZE]	=	{
23
	58, 50, 42, 34, 26, 18, 10, 2,
24
	60, 52, 44, 36, 28, 20, 12, 4,
25
	62, 54, 46, 38, 30, 22, 14, 6,
26
	64, 56, 48, 40, 32, 24, 16, 8,
27
	57, 49, 41, 33, 25, 17,  9, 1,
28
	59, 51, 43, 35, 27, 19, 11, 3,
29
	61, 53, 45, 37, 29, 21, 13, 5,
30
	63, 55, 47, 39, 31, 23, 15, 7
31
};
32

33
static const uint8_t final_permunation[DES_BITMAP_SIZE]	=	{
34
	40, 8, 48, 16, 56, 24, 64, 32,
35
	39, 7, 47, 15, 55, 23, 63, 31,
36
	38, 6, 46, 14, 54, 22, 62, 30,
37
	37, 5, 45, 13, 53, 21, 61, 29,
38
	36, 4, 44, 12, 52, 20, 60, 28,
39
	35, 3, 43, 11, 51, 19, 59, 27,
40
	34, 2, 42, 10, 50, 18, 58, 26,
41
	33, 1, 41,  9, 49, 17, 57, 25
42
};
43

44
/* Substitution boxes (S-boxes)
45
 * This table lists the eight S-boxes used in DES.
46
 * Each S-box replaces a 6-bit input with a 4-bit output. Given a 6-bit input,
47
 * the 4-bit output is found by selecting the row using the outer two bits,
48
 * and the column using the inner four bits. For example, an input "011011"
49
 * has outer bits "01" and inner bits "1101"; noting that the first row is "00"
50
 * and the first column is "0000", the corresponding output for S-box S5
51
 * would be "1001" (=9), the value in the second row, 14th column. (See S-box).
52
 */
53
static const uint8_t s_boxes[8][4][16]	=	{
54
	/* S1 */
55
	{
56
		{14,  4, 13, 1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
57
		{ 0, 15,  7, 4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
58
		{ 4,  1, 14, 8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
59
		{15, 12,  8, 2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}
60
	},
61
	/* S2 */
62
	{
63
		{15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10},
64
		{ 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5},
65
		{ 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15},
66
		{13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}
67
	},
68
	/* S3 */
69
	{
70
		{10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8},
71
		{13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1},
72
		{13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7},
73
		{ 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}
74
	},
75
	/* S4 */
76
	{
77
		{ 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15},
78
		{13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9},
79
		{10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4},
80
		{ 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}
81
	},
82
	/* S5 */
83
	{
84
		{ 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9},
85
		{14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6},
86
		{ 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14},
87
		{11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}
88
	},
89
	/* S6 */
90
	{
91
		{12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11},
92
		{10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8},
93
		{ 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6},
94
		{ 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}
95
	},
96
	/* S7 */
97
	{
98
		{ 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1},
99
		{13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6},
100
		{ 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2},
101
		{ 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}
102
	},
103
	/* S8 */
104
	{
105
		{13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
106
		{ 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
107
		{ 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
108
		{ 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}
109
	}
110
};
111

112
static const char des_extansion[48]= {
113
	 32,  1,  2,  3,  4,  5,
114
	  4,  5,  6,  7  ,8,  9,
115
	  8,  9, 10, 11, 12, 13,
116
	 12, 13, 14, 15, 16, 17,
117
	 16, 17, 18, 19, 20, 21,
118
	 20, 21, 22, 23, 24, 25,
119
	 24, 25, 26, 27, 28, 29,
120
	 28, 29, 30, 31, 32,  1
121
};
122

123
/* The P permutation shuffles the bits of a 32-bit half-block. */
124
static const char permutation[32]={
125
	 16,  7, 20, 21, 29, 12, 28, 17,
126
	  1, 15, 23, 26,  5, 18, 31, 10,
127
	  2,  8, 24, 14, 32, 27,  3,  9,
128
	 19, 13, 30,  6, 22, 11,  4,  25
129
};
130

131
/* The "Left" and "Right" halves of the table show which bits from
132
 * the input key form the left and right sections of the key schedule state.
133
 * Note that only 56 bits of the 64 bits of the input are selected;
134
 * the remaining eight (8, 16, 24, 32, 40, 48, 56, 64) were specified for use as parity bits.
135
 */
136
static const char permuted_choice_1[56] = {
137
		 57, 49, 41, 33, 25, 17,  9,
138
		  1, 58, 50, 42, 34, 26, 18,
139
		 10,  2, 59, 51, 43, 35, 27,
140
		 19, 11,  3, 60, 52, 44, 36,
141
		 63, 55, 47, 39, 31, 23, 15,
142
		  7, 62, 54, 46, 38, 30, 22,
143
		 14,  6, 61, 53, 45, 37, 29,
144
		 21, 13,  5, 28, 20, 12,  4
145
};
146

147
static const char rotation_table[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
148

149
static const char permuted_choice_2[48]= {
150
		 14, 17, 11, 24,  1,  5,
151
		  3, 28, 15,  6, 21, 10,
152
		 23, 19, 12,  4, 26,  8,
153
		 16,  7, 27, 20, 13,  2,
154
		 41, 52, 31, 37, 47, 55,
155
		 30, 40, 51, 45, 33, 48,
156
		 44, 49, 39, 56, 34, 53,
157
		 46, 42, 50, 36, 29, 32
158
};
159

160
static inline void bytes_to_bits(uint8_t src[8], uint8_t dst[DES_BITMAP_SIZE]) {
161
	int i, k, n;
162

163
	n = 0;
164

165
	memset(dst, 0 , DES_BITMAP_SIZE);
166

167
	for (i = 0; i < 8; i++) {
168
		for (k = 7; k >= 0; k--) {
169
			dst[n] = (src[i] >> k) & 0x01;
170
			n++;
171
		}
172
	}
173
}
174

175
static inline void bits_to_bytes(uint8_t dst[DES_BITMAP_SIZE], uint8_t src[8]) {
176
	int n;
177

178
	memset(src, 0, 8);
179

180
	for (n = 0; n < DES_BITMAP_SIZE; n++) {
181
		src[n / 8] |= dst[n] << (7 - (n % 8));
182
	}
183
}
184

185
static inline void
186
permutation_init(uint8_t data[8], uint8_t left[32], uint8_t right[32]) {
187
	int i;
188
	uint8_t bits[DES_BITMAP_SIZE];
189

190
	bytes_to_bits(data, bits);
191

192
	i = 0;
193

194
	for (; i < 32; i++) {
195
		left[i] = bits[initial_permutation[i] - 1];
196
		right[i] = bits[initial_permutation[i + 32] - 1];
197
	}
198
}
199

200
static inline void
201
permutation_finit(uint8_t res[8], uint8_t left[32], uint8_t right[32]) {
202
	uint8_t tmp1[DES_BITMAP_SIZE];
203
	uint8_t d[DES_BITMAP_SIZE];
204
	int i;
205

206
	for (i = 0; i < 32; i++) {
207
		d[i + 32] = right[i];
208
		d[i] = left[i];
209
	}
210

211
	for (i = 0; i < 32; i++) {
212
		tmp1[i] = d[final_permunation[i] - 1];
213
		tmp1[i + 32] = d[final_permunation[i + 32] - 1];
214
	}
215

216
	bits_to_bytes(tmp1, res);
217
}
218

219
static inline void fill_keys(uint8_t bin_key[8], uint8_t c[28], uint8_t d[28]) {
220
	int i;
221
	uint8_t key_bits[DES_BITMAP_SIZE];
222

223
	bytes_to_bits(bin_key, key_bits);
224

225
	for (i = 0; i < 28; i++) {
226
		c[i] = key_bits[permuted_choice_1[i] - 1];
227
		d[i] = key_bits[permuted_choice_1[i + 28] - 1];
228
	}
229
}
230

231
static inline void rotate(int step, uint8_t c[28], uint8_t d[28], uint8_t key[48]) {
232
	int i, k;
233
	uint8_t tmp_key[56];
234

235
	for (i = 0; i < 28; i++) {
236
		k = (i + rotation_table[step]) % 28;
237
		tmp_key[i] = c[k];
238
		tmp_key[i + 28] = d[k];
239
	}
240

241
	for (i = 0; i < 28; i++) {
242
		d[i] = tmp_key[i + 28];
243
		c[i] = tmp_key[i];
244
	}
245

246
	for (i = 0; i < 48; i++) {
247
		key[i] = tmp_key[permuted_choice_2[i] - 1];
248
	}
249
}
250

251
static inline void
252
permutate(uint8_t left[32], uint8_t right[32], uint8_t key[48], uint8_t res[32]) {
253
	uint8_t tmp_key[48];
254
	int i;
255
	uint8_t tmp[32];
256

257
	for (i = 0; i < 48; i++) {
258
		tmp_key[i] = (uint8_t) (right[des_extansion[i] - 1] ^ key[i]);
259
	}
260

261
	/* 48->32 */
262
	for (i = 0; i < 8; i++) {
263
		uint8_t *p = &tmp_key[i * 6];
264
		uint8_t col, row;
265
		uint8_t k;
266

267
		col = (p[1] << 3) ^ (p[2] << 2) ^ (p[3] << 1) ^ p[4];
268
		row = (p[0] << 1) ^ p[5];
269

270
		k = s_boxes[i][row][col];
271

272
		tmp[i * 4 + 0] = ((k >> 3) & 0x01);
273
		tmp[i * 4 + 1] = ((k >> 2) & 0x01);
274
		tmp[i * 4 + 2] = ((k >> 1) & 0x01);
275
		tmp[i * 4 + 3] = ((k >> 0) & 0x01);
276
	}
277

278
	for (i = 0; i < 32; i++) {
279
		res[i] = tmp[permutation[i] - 1] ^ left[i];
280
	}
281
}
282

283
void des_encrypt(uint8_t data[8], uint8_t key[8], uint8_t res[8]) {
284
	int n;
285
	uint8_t left[DES_BITMAP_SIZE / 2], right[DES_BITMAP_SIZE / 2];
286
	uint8_t tmp_bits[DES_BITMAP_SIZE / 2];
287
	uint8_t c[28], d[28];
288
	uint8_t tmp_key[48];
289

290
	/* 8 bytes -> 64 bytes -> 2 x 28 (56) bytes */
291
	fill_keys(key, c, d);
292

293
	permutation_init(data, left, right);
294

295
	for (n = 0; n < 16; n++) {
296

297
		rotate(n, c, d, tmp_key);
298

299
		permutate(left, right, tmp_key, tmp_bits);
300

301
		memcpy(left, right, sizeof(left));
302
		memcpy(right, tmp_bits, sizeof(right));
303
	}
304

305
	permutation_finit(res, right, left);
306
}
307

308
void des_decrypt(uint8_t data[8], uint8_t key[8], uint8_t res[8]) {
309
	int  n;
310
	uint8_t left[DES_BITMAP_SIZE / 2], right[DES_BITMAP_SIZE / 2];
311
	uint8_t tmp_bits[DES_BITMAP_SIZE / 2];
312
	uint8_t c[28], d[28];
313
	uint8_t tmp_keys[16][48];
314

315
	fill_keys(key, c, d);
316

317
	permutation_init(data, right, left);
318

319
	for (n = 15; n >= 0; n--) {
320
		rotate(15 - n, c, d, tmp_keys[n]);
321
	}
322

323
	for (n = 0; n < 16; n++) {
324
		permutate(right, left, tmp_keys[n], tmp_bits);
325

326
		memcpy(right, left, 32);
327
		memcpy(left, tmp_bits, 32);
328
	}
329

330
	permutation_finit(res, left, right);
331
}
332