![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to des.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / des|
Return to des.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / des |
1.1 root 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * This code is derived from software contributed to Berkeley by
6: * Phil Karn, derived from original work by Jim Gillogly and
7: * Richard Outerbridge.
8: *
9: * Redistribution and use in source and binary forms are permitted
10: * provided that: (1) source distributions retain this entire copyright
11: * notice and comment, and (2) distributions including binaries display
12: * the following acknowledgement: ``This product includes software
13: * developed by the University of California, Berkeley and its contributors''
14: * in the documentation or other materials provided with the distribution
15: * and in all advertising materials mentioning features or use of this
16: * software. Neither the name of the University nor the names of its
17: * contributors may be used to endorse or promote products derived
18: * from this software without specific prior written permission.
19: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
20: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
21: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
22: */
23:
24: #ifndef lint
25: static char sccsid[] = "@(#)des.c 5.3 (Berkeley) 6/1/90";
26: #endif /* not lint */
27:
28: /* Sofware DES functions
29: * written 12 Dec 1986 by Phil Karn, KA9Q; large sections adapted from
30: * the 1977 public-domain program by Jim Gillogly
31: */
32:
33: #include <machine/endian.h>
34: #include <stdio.h>
35:
36: #if BYTE_ORDER == LITTLE_ENDIAN
37: static long byteswap();
38: #endif
39: static void permute(),perminit(),spinit();
40: static long f();
41:
42: /* Tables defined in the Data Encryption Standard documents */
43:
44: /* initial permutation IP */
45: static char ip[] = {
46: 58, 50, 42, 34, 26, 18, 10, 2,
47: 60, 52, 44, 36, 28, 20, 12, 4,
48: 62, 54, 46, 38, 30, 22, 14, 6,
49: 64, 56, 48, 40, 32, 24, 16, 8,
50: 57, 49, 41, 33, 25, 17, 9, 1,
51: 59, 51, 43, 35, 27, 19, 11, 3,
52: 61, 53, 45, 37, 29, 21, 13, 5,
53: 63, 55, 47, 39, 31, 23, 15, 7
54: };
55:
56: /* final permutation IP^-1 */
57: static char fp[] = {
58: 40, 8, 48, 16, 56, 24, 64, 32,
59: 39, 7, 47, 15, 55, 23, 63, 31,
60: 38, 6, 46, 14, 54, 22, 62, 30,
61: 37, 5, 45, 13, 53, 21, 61, 29,
62: 36, 4, 44, 12, 52, 20, 60, 28,
63: 35, 3, 43, 11, 51, 19, 59, 27,
64: 34, 2, 42, 10, 50, 18, 58, 26,
65: 33, 1, 41, 9, 49, 17, 57, 25
66: };
67:
68: /* expansion operation matrix
69: * This is for reference only; it is unused in the code
70: * as the f() function performs it implicitly for speed
71: */
72: #ifdef notdef
73: static char ei[] = {
74: 32, 1, 2, 3, 4, 5,
75: 4, 5, 6, 7, 8, 9,
76: 8, 9, 10, 11, 12, 13,
77: 12, 13, 14, 15, 16, 17,
78: 16, 17, 18, 19, 20, 21,
79: 20, 21, 22, 23, 24, 25,
80: 24, 25, 26, 27, 28, 29,
81: 28, 29, 30, 31, 32, 1
82: };
83: #endif
84:
85: /* permuted choice table (key) */
86: static char pc1[] = {
87: 57, 49, 41, 33, 25, 17, 9,
88: 1, 58, 50, 42, 34, 26, 18,
89: 10, 2, 59, 51, 43, 35, 27,
90: 19, 11, 3, 60, 52, 44, 36,
91:
92: 63, 55, 47, 39, 31, 23, 15,
93: 7, 62, 54, 46, 38, 30, 22,
94: 14, 6, 61, 53, 45, 37, 29,
95: 21, 13, 5, 28, 20, 12, 4
96: };
97:
98: /* number left rotations of pc1 */
99: static char totrot[] = {
100: 1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
101: };
102:
103: /* permuted choice key (table) */
104: static char pc2[] = {
105: 14, 17, 11, 24, 1, 5,
106: 3, 28, 15, 6, 21, 10,
107: 23, 19, 12, 4, 26, 8,
108: 16, 7, 27, 20, 13, 2,
109: 41, 52, 31, 37, 47, 55,
110: 30, 40, 51, 45, 33, 48,
111: 44, 49, 39, 56, 34, 53,
112: 46, 42, 50, 36, 29, 32
113: };
114:
115: /* The (in)famous S-boxes */
116: static char si[8][64] = {
117: /* S1 */
118: 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
119: 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
120: 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
121: 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,
122:
123: /* S2 */
124: 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
125: 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
126: 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
127: 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9,
128:
129: /* S3 */
130: 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
131: 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
132: 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
133: 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12,
134:
135: /* S4 */
136: 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
137: 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
138: 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
139: 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14,
140:
141: /* S5 */
142: 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
143: 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
144: 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
145: 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3,
146:
147: /* S6 */
148: 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
149: 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
150: 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
151: 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13,
152:
153: /* S7 */
154: 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
155: 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
156: 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
157: 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12,
158:
159: /* S8 */
160: 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
161: 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
162: 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
163: 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
164: };
165:
166: /* 32-bit permutation function P used on the output of the S-boxes */
167: static char p32i[] = {
168: 16, 7, 20, 21,
169: 29, 12, 28, 17,
170: 1, 15, 23, 26,
171: 5, 18, 31, 10,
172: 2, 8, 24, 14,
173: 32, 27, 3, 9,
174: 19, 13, 30, 6,
175: 22, 11, 4, 25
176: };
177: /* End of DES-defined tables */
178:
179: /* Lookup tables initialized once only at startup by desinit() */
180: static long (*sp)[64]; /* Combined S and P boxes */
181:
182: static char (*iperm)[16][8]; /* Initial and final permutations */
183: static char (*fperm)[16][8];
184:
185: /* 8 6-bit subkeys for each of 16 rounds, initialized by setkey() */
186: static char (*kn)[8];
187:
188: /* bit 0 is left-most in byte */
189: static int bytebit[] = {
190: 0200,0100,040,020,010,04,02,01
191: };
192:
193: static int nibblebit[] = {
194: 010,04,02,01
195: };
196: static int desmode;
197:
198: /* Allocate space and initialize DES lookup arrays
199: * mode == 0: standard Data Encryption Algorithm
200: * mode == 1: DEA without initial and final permutations for speed
201: * mode == 2: DEA without permutations and with 128-byte key (completely
202: * independent subkeys for each round)
203: */
204: int
205: desinit(mode)
206: int mode;
207: {
208: char *malloc();
209:
210: if(sp != NULL){
211: /* Already initialized */
212: return 0;
213: }
214: desmode = mode;
215:
216: if((sp = (long (*)[64])malloc(sizeof(long) * 8 * 64)) == NULL){
217: return -1;
218: }
219: spinit();
220: kn = (char (*)[8])malloc(sizeof(char) * 8 * 16);
221: if(kn == NULL){
222: free((char *)sp);
223: return -1;
224: }
225: if(mode == 1 || mode == 2) /* No permutations */
226: return 0;
227:
228: iperm = (char (*)[16][8])malloc(sizeof(char) * 16 * 16 * 8);
229: if(iperm == NULL){
230: free((char *)sp);
231: free((char *)kn);
232: return -1;
233: }
234: perminit(iperm,ip);
235:
236: fperm = (char (*)[16][8])malloc(sizeof(char) * 16 * 16 * 8);
237: if(fperm == NULL){
238: free((char *)sp);
239: free((char *)kn);
240: free((char *)iperm);
241: return -1;
242: }
243: perminit(fperm,fp);
244:
245: return 0;
246: }
247: /* Free up storage used by DES */
248: void
249: desdone()
250: {
251: if(sp == NULL)
252: return; /* Already done */
253:
254: free((char *)sp);
255: free((char *)kn);
256: if(iperm != NULL)
257: free((char *)iperm);
258: if(fperm != NULL)
259: free((char *)fperm);
260:
261: sp = NULL;
262: iperm = NULL;
263: fperm = NULL;
264: kn = NULL;
265: }
266: /* Set key (initialize key schedule array) */
267: void
268: setkey(key)
269: char *key; /* 64 bits (will use only 56) */
270: {
271: char pc1m[56]; /* place to modify pc1 into */
272: char pcr[56]; /* place to rotate pc1 into */
273: register int i,j,l;
274: int m;
275:
276: /* In mode 2, the 128 bytes of subkey are set directly from the
277: * user's key, allowing him to use completely independent
278: * subkeys for each round. Note that the user MUST specify a
279: * full 128 bytes.
280: *
281: * I would like to think that this technique gives the NSA a real
282: * headache, but I'm not THAT naive.
283: */
284: if(desmode == 2){
285: for(i=0;i<16;i++)
286: for(j=0;j<8;j++)
287: kn[i][j] = *key++;
288: return;
289: }
290: /* Clear key schedule */
291: memset((char *)kn,0,16*8);
292:
293: for (j=0; j<56; j++) { /* convert pc1 to bits of key */
294: l=pc1[j]-1; /* integer bit location */
295: m = l & 07; /* find bit */
296: pc1m[j]=(key[l>>3] & /* find which key byte l is in */
297: bytebit[m]) /* and which bit of that byte */
298: ? 1 : 0; /* and store 1-bit result */
299: }
300: for (i=0; i<16; i++) { /* key chunk for each iteration */
301: for (j=0; j<56; j++) /* rotate pc1 the right amount */
302: pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
303: /* rotate left and right halves independently */
304: for (j=0; j<48; j++){ /* select bits individually */
305: /* check bit that goes to kn[j] */
306: if (pcr[pc2[j]-1]){
307: /* mask it in if it's there */
308: l= j % 6;
309: kn[i][j/6] |= bytebit[l] >> 2;
310: }
311: }
312: }
313: }
314: /* In-place encryption of 64-bit block */
315: void
316: endes(block)
317: char *block;
318: {
319: register long left,right;
320: register char *knp;
321: long work[2]; /* Working data storage */
322:
323: permute(block,iperm,(char *)work); /* Initial Permutation */
324: #if BYTE_ORDER == LITTLE_ENDIAN
325: left = byteswap(work[0]);
326: right = byteswap(work[1]);
327: #else
328: left = work[0];
329: right = work[1];
330: #endif
331:
332: /* Do the 16 rounds.
333: * The rounds are numbered from 0 to 15. On even rounds
334: * the right half is fed to f() and the result exclusive-ORs
335: * the left half; on odd rounds the reverse is done.
336: */
337: knp = &kn[0][0];
338: left ^= f(right,knp);
339: knp += 8;
340: right ^= f(left,knp);
341: knp += 8;
342: left ^= f(right,knp);
343: knp += 8;
344: right ^= f(left,knp);
345: knp += 8;
346: left ^= f(right,knp);
347: knp += 8;
348: right ^= f(left,knp);
349: knp += 8;
350: left ^= f(right,knp);
351: knp += 8;
352: right ^= f(left,knp);
353: knp += 8;
354: left ^= f(right,knp);
355: knp += 8;
356: right ^= f(left,knp);
357: knp += 8;
358: left ^= f(right,knp);
359: knp += 8;
360: right ^= f(left,knp);
361: knp += 8;
362: left ^= f(right,knp);
363: knp += 8;
364: right ^= f(left,knp);
365: knp += 8;
366: left ^= f(right,knp);
367: knp += 8;
368: right ^= f(left,knp);
369:
370: /* Left/right half swap, plus byte swap if little-endian */
371: #if BYTE_ORDER == LITTLE_ENDIAN
372: work[1] = byteswap(left);
373: work[0] = byteswap(right);
374: #else
375: work[0] = right;
376: work[1] = left;
377: #endif
378: permute((char *)work,fperm,block); /* Inverse initial permutation */
379: }
380: /* In-place decryption of 64-bit block. This function is the mirror
381: * image of encryption; exactly the same steps are taken, but in
382: * reverse order
383: */
384: void
385: dedes(block)
386: char *block;
387: {
388: register long left,right;
389: register char *knp;
390: long work[2]; /* Working data storage */
391:
392: permute(block,iperm,(char *)work); /* Initial permutation */
393:
394: /* Left/right half swap, plus byte swap if little-endian */
395: #if BYTE_ORDER == LITTLE_ENDIAN
396: right = byteswap(work[0]);
397: left = byteswap(work[1]);
398: #else
399: right = work[0];
400: left = work[1];
401: #endif
402: /* Do the 16 rounds in reverse order.
403: * The rounds are numbered from 15 to 0. On even rounds
404: * the right half is fed to f() and the result exclusive-ORs
405: * the left half; on odd rounds the reverse is done.
406: */
407: knp = &kn[15][0];
408: right ^= f(left,knp);
409: knp -= 8;
410: left ^= f(right,knp);
411: knp -= 8;
412: right ^= f(left,knp);
413: knp -= 8;
414: left ^= f(right,knp);
415: knp -= 8;
416: right ^= f(left,knp);
417: knp -= 8;
418: left ^= f(right,knp);
419: knp -= 8;
420: right ^= f(left,knp);
421: knp -= 8;
422: left ^= f(right,knp);
423: knp -= 8;
424: right ^= f(left,knp);
425: knp -= 8;
426: left ^= f(right,knp);
427: knp -= 8;
428: right ^= f(left,knp);
429: knp -= 8;
430: left ^= f(right,knp);
431: knp -= 8;
432: right ^= f(left,knp);
433: knp -= 8;
434: left ^= f(right,knp);
435: knp -= 8;
436: right ^= f(left,knp);
437: knp -= 8;
438: left ^= f(right,knp);
439:
440: #if BYTE_ORDER == LITTLE_ENDIAN
441: work[0] = byteswap(left);
442: work[1] = byteswap(right);
443: #else
444: work[0] = left;
445: work[1] = right;
446: #endif
447: permute((char *)work,fperm,block); /* Inverse initial permutation */
448: }
449:
450: /* Permute inblock with perm */
451: static void
452: permute(inblock,perm,outblock)
453: char *inblock, *outblock; /* result into outblock,64 bits */
454: char perm[16][16][8]; /* 2K bytes defining perm. */
455: {
456: register char *ib, *ob; /* ptr to input or output block */
457: register char *p, *q;
458: register int j;
459:
460: if(perm == NULL){
461: /* No permutation, just copy */
462: memcpy(outblock,inblock,8);
463: return;
464: }
465: /* Clear output block */
466: memset(outblock,'\0',8);
467:
468: ib = inblock;
469: for (j = 0; j < 16; j += 2, ib++) { /* for each input nibble */
470: ob = outblock;
471: p = perm[j][(*ib >> 4) & 0xf];
472: q = perm[j + 1][*ib & 0xf];
473: /* and each output byte, OR the masks together */
474: *ob++ |= *p++ | *q++;
475: *ob++ |= *p++ | *q++;
476: *ob++ |= *p++ | *q++;
477: *ob++ |= *p++ | *q++;
478: *ob++ |= *p++ | *q++;
479: *ob++ |= *p++ | *q++;
480: *ob++ |= *p++ | *q++;
481: *ob++ |= *p++ | *q++;
482: }
483: }
484:
485: /* The nonlinear function f(r,k), the heart of DES */
486: static long
487: f(r,subkey)
488: register long r; /* 32 bits */
489: register char *subkey; /* 48-bit key for this round */
490: {
491: register long *spp;
492: register long rval,rt;
493: register int er;
494:
495: #ifdef TRACE
496: printf("f(%08lx, %02x %02x %02x %02x %02x %02x %02x %02x) = ",
497: r,
498: subkey[0], subkey[1], subkey[2],
499: subkey[3], subkey[4], subkey[5],
500: subkey[6], subkey[7]);
501: #endif
502: /* Run E(R) ^ K through the combined S & P boxes.
503: * This code takes advantage of a convenient regularity in
504: * E, namely that each group of 6 bits in E(R) feeding
505: * a single S-box is a contiguous segment of R.
506: */
507: subkey += 7;
508:
509: /* Compute E(R) for each block of 6 bits, and run thru boxes */
510: er = ((int)r << 1) | ((r & 0x80000000) ? 1 : 0);
511: spp = &sp[7][0];
512: rval = spp[(er ^ *subkey--) & 0x3f];
513: spp -= 64;
514: rt = (unsigned long)r >> 3;
515: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
516: spp -= 64;
517: rt >>= 4;
518: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
519: spp -= 64;
520: rt >>= 4;
521: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
522: spp -= 64;
523: rt >>= 4;
524: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
525: spp -= 64;
526: rt >>= 4;
527: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
528: spp -= 64;
529: rt >>= 4;
530: rval |= spp[((int)rt ^ *subkey--) & 0x3f];
531: spp -= 64;
532: rt >>= 4;
533: rt |= (r & 1) << 5;
534: rval |= spp[((int)rt ^ *subkey) & 0x3f];
535: #ifdef TRACE
536: printf(" %08lx\n",rval);
537: #endif
538: return rval;
539: }
540: /* initialize a perm array */
541: static void
542: perminit(perm,p)
543: char perm[16][16][8]; /* 64-bit, either init or final */
544: char p[64];
545: {
546: register int l, j, k;
547: int i,m;
548:
549: /* Clear the permutation array */
550: memset((char *)perm,0,16*16*8);
551:
552: for (i=0; i<16; i++) /* each input nibble position */
553: for (j = 0; j < 16; j++)/* each possible input nibble */
554: for (k = 0; k < 64; k++)/* each output bit position */
555: { l = p[k] - 1; /* where does this bit come from*/
556: if ((l >> 2) != i) /* does it come from input posn?*/
557: continue; /* if not, bit k is 0 */
558: if (!(j & nibblebit[l & 3]))
559: continue; /* any such bit in input? */
560: m = k & 07; /* which bit is this in the byte*/
561: perm[i][j][k>>3] |= bytebit[m];
562: }
563: }
564:
565: /* Initialize the lookup table for the combined S and P boxes */
566: static void
567: spinit()
568: {
569: char pbox[32];
570: int p,i,s,j,rowcol;
571: long val;
572:
573: /* Compute pbox, the inverse of p32i.
574: * This is easier to work with
575: */
576: for(p=0;p<32;p++){
577: for(i=0;i<32;i++){
578: if(p32i[i]-1 == p){
579: pbox[p] = i;
580: break;
581: }
582: }
583: }
584: for(s = 0; s < 8; s++){ /* For each S-box */
585: for(i=0; i<64; i++){ /* For each possible input */
586: val = 0;
587: /* The row number is formed from the first and last
588: * bits; the column number is from the middle 4
589: */
590: rowcol = (i & 32) | ((i & 1) ? 16 : 0) | ((i >> 1) & 0xf);
591: for(j=0;j<4;j++){ /* For each output bit */
592: if(si[s][rowcol] & (8 >> j)){
593: val |= 1L << (31 - pbox[4*s + j]);
594: }
595: }
596: sp[s][i] = val;
597:
598: #ifdef DEBUG
599: printf("sp[%d][%2d] = %08lx\n",s,i,sp[s][i]);
600: #endif
601: }
602: }
603: }
604:
605: #if BYTE_ORDER == LITTLE_ENDIAN
606: /* Byte swap a long */
607: static long
608: byteswap(x)
609: unsigned long x;
610: {
611: register char *cp,tmp;
612:
613: cp = (char *)&x;
614: tmp = cp[3];
615: cp[3] = cp[0];
616: cp[0] = tmp;
617:
618: tmp = cp[2];
619: cp[2] = cp[1];
620: cp[1] = tmp;
621:
622: return x;
623: }
624: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.