Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 616
1
2
/*
3
* Fast implementation of the DES, as described in the Federal Register,
4
* Vol. 40, No. 52, p. 12134, March 17, 1975.
5
*
6
* Stuart Levy, Minnesota Supercomputer Center, April 1988.
7
* Currently (2007) [email protected]
8
* NCSA, University of Illinois Urbana-Champaign
9
*
10
* Calling sequence:
11
*
12
* typedef unsigned long keysched[32];
13
*
14
* fsetkey(key, keysched) / * Converts a DES key to a "key schedule" * /
15
* unsigned char key[8];
16
* keysched *ks;
17
*
18
* fencrypt(block, decrypt, keysched) / * En/decrypts one 64-bit block * /
19
* unsigned char block[8]; / * data, en/decrypted in place * /
20
* int decrypt; / * 0=>encrypt, 1=>decrypt * /
21
* keysched *ks; / * key schedule, as set by fsetkey * /
22
*
23
* Key and data block representation:
24
* The 56-bit key (bits 1..64 including "parity" bits 8, 16, 24, ..., 64)
25
* and the 64-bit data block (bits 1..64)
26
* are each stored in arrays of 8 bytes.
27
* Following the NBS numbering, the MSB has the bit number 1, so
28
* key[0] = 128*bit1 + 64*bit2 + ... + 1*bit8, ... through
29
* key[7] = 128*bit57 + 64*bit58 + ... + 1*bit64.
30
* In the key, "parity" bits are not checked; their values are ignored.
31
*
32
*/
33
34
/*
35
===============================================================================
36
License
37
38
des56.c is licensed under the terms of the MIT license reproduced below.
39
This means that des56.c is free software and can be used for both academic
40
and commercial purposes at absolutely no cost.
41
===============================================================================
42
Copyright (C) 1988 Stuart Levy
43
44
Permission is hereby granted, free of charge, to any person obtaining a copy
45
of this software and associated documentation files (the "Software"), to deal
46
in the Software without restriction, including without limitation the rights
47
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
48
copies of the Software, and to permit persons to whom the Software is
49
furnished to do so, subject to the following conditions:
50
51
The above copyright notice and this permission notice shall be included in
52
all copies or substantial portions of the Software.
53
54
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
55
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
56
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
57
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
58
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
59
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
60
THE SOFTWARE.
61
*/
62
63
64
#include "des56.h"
65
66
67
/*
68
* Key schedule generation.
69
* We begin by pointlessly permuting the 56 useful key bits into
70
* two groups of 28 bits called C and D.
71
* bK_C and bK_D are indexed by C and D bit numbers, respectively,
72
* and give the key bit number (1..64) which should initialize that C/D bit.
73
* This is the "permuted choice 1" table.
74
*/
75
76
static tiny bK_C[28] = {
77
57, 49, 41, 33, 25, 17, 9,
78
1, 58, 50, 42, 34, 26, 18,
79
10, 2, 59, 51, 43, 35, 27,
80
19, 11, 3, 60, 52, 44, 36,
81
};
82
static tiny bK_D[28] = {
83
63, 55, 47, 39, 31, 23, 15,
84
7, 62, 54, 46, 38, 30, 22,
85
14, 6, 61, 53, 45, 37, 29,
86
21, 13, 5, 28, 20, 12, 4,
87
};
88
89
/*
90
* For speed, we invert these, building tables to map groups of
91
* key bits into the corresponding C and D bits.
92
* We represent C and D each as 28 contiguous bits right-justified in a
93
* word, padded on the left with zeros.
94
* If key byte `i' is said to contain bits Ki,0 (MSB) Ki,1 ... Ki,7 (LSB)
95
* then
96
* wC_K4[i][Ki,0 Ki,1 Ki,2 Ki,3] gives the C bits for Ki,0..3,
97
* wD_K4[i][Ki,0 Ki,1 Ki,2 Ki,3] the corresponding D bits,
98
* wC_K3[i][Ki,4 Ki,5 Ki,6] the C bits for Ki,4..6,
99
* and wD_K3[i][Ki,4 Ki,5 Ki,6] the D bits for Ki,4..6.
100
* Ki,7 is ignored since it is the nominal parity bit.
101
* We could just use a single table for [i][Ki,0 .. Ki,6] but that
102
* would take a lot of storage for such a rarely-used function.
103
*/
104
105
static word32 wC_K4[8][16], wC_K3[8][8];
106
static word32 wD_K4[8][16], wD_K3[8][8];
107
108
/*
109
* Successive Ci and Di for the sixteen steps in the key schedule are
110
* created by independent 28-bit left circular shifts on C and D.
111
* The shift count varies with the step number.
112
*/
113
static tiny preshift[16] = {
114
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
115
};
116
117
/*
118
* Each step in the key schedule is generated by selecting 48 bits
119
* (8 groups of 6 bits) from the appropriately shifted Ci and Di.
120
* bCD_KS, indexed by the key schedule bit number, gives the bit number
121
* in CD (CD1 = MSB of C, CD28 = LSB of C, CD29 = MSB of D, CD56 = LSB of D)
122
* which determines that bit of the key schedule.
123
* Note that only C bits (1..28) appear in the first (upper) 24 bits of
124
* the key schedule, and D bits (29..56) in the second (lower) 24 bits.
125
* This is the "permuted-choice-2" table.
126
*/
127
128
static tiny bCD_KS[48] = {
129
14, 17, 11, 24, 1, 5,
130
3, 28, 15, 6, 21, 10,
131
23, 19, 12, 4, 26, 8,
132
16, 7, 27, 20, 13, 2,
133
41, 52, 31, 37, 47, 55,
134
30, 40, 51, 45, 33, 48,
135
44, 49, 39, 56, 34, 53,
136
46, 42, 50, 36, 29, 32,
137
};
138
139
/*
140
* We invert bCD_KS into a pair of tables which map groups of 4
141
* C or D bits into corresponding key schedule bits.
142
* We represent each step of the key schedule as 8 groups of 8 bits,
143
* with the 6 real bits right-justified in each 8-bit group.
144
* hKS_C4[i][C4i+1 .. C4i+4] gives the bits in the high order (first four)
145
* key schedule "bytes" which correspond to C bits 4i+1 .. 4i+4.
146
* lKS_D4[i][D4i+1 .. D4i+4] gives the appropriate bits in the latter (last 4)
147
* key schedule bytes, from the corresponding D bits.
148
*/
149
150
static word32 hKS_C4[7][16];
151
static word32 lKS_D4[7][16];
152
153
/*
154
* Encryption/decryption.
155
* Before beginning, and after ending, we perform another useless permutation
156
* on the bits in the data block.
157
*
158
* The initial permutation and its inverse, final permutation
159
* are too simple to need a table for. If we break the input I1 .. I64 into
160
* 8-bit chunks I0,0 I0,1 ... I0,7 I1,0 I1,1 ... I7,7
161
* then the initial permutation sets LR as follows:
162
* L = I7,1 I6,1 I5,1 ... I0,1 I7,3 I6,3 ... I0,3 I7,5 ... I0,5 I7,7 ... I0,7
163
* and
164
* R = I7,0 I6,0 I5,0 ... I0,0 I7,2 I6,2 ... I0,2 I7,4 ... I0,4 I7,6 ... I0,6
165
*
166
* If we number the bits in the final LR similarly,
167
* L = L0,0 L0,1 ... L3,7 R = R0,0 R0,1 ... R3,7
168
* then the output is
169
* O = R0,7 L0,7 R1,7 L1,7 ... R3,7 L3,7 R0,6 L0,6 ... L3,6 R0,5 ... R3,0 L3,0
170
*
171
* To speed I => LR shuffling we use an array of 32-bit values indexed by
172
* 8-bit input bytes.
173
* wL_I8[ 0 I0,1 0 I0,3 0 I0,5 0 I0,7 ] = the corresponding L bits.
174
* Other R and L bits are derived from wL_I8 by shifting.
175
*
176
* To speed LR => O shuffling, an array of 32-bit values indexed by 4-bit lumps:
177
* wO_L4[ L0,4 L0,5 L0,6 L0,7 ] = the corresponding high-order 32 O bits.
178
*/
179
180
static word32 wL_I8[0x55 + 1];
181
static word32 wO_L4[16];
182
183
/*
184
* Core of encryption/decryption.
185
* In each key schedule stage, we:
186
* take 8 overlapping groups of 6 bits each from R
187
* (the NBS tabulates the bit selections in the E table,
188
* but it's so simple we just use shifting to get the right bits)
189
* XOR each group with the corresponding bits from the key schedule
190
* Use the resulting 6 bits as an index into the appropriate S table
191
* (there are 8 such tables, one per group of 6 bits)
192
* Each S entry yields 4 bits.
193
* The 8 groups of 4 bits are catenated into a 32-bit value.
194
* Those 32 bits are permuted according to the P table.
195
* Finally the permuted 32-bit value is XORed with L and becomes
196
* the R value for the next stage, while the previous R becomes the new L.
197
*
198
* Here, we merge the P permutation with the S tables by making the
199
* S entries be 32-bit masks, already suitably permuted.
200
* Also, the bits in each six-bit group must be permuted before use as
201
* an index into the NBS-tabulated S tables.
202
* We rearrange entries in wPS so that natural bit order can be used.
203
*/
204
205
static word32 wPS[8][64];
206
207
static tiny P[32] = {
208
16, 7, 20, 21,
209
29, 12, 28, 17,
210
1, 15, 23, 26,
211
5, 18, 31, 10,
212
2, 8, 24, 14,
213
32, 27, 3, 9,
214
19, 13, 30, 6,
215
22, 11, 4, 25,
216
};
217
218
static tiny S[8][64] = {
219
{
220
14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
221
0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
222
4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
223
15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,
224
},
225
226
{
227
15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
228
3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
229
0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
230
13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,
231
},
232
233
{
234
10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
235
13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
236
13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
237
1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,
238
},
239
240
{
241
7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
242
13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
243
10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
244
3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,
245
},
246
247
{
248
2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
249
14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
250
4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
251
11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,
252
},
253
254
{
255
12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
256
10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
257
9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
258
4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,
259
},
260
261
{
262
4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
263
13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
264
1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
265
6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,
266
},
267
268
{
269
13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
270
1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
271
7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
272
2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11,
273
},
274
};
275
276
static void buildtables( void )
277
{
278
register int i, j;
279
register word32 v;
280
word32 wC_K[64], wD_K[64];
281
word32 hKS_C[28], lKS_D[28];
282
int Smap[64];
283
word32 wP[32];
284
285
#if USG
286
# define ZERO(array) memset((char *)(array), '\0', sizeof(array))
287
#else
288
# if BSD
289
# define ZERO(array) bzero((char *)(array), sizeof(array))
290
# else
291
# define ZERO(array) { register word32 *p = (word32 *)(array); \
292
i = sizeof(array) / sizeof(*p); \
293
do { *p++ = 0; } while(--i > 0); \
294
}
295
# endif
296
#endif
297
298
299
/* Invert permuted-choice-1 (key => C,D) */
300
301
ZERO(wC_K);
302
ZERO(wD_K);
303
v = 1;
304
for(j = 28; --j >= 0; ) {
305
wC_K[ bK_C[j] - 1 ] = wD_K[ bK_D[j] - 1 ] = v;
306
v += v; /* (i.e. v <<= 1) */
307
}
308
309
for(i = 0; i < 64; i++) {
310
int t = 8 >> (i & 3);
311
for(j = 0; j < 16; j++) {
312
if(j & t) {
313
wC_K4[i >> 3][j] |= wC_K[i];
314
wD_K4[i >> 3][j] |= wD_K[i];
315
if(j < 8) {
316
wC_K3[i >> 3][j] |= wC_K[i + 3];
317
wD_K3[i >> 3][j] |= wD_K[i + 3];
318
}
319
}
320
}
321
/* Generate the sequence 0,1,2,3, 8,9,10,11, ..., 56,57,58,59. */
322
if(t == 1) i += 4;
323
}
324
325
/* Invert permuted-choice-2 */
326
327
ZERO(hKS_C);
328
ZERO(lKS_D);
329
v = 1;
330
for(i = 24; (i -= 6) >= 0; ) {
331
j = i+5;
332
do {
333
hKS_C[ bCD_KS[j] - 1 ] = lKS_D[ bCD_KS[j+24] - 28 - 1 ] = v;
334
v += v; /* Like v <<= 1 but may be faster */
335
} while(--j >= i);
336
v <<= 2; /* Keep byte aligned */
337
}
338
339
for(i = 0; i < 28; i++) {
340
v = 8 >> (i & 3);
341
for(j = 0; j < 16; j++) {
342
if(j & v) {
343
hKS_C4[i >> 2][j] |= hKS_C[i];
344
lKS_D4[i >> 2][j] |= lKS_D[i];
345
}
346
}
347
}
348
349
/* Initial permutation */
350
351
for(i = 0; i <= 0x55; i++) {
352
v = 0;
353
if(i & 64) v = (word32) 1 << 24;
354
if(i & 16) v |= (word32) 1 << 16;
355
if(i & 4) v |= (word32) 1 << 8;
356
if(i & 1) v |= 1;
357
wL_I8[i] = v;
358
}
359
360
/* Final permutation */
361
362
for(i = 0; i < 16; i++) {
363
v = 0;
364
if(i & 1) v = (word32) 1 << 24;
365
if(i & 2) v |= (word32) 1 << 16;
366
if(i & 4) v |= (word32) 1 << 8;
367
if(i & 8) v |= (word32) 1;
368
wO_L4[i] = v;
369
}
370
371
/* Funny bit rearrangement on second index into S tables */
372
373
for(i = 0; i < 64; i++) {
374
Smap[i] = (i & 0x20) | (i & 1) << 4 | (i & 0x1e) >> 1;
375
}
376
377
/* Invert permutation P into mask indexed by R bit number */
378
379
v = 1;
380
for(i = 32; --i >= 0; ) {
381
wP[ P[i] - 1 ] = v;
382
v += v;
383
}
384
385
/* Build bit-mask versions of S tables, indexed in natural bit order */
386
387
for(i = 0; i < 8; i++) {
388
for(j = 0; j < 64; j++) {
389
int k, t;
390
391
t = S[i][ Smap[j] ];
392
for(k = 0; k < 4; k++) {
393
if(t & 8)
394
wPS[i][j] |= wP[4*i + k];
395
t += t;
396
}
397
}
398
}
399
}
400
401
402
void fsetkey(char key[8], keysched *ks)
403
{
404
register int i;
405
register word32 C, D;
406
static int built = 0;
407
408
if(!built) {
409
buildtables();
410
built = 1;
411
}
412
413
C = D = 0;
414
for(i = 0; i < 8; i++) {
415
register int v;
416
417
v = key[i] >> 1; /* Discard "parity" bit */
418
C |= wC_K4[i][(v>>3) & 15] | wC_K3[i][v & 7];
419
D |= wD_K4[i][(v>>3) & 15] | wD_K3[i][v & 7];
420
}
421
422
/*
423
* C and D now hold the suitably right-justified
424
* 28 permuted key bits each.
425
*/
426
for(i = 0; i < 16; i++) {
427
#ifdef CRAY
428
#define choice2(x, v) x[6][v&15] | x[5][(v>>4)&15] | x[4][(v>>8)&15] | \
429
x[3][(v>>12)&15] | x[2][(v>>16)&15] | x[1][(v>>20)&15] | \
430
x[0][(v>>24)&15]
431
#else
432
register word32 *ap;
433
434
# define choice2(x, v) ( \
435
ap = &(x)[0][0], \
436
ap[16*6 + (v&15)] | \
437
ap[16*5 + ((v>>4)&15)] | ap[16*4 + ((v>>8)&15)] | \
438
ap[16*3 + ((v>>12)&15)] | ap[16*2 + ((v>>16)&15)] | \
439
ap[16*1 + ((v>>20)&15)] | ap[16*0 + ((v>>24)&15)] )
440
#endif
441
442
443
/* 28-bit left circular shift */
444
C <<= preshift[i];
445
C = ((C >> 28) & 3) | (C & (((word32)1<<28) - 1));
446
ks->KS[i].h = choice2(hKS_C4, C);
447
448
D <<= preshift[i];
449
D = ((D >> 28) & 3) | (D & (((word32)1<<28) - 1));
450
ks->KS[i].l = choice2(lKS_D4, D);
451
}
452
}
453
454
void
455
fencrypt(char block[8], int decrypt, keysched *ks)
456
{
457
int i;
458
register word32 L, R;
459
register struct keystage *ksp;
460
register word32 *ap;
461
462
/* Initial permutation */
463
464
L = R = 0;
465
i = 7;
466
ap = wL_I8;
467
do {
468
register int v;
469
470
v = block[i]; /* Could optimize according to ENDIAN */
471
L = ap[v & 0x55] | (L << 1);
472
R = ap[(v >> 1) & 0x55] | (R << 1);
473
} while(--i >= 0);
474
475
if(decrypt) {
476
ksp = (keystage*) &(ks->KS[15]);
477
} else {
478
ksp = (keystage*) &(ks->KS[0]);
479
}
480
481
#ifdef CRAY
482
# define PS(i,j) wPS[i][j]
483
#else
484
# define PS(i,j) ap[64*(i) + (j)]
485
ap = &wPS[0][0];
486
#endif
487
488
i = 16;
489
do {
490
register word32 k, tR;
491
492
tR = (R >> 15) | (R << 17);
493
494
k = (word32) ksp->h;
495
L ^= PS(0, ((tR >> 12) ^ (k >> 24)) & 63)
496
| PS(1, ((tR >> 8) ^ (k >> 16)) & 63)
497
| PS(2, ((tR >> 4) ^ (k >> 8)) & 63)
498
| PS(3, (tR ^ k) & 63);
499
500
k = ksp->l;
501
L ^= PS(4, ((R >> 11) ^ (k >> 24)) & 63)
502
| PS(5, ((R >> 7) ^ (k >> 16)) & 63)
503
| PS(6, ((R >> 3) ^ (k >> 8)) & 63)
504
| PS(7, ((tR >> 16) ^ k) & 63);
505
506
tR = L;
507
L = R;
508
R = tR;
509
510
511
if(decrypt)
512
ksp--;
513
else
514
ksp++;
515
} while(--i > 0);
516
{
517
register word32 t;
518
519
#ifdef CRAY
520
# define FP(k) (wO_L4[ (L >> (k)) & 15 ] << 1 | wO_L4[ (R >> (k)) & 15 ])
521
#else
522
# define FP(k) (ap[ (L >> (k)) & 15 ] << 1 | ap[ (R >> (k)) & 15 ])
523
524
ap = wO_L4;
525
#endif
526
527
t = FP(0) | (FP(8) | (FP(16) | (FP(24) << 2)) << 2) << 2;
528
R = FP(4) | (FP(12) | (FP(20) | (FP(28) << 2)) << 2) << 2;
529
L = t;
530
}
531
{
532
register word32 t;
533
register char *bp;
534
535
bp = &block[7];
536
t = R;
537
*bp = t & 255;
538
*--bp = (t >>= 8) & 255;
539
*--bp = (t >>= 8) & 255;
540
*--bp = (t >> 8) & 255;
541
t = L;
542
*--bp = t & 255;
543
*--bp = (t >>= 8) & 255;
544
*--bp = (t >>= 8) & 255;
545
*--bp = (t >> 8) & 255;
546
}
547
}
548
549
550
551