/[eiffelstudio]/trunk/Src/library/encryption/Clib/des.c
ViewVC logotype

Contents of /trunk/Src/library/encryption/Clib/des.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 13732 - (show annotations)
Tue Mar 16 22:05:16 1999 UTC (20 years, 11 months ago) by manus
File MIME type: text/plain
File size: 13890 byte(s)
Initial revision

1 /*
2
3 ##### ###### #### ####
4 # # # # # #
5 # # ##### #### #
6 # # # # ### #
7 # # # # # ### # #
8 ##### ###### #### ### ####
9
10 Sofware DES functions.
11
12 Written 12 Dec 1986 by Phil Karn, KA9Q; large sections adapted from
13 the 1977 public-domain program by Jim Gillogly
14 */
15
16 #include "eif_config.h"
17 #include "eif_portable.h"
18
19 /* These routines are written for a big endian machine. Make sure we swap
20 * the bytes on a little endian machine.
21 */
22 #if BYTEORDER == 0x12345678
23 #define LITTLE_ENDIAN
24 #endif
25 #if BYTEORDER == 0x1234
26 #define LITTLE_ENDIAN
27 #endif
28
29 #ifdef LITTLE_ENDIAN
30 static uint32 byteswap();
31 #endif
32
33 /* Tables defined in the Data Encryption Standard documents */
34
35 /* initial permutation IP */
36 static char ip[] = {
37 58, 50, 42, 34, 26, 18, 10, 2,
38 60, 52, 44, 36, 28, 20, 12, 4,
39 62, 54, 46, 38, 30, 22, 14, 6,
40 64, 56, 48, 40, 32, 24, 16, 8,
41 57, 49, 41, 33, 25, 17, 9, 1,
42 59, 51, 43, 35, 27, 19, 11, 3,
43 61, 53, 45, 37, 29, 21, 13, 5,
44 63, 55, 47, 39, 31, 23, 15, 7
45 };
46
47 /* final permutation IP^-1 */
48 static char fp[] = {
49 40, 8, 48, 16, 56, 24, 64, 32,
50 39, 7, 47, 15, 55, 23, 63, 31,
51 38, 6, 46, 14, 54, 22, 62, 30,
52 37, 5, 45, 13, 53, 21, 61, 29,
53 36, 4, 44, 12, 52, 20, 60, 28,
54 35, 3, 43, 11, 51, 19, 59, 27,
55 34, 2, 42, 10, 50, 18, 58, 26,
56 33, 1, 41, 9, 49, 17, 57, 25
57 };
58
59 /* expansion operation matrix
60 * This is for reference only; it is unused in the code
61 * as the f() function performs it implicitly for speed
62 */
63 #ifdef notdef
64 static char ei[] = {
65 32, 1, 2, 3, 4, 5,
66 4, 5, 6, 7, 8, 9,
67 8, 9, 10, 11, 12, 13,
68 12, 13, 14, 15, 16, 17,
69 16, 17, 18, 19, 20, 21,
70 20, 21, 22, 23, 24, 25,
71 24, 25, 26, 27, 28, 29,
72 28, 29, 30, 31, 32, 1
73 };
74 #endif
75
76 /* permuted choice table (key) */
77 static char pc1[] = {
78 57, 49, 41, 33, 25, 17, 9,
79 1, 58, 50, 42, 34, 26, 18,
80 10, 2, 59, 51, 43, 35, 27,
81 19, 11, 3, 60, 52, 44, 36,
82 63, 55, 47, 39, 31, 23, 15,
83 7, 62, 54, 46, 38, 30, 22,
84 14, 6, 61, 53, 45, 37, 29,
85 21, 13, 5, 28, 20, 12, 4
86 };
87
88 /* number left rotations of pc1 */
89 static char totrot[] = {
90 1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
91 };
92
93 /* permuted choice key (table) */
94 static char pc2[] = {
95 14, 17, 11, 24, 1, 5,
96 3, 28, 15, 6, 21, 10,
97 23, 19, 12, 4, 26, 8,
98 16, 7, 27, 20, 13, 2,
99 41, 52, 31, 37, 47, 55,
100 30, 40, 51, 45, 33, 48,
101 44, 49, 39, 56, 34, 53,
102 46, 42, 50, 36, 29, 32
103 };
104
105 /* The (in)famous S-boxes */
106 static char si[8][64] = {
107 /* S1 */
108 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
109 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
110 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
111 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,
112
113 /* S2 */
114 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
115 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
116 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
117 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9,
118
119 /* S3 */
120 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
121 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
122 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
123 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12,
124
125 /* S4 */
126 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
127 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
128 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
129 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14,
130
131 /* S5 */
132 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
133 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
134 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
135 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3,
136
137 /* S6 */
138 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
139 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
140 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
141 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13,
142
143 /* S7 */
144 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
145 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
146 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
147 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12,
148
149 /* S8 */
150 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
151 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
152 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
153 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
154 };
155
156 /* 32-bit permutation function P used on the output of the S-boxes */
157 static char p32i[] = {
158 16, 7, 20, 21,
159 29, 12, 28, 17,
160 1, 15, 23, 26,
161 5, 18, 31, 10,
162 2, 8, 24, 14,
163 32, 27, 3, 9,
164 19, 13, 30, 6,
165 22, 11, 4, 25
166 };
167 /* End of DES-defined tables */
168
169 /* Lookup tables initialized once only at startup by desinit() */
170 static int32 (*sp)[64]; /* Combined S and P boxes */
171
172 static char (*iperm)[16][8]; /* Initial and final permutations */
173 static char (*fperm)[16][8];
174
175 /* 8 6-bit subkeys for each of 16 rounds, initialized by setkey() */
176 static unsigned char (*kn)[8];
177
178 /* bit 0 is left-most in byte */
179 static int bytebit[] = {
180 0200,0100,040,020,010,04,02,01
181 };
182
183 static int nibblebit[] = {
184 010,04,02,01
185 };
186 static int desmode;
187
188 rt_private void permute();
189 rt_private void round();
190 rt_private int32 f();
191 rt_private void perminit();
192 rt_private int spinit();
193
194 /* Allocate space and initialize DES lookup arrays
195 * mode == 0: standard Data Encryption Algorithm
196 * mode == 1: DEA without initial and final permutations for speed
197 * mode == 2: DEA without permutations and with 128-byte key (completely
198 * independent subkeys for each round)
199 */
200 int desinit(int mode)
201 {
202 #ifdef __VMS /* why? this belongs in a header! And, it's wrong to boot. */
203 /* s.b. void* malloc(size_t); */
204 #else
205 /* char *malloc(); */
206 #endif
207
208 if(sp != NULL){
209 /* Already initialized */
210 return 0;
211 }
212 desmode = mode;
213
214 if((sp = (int32 (*)[64])malloc(sizeof(int32) * 8 * 64)) == NULL){
215 return -1;
216 }
217 spinit();
218 kn = (unsigned char (*)[8])malloc(sizeof(char) * 8 * 16);
219 if(kn == NULL){
220 free((char *)sp);
221 return -1;
222 }
223 if(mode == 1 || mode == 2) /* No permutations */
224 return 0;
225
226 iperm = (char (*)[16][8])malloc(sizeof(char) * 16 * 16 * 8);
227 if(iperm == NULL){
228 free((char *)sp);
229 free((char *)kn);
230 return -1;
231 }
232 perminit(iperm,ip);
233
234 fperm = (char (*)[16][8])malloc(sizeof(char) * 16 * 16 * 8);
235 if(fperm == NULL){
236 free((char *)sp);
237 free((char *)kn);
238 free((char *)iperm);
239 return -1;
240 }
241 perminit(fperm,fp);
242
243 return 0;
244 }
245 /* Free up storage used by DES */
246 void desdone()
247 {
248 if(sp == NULL)
249 return; /* Already done */
250
251 free((char *)sp);
252 free((char *)kn);
253 if(iperm != NULL)
254 free((char *)iperm);
255 if(fperm != NULL)
256 free((char *)fperm);
257
258 sp = NULL;
259 iperm = NULL;
260 fperm = NULL;
261 kn = NULL;
262 }
263 /* Set key (initialize key schedule array) */
264 void setkey(char *key)
265 /* 64 bits (will use only 56) */
266 {
267 char pc1m[56]; /* place to modify pc1 into */
268 char pcr[56]; /* place to rotate pc1 into */
269 register int i,j,l;
270 int m;
271
272 /* In mode 2, the 128 bytes of subkey are set directly from the
273 * user's key, allowing him to use completely independent
274 * subkeys for each round. Note that the user MUST specify a
275 * full 128 bytes.
276 *
277 * I would like to think that this technique gives the NSA a real
278 * headache, but I'm not THAT naive.
279 */
280 if(desmode == 2){
281 for(i=0;i<16;i++)
282 for(j=0;j<8;j++)
283 kn[i][j] = *key++;
284 return;
285 }
286 /* Clear key schedule */
287 for (i=0; i<16; i++)
288 for (j=0; j<8; j++)
289 kn[i][j]=0;
290
291 for (j=0; j<56; j++) { /* convert pc1 to bits of key */
292 l=pc1[j]-1; /* integer bit location */
293 m = l & 07; /* find bit */
294 pc1m[j]=(key[l>>3] & /* find which key byte l is in */
295 bytebit[m]) /* and which bit of that byte */
296 ? 1 : 0; /* and store 1-bit result */
297 }
298 for (i=0; i<16; i++) { /* key chunk for each iteration */
299 for (j=0; j<56; j++) /* rotate pc1 the right amount */
300 pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
301 /* rotate left and right halves independently */
302 for (j=0; j<48; j++){ /* select bits individually */
303 /* check bit that goes to kn[j] */
304 if (pcr[pc2[j]-1]){
305 /* mask it in if it's there */
306 l= j % 6;
307 kn[i][j/6] |= bytebit[l] >> 2;
308 }
309 }
310 }
311 }
312 /* In-place encryption of 64-bit block */
313 void endes(char *block)
314 {
315 register int i;
316 uint32 work[2]; /* Working data storage */
317 int32 tmp;
318
319 permute(block,iperm,(char *)work); /* Initial Permutation */
320 #ifdef LITTLE_ENDIAN
321 work[0] = byteswap(work[0]);
322 work[1] = byteswap(work[1]);
323 #endif
324
325 /* Do the 16 rounds */
326 for (i=0; i<16; i++)
327 round(i,work);
328
329 /* Left/right half swap */
330 tmp = work[0];
331 work[0] = work[1];
332 work[1] = tmp;
333
334 #ifdef LITTLE_ENDIAN
335 work[0] = byteswap(work[0]);
336 work[1] = byteswap(work[1]);
337 #endif
338 permute((char *)work,fperm,block); /* Inverse initial permutation */
339 }
340
341 /* In-place decryption of 64-bit block */
342 void dedes(char *block)
343 {
344 register int i;
345 uint32 work[2]; /* Working data storage */
346 int32 tmp;
347
348 permute(block,iperm,(char *)work); /* Initial permutation */
349
350 #ifdef LITTLE_ENDIAN
351 work[0] = byteswap(work[0]);
352 work[1] = byteswap(work[1]);
353 #endif
354
355 /* Left/right half swap */
356 tmp = work[0];
357 work[0] = work[1];
358 work[1] = tmp;
359
360 /* Do the 16 rounds in reverse order */
361 for (i=15; i >= 0; i--)
362 round(i,work);
363
364 #ifdef LITTLE_ENDIAN
365 work[0] = byteswap(work[0]);
366 work[1] = byteswap(work[1]);
367 #endif
368
369 permute((char *)work,fperm,block); /* Inverse initial permutation */
370 }
371
372 /* Permute inblock with perm */
373 rt_private void permute(char *inblock, char perm[16][16][8], char *outblock)
374 /* result into outblock,64 bits */
375 /* perm: 2K bytes defining perm. */
376 {
377 register int i,j;
378 register char *ib, *ob; /* ptr to input or output block */
379 register char *p, *q;
380
381 if(perm == NULL){
382 /* No permutation, just copy */
383 for(i=8; i!=0; i--)
384 *outblock++ = *inblock++;
385 return;
386 }
387 /* Clear output block */
388 for (i=8, ob = outblock; i != 0; i--)
389 *ob++ = 0;
390
391 ib = inblock;
392 for (j = 0; j < 16; j += 2, ib++) { /* for each input nibble */
393 ob = outblock;
394 p = perm[j][(*ib >> 4) & 017];
395 q = perm[j + 1][*ib & 017];
396 for (i = 8; i != 0; i--){ /* and each output byte */
397 *ob++ |= *p++ | *q++; /* OR the masks together*/
398 }
399 }
400 }
401
402 /* Do one DES cipher round */
403 rt_private void round(int num, uint32 *block)
404 /* num: i.e. the num-th one */
405 {
406 int32 f();
407
408 /* The rounds are numbered from 0 to 15. On even rounds
409 * the right half is fed to f() and the result exclusive-ORs
410 * the left half; on odd rounds the reverse is done.
411 */
412 if(num & 1){
413 block[1] ^= f(block[0],kn[num]);
414 } else {
415 block[0] ^= f(block[1],kn[num]);
416 }
417 }
418 /* The nonlinear function f(r,k), the heart of DES */
419 rt_private int32 f(uint32 r, unsigned char subkey[8])
420 /* 32 bits */
421 /* 48-bit key for this round */
422 {
423 register uint32 rval,rt;
424 #ifdef TRACE
425 unsigned char *cp;
426 int i;
427
428 printf("f(%08lx, %02x %02x %02x %02x %02x %02x %02x %02x) = ",
429 r,
430 subkey[0], subkey[1], subkey[2],
431 subkey[3], subkey[4], subkey[5],
432 subkey[6], subkey[7]);
433 #endif
434 /* Run E(R) ^ K through the combined S & P boxes
435 * This code takes advantage of a convenient regularity in
436 * E, namely that each group of 6 bits in E(R) feeding
437 * a single S-box is a contiguous segment of R.
438 */
439 rt = (r >> 1) | ((r & 1) ? 0x80000000 : 0);
440 rval = 0;
441 rval |= sp[0][((rt >> 26) ^ *subkey++) & 0x3f];
442 rval |= sp[1][((rt >> 22) ^ *subkey++) & 0x3f];
443 rval |= sp[2][((rt >> 18) ^ *subkey++) & 0x3f];
444 rval |= sp[3][((rt >> 14) ^ *subkey++) & 0x3f];
445 rval |= sp[4][((rt >> 10) ^ *subkey++) & 0x3f];
446 rval |= sp[5][((rt >> 6) ^ *subkey++) & 0x3f];
447 rval |= sp[6][((rt >> 2) ^ *subkey++) & 0x3f];
448 rt = (r << 1) | ((r & 0x80000000) ? 1 : 0);
449 rval |= sp[7][(rt ^ *subkey) & 0x3f];
450 #ifdef TRACE
451 printf(" %08lx\n",rval);
452 #endif
453 return rval;
454 }
455 /* initialize a perm array */
456 rt_private void perminit(char perm[16][16][8], char p[64])
457 /* perm: 64-bit, either init or final */
458 {
459 register int l, j, k;
460 int i,m;
461
462 /* Clear the permutation array */
463 for (i=0; i<16; i++)
464 for (j=0; j<16; j++)
465 for (k=0; k<8; k++)
466 perm[i][j][k]=0;
467
468 for (i=0; i<16; i++) /* each input nibble position */
469 for (j = 0; j < 16; j++)/* each possible input nibble */
470 for (k = 0; k < 64; k++)/* each output bit position */
471 { l = p[k] - 1; /* where does this bit come from*/
472 if ((l >> 2) != i) /* does it come from input posn?*/
473 continue; /* if not, bit k is 0 */
474 if (!(j & nibblebit[l & 3]))
475 continue; /* any such bit in input? */
476 m = k & 07; /* which bit is this in the byte*/
477 perm[i][j][k>>3] |= bytebit[m];
478 }
479 }
480
481 /* Initialize the lookup table for the combined S and P boxes */
482 rt_private int spinit()
483 {
484 char pbox[32];
485 int p,i,s,j,rowcol;
486 int32 val;
487
488 /* Compute pbox, the inverse of p32i.
489 * This is easier to work with
490 */
491 for(p=0;p<32;p++){
492 for(i=0;i<32;i++){
493 if(p32i[i]-1 == p){
494 pbox[p] = i;
495 break;
496 }
497 }
498 }
499 for(s = 0; s < 8; s++){ /* For each S-box */
500 for(i=0; i<64; i++){ /* For each possible input */
501 val = 0;
502 /* The row number is formed from the first and last
503 * bits; the column number is from the middle 4
504 */
505 rowcol = (i & 32) | ((i & 1) ? 16 : 0) | ((i >> 1) & 0xf);
506 for(j=0;j<4;j++){ /* For each output bit */
507 if(si[s][rowcol] & (8 >> j)){
508 val |= 1L << (31 - pbox[4*s + j]);
509 }
510 }
511 sp[s][i] = val;
512
513 #ifdef DES_DEBUG
514 printf("sp[%d][%2d] = %08lx\n",s,i,sp[s][i]);
515 #endif
516 }
517 }
518 return 0;
519 }
520 #ifdef LITTLE_ENDIAN
521 /* Byte swap a int32 */
522 static uint32 byteswap(uint32 x)
523 {
524 register char *cp,tmp;
525
526 cp = (char *)&x;
527 tmp = cp[3];
528 cp[3] = cp[0];
529 cp[0] = tmp;
530
531 tmp = cp[2];
532 cp[2] = cp[1];
533 cp[1] = tmp;
534
535 return x;
536 }
537 #endif

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.23