Received: from louie.udel.edu by huey.udel.edu id ab24775; 4 May 89 12:17 EDT Received: from ccv.bbn.com by louie.udel.edu id aa09055; 4 May 89 12:14 EDT Date: Thu, 4 May 89 12:10:52 EDT From: Steve Kent To: Mills@udel.edu Subject: Re: DES routines Message-ID: <8905041214.aa09055@louie.udel.edu> Dave, Pardon the lateness, but as I mentioned before John Linn left in March and it's taking some time to regroup and find where various things are (though John did do an excellent job of organizing stuff and letting us know the state of the world before he left). I've enclosed some c routines for DES and DES key schedule construction. ZIHHIf you want the faster MC68K versions I could provide them too. I also understand that the next BSD release will contain code that is much faster than the current "crypt" and the code contains elements of the speedups which are present in these routines. Let me know if you have any problems with this code and how well it performs for your application. I will ask the PTF members to review your NTP authentication paper during our next meeting, so I can get back to you with comments by the beginning of June (if I don't get to it myself prior to then). Steve ------------------------ /* ----------------------------------------------------------------- */ /* This DES software was developed by Steve Kent and John Linn */ /* of BBN Communications Corporation, Cambridge, MA */ /* Do not redistribute this software, or integrate with other */ /* software, without preserving this notice */ /* ----------------------------------------------------------------- */ /* ksb.c -- John Linn, 21 April 1983 -- This program uses an optimized, table-driven method to compute a DES key schedule from 8 input bytes. Once the optimizing table (pc2otab) has been computed, generation of a schedule takes approximately 12 user ms on a C/70. Note: there is still room to optimize pc1 and tweak out a couple of extra milliseconds from the key schedule build, but this should only be important if and when adaptation to an environment which needs to dynamically change keys is considered. 21 Apr. -- removed c30 special case. c30 now takes same key format, and output is always to file 'ks'. 6 May -- added command line option to specify name of output file. if no command arg, output is still to 'ks'. */ #include /* tables to describe permutations, per NBS FIPS */ static int pc1c [] = { 57, 49, 41, 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 }; static int pc1d [] = { 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 }; static int shiftsked []= { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; static int pc2 [] = { 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 }; /* --- some bit manipulation primitives --- */ /* g_keybit -- extract bit bnum from the key in inkey */ #define g_keybit(bnum) (01 & (inkey [bnum/8] >> (8 - (bnum%8)))) long lrot28 (lval) /* do left rotate of 28 bit quantity */ long lval; { lval <<= 1; if (0X10000000L & lval) lval++; lval &= 0XFFFFFFFL; return (lval); } /* --- following code and data does key schedule generation --- */ unsigned skedkeys [16] [4]; unsigned inkey [8]; /* input key goes here */ long pc2otab [8] [128]; /* table to optimize pc2 */ spc2otab () /* initialize pc2otab for pc2 lookups */ { #define NOTSEL -1 extern long pc2otab [8] [128]; extern int pc2 [48]; int bn, bv, bitloc, i; int bitindx [7]; for (bn = 0; bn < 8; bn++) /* each input 7-bit byte, l->r */ { for (i = 0; i < 7; i++) /* find each bit in the byte */ { /* determine where (or if) pc2 places the given bit in the output. set bitindx [0] to the bit number (1->48,l->r) where the MSB of the byte occurs, or to NOTSEL if pc2 doesn't pick it. similar down through bitindx [6]. */ for (bitloc = 0; bitloc < 48; bitloc++) { /* trying until a match in pc2 found or table exhausted */ if (pc2 [bitloc] == (1 + ((bn * 7) + i))) { bitindx [i] = bitloc + 1; break; } } if (bitloc == 48) bitindx [i] = NOTSEL; } for (bv = 0; bv < 128; bv++) { /* setting up a table entry for each input byte value */ pc2otab [bn] [bv] = 0L; if (bn < 4) /* this is left word (nbs bits 1-24) */ { for (i = 0; i < 7; i++) { if (NOTSEL == bitindx [i]) continue; if (bv & (01 << (6 - i))) pc2otab [bn] [bv] |= (0X1L << (24 - bitindx [i])); } } else /* this is right word (nbs bits 25-48) */ { for (i = 0; i < 7; i++) { if (NOTSEL == bitindx [i]) continue; if (bv & (01 << (6 - i))) pc2otab [bn] [bv] |= (0X1L << (48 - bitindx [i])); } } } } } ksmake () /* Make a key schedule from key bytes in inkey */ { extern unsigned skedkeys [16] [4]; extern long pc2otab [8] [128]; int round; long pcct, pcdt; long pc2out [2]; int i; /* do pc-1 permutation, extracting bits from inkey */ pcct = pcdt = 0L; for (i = 0; i < 27; i++) /* filling all appropriate bits */ { pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); pcct <<= 1; pcdt <<= 1; } /* one final ior, without a shift */ pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); for (round = 0; round < 16; round++) { /* always at least one shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); if (shiftsked [round] == 2) { /* this round needs another shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); } /* Now, pcct and pcdt have the values on which we can apply pc2 and select the key bits, storing them in pc2out[0] and pc2out[1]. The high order [pc2out[0]] bits all come from pcct, and the low order from pcdt. */ pc2out [0] = pc2otab [0] [pcct >> 21]; pc2out [0] |= pc2otab [1] [0X7F & (pcct >> 14)]; pc2out [0] |= pc2otab [2] [0X7F & (pcct >> 7)]; pc2out [0] |= pc2otab [3] [0X7F & pcct]; pc2out [1] = pc2otab [4] [pcdt >> 21]; pc2out [1] |= pc2otab [5] [0X7F & (pcdt >> 14)]; pc2out [1] |= pc2otab [6] [0X7F & (pcdt >> 7)]; pc2out [1] |= pc2otab [7] [0X7F & pcdt]; /* order key bits and bytes so as to be compatible with the format generated by the E implementation */ skedkeys [round] [0] = 0XFC00 & (pc2out [0] >> 8); skedkeys [round] [0] |= (0XFC & (pc2out [0] >> 4)); skedkeys [round] [1] = 0XFC00 & (pc2out [1] >> 8); skedkeys [round] [1] |= (0XFC & (pc2out [1] >> 4)); skedkeys [round] [2] = 0XFC00 & (pc2out [0] >> 2); skedkeys [round] [2] |= (0XFC & (pc2out [0] << 2)); skedkeys [round] [3] = 0XFC00 & (pc2out [1] >> 2); skedkeys [round] [3] |= (0XFC & (pc2out [1] << 2)); } } int parval () /* test parity of key in inkey; return 1 iff OK */ { int i, j; int parac; unsigned incopy; for (i = 0; i < 8; i++) /* do each byte */ { parac = 0; incopy = inkey [i]; for (j = 0; j < 8; j++) /* 8 bits in a DES byte */ { if (incopy & 01) parac++; incopy >>= 1; } if (! (parac & 01)) return (0); /* no odd parity on this byte */ } return (1); /* OK on all of them */ } /* main for ksb -- accept and validate key, output schedule */ main (argc, argv) int argc; char *argv []; { extern unsigned skedkeys [16] [4]; extern unsigned inkey [8]; int i, j; FILE * fp, *fopen (); spc2otab (); /* compute internal table */ printf ("Enter DES key as 8 hex bytes: "); scanf ("%x %x %x %x %x %x %x %x", &inkey [0], &inkey [1], &inkey [2], &inkey [3], &inkey [4], &inkey [5], &inkey [6], &inkey [7]); if (! parval ()) { printf ("Bad parity on key... aborting...\n"); exit (1); } ksmake (); if (NULL == (fp = fopen (((argc > 1) ? argv [1] : "ks"), "w"))) { printf ("ksb -- can't open output file '%s'\n", ((argc > 1) ? argv [1] : "ks")); exit (1); } for (i = 0; i < 16; i++) /* output entire schedule to file */ { for (j = 0; j < 4; j++) /* format is xxxxxx00xxxxxx00 */ fprintf (fp, "%x\n", skedkeys [i] [j]); } printf ("ksb -- key schedule output to file '%s'\n", ((argc > 1) ? argv [1] : "ks")); } /* modified 6 May 1983 to allow optional command arg which specifies output file name. if no arg, output goes to file 'ks' */ #include /* tables to describe permutations, per NBS FIPS */ static int pc1c [] = { 57, 49, 41, 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 }; static int pc1d [] = { 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 }; static int shiftsked []= { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; static int pc2 [] = { 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 }; /* --- some bit manipulation primitives --- */ /* g_keybit -- extract bit bnum from the key in inkey */ #define g_keybit(bnum) (01 & (inkey [bnum/8] >> (8 - (bnum%8)))) long lrot28 (lval) /* do left rotate of 28 bit quantity */ long lval; { lval <<= 1; if (0X10000000L & lval) lval++; lval &= 0XFFFFFFFL; return (lval); } /* --- following code and data does key schedule generation --- */ unsigned skedkeys [16] [4]; unsigned inkey [8]; /* input key goes here */ long pc2otab [8] [128]; /* table to optimize pc2 */ spc2otab () /* initialize pc2otab for pc2 lookups */ { #define NOTSEL -1 extern long pc2otab [8] [128]; extern int pc2 [48]; int bn, bv, bitloc, i; int bitindx [7]; for (bn = 0; bn < 8; bn++) /* each input 7-bit byte, l->r */ { for (i = 0; i < 7; i++) /* find each bit in the byte */ { /* determine where (or if) pc2 places the given bit in the output. set bitindx [0] to the bit number (1->48,l->r) where the MSB of the byte occurs, or to NOTSEL if pc2 doesn't pick it. similar down through bitindx [6]. */ for (bitloc = 0; bitloc < 48; bitloc++) { /* trying until a match in pc2 found or table exhausted */ if (pc2 [bitloc] == (1 + ((bn * 7) + i))) { bitindx [i] = bitloc + 1; break; } } if (bitloc == 48) bitindx [i] = NOTSEL; } for (bv = 0; bv < 128; bv++) { /* setting up a table entry for each input byte value */ pc2otab [bn] [bv] = 0L; if (bn < 4) /* this is left word (nbs bits 1-24) */ { for (i = 0; i < 7; i++) { if (NOTSEL == bitindx [i]) continue; if (bv & (01 << (6 - i))) pc2otab [bn] [bv] |= (0X1L << (24 - bitindx [i])); } } else /* this is right word (nbs bits 25-48) */ { for (i = 0; i < 7; i++) { if (NOTSEL == bitindx [i]) continue; if (bv & (01 << (6 - i))) pc2otab [bn] [bv] |= (0X1L << (48 - bitindx [i])); } } } } } ksmake () /* Make a key schedule from key bytes in inkey */ { extern unsigned skedkeys [16] [4]; extern long pc2otab [8] [128]; int round; long pcct, pcdt; long pc2out [2]; int i; /* do pc-1 permutation, extracting bits from inkey */ pcct = pcdt = 0L; for (i = 0; i < 27; i++) /* filling all appropriate bits */ { pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); pcct <<= 1; pcdt <<= 1; } /* one final ior, without a shift */ pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); for (round = 0; round < 16; round++) { /* always at least one shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); if (shiftsked [round] == 2) { /* this round needs another shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); } /* Now, pcct and pcdt have the values on which we can apply pc2 and select the key bits, storing them in pc2out[0] and pc2out[1]. The high order [pc2out[0]] bits all come from pcct, and the low order from pcdt. */ pc2out [0] = pc2otab [0] [pcct >> 21]; pc2out [0] |= pc2otab [1] [0X7F & (pcct >> 14)]; pc2out [0] |= pc2otab [2] [0X7F & (pcct >> 7)]; pc2out [0] |= pc2otab [3] [0X7F & pcct]; pc2out [1] = pc2otab [4] [pcdt >> 21]; pc2out [1] |= pc2otab [5] [0X7F & (pcdt >> 14)]; pc2out [1] |= pc2otab [6] [0X7F & (pcdt >> 7)]; pc2out [1] |= pc2otab [7] [0X7F & pcdt]; /* order key bits and bytes so as to be compatible with the format generated by the E implementation */ skedkeys [round] [0] = 0XFC00 & (pc2out [0] >> 8); skedkeys [round] [0] |= (0XFC & (pc2out [0] >> 4)); skedkeys [round] [1] = 0XFC00 & (pc2out [1] >> 8); skedkeys [round] [1] |= (0XFC & (pc2out [1] >> 4)); skedkeys [round] [2] = 0XFC00 & (pc2out [0] >> 2); skedkeys [round] [2] |= (0XFC & (pc2out [0] << 2)); skedkeys [round] [3] = 0XFC00 & (pc2out [1] >> 2); skedkeys [round] [3] |= (0XFC & (pc2out [1] << 2)); } } int parval () /* test parity of key in inkey; return 1 iff OK */ { int i, j; int parac; unsigned incopy; for (i = 0; i < 8; i++) /* do each byte */ { parac = 0; incopy = inkey [i]; for (j = 0; j < 8; j++) /* 8 bits in a DES byte */ { if (incopy & 01) parac++; incopy >>= 1; } if (! (parac & 01)) return (0); /* no odd parity on this byte */ } return (1); /* OK on all of them */ } int tossbit () /* request and return a coin toss value */ { char inarr [10]; for (;;) /* infinite loop until acceptable result entered */ { printf ("heads or tails? (h or t): "); scanf ("%s", inarr); if ((inarr [0] == 'h') || (inarr [0] == 'H')) return (1); if ((inarr [0] == 't') || (inarr [0] == 'T')) return (0); printf ("Input unacceptable! Enter 'h' or 't'\n"); } } coin_to_key () /* prompt for and accept coin tosses, build inkey */ { extern unsigned inkey [8]; int kbyte, kbit, parchk, toss, tosstot; tosstot = 0; for (kbyte = 0; kbyte < 8; kbyte++) { inkey [kbyte] = 0; parchk = 0; /* parity accumulator */ for (kbit = 0; kbit < 7; kbit++) /* get 7 real bits for byte */ { toss = tossbit (); inkey [kbyte] |= (01 << (7 - kbit)) * toss; parchk += toss; tosstot += toss; /* keep track of how many ones */ } inkey [kbyte] |= 01 * (0 == (parchk & 01)); printf ("key byte %d (parity adjusted) is %x\n", kbyte+1, inkey [kbyte]); } printf ("Entire key is: "); for (kbyte = 0; kbyte < 8; kbyte++) printf ("%x ", inkey [kbyte]); printf ("\n"); printf ("Of 56 tossed bits, %d were ones\n", tosstot); } /* main for tosskey -- accept and validate key, output schedule */ main (argc, argv) int argc; char *argv []; { extern unsigned skedkeys [16] [4]; int i, j; FILE * fp, *fopen (); spc2otab (); printf ("Welcome to tosskey. Prepare your coin for use.\n"); coin_to_key (); /* get individual entries, compose inkey */ if (! parval ()) { printf ("Bad parity on key... aborting...\n"); exit (1); } printf ("Computing key schedule...\n"); ksmake (); if (NULL == (fp = fopen (((argc > 1) ? argv [1] : "ks"), "w"))) { printf ("tosskey -- can't open output file '%s'", ((argc > 1) ? argv [1] : "ks")); exit (1); } for (i = 0; i < 16; i++) /* output entire schedule to file */ { for (j = 0; j < 4; j++) /* output format is xxxxxx00xxxxxx00 */ fprintf (fp, "%x\n", skedkeys [i] [j]); } printf ("tosskey -- key schedule output to file '%s'\n", ((argc > 1) ? argv [1] : "ks")); } /* des.c -- this file contains an optimized C-based DES algorithm */ /* implementation. Many loops are stretched out into straight-line code, */ /* so this version is not particularly short, modular, or readable. (size */ /* as of 31 Aug 83: 7338+1426+6372 = 15136b = 035440b) However, it is */ /* quick. (A DES encryption times at approximately 7 user ms on a C/70) It */ /* reads its key schedule and certain tables from files generated by */ /* associated programs ksb.c and tblbld.c. John Linn -- 8 April 1983 */ /* "Bug" fix 17 Feb 1984 - insert masking so as to have E work on 32 bit machines with sign extension on right shifts (like Vax, 68k (?)) */ /* observation: when compiled onto vax, takes only ~ 2.6 ms to encrypt */ #include #define LMASK 0XFCFCFCFCL; /* data structures to be read from files */ static long ip [2] [256]; static long ipi [2] [256]; static long snop [8] [64]; unsigned ks [16] [4]; /* rdfiles -- reads filed info, returns 1 iff success, 0 otherwise */ int rdfiles () { int i, j; FILE *fp, *fopen (); if (NULL == (fp = fopen ("ip", "r"))) { printf ("des -- can't read file 'ip'\n"); return (0); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) if (EOF == fscanf (fp, "%lx", &ip [i] [j])) { printf ("des -- 'ip' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("ipi", "r"))) { printf ("des -- can't read file 'ipi'\n"); return (0); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) if (EOF == fscanf (fp, "%lx", &ipi [i] [j])) { printf ("des -- 'ipi' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("snop", "r"))) { printf ("des -- can't read file 'snop'\n"); return (0); } for (i = 0; i < 8; i++) for (j = 0; j < 64; j++) if (EOF == fscanf (fp, "%lx", &snop [i] [j])) { printf ("des -- 'snop' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("ks", "r"))) { printf ("des -- can't read file 'ks'\n"); return (0); } for (i = 0; i < 16; i++) for (j = 0; j < 4; j++) if (EOF == fscanf (fp, "%x", &ks [i] [j])) { printf ("des -- 'ks' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); return (1); /* success */ } #define BINBLK 8 /* number of bytes in an encryption chunk */ #define BINLNG 4 /* the number of bytes in 32 bits of a long */ /* doip -- use ip table to permute 64 bits from inar to outar */ doip (inar, outar) long inar [2]; long outar [2]; { extern long ip [2] [256]; outar [0] = outar [1] = 0L; outar [0] |= ip [0] [0XFF & inar [1]]; outar [1] |= ip [1] [0XFF & inar [1]]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [1] >> 8)]; outar [1] |= ip [1] [0XFF & (inar [1] >> 8)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [1] >> 16)]; outar [1] |= ip [1] [0XFF & (inar [1] >> 16)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [1] >> 24)]; outar [1] |= ip [1] [0XFF & (inar [1] >> 24)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & inar [0]]; outar [1] |= ip [1] [0XFF & inar [0]]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [0] >> 8)]; outar [1] |= ip [1] [0XFF & (inar [0] >> 8)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [0] >> 16)]; outar [1] |= ip [1] [0XFF & (inar [0] >> 16)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ip [0] [0XFF & (inar [0] >> 24)]; outar [1] |= ip [1] [0XFF & (inar [0] >> 24)]; } /* doipi -- use ipi to perform ip-inverse */ /* doesn't use ipis table: knowledge of byte order is hardcoded */ doipi (inar, outar) long inar [2]; long outar [2]; { extern long ipi [2] [256]; outar [0] = outar [1] = 0L; outar [0] |= ipi [0] [0XFF & (inar [1] >> 24)]; /* "5" */ outar [1] |= ipi [1] [0XFF & (inar [1] >> 24)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & (inar [0] >> 24)]; /* "1" */ outar [1] |= ipi [1] [0XFF & (inar [0] >> 24)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & (inar [1] >> 16)]; /* "6" */ outar [1] |= ipi [1] [0XFF & (inar [1] >> 16)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & (inar [0] >> 16)]; /* "2" */ outar [1] |= ipi [1] [0XFF & (inar [0] >> 16)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & (inar [1] >> 8)]; /* "7" */ outar [1] |= ipi [1] [0XFF & (inar [1] >> 8)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & (inar [0] >> 8)]; /* "3" */ outar [1] |= ipi [1] [0XFF & (inar [0] >> 8)]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & inar [1]]; /* "8" */ outar [1] |= ipi [1] [0XFF & inar [1]]; outar [0] <<= 1; outar [1] <<= 1; outar [0] |= ipi [0] [0XFF & inar [0]]; /* "4" */ outar [1] |= ipi [1] [0XFF & inar [0]]; } /* des_encrypt -- encrypt a block under key sched in ks */ des_encrypt (inar, outar) long inar [2]; long outar [2]; { extern unsigned ks [16] [4]; extern long snop [8] [64]; register int round, oddbit; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy, tlong; long oarr [2]; doip (inar, outar); for (round = 0; round < 16; round++) { sbout = 0L; tlong = outar [1]; oddbit = (int) (01 & tlong); tlong >>= 1; tlong &= 0X7FFFFFFFL; /* defeat sign extend -- jl 17 feb 84 */ if (oddbit) tlong |= 0X80000000L; tlong &= LMASK; expan [0] = (unsigned) (tlong >> 16); expan [1] = (unsigned) tlong; tlong = outar [1]; oddbit = !! (tlong & 0X80000000L); tlong <<= 3; if (oddbit) tlong |= 04; tlong &= LMASK; expan [2] = (unsigned) (tlong >> 16); expan [3] = (unsigned) tlong; /* this code bypasses the alternative of loop setup and resultant computation within the loop for speed */ expan [0] ^= ks [round] [0]; sbout |= snop [0] [0X3F & (expan [0] >> 10)]; sbout |= snop [1] [0X3F & (expan [0] >> 2)]; expan [1] ^= ks [round] [1]; sbout |= snop [2] [0X3F & (expan [1] >> 10)]; sbout |= snop [3] [0X3F & (expan [1] >> 2)]; expan [2] ^= ks [round] [2]; sbout |= snop [4] [0X3F & (expan [2] >> 10)]; sbout |= snop [5] [0X3F & (expan [2] >> 2)]; expan [3] ^= ks [round] [3]; sbout |= snop [6] [0X3F & (expan [3] >> 10)]; sbout |= snop [7] [0X3F & (expan [3] >> 2)]; scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } /* des_decrypt -- decrypt a block under key sched in ks */ des_decrypt (inar, outar) long inar [2]; long outar [2]; { extern unsigned ks [16] [4]; extern long snop [8] [64]; register int round, oddbit; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy, tlong; long oarr [2]; doip (inar, outar); for (round = 15; round >= 0; round--) /* note that decryption selects schedule keys in opposite order */ { sbout = 0L; tlong = outar [1]; oddbit = (int) (01 & tlong); tlong >>= 1; tlong &= 0X7FFFFFFFL; /* defeat sign extend -- jl 17 feb 84 */ if (oddbit) tlong |= 0X80000000L; tlong &= LMASK; expan [0] = (unsigned) (tlong >> 16); expan [1] = (unsigned) tlong; tlong = outar [1]; oddbit = !! (tlong & 0X80000000L); tlong <<= 3; if (oddbit) tlong |= 04; tlong &= LMASK; expan [2] = (unsigned) (tlong >> 16); expan [3] = (unsigned) tlong; /* this code bypasses the alternative of loop setup and resultant computation within the loop for speed */ expan [0] ^= ks [round] [0]; sbout |= snop [0] [0X3F & (expan [0] >> 10)]; sbout |= snop [1] [0X3F & (expan [0] >> 2)]; expan [1] ^= ks [round] [1]; sbout |= snop [2] [0X3F & (expan [1] >> 10)]; sbout |= snop [3] [0X3F & (expan [1] >> 2)]; expan [2] ^= ks [round] [2]; sbout |= snop [4] [0X3F & (expan [2] >> 10)]; sbout |= snop [5] [0X3F & (expan [2] >> 2)]; expan [3] ^= ks [round] [3]; sbout |= snop [6] [0X3F & (expan [3] >> 10)]; sbout |= snop [7] [0X3F & (expan [3] >> 2)]; scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } /* facilities for timing */ struct tbuffer { long proc_utime; long proc_stime; long child_utime; long child_stime; }; struct tbuffer t_before; struct tbuffer t_after; main () { int itnum, i; long plain [2], crypt [2], cprbuf [2]; long udiff, bitsdone, u_msec; /* begin by reading tables and key schedule from files */ printf ("Reading filed tables and key schedule...\n"); if (1 != rdfiles ()) { printf ("des -- couldn't get tables or key schedule\n"); exit (1); } printf ("Enter input to encrypt as two hex longs: "); scanf ("%lx %lx", &plain [0], &plain [1]); des_encrypt (plain, crypt); printf ("Result of encryption: %lx %lx\n", crypt [0], crypt [1]); printf ("Enter number of test iterations [decimal]: "); scanf ("%d", &itnum); times (&t_before); for (i = 0; i < itnum; i++) { des_encrypt (plain, crypt); des_decrypt (crypt, cprbuf); if ((plain [0] != cprbuf [0]) || (plain [1] != cprbuf [1])) { printf ("Encrypt and decrypt disagree -- aborting!!\n"); exit (1); } } times (&t_after); printf ("All encryptions and decryptions verified consistent\n"); /* note: the following code won't work if one times a number of encryptions that take less than one tick, as can occur on a vax with a small number of tests */ udiff = t_after.proc_utime - t_before.proc_utime; printf ("user 1/60 sec ticks = %ld\n", udiff); bitsdone = 2 * (itnum * 64); u_msec = (udiff * 1000) / 60; printf ("%ld user msec/DES cycle\n", u_msec / ((long) 2 * itnum)); printf ("%ld bits/user second\n", (bitsdone * 1000) / u_msec); } /* slowdes.c -- this file contains a C-based DES algorithm implementation; the version is modeled after the MBB implementation for instructive clarity, and is not the most efficient version available for the C/70. It reads its key schedule and certain tables from files generated by associated programs ksbuild.c and tblbuild.c. John Linn -- 4 March 1983 */ #include /* data structures to be read from files */ static long ip [2] [256]; static long ipi [2] [256]; static int ipis [8]; static long snop [8] [64]; unsigned ks [16] [4]; /* rdfiles -- reads filed info, returns 1 iff success, 0 otherwise */ int rdfiles () { int i, j; FILE *fp, *fopen (); if (NULL == (fp = fopen ("ip", "r"))) { printf ("dodes -- can't read file 'ip'\n"); return (0); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) if (EOF == fscanf (fp, "%lx", &ip [i] [j])) { printf ("dodes -- 'ip' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("ipi", "r"))) { printf ("dodes -- can't read file 'ipi'\n"); return (0); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) if (EOF == fscanf (fp, "%lx", &ipi [i] [j])) { printf ("dodes -- 'ipi' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("ipis", "r"))) { printf ("dodes -- can't read file 'ipis'\n"); return (0); } for (i = 0; i < 8; i++) if (EOF == fscanf (fp, "%x", &ipis [i])) { printf ("dodes -- 'ipis' read failed at i=%d\n"); return (0); } fclose (fp); if (NULL == (fp = fopen ("snop", "r"))) { printf ("dodes -- can't read file 'snop'\n"); return (0); } for (i = 0; i < 8; i++) for (j = 0; j < 64; j++) if (EOF == fscanf (fp, "%lx", &snop [i] [j])) { printf ("dodes -- 'snop' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); if (NULL == (fp = fopen ("ks", "r"))) { printf ("dodes -- can't read file 'ks'\n"); return (0); } for (i = 0; i < 16; i++) for (j = 0; j < 4; j++) if (EOF == fscanf (fp, "%x", &ks [i] [j])) { printf ("dodes -- 'ks' read failed at i=%d, j=%d\n", i, j); return (0); } fclose (fp); return (1); /* success */ } /* eexpand -- this routine performs a version of the DES E transform, per Kent's algorithm for the MBB. It accepts an input long and returns its result in 4 words of an unsigned array, ordered (1 3) (5 7) (2 4) (6 8). Significant bits are left justified in 8-bit bytes in these words: the two low order bits will always be zeroes. This version is coded for clarity of correspondence to the C/30 MBB version, not taking much advantage of 32-bit operations. */ #define MASK 0XFCFC; eexpand (inlong, outarr) long inlong; unsigned outarr []; { unsigned rega, regb, regc, regd; int oddbith, oddbitl, i; rega = regc = (unsigned) (0XFFFFL & (inlong >> 16)); /* high bits */ regb = regd = (unsigned) (0XFFFFL & inlong); /* low bits */ /* rotate regc-regd pair right one */ oddbith = !! (regc & 01); oddbitl = !! (regd & 01); regc >>= 1; regd >>= 1; if (oddbitl) regc |= 0X8000; if (oddbith) regd |= 0X8000; /* kill unused bits */ regc &= MASK; regd &= MASK; /* rotate rega-regb pair left by three */ for (i = 0; i < 3; i++) { oddbith = !! (rega & 0X8000); oddbitl = !! (regb & 0X8000); rega <<= 1; regb <<= 1; if (oddbitl) rega |= 01; if (oddbith) regb |= 01; } /* kill unused bits */ rega &= MASK; regb &= MASK; outarr [0] = regc; outarr [1] = regd; outarr [2] = rega; outarr [3] = regb; } #define BINBLK 8 /* number of bytes in an encryption chunk */ #define BINLNG 4 /* the number of bytes in 32 bits of a long */ /* doip -- use ip table to permute 64 bits from inar to outar */ doip (inar, outar) long inar [2]; long outar [2]; { extern long ip [2] [256]; int i,j; outar [0] = outar [1] = 0L; for (i = 0; i < BINBLK; i++) /* input is 8 bytes */ /* msb of inar [0] ... lsb of inar [1] */ { for (j = 0; j < 2; j++) /* scan from r -> l */ outar [j] |= ip [j] [0XFF & ((i < BINLNG) ? ((int) ((inar [1] >> (i * 8)))) : ((int) ((inar [0] >> ((i - BINLNG) * 8)))) )]; if (i == (BINBLK - 1)) break; /* don't shift an extra time */ for (j = 0; j < 2; j++) outar [j] <<= 1; } } /* doipi -- use ipi, ipis to perform ip-inverse */ doipi (inar, outar) long inar [2]; long outar [2]; { extern int ipis [8]; extern long ipi [2] [256]; int i, j, bp; outar [0] = outar [1] = 0L; for (i = 0; i < BINBLK; i++) /* input is 8 bytes */ { bp = ipis [i] - 1; /* translate byte indexes to zero origin */ for (j = 0; j < 2; j++) outar [j] |= ipi [j] [0XFF & ((bp < BINLNG) ? ((int) (inar [0] >> (((BINLNG - bp) - 1) * 8))) : ((int) (inar [1] >> (((BINLNG - (bp-4)) - 1) * 8))) )]; if (i == (BINBLK - 1)) break; for (j = 0; j < 2; j++) outar [j] <<= 1; } } /* des_encrypt -- encrypt a block under key sched in ks */ des_encrypt (inar, outar) long inar [2]; long outar [2]; { extern unsigned ks [16] [4]; extern long snop [8] [64]; int round, i, j; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy; long oarr [2]; doip (inar, outar); for (round = 0; round < 16; round++) { sbout = 0L; eexpand (outar [1], expan); for (i = 0; i < 4; i++) { expan [i] ^= ks [round] [i]; for (j = 0; j < 2; j++) { sbout |= snop [(i*2)+j] [0X3F & (j ? (expan [i] >> 2) : (expan [i] >> 10))]; } } scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } /* des_decrypt -- decrypt a block under key sched in ks */ des_decrypt (inar, outar) long inar [2]; long outar [2]; { extern unsigned ks [16] [4]; extern long snop [8] [64]; int round, i, j; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy; long oarr [2]; doip (inar, outar); for (round = 15; round >= 0; round--) /* to do a DES decrypt, use key schedule in reverse order */ { sbout = 0L; eexpand (outar [1], expan); for (i = 0; i < 4; i++) { expan [i] ^= ks [round] [i]; for (j = 0; j < 2; j++) { sbout |= snop [(i*2)+j] [0X3F & (j ? (expan [i] >> 2) : (expan [i] >> 10))]; } } scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } main () { long plain [2], crypt [2], cprbuf [2]; /* begin by reading tables and key schedule from files */ printf ("Reading filed tables and key schedule...\n"); if (1 != rdfiles ()) { printf ("dodes -- couldn't get tables or key schedule\n"); exit (1); } printf ("Enter input to encrypt as two hex longs: "); scanf ("%lx %lx", &plain [0], &plain [1]); des_encrypt (plain, crypt); printf ("Encrypted result is: %lx %lx\n", crypt [0], crypt [1]); des_decrypt (crypt, cprbuf); printf ("Decrypting that result: %lx %lx\n", cprbuf [0], cprbuf [1]); } #include /* tables to define S boxes and P, per NBS */ static int s_table [8] [4] [16] = { 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, 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, 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, 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, 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, 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, 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, 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 }; static int ptab [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 }; /* --- following is code to compute and store optimized tables --- */ /* The ip, ipi, and ipis tables, their use and generation... The IP table is used to perform the IP operations of DES efficiently, on a byte-by-byte basis. There are 256 entries, each of which is 64 bits wide. Each 64 bit entry is composed of two longs, and the [0]'th long contains the high order bits.) To do the IP transformation, one starts by extracting the rightmost byte from the block to be encrypted, and looking up the corresponding table entry. Proceed by shifting the accumulated partial IP left one place and inclusive-OR'ing the table value for each more significant byte. Continue until all bytes have been processed. Regrettably, the structure of the IP-inverse operation is not such as to allow table lookup based on bytes selected in left-to-right (or right-to-left) order. To compensate for this fact, the ipis table is supplied. As one advances through the entries in ipis, one finds indexes which select the input byte (from 1-8, going left to right) whose value should be used to select the next entry in ipi. If this reordering is followed, the entries extracted from ipi can be inclusive-OR'd and left shifted (in the same manner described for ip), to perform the ip-inverse transformation. */ static long ip [2] [256]; static long ipi [2] [256]; static int ipis [8] = {5, 1, 6, 2, 7, 3, 8, 4}; /* setipent -- given a byte value, compute the corresponding entry and store it in the ip table. Computation based on embedded knowledge of DES algorithm structure. */ setipent (val) int val; { extern long ip [2] [256]; ip [0] [val] = ip [1] [val] = 0L; if (val & 0X40) ip [0] [val] |= 0X1000000L; if (val & 0X10) ip [0] [val] |= 0X10000L; if (val & 0X4) ip [0] [val] |= 0X100L; if (val & 0X1) ip [0] [val] |= 0X1L; if (val & 0X80) ip [1] [val] |= 0X1000000L; if (val & 0X20) ip [1] [val] |= 0X10000L; if (val & 0X8) ip [1] [val] |= 0X100L; if (val & 0X2) ip [1] [val] |= 0X1L; } /* setipient -- given a byte value, compute the corresponding entry and store it in the ipi table. Computation based on embedded knowledge of DES algorithm structure. */ setipient (val) int val; { extern long ipi [2] [256]; ipi [0] [val] = ipi [1] [val] = 0L; if (val & 0X1) ipi [0] [val] |= 0X1000000L; if (val & 0X2) ipi [0] [val] |= 0X10000L; if (val & 0X4) ipi [0] [val] |= 0X100L; if (val & 0X8) ipi [0] [val] |= 0X1L; if (val & 0X10) ipi [1] [val] |= 0X1000000L; if (val & 0X20) ipi [1] [val] |= 0X10000L; if (val & 0X40) ipi [1] [val] |= 0X100L; if (val & 0X80) ipi [1] [val] |= 0X1L; } /* setip -- initialize ip and ipi tables */ setip () { int i; for (i = 0; i < 256; i++) { setipent (i); setipient (i); } } /* the snop table... its generation and use Structure snop is a two-dimensional array. The high-order dimension corresponds to 1 of 8 input bytes, each in the format produced by skedkeys and the E implementation (each byte has 6 significant bits, left-justified in an 8-bit byte, and the input stream of bytes appears in 4 words as (1 3) (5 7) (2 4) (6 8). As the dimension varies from 0->7, bytes are selected from this ordering from left to right. Using a series of 8 table lookups in snop (one for each byte), and IOR'ing the corresponding 32-bit entries, the caller can assemble the composition of s-box lookup and P permutation as specified in DES. In a table entry corresponding to a particular byte, only those bits are set which correspond to those selected by P for the particular s-box. The current format for snop has 64, not 256 entries per byte position. Therefore, it is necessary to divide a byte's value by 4 before using it as a table index. setsnop () computes the entries in snop, based on the NBS tables. */ static long snop [8] [64]; setsnop () { extern long snop [8] [64]; static int map_to_e [8] = {0, 2, 4, 6, 1, 3, 5, 7}; /* table used so that bytes ordered as produced by the E algorithm implementation can be looked up left-to-right */ int i, j, ns, ni; int srow, scol; for (i = 0; i < 8; i++) { for (j = 0; j < 64; j++) snop [i] [j] = 0L; } for (ns = 0; ns < 8; ns++) /* do for each of 8 S-boxes */ { for (ni = 0; ni < 64; ni++) /* do each entry in each box */ { srow = ((ni & 32) >> 4) | (ni & 01); /* lsb and msb of 6 bits */ scol = (ni >> 1) & 0XF; /* now, do successive left shifts on a snop entry, IOR'ing in bits iff P selects a position from the S-box */ for (i = 0; i < 32; i++) /* over each bit in the entry */ { if (map_to_e[ns] != ((ptab [i] - 1) / 4)) { /* this bit not from this S-box: leave alone */ if (i != 31) snop [ns] [ni] <<= 1; continue; } else { snop [ns] [ni] |= (01 & (s_table [map_to_e[ns]] [srow] [scol] >> (3 - ((ptab [i] - 1) % 4)))); if (i != 31) snop [ns] [ni] <<= 1; } } } } /* for (i = 0; i < 8; i++) { for (j = 0; j < 64; j++) printf ("snop [%d] [%d] = %lx\n", i, j, snop [i] [j]); } */ } /* main for tblbuild: compute and output ip, ipi, ipis, snop */ main () { extern long ip [2] [256]; extern long ipi [2] [256]; extern int ipis [8]; extern long snop [8] [64]; int i, j; FILE *fp, *fopen (); /* compute the static tables */ printf ("Computing transformation tables...\n"); setip (); setsnop (); if (NULL == (fp = fopen ("ip", "w"))) { printf ("tblbuild -- can't open output file 'ip'\n"); exit (1); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) fprintf (fp, "%lx\n", ip [i] [j]); fclose (fp); if (NULL == (fp = fopen ("ipi", "w"))) { printf ("tblbuild -- can't open output file 'ipi'\n"); exit (1); } for (i = 0; i < 2; i++) for (j = 0; j < 256; j++) fprintf (fp, "%lx\n", ipi [i] [j]); fclose (fp); if (NULL == (fp = fopen ("ipis", "w"))) { printf ("tblbuild -- can't open output file 'ipis'\n"); exit (1); } for (i = 0; i < 8; i++) fprintf (fp, "%x\n", ipis [i]); fclose (fp); if (NULL == (fp = fopen ("snop", "w"))) { printf ("tblbuild -- can't open output file 'snop'\n"); exit (1); } for (i = 0; i < 8; i++) for (j = 0; j < 64; j++) fprintf (fp, "%lx\n", snop [i] [j]); fclose (fp); printf ("tblbuild -- table files output\n"); } /* demodes.c: jl 30 April 1986: demonstrate DES in various modes */ /* this uses a version of DES that is driven directly */ /* from the NBS tables (including E) and hence is rather slow */ /* (100ms to encrypt a block on a C/70). */ /* it is fairly compact. */ /* key schedule code (from dumbksb.c) does not use the pc2 optimization */ /* and outputs a key schedule as an array of longs */ /* where each long contains a 24-bit right-justified */ /* quantity, compatible with unoptimized e */ #include #include #include /* --- some bit manipulation primitives --- */ /* g_bit -- extract bit bnum from a byte. As per NBS, MSB is bit 1, LSB bit 8 */ int g_bit (bnum, byte) int bnum; unsigned byte; { byte &= 0XFF; return (01 & (byte >> (8 - bnum)) ); } int gb_f28 (bnum, lval) /* get the bnum bit from 28-bit lval */ int bnum; long lval; { return (01 & (lval >> (28 - bnum)) ); } /* --- following code and data does key schedule generation --- */ #define NINPC1 28 #define NINPC2 48 #define PC2FRR 24 /* number of output bits from C or D */ #define SUCCESS 0 /* return values from ksmake */ #define FAILURE 1 int ksmake (inkey, ks) /* Make a key schedule from key bytes in inkey */ /* result is SUCCESS if OK, FAILURE otherwise */ unsigned inkey [8]; long ks [16] [2]; { static int pc1c [] = { 57, 49, 41, 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 }; static int pc1d [] = { 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 }; static int shiftsked []= { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; static int pc2 [] = { 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 }; int i, j, parac, round, nshifts; long pcc, pcd; unsigned incopy; /* first check parity */ for (i = 0; i < 8; i++) /* do each byte */ { parac = 0; incopy = inkey [i]; for (j = 0; j < 8; j++) /* 8 bits in a DES byte */ { if (incopy & 01) parac++; incopy >>= 1; } if (! (parac & 01)) return (FAILURE); /* no odd parity on this byte */ } /* now do pc1 permutation */ pcc = pcd = 0L; for (i = 0; i < NINPC1; i++) /* filling all appropriate bits */ { pcc |= (01 & g_bit (pc1c [i] % 8, (unsigned) (inkey [pc1c [i] / 8]))); pcd |= (01 & g_bit (pc1d [i] % 8, (unsigned) (inkey [pc1d [i] / 8]))); if (i != (NINPC1 - 1)) /* avoid superfluous final shift */ { pcc <<= 1; pcd <<= 1; } } for (round = 0; round < 16; round++) { for (nshifts = 0; nshifts < shiftsked [round]; nshifts++) { /* do appropriate number of 28-bit left rotates on pcc, pcd */ pcc <<= 1; if (0X10000000L & pcc) pcc++; pcc &= 0XFFFFFFFL; pcd <<= 1; if (0X10000000L & pcd) pcd++; pcd &= 0XFFFFFFFL; } /* Now, pcc and pcd have the values on which we can apply pc2 and select the key bits, storing them in ks[0] and ks[1]. The high order [ks[0]] bits all come from pcc, and the low order from pcd. */ ks [round] [0] = ks [round] [1] = 0; for (i = 0; i < PC2FRR; i++) { ks [round] [0] |= gb_f28 (pc2 [i], pcc); if (i != (PC2FRR - 1)) ks [round] [0] <<= 1; } for (i = PC2FRR; i < NINPC2; i++) { ks [round] [1] |= gb_f28 (pc2 [i] - NINPC1, pcd); if (i != (NINPC2 - 1)) ks [round] [1] <<= 1; } } return (SUCCESS); } #define IP 1 /* flag to select IP */ #define IPI IP+1 /* flag to select IPI */ #define ENCRYPT IPI+1 /* flag to select encryption */ #define DECRYPT ENCRYPT+1 /* flag to select decryption */ /* dop -- permute 64 bits via choice of IP or IPI */ dop (inar, outar, flag) long inar [2]; long outar [2]; int flag; { static int 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}; static int ipi [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}; int i; outar [0] = outar [1] = 0L; for (i = 1; i < 33; i++) { outar [0] |= 01 & ((((flag == IP) ? ip[i-1] : ipi[i-1]) < 33) ? (inar [0] >> (32 - ((flag == IP) ? ip[i-1] : ipi[i-1]))) : (inar [1] >> (64 - ((flag == IP) ? ip[i-1] : ipi[i-1]))) ); if (i != 32) outar [0] <<= 1; } for (i = 33; i < 65; i++) { outar [1] |= 01 & ((((flag == IP) ? ip[i-1] : ipi[i-1]) < 33) ? (inar [0] >> (32 - ((flag == IP) ? ip[i-1] : ipi[i-1]))) : (inar [1] >> (64 - ((flag == IP) ? ip[i-1] : ipi[i-1]))) ); if (i != 64) outar [1] <<= 1; } } /* dodes -- encrypt or decrypt a block under key sched in ks */ dodes (inar, outar, flag, ks) long inar [2]; long outar [2]; int flag; long ks [16] [2]; { /* tables to define S boxes and P, per NBS */ static int s_table [8] [4] [16] = { 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, 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, 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, 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, 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, 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, 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, 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 }; static int ptab [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 }; static int etab [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}; register int round, sb, sbidx, i, j; long expan [2]; /* receives output of E transform */ long sbout, scopy; long oarr [2]; dop (inar, outar, IP); for (round = 0; round < 16; round++) { /* first perform des e transformation of 32->48 bits. accepts an input long, returns result into an array of two longs with 24 low-order bits in each element */ expan [0] = expan [1] = 0L; for (i = 1; i < 25; i++) { expan [0] |= 01 & (outar [1] >> (32 - etab[i-1])); if (i != 24) expan [0] <<= 1; } for (i = 25; i < 49; i++) { expan [1] |= 01 & (outar [1] >> (32 - etab[i-1])); if (i != 48) expan [1] <<= 1; } /* xor expanded quantity with key schedule */ expan [0] ^= ks [(flag == ENCRYPT) ? round : 15 - round] [0]; expan [1] ^= ks [(flag == ENCRYPT) ? round : 15 - round] [1]; scopy = 0L; for (sb = 0; sb < 8; sb++) { /* look up bits in s-boxes, filling a 32 bit word */ sbidx = 0X3F & ((sb < 4) ? (expan [0] >> (18 - (6 * sb))) : (expan [1] >> (18 - (6 * (sb-4)))) ); /* select bits per nbs spec */ i = sbidx; i &= 0X20; i >>= 4; i |= 01 & sbidx; j = sbidx; j &= 0X1E; j >>= 1; scopy |= s_table [sb] [i] [j]; if (sb != 7) scopy <<= 4; } /* now, perform p permutation into 'sbout' */ sbout = 0L; for (i = 1; i < 33; i++) { sbout |= 01 & (scopy >> (32 - ptab [i-1])); if (i != 32) sbout <<= 1; } scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap into temp copy - let dop move into true output array */ scopy = outar [0]; oarr [0] = outar [1]; oarr [1] = scopy; dop (oarr, outar, IPI); } /* support routines for demodes */ /* read input bytes from stdin */ int g_inbytes (nby, buffer) /* returns TRUE iff EOF reached */ int nby; /* number of bytes needed at a time */ /* if insufficient, will be padded with nulls */ char buffer []; { int bufix; int getcval; /* init all significant bytes to null pad */ for (bufix = 0; bufix < nby; bufix++) buffer[bufix] = 0; for (bufix = 0; bufix < nby; bufix++) { getcval = getchar (); buffer [bufix] = (char) getcval; if (getcval == EOF) { buffer[bufix] = 0; /* replace with pad */ return (TRUE); /* indicating that EOF detected */ } } return (FALSE); /* indicating no EOF detected */ } /* represent a series of bytes (conditionally) in two buffers, as printable representation and hex representation */ di_bytes (nby, inbuf, pr_buf, hx_buf) int nby; char inbuf []; char pr_buf []; /* NULL if not desired */ char hx_buf []; /* NULL if not desired */ { int i; for (i = 0; i < nby; i++) { if (pr_buf != NULL) { /* Try to show as a printable character, either directly or */ /* by masking off the MSB (if the latter, prefix with '#') */ if (inbuf [i] > 0x7f) { if (isprint (inbuf [i] & 0x7f)) sprintf (pr_buf, "#%c", inbuf [i] & 0x7f); else sprintf (pr_buf, " "); } else { if (isprint (inbuf [i])) sprintf (pr_buf, " %c", inbuf [i]); else sprintf (pr_buf, " "); } pr_buf += 2; } if (hx_buf != NULL) { sprintf (hx_buf, "%1x%1x", 0xf & (inbuf[i]>>4),0xf & inbuf [i]); hx_buf += 2; } } if (pr_buf != NULL) sprintf (pr_buf, "|"); if (hx_buf != NULL) sprintf (hx_buf, "|"); } packbtol (as_ba, as_l) /* pack 4 bytes into a long */ char as_ba []; long *as_l; { long lt; lt = as_ba [0] & 0xff; lt <<= 8; lt |= as_ba [1] & 0xff; lt <<= 8; lt |= as_ba [2] & 0xff; lt <<= 8; lt |= as_ba [3] & 0xff; *as_l = lt; } sprdltob (as_l, as_ba) /* spread a long into 4 bytes */ long as_l; char as_ba []; { as_ba [0] = (char) ((as_l >> 24) & 0xff); as_ba [1] = (char) ((as_l >> 16) & 0xff); as_ba [2] = (char) ((as_l >> 8) & 0xff); as_ba [3] = (char) (as_l & 0xff); } lsh64 (lar, count) /* left shift a 64-bit quantity maintained */ long lar[]; /* in a 2-element long array. Assumes that */ int count; /* a long has at least 32 bits */ { int i; long t; for (i = 0; i < count; i++) { t = (lar [1] >> 31) & 0x1l; lar [1] <<= 1; lar [0] <<= 1; lar [0] |= t; } lar [0] &= 0xffffffffl; lar [1] &= 0xffffffffl; } rsh64 (lar, count) /* right shift a 64-bit quantity maintained */ long lar[]; /* in a 2-element long array. Assumes that */ int count; /* a long has at least 32 bits */ { int i; long t; for (i = 0; i < count; i++) { t = lar [0] & 0x1l; lar [1] >>= 1; lar [0] >>= 1; lar [1] |= (t << 31); } } rplr64 (base, modr, nbits) /* replace rightmost nbits of base */ long base[]; /* (64-bit qty in 2-elmt long array) */ long modr[]; /* with corresponding bits from modr */ int nbits; { /* Assumes longs are 32 bits or more */ long mask; long lmod; /* local copy of modr word */ mask = (nbits >= 32) ? 0xffffffffl : ((0x1l << nbits) - 1); /* mask = (0x1l << ((nbits > 32) ? 32 : nbits)) - 1; */ base [1] &= ~mask; /* wipe out existing low bits */ lmod = modr [1] & mask; base [1] |= lmod; nbits -= 32; if (nbits <= 0) return; mask = (0x1l << nbits) - 1; base [0] &= ~mask; lmod = modr [0] & mask; base [0] |= lmod; } cpy64 (src, dest) /* copy src 2-elmt long array to dest */ long src[]; long dest[]; { dest [0] = src [0]; dest [1] = src [1]; } #define ECB 1 #define CBC ECB+1 #define OFB CBC+1 #define CFB OFB+1 main (argc,argv) int argc; char *argv []; { int argn; int dmode; int eofyet = FALSE; /* will set to TRUE when end of input */ int quant = 0; /* quantum size (in bits) for selected mode */ int flwid; /* size to display a 64-bit chunk of pt or ct */ int i, j; long iv [2], keyl [2]; unsigned inkey [8]; char inkeyc [8]; char inbbuf [8], otbbuf [8]; char iprline [80], ihxline [80], ohxline [80]; long ks [16] [2]; long plain [2], crypt [2], cprbuf [2], cipher [2]; /* default key and IV to NBS sample values */ keyl [0] = 0x01234567l; keyl [1] = 0x89abcdefl; iv [0] = 0x12345678l; iv [1] = 0x90abcdefl; /* scan the command line */ for (argn = 1; argn <= argc; argn++) { if (seq_nocase (argv[argn], "-m")) /* mode specifier */ { /* one string argument expected */ argn++; if (seq_nocase (argv[argn], "ecb")) { dmode = ECB; quant = 64; } else if (seq_nocase (argv[argn], "cbc")) { dmode = CBC; quant = 64; } else if (seq_nocase (argv[argn], "ofb")) { dmode = OFB; if (quant == 0) quant = 64; /* may be overridden */ } else if (seq_nocase (argv[argn], "cfb")) { dmode = CFB; if (quant == 0) quant = 64; /* may be overridden */ } } else if (seq_nocase (argv[argn], "-k")) /* key specifier */ { /* two long hex numerics expected */ argn++; sscanf (argv[argn], "%lx", &keyl [0]); argn++; sscanf (argv[argn], "%lx", &keyl [1]); } else if (seq_nocase (argv[argn], "-iv")) /* IV specifier */ { /* two long hex numerics expected */ argn++; sscanf (argv[argn], "%lx", &iv [0]); argn++; sscanf (argv[argn], "%lx", &iv [1]); } else if (seq_nocase (argv[argn], "-q")) /* quantum specifier */ { /* one decimal number expected */ argn++; sscanf (argv[argn], "%d", &quant); } } if (((dmode == ECB) || (dmode == CBC)) && (quant != 64)) { printf ("Can't override quantum of 64 for ECB or CBC modes... aborting\n"); exit (1); } /* build key schedule (outside scanner, so default works) */ sprdltob (keyl [0], & inkeyc [0]); sprdltob (keyl [1], & inkeyc [4]); for (i = 0; i < 8; i++) inkey [i] = (unsigned) (inkeyc [i] & 0xff); if (ksmake (inkey, ks) != SUCCESS) { printf ("Bad parity on key... aborting...\n"); exit (1); } printf ("Mode is "); switch (dmode) { case ECB: printf ("ECB;"); break; case CBC: printf ("CBC;"); break; case OFB: printf ("OFB;"); printf (" Quantum is %d;", quant); break; case CFB: printf ("CFB;"); printf (" Quantum is %d;", quant); break; default: printf ("Unknown;"); break; } printf (" Key is %lx %lx;", keyl [0], keyl [1]); if (dmode != ECB) printf (" IV is %lx %lx;", iv [0], iv [1]); printf ("\n"); flwid = (8 * 2) + 1; /* 8 bytes, 2 chars/byte, and a delimiter */ while (eofyet == FALSE) /* until EOF detected on input */ { if (dmode == ECB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); dodes (plain, crypt, ENCRYPT, ks); sprdltob (crypt[0], &otbbuf[0]); sprdltob (crypt[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } else if (dmode == CBC) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); plain [0] ^= iv [0]; /* XOR IV with input plaintext */ plain [1] ^= iv [1]; dodes (plain, crypt, ENCRYPT, ks); sprdltob (crypt[0], &otbbuf[0]); sprdltob (crypt[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); iv [0] = crypt [0]; /* use ciphertext output as next IV */ iv [1] = crypt [1]; if (TRUE == eofyet) break; } } else if (dmode == CFB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ /* does file read and display in 64-bit units regardless of quantum */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); for (j = 0; j < 64; j+=quant) { dodes (iv, crypt, ENCRYPT, ks); rsh64 (crypt, 64-quant); /* right-align active DES output bits */ cpy64 (plain, cprbuf); /* copy plaintext to scratch */ rsh64 (cprbuf, 64-(quant+j)); /* right-align active plaintext bits */ /* XOR them into DES output */ crypt [0] ^= cprbuf [0]; crypt [1] ^= cprbuf [1]; lsh64 (iv, quant); /* shift existing IV over */ rplr64 (iv, crypt, quant); /* replace LS IV bits with DES output */ lsh64 (cipher, quant); /* make space in cipher out array */ rplr64 (cipher, crypt, quant); /* insert new output bits */ } sprdltob (cipher[0], &otbbuf[0]); sprdltob (cipher[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } else if (dmode == OFB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); for (j = 0; j < 64; j+=quant) { dodes (iv, crypt, ENCRYPT, ks); rsh64 (crypt, 64-quant); /* right-align active DES output bits */ lsh64 (iv, quant); /* shift existing IV over */ rplr64 (iv, crypt, quant); /* replace LS IV bits with DES output */ cpy64 (plain, cprbuf); /* copy plaintext to scratch */ rsh64 (cprbuf, 64-(quant+j)); /* right-align active plaintext bits */ /* XOR them into DES output */ crypt [0] ^= cprbuf [0]; crypt [1] ^= cprbuf [1]; lsh64 (cipher, quant); /* make space in cipher out array */ rplr64 (cipher, crypt, quant); /* insert new output bits */ } sprdltob (cipher[0], &otbbuf[0]); sprdltob (cipher[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } printf ("%s\n%s\n%s\n", iprline, ihxline, ohxline); } printf ("\n"); } /* ------------------------------------------------------ */ /* This DES software was developed by Steve Kent and John Linn */ /* at BBN Communications Corporation, Cambridge, MA */ /* Do not redistribute this software, or integrate with other */ /* software, without preserving this notice */ /* ------------------------------------------------------ */ /* fastdemo.c: jl 5 May 1986: demonstrate DES in various modes, using */ /* optimized DES version */ /* changes 2 June 1986: */ /* use Dan Hoey's IP, IP-1 optimization */ /* define TIMEONLY to time DES cycles rather than run ordinary demo */ /* timing data on C/70, (compiled -O) with 500 iterations */ /* (each iteration is an encrypt+decrypt) */ /* without HOEYOPT: typical DES op is about 7.825 msec (470 ticks/1000 opns) */ /* with HOEYOPT: typical DES op is about 7.425 msec (445 ticks/1000 opns) */ /* this compares with VAX timing of a slightly different version, */ /* (pre-HOEYOPT) of 2.6 ms/cycle */ /* Additional timing data, from David Balenson at NBS, March 1988 */ /* I initially tried it on our VAX 11/750 and SUN 3/160 (both */ /* running UNIX BSD 4.2) and acheived measurements of 15.3Kbps on the */ /* VAX and 54.1Kbps(!!!) on the SUN. It also compiled and ran successfully */ /* under PC-DOS using the Computer Innovations C86 C compiler. I added */ /* DOS-based timing routines in place of your UNIX routines and got times */ /* of 8.4Kbps on an 8MHz AT and 10.2Kbps on a PS/2-50. */ #include #include #define FALSE 0 #define TRUE 1 #define ECB 1 #define CBC ECB+1 #define OFB CBC+1 #define CFB OFB+1 /* Dan Hoey (hoey@nrl-aic)'s optimization, per 16 May 1986 netmail */ /* Exchange bits of A selected by mask M with bits of B selected by */ /* mask (M << S). TMP is a temporary. */ #define EXSHMSK(A,M,B,S,TMP) \ TMP = ((B >> S) ^ A) & M; \ A ^= TMP; \ TMP <<= S; \ B ^= TMP /* tables to describe permutations, per NBS FIPS */ static int pc1c [] = { 57, 49, 41, 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 }; static int pc1d [] = { 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 }; static int shiftsked []= { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; #ifdef TIMEONLY /* facilities for timing */ struct tbuffer { long proc_utime; long proc_stime; long child_utime; long child_stime; }; struct tbuffer t_before; struct tbuffer t_after; #endif long snop [8] [64] = { 0X808200L,0X0L,0X8000L,0X808202L, 0X808002L,0X8202L,0X2L,0X8000L, 0X200L,0X808200L,0X808202L,0X200L, 0X800202L,0X808002L,0X800000L,0X2L, 0X202L,0X800200L,0X800200L,0X8200L, 0X8200L,0X808000L,0X808000L,0X800202L, 0X8002L,0X800002L,0X800002L,0X8002L, 0X0L,0X202L,0X8202L,0X800000L, 0X8000L,0X808202L,0X2L,0X808000L, 0X808200L,0X800000L,0X800000L,0X200L, 0X808002L,0X8000L,0X8200L,0X800002L, 0X200L,0X2L,0X800202L,0X8202L, 0X808202L,0X8002L,0X808000L,0X800202L, 0X800002L,0X202L,0X8202L,0X808200L, 0X202L,0X800200L,0X800200L,0X0L, 0X8002L,0X8200L,0X0L,0X808002L, 0X104L,0X4010100L,0X0L,0X4010004L, 0X4000100L,0X0L,0X10104L,0X4000100L, 0X10004L,0X4000004L,0X4000004L,0X10000L, 0X4010104L,0X10004L,0X4010000L,0X104L, 0X4000000L,0X4L,0X4010100L,0X100L, 0X10100L,0X4010000L,0X4010004L,0X10104L, 0X4000104L,0X10100L,0X10000L,0X4000104L, 0X4L,0X4010104L,0X100L,0X4000000L, 0X4010100L,0X4000000L,0X10004L,0X104L, 0X10000L,0X4010100L,0X4000100L,0X0L, 0X100L,0X10004L,0X4010104L,0X4000100L, 0X4000004L,0X100L,0X0L,0X4010004L, 0X4000104L,0X10000L,0X4000000L,0X4010104L, 0X4L,0X10104L,0X10100L,0X4000004L, 0X4010000L,0X4000104L,0X104L,0X4010000L, 0X10104L,0X4L,0X4010004L,0X10100L, 0X80L,0X1040080L,0X1040000L,0X21000080L, 0X40000L,0X80L,0X20000000L,0X1040000L, 0X20040080L,0X40000L,0X1000080L,0X20040080L, 0X21000080L,0X21040000L,0X40080L,0X20000000L, 0X1000000L,0X20040000L,0X20040000L,0X0L, 0X20000080L,0X21040080L,0X21040080L,0X1000080L, 0X21040000L,0X20000080L,0X0L,0X21000000L, 0X1040080L,0X1000000L,0X21000000L,0X40080L, 0X40000L,0X21000080L,0X80L,0X1000000L, 0X20000000L,0X1040000L,0X21000080L,0X20040080L, 0X1000080L,0X20000000L,0X21040000L,0X1040080L, 0X20040080L,0X80L,0X1000000L,0X21040000L, 0X21040080L,0X40080L,0X21000000L,0X21040080L, 0X1040000L,0X0L,0X20040000L,0X21000000L, 0X40080L,0X1000080L,0X20000080L,0X40000L, 0X0L,0X20040000L,0X1040080L,0X20000080L, 0X100000L,0X2100001L,0X2000401L,0X0L, 0X400L,0X2000401L,0X100401L,0X2100400L, 0X2100401L,0X100000L,0X0L,0X2000001L, 0X1L,0X2000000L,0X2100001L,0X401L, 0X2000400L,0X100401L,0X100001L,0X2000400L, 0X2000001L,0X2100000L,0X2100400L,0X100001L, 0X2100000L,0X400L,0X401L,0X2100401L, 0X100400L,0X1L,0X2000000L,0X100400L, 0X2000000L,0X100400L,0X100000L,0X2000401L, 0X2000401L,0X2100001L,0X2100001L,0X1L, 0X100001L,0X2000000L,0X2000400L,0X100000L, 0X2100400L,0X401L,0X100401L,0X2100400L, 0X401L,0X2000001L,0X2100401L,0X2100000L, 0X100400L,0X0L,0X1L,0X2100401L, 0X0L,0X100401L,0X2100000L,0X400L, 0X2000001L,0X2000400L,0X400L,0X100001L, 0X40084010L,0X40004000L,0X4000L,0X84010L, 0X80000L,0X10L,0X40080010L,0X40004010L, 0X40000010L,0X40084010L,0X40084000L,0X40000000L, 0X40004000L,0X80000L,0X10L,0X40080010L, 0X84000L,0X80010L,0X40004010L,0X0L, 0X40000000L,0X4000L,0X84010L,0X40080000L, 0X80010L,0X40000010L,0X0L,0X84000L, 0X4010L,0X40084000L,0X40080000L,0X4010L, 0X0L,0X84010L,0X40080010L,0X80000L, 0X40004010L,0X40080000L,0X40084000L,0X4000L, 0X40080000L,0X40004000L,0X10L,0X40084010L, 0X84010L,0X10L,0X4000L,0X40000000L, 0X4010L,0X40084000L,0X80000L,0X40000010L, 0X80010L,0X40004010L,0X40000010L,0X80010L, 0X84000L,0X0L,0X40004000L,0X4010L, 0X40000000L,0X40080010L,0X40084010L,0X84000L, 0X80401000L,0X80001040L,0X80001040L,0X40L, 0X401040L,0X80400040L,0X80400000L,0X80001000L, 0X0L,0X401000L,0X401000L,0X80401040L, 0X80000040L,0X0L,0X400040L,0X80400000L, 0X80000000L,0X1000L,0X400000L,0X80401000L, 0X40L,0X400000L,0X80001000L,0X1040L, 0X80400040L,0X80000000L,0X1040L,0X400040L, 0X1000L,0X401040L,0X80401040L,0X80000040L, 0X400040L,0X80400000L,0X401000L,0X80401040L, 0X80000040L,0X0L,0X0L,0X401000L, 0X1040L,0X400040L,0X80400040L,0X80000000L, 0X80401000L,0X80001040L,0X80001040L,0X40L, 0X80401040L,0X80000040L,0X80000000L,0X1000L, 0X80400000L,0X80001000L,0X401040L,0X80400040L, 0X80001000L,0X1040L,0X400000L,0X80401000L, 0X40L,0X400000L,0X1000L,0X401040L, 0X10000008L,0X10200000L,0X2000L,0X10202008L, 0X10200000L,0X8L,0X10202008L,0X200000L, 0X10002000L,0X202008L,0X200000L,0X10000008L, 0X200008L,0X10002000L,0X10000000L,0X2008L, 0X0L,0X200008L,0X10002008L,0X2000L, 0X202000L,0X10002008L,0X8L,0X10200008L, 0X10200008L,0X0L,0X202008L,0X10202000L, 0X2008L,0X202000L,0X10202000L,0X10000000L, 0X10002000L,0X8L,0X10200008L,0X202000L, 0X10202008L,0X200000L,0X2008L,0X10000008L, 0X200000L,0X10002000L,0X10000000L,0X2008L, 0X10000008L,0X10202008L,0X202000L,0X10200000L, 0X202008L,0X10202000L,0X0L,0X10200008L, 0X8L,0X2000L,0X10200000L,0X202008L, 0X2000L,0X200008L,0X10002008L,0X0L, 0X10202000L,0X10000000L,0X200008L,0X10002008L, 0X8000820L,0X800L,0X20000L,0X8020820L, 0X8000000L,0X8000820L,0X20L,0X8000000L, 0X20020L,0X8020000L,0X8020820L,0X20800L, 0X8020800L,0X20820L,0X800L,0X20L, 0X8020000L,0X8000020L,0X8000800L,0X820L, 0X20800L,0X20020L,0X8020020L,0X8020800L, 0X820L,0X0L,0X0L,0X8020020L, 0X8000020L,0X8000800L,0X20820L,0X20000L, 0X20820L,0X20000L,0X8020800L,0X800L, 0X20L,0X8020020L,0X800L,0X20820L, 0X8000800L,0X20L,0X8000020L,0X8020000L, 0X8020020L,0X8000000L,0X20000L,0X8000820L, 0X0L,0X8020820L,0X20020L,0X8000020L, 0X8020000L,0X8000800L,0X8000820L,0X0L, 0X8020820L,0X20800L,0X20800L,0X820L, 0X820L,0X20020L,0X8000000L,0X8020800L }; long pc2otab [8] [128] = { 0X0L,0X10L,0X4000L,0X4010L,0X40000L,0X40010L,0X44000L,0X44010L, 0X100L,0X110L,0X4100L,0X4110L,0X40100L,0X40110L,0X44100L,0X44110L, 0X20000L,0X20010L,0X24000L,0X24010L,0X60000L,0X60010L,0X64000L,0X64010L, 0X20100L,0X20110L,0X24100L,0X24110L,0X60100L,0X60110L,0X64100L,0X64110L, 0X1L,0X11L,0X4001L,0X4011L,0X40001L,0X40011L,0X44001L,0X44011L, 0X101L,0X111L,0X4101L,0X4111L,0X40101L,0X40111L,0X44101L,0X44111L, 0X20001L,0X20011L,0X24001L,0X24011L,0X60001L,0X60011L,0X64001L,0X64011L, 0X20101L,0X20111L,0X24101L,0X24111L,0X60101L,0X60111L,0X64101L,0X64111L, 0X80000L,0X80010L,0X84000L,0X84010L,0XC0000L,0XC0010L,0XC4000L,0XC4010L, 0X80100L,0X80110L,0X84100L,0X84110L,0XC0100L,0XC0110L,0XC4100L,0XC4110L, 0XA0000L,0XA0010L,0XA4000L,0XA4010L,0XE0000L,0XE0010L,0XE4000L,0XE4010L, 0XA0100L,0XA0110L,0XA4100L,0XA4110L,0XE0100L,0XE0110L,0XE4100L,0XE4110L, 0X80001L,0X80011L,0X84001L,0X84011L,0XC0001L,0XC0011L,0XC4001L,0XC4011L, 0X80101L,0X80111L,0X84101L,0X84111L,0XC0101L,0XC0111L,0XC4101L,0XC4111L, 0XA0001L,0XA0011L,0XA4001L,0XA4011L,0XE0001L,0XE0011L,0XE4001L,0XE4011L, 0XA0101L,0XA0111L,0XA4101L,0XA4111L,0XE0101L,0XE0111L,0XE4101L,0XE4111L, 0X0L,0X800000L,0X2L,0X800002L,0X200L,0X800200L,0X202L,0X800202L, 0X200000L,0XA00000L,0X200002L,0XA00002L,0X200200L,0XA00200L,0X200202L,0XA00202L, 0X1000L,0X801000L,0X1002L,0X801002L,0X1200L,0X801200L,0X1202L,0X801202L, 0X201000L,0XA01000L,0X201002L,0XA01002L,0X201200L,0XA01200L,0X201202L,0XA01202L, 0X0L,0X800000L,0X2L,0X800002L,0X200L,0X800200L,0X202L,0X800202L, 0X200000L,0XA00000L,0X200002L,0XA00002L,0X200200L,0XA00200L,0X200202L,0XA00202L, 0X1000L,0X801000L,0X1002L,0X801002L,0X1200L,0X801200L,0X1202L,0X801202L, 0X201000L,0XA01000L,0X201002L,0XA01002L,0X201200L,0XA01200L,0X201202L,0XA01202L, 0X40L,0X800040L,0X42L,0X800042L,0X240L,0X800240L,0X242L,0X800242L, 0X200040L,0XA00040L,0X200042L,0XA00042L,0X200240L,0XA00240L,0X200242L,0XA00242L, 0X1040L,0X801040L,0X1042L,0X801042L,0X1240L,0X801240L,0X1242L,0X801242L, 0X201040L,0XA01040L,0X201042L,0XA01042L,0X201240L,0XA01240L,0X201242L,0XA01242L, 0X40L,0X800040L,0X42L,0X800042L,0X240L,0X800240L,0X242L,0X800242L, 0X200040L,0XA00040L,0X200042L,0XA00042L,0X200240L,0XA00240L,0X200242L,0XA00242L, 0X1040L,0X801040L,0X1042L,0X801042L,0X1240L,0X801240L,0X1242L,0X801242L, 0X201040L,0XA01040L,0X201042L,0XA01042L,0X201240L,0XA01240L,0X201242L,0XA01242L, 0X0L,0X2000L,0X4L,0X2004L,0X400L,0X2400L,0X404L,0X2404L, 0X0L,0X2000L,0X4L,0X2004L,0X400L,0X2400L,0X404L,0X2404L, 0X400000L,0X402000L,0X400004L,0X402004L,0X400400L,0X402400L,0X400404L,0X402404L, 0X400000L,0X402000L,0X400004L,0X402004L,0X400400L,0X402400L,0X400404L,0X402404L, 0X20L,0X2020L,0X24L,0X2024L,0X420L,0X2420L,0X424L,0X2424L, 0X20L,0X2020L,0X24L,0X2024L,0X420L,0X2420L,0X424L,0X2424L, 0X400020L,0X402020L,0X400024L,0X402024L,0X400420L,0X402420L,0X400424L,0X402424L, 0X400020L,0X402020L,0X400024L,0X402024L,0X400420L,0X402420L,0X400424L,0X402424L, 0X8000L,0XA000L,0X8004L,0XA004L,0X8400L,0XA400L,0X8404L,0XA404L, 0X8000L,0XA000L,0X8004L,0XA004L,0X8400L,0XA400L,0X8404L,0XA404L, 0X408000L,0X40A000L,0X408004L,0X40A004L,0X408400L,0X40A400L,0X408404L,0X40A404L, 0X408000L,0X40A000L,0X408004L,0X40A004L,0X408400L,0X40A400L,0X408404L,0X40A404L, 0X8020L,0XA020L,0X8024L,0XA024L,0X8420L,0XA420L,0X8424L,0XA424L, 0X8020L,0XA020L,0X8024L,0XA024L,0X8420L,0XA420L,0X8424L,0XA424L, 0X408020L,0X40A020L,0X408024L,0X40A024L,0X408420L,0X40A420L,0X408424L,0X40A424L, 0X408020L,0X40A020L,0X408024L,0X40A024L,0X408420L,0X40A420L,0X408424L,0X40A424L, 0X0L,0X10000L,0X8L,0X10008L,0X80L,0X10080L,0X88L,0X10088L, 0X0L,0X10000L,0X8L,0X10008L,0X80L,0X10080L,0X88L,0X10088L, 0X100000L,0X110000L,0X100008L,0X110008L,0X100080L,0X110080L,0X100088L,0X110088L, 0X100000L,0X110000L,0X100008L,0X110008L,0X100080L,0X110080L,0X100088L,0X110088L, 0X800L,0X10800L,0X808L,0X10808L,0X880L,0X10880L,0X888L,0X10888L, 0X800L,0X10800L,0X808L,0X10808L,0X880L,0X10880L,0X888L,0X10888L, 0X100800L,0X110800L,0X100808L,0X110808L,0X100880L,0X110880L,0X100888L,0X110888L, 0X100800L,0X110800L,0X100808L,0X110808L,0X100880L,0X110880L,0X100888L,0X110888L, 0X0L,0X10000L,0X8L,0X10008L,0X80L,0X10080L,0X88L,0X10088L, 0X0L,0X10000L,0X8L,0X10008L,0X80L,0X10080L,0X88L,0X10088L, 0X100000L,0X110000L,0X100008L,0X110008L,0X100080L,0X110080L,0X100088L,0X110088L, 0X100000L,0X110000L,0X100008L,0X110008L,0X100080L,0X110080L,0X100088L,0X110088L, 0X800L,0X10800L,0X808L,0X10808L,0X880L,0X10880L,0X888L,0X10888L, 0X800L,0X10800L,0X808L,0X10808L,0X880L,0X10880L,0X888L,0X10888L, 0X100800L,0X110800L,0X100808L,0X110808L,0X100880L,0X110880L,0X100888L,0X110888L, 0X100800L,0X110800L,0X100808L,0X110808L,0X100880L,0X110880L,0X100888L,0X110888L, 0X0L,0X0L,0X80L,0X80L,0X2000L,0X2000L,0X2080L,0X2080L, 0X1L,0X1L,0X81L,0X81L,0X2001L,0X2001L,0X2081L,0X2081L, 0X200000L,0X200000L,0X200080L,0X200080L,0X202000L,0X202000L,0X202080L,0X202080L, 0X200001L,0X200001L,0X200081L,0X200081L,0X202001L,0X202001L,0X202081L,0X202081L, 0X20000L,0X20000L,0X20080L,0X20080L,0X22000L,0X22000L,0X22080L,0X22080L, 0X20001L,0X20001L,0X20081L,0X20081L,0X22001L,0X22001L,0X22081L,0X22081L, 0X220000L,0X220000L,0X220080L,0X220080L,0X222000L,0X222000L,0X222080L,0X222080L, 0X220001L,0X220001L,0X220081L,0X220081L,0X222001L,0X222001L,0X222081L,0X222081L, 0X2L,0X2L,0X82L,0X82L,0X2002L,0X2002L,0X2082L,0X2082L, 0X3L,0X3L,0X83L,0X83L,0X2003L,0X2003L,0X2083L,0X2083L, 0X200002L,0X200002L,0X200082L,0X200082L,0X202002L,0X202002L,0X202082L,0X202082L, 0X200003L,0X200003L,0X200083L,0X200083L,0X202003L,0X202003L,0X202083L,0X202083L, 0X20002L,0X20002L,0X20082L,0X20082L,0X22002L,0X22002L,0X22082L,0X22082L, 0X20003L,0X20003L,0X20083L,0X20083L,0X22003L,0X22003L,0X22083L,0X22083L, 0X220002L,0X220002L,0X220082L,0X220082L,0X222002L,0X222002L,0X222082L,0X222082L, 0X220003L,0X220003L,0X220083L,0X220083L,0X222003L,0X222003L,0X222083L,0X222083L, 0X0L,0X10L,0X800000L,0X800010L,0X10000L,0X10010L,0X810000L,0X810010L, 0X200L,0X210L,0X800200L,0X800210L,0X10200L,0X10210L,0X810200L,0X810210L, 0X0L,0X10L,0X800000L,0X800010L,0X10000L,0X10010L,0X810000L,0X810010L, 0X200L,0X210L,0X800200L,0X800210L,0X10200L,0X10210L,0X810200L,0X810210L, 0X100000L,0X100010L,0X900000L,0X900010L,0X110000L,0X110010L,0X910000L,0X910010L, 0X100200L,0X100210L,0X900200L,0X900210L,0X110200L,0X110210L,0X910200L,0X910210L, 0X100000L,0X100010L,0X900000L,0X900010L,0X110000L,0X110010L,0X910000L,0X910010L, 0X100200L,0X100210L,0X900200L,0X900210L,0X110200L,0X110210L,0X910200L,0X910210L, 0X4L,0X14L,0X800004L,0X800014L,0X10004L,0X10014L,0X810004L,0X810014L, 0X204L,0X214L,0X800204L,0X800214L,0X10204L,0X10214L,0X810204L,0X810214L, 0X4L,0X14L,0X800004L,0X800014L,0X10004L,0X10014L,0X810004L,0X810014L, 0X204L,0X214L,0X800204L,0X800214L,0X10204L,0X10214L,0X810204L,0X810214L, 0X100004L,0X100014L,0X900004L,0X900014L,0X110004L,0X110014L,0X910004L,0X910014L, 0X100204L,0X100214L,0X900204L,0X900214L,0X110204L,0X110214L,0X910204L,0X910214L, 0X100004L,0X100014L,0X900004L,0X900014L,0X110004L,0X110014L,0X910004L,0X910014L, 0X100204L,0X100214L,0X900204L,0X900214L,0X110204L,0X110214L,0X910204L,0X910214L, 0X0L,0X400L,0X1000L,0X1400L,0X80000L,0X80400L,0X81000L,0X81400L, 0X20L,0X420L,0X1020L,0X1420L,0X80020L,0X80420L,0X81020L,0X81420L, 0X4000L,0X4400L,0X5000L,0X5400L,0X84000L,0X84400L,0X85000L,0X85400L, 0X4020L,0X4420L,0X5020L,0X5420L,0X84020L,0X84420L,0X85020L,0X85420L, 0X800L,0XC00L,0X1800L,0X1C00L,0X80800L,0X80C00L,0X81800L,0X81C00L, 0X820L,0XC20L,0X1820L,0X1C20L,0X80820L,0X80C20L,0X81820L,0X81C20L, 0X4800L,0X4C00L,0X5800L,0X5C00L,0X84800L,0X84C00L,0X85800L,0X85C00L, 0X4820L,0X4C20L,0X5820L,0X5C20L,0X84820L,0X84C20L,0X85820L,0X85C20L, 0X0L,0X400L,0X1000L,0X1400L,0X80000L,0X80400L,0X81000L,0X81400L, 0X20L,0X420L,0X1020L,0X1420L,0X80020L,0X80420L,0X81020L,0X81420L, 0X4000L,0X4400L,0X5000L,0X5400L,0X84000L,0X84400L,0X85000L,0X85400L, 0X4020L,0X4420L,0X5020L,0X5420L,0X84020L,0X84420L,0X85020L,0X85420L, 0X800L,0XC00L,0X1800L,0X1C00L,0X80800L,0X80C00L,0X81800L,0X81C00L, 0X820L,0XC20L,0X1820L,0X1C20L,0X80820L,0X80C20L,0X81820L,0X81C20L, 0X4800L,0X4C00L,0X5800L,0X5C00L,0X84800L,0X84C00L,0X85800L,0X85C00L, 0X4820L,0X4C20L,0X5820L,0X5C20L,0X84820L,0X84C20L,0X85820L,0X85C20L, 0X0L,0X100L,0X40000L,0X40100L,0X0L,0X100L,0X40000L,0X40100L, 0X40L,0X140L,0X40040L,0X40140L,0X40L,0X140L,0X40040L,0X40140L, 0X400000L,0X400100L,0X440000L,0X440100L,0X400000L,0X400100L,0X440000L,0X440100L, 0X400040L,0X400140L,0X440040L,0X440140L,0X400040L,0X400140L,0X440040L,0X440140L, 0X8000L,0X8100L,0X48000L,0X48100L,0X8000L,0X8100L,0X48000L,0X48100L, 0X8040L,0X8140L,0X48040L,0X48140L,0X8040L,0X8140L,0X48040L,0X48140L, 0X408000L,0X408100L,0X448000L,0X448100L,0X408000L,0X408100L,0X448000L,0X448100L, 0X408040L,0X408140L,0X448040L,0X448140L,0X408040L,0X408140L,0X448040L,0X448140L, 0X8L,0X108L,0X40008L,0X40108L,0X8L,0X108L,0X40008L,0X40108L, 0X48L,0X148L,0X40048L,0X40148L,0X48L,0X148L,0X40048L,0X40148L, 0X400008L,0X400108L,0X440008L,0X440108L,0X400008L,0X400108L,0X440008L,0X440108L, 0X400048L,0X400148L,0X440048L,0X440148L,0X400048L,0X400148L,0X440048L,0X440148L, 0X8008L,0X8108L,0X48008L,0X48108L,0X8008L,0X8108L,0X48008L,0X48108L, 0X8048L,0X8148L,0X48048L,0X48148L,0X8048L,0X8148L,0X48048L,0X48148L, 0X408008L,0X408108L,0X448008L,0X448108L,0X408008L,0X408108L,0X448008L,0X448108L, 0X408048L,0X408148L,0X448048L,0X448148L,0X408048L,0X408148L,0X448048L,0X448148L }; /* --- some bit manipulation primitives --- */ /* g_keybit -- extract bit bnum from the key in inkey */ #define g_keybit(bnum) (01 & (inkey [bnum/8] >> (8 - (bnum%8)))) long lrot28 (lval) /* do left rotate of 28 bit quantity */ long lval; { lval <<= 1; if (0X10000000L & lval) lval++; lval &= 0XFFFFFFFL; return (lval); } /* --- following code and data does key schedule generation --- */ #define SUCCESS 0 /* return codes for ksmake */ #define FAILURE SUCCESS + 1 int ksmake (inkey,ks) /* Make a key schedule from key bytes in inkey */ unsigned inkey [8]; unsigned ks [16] [4]; { extern long pc2otab [8] [128]; int round; long pcct, pcdt; long pc2out [2]; int i, j, parac; unsigned incopy; /* test parity of bytes in inkey */ for (i = 0; i < 8; i++) /* do each byte */ { parac = 0; incopy = inkey [i]; for (j = 0; j < 8; j++) /* 8 bits in a DES byte */ { if (incopy & 01) parac++; incopy >>= 1; } if (! (parac & 01)) return (FAILURE); /* no odd parity on this byte */ } /* do pc-1 permutation, extracting bits from inkey */ pcct = pcdt = 0L; for (i = 0; i < 27; i++) /* filling all appropriate bits */ { pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); pcct <<= 1; pcdt <<= 1; } /* one final ior, without a shift */ pcct |= g_keybit(pc1c [i]); pcdt |= g_keybit(pc1d [i]); for (round = 0; round < 16; round++) { /* always at least one shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); if (shiftsked [round] == 2) { /* this round needs another shift */ pcct = lrot28 (pcct); pcdt = lrot28 (pcdt); } /* Now, pcct and pcdt have the values on which we can apply pc2 and select the key bits, storing them in pc2out[0] and pc2out[1]. The high order [pc2out[0]] bits all come from pcct, and the low order from pcdt. */ pc2out [0] = pc2otab [0] [pcct >> 21]; pc2out [0] |= pc2otab [1] [0X7F & (pcct >> 14)]; pc2out [0] |= pc2otab [2] [0X7F & (pcct >> 7)]; pc2out [0] |= pc2otab [3] [0X7F & pcct]; pc2out [1] = pc2otab [4] [pcdt >> 21]; pc2out [1] |= pc2otab [5] [0X7F & (pcdt >> 14)]; pc2out [1] |= pc2otab [6] [0X7F & (pcdt >> 7)]; pc2out [1] |= pc2otab [7] [0X7F & pcdt]; /* order key bits and bytes so as to be compatible with the format generated by the E implementation */ ks [round] [0] = 0XFC00 & (pc2out [0] >> 8); ks [round] [0] |= (0XFC & (pc2out [0] >> 4)); ks [round] [1] = 0XFC00 & (pc2out [1] >> 8); ks [round] [1] |= (0XFC & (pc2out [1] >> 4)); ks [round] [2] = 0XFC00 & (pc2out [0] >> 2); ks [round] [2] |= (0XFC & (pc2out [0] << 2)); ks [round] [3] = 0XFC00 & (pc2out [1] >> 2); ks [round] [3] |= (0XFC & (pc2out [1] << 2)); } return (SUCCESS); } #define LMASK 0XFCFCFCFCL; /* doip -- permute 64 bits from inar to outar */ doip (inar, outar) long inar [2]; long outar [2]; { long lt; outar [0] = inar [0]; outar [1] = inar [1]; EXSHMSK(outar[1],0x0f0f0f0f,outar[0],4,lt); EXSHMSK(outar[1],0x0000ffff,outar[0],16,lt); EXSHMSK(outar[0],0x33333333,outar[1],2,lt); EXSHMSK(outar[0],0x00ff00ff,outar[1],8,lt); EXSHMSK(outar[1],0x55555555,outar[0],1,lt); } /* doipi -- perform ip-inverse */ doipi (inar, outar) long inar [2]; long outar [2]; { long lt; outar [0] = inar [0]; outar [1] = inar [1]; EXSHMSK(outar[1],0x55555555,outar[0],1,lt); EXSHMSK(outar[0],0x00ff00ff,outar[1],8,lt); EXSHMSK(outar[0],0x33333333,outar[1],2,lt); EXSHMSK(outar[1],0x0000ffff,outar[0],16,lt); EXSHMSK(outar[1],0x0f0f0f0f,outar[0],4,lt); } /* des_encrypt -- encrypt a block under key sched in ks */ des_encrypt (inar, outar, ks) long inar [2]; long outar [2]; unsigned ks [16] [4]; { extern long snop [8] [64]; register int round, oddbit; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy, tlong; long oarr [2]; doip (inar, outar); for (round = 0; round < 16; round++) { sbout = 0L; tlong = outar [1]; oddbit = (int) (01 & tlong); tlong >>= 1; tlong &= 0X7FFFFFFFL; /* defeat sign extend -- jl 17 feb 84 */ if (oddbit) tlong |= 0X80000000L; tlong &= LMASK; expan [0] = (unsigned) (tlong >> 16); expan [1] = (unsigned) tlong; tlong = outar [1]; oddbit = !! (tlong & 0X80000000L); tlong <<= 3; if (oddbit) tlong |= 04; tlong &= LMASK; expan [2] = (unsigned) (tlong >> 16); expan [3] = (unsigned) tlong; /* this code bypasses the alternative of loop setup and resultant computation within the loop for speed */ expan [0] ^= ks [round] [0]; sbout |= snop [0] [0X3F & (expan [0] >> 10)]; sbout |= snop [1] [0X3F & (expan [0] >> 2)]; expan [1] ^= ks [round] [1]; sbout |= snop [2] [0X3F & (expan [1] >> 10)]; sbout |= snop [3] [0X3F & (expan [1] >> 2)]; expan [2] ^= ks [round] [2]; sbout |= snop [4] [0X3F & (expan [2] >> 10)]; sbout |= snop [5] [0X3F & (expan [2] >> 2)]; expan [3] ^= ks [round] [3]; sbout |= snop [6] [0X3F & (expan [3] >> 10)]; sbout |= snop [7] [0X3F & (expan [3] >> 2)]; scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } /* des_decrypt -- decrypt a block under key sched in ks */ /* not used as of 5 May, but retained for completeness */ des_decrypt (inar, outar, ks) long inar [2]; long outar [2]; unsigned ks [16] [4]; { extern long snop [8] [64]; register int round, oddbit; unsigned expan [4]; /* receives output of E transform */ long sbout, scopy, tlong; long oarr [2]; doip (inar, outar); for (round = 15; round >= 0; round--) /* note that decryption selects schedule keys in opposite order */ { sbout = 0L; tlong = outar [1]; oddbit = (int) (01 & tlong); tlong >>= 1; tlong &= 0X7FFFFFFFL; /* defeat sign extend -- jl 17 feb 84 */ if (oddbit) tlong |= 0X80000000L; tlong &= LMASK; expan [0] = (unsigned) (tlong >> 16); expan [1] = (unsigned) tlong; tlong = outar [1]; oddbit = !! (tlong & 0X80000000L); tlong <<= 3; if (oddbit) tlong |= 04; tlong &= LMASK; expan [2] = (unsigned) (tlong >> 16); expan [3] = (unsigned) tlong; /* this code bypasses the alternative of loop setup and resultant computation within the loop for speed */ expan [0] ^= ks [round] [0]; sbout |= snop [0] [0X3F & (expan [0] >> 10)]; sbout |= snop [1] [0X3F & (expan [0] >> 2)]; expan [1] ^= ks [round] [1]; sbout |= snop [2] [0X3F & (expan [1] >> 10)]; sbout |= snop [3] [0X3F & (expan [1] >> 2)]; expan [2] ^= ks [round] [2]; sbout |= snop [4] [0X3F & (expan [2] >> 10)]; sbout |= snop [5] [0X3F & (expan [2] >> 2)]; expan [3] ^= ks [round] [3]; sbout |= snop [6] [0X3F & (expan [3] >> 10)]; sbout |= snop [7] [0X3F & (expan [3] >> 2)]; scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy ^ sbout; } /* a final swap */ scopy = outar [0]; outar [0] = outar [1]; outar [1] = scopy; doipi (outar, oarr); /* perform ip-inverse into temp copy */ outar [0] = oarr [0]; outar [1] = oarr [1]; } /* support routines for demodes */ /* read input bytes from stdin */ int g_inbytes (nby, buffer) /* returns TRUE iff EOF reached */ int nby; /* number of bytes needed at a time */ /* if insufficient, will be padded with nulls */ char buffer []; { int bufix; int getcval; /* init all significant bytes to null pad */ for (bufix = 0; bufix < nby; bufix++) buffer[bufix] = 0; for (bufix = 0; bufix < nby; bufix++) { getcval = getchar (); buffer [bufix] = (char) getcval; if (getcval == EOF) { buffer[bufix] = 0; /* replace with pad */ return (TRUE); /* indicating that EOF detected */ } } return (FALSE); /* indicating no EOF detected */ } /* represent a series of bytes (conditionally) in two buffers, as printable representation and hex representation */ di_bytes (nby, inbuf, pr_buf, hx_buf) int nby; char inbuf []; char pr_buf []; /* NULL if not desired */ char hx_buf []; /* NULL if not desired */ { int i; for (i = 0; i < nby; i++) { if (pr_buf != NULL) { /* Try to show as a printable character, either directly or */ /* by masking off the MSB (if the latter, prefix with '#') */ if (inbuf [i] > 0x7f) { if (isprint (inbuf [i] & 0x7f)) sprintf (pr_buf, "#%c", inbuf [i] & 0x7f); else sprintf (pr_buf, " "); } else { if (isprint (inbuf [i])) sprintf (pr_buf, " %c", inbuf [i]); else sprintf (pr_buf, " "); } pr_buf += 2; } if (hx_buf != NULL) { sprintf (hx_buf, "%1x%1x", 0xf & (inbuf[i]>>4),0xf & inbuf [i]); hx_buf += 2; } } if (pr_buf != NULL) sprintf (pr_buf, "|"); if (hx_buf != NULL) sprintf (hx_buf, "|"); } packbtol (as_ba, as_l) /* pack 4 bytes into a long */ char as_ba []; long *as_l; { long lt; lt = as_ba [0] & 0xff; lt <<= 8; lt |= as_ba [1] & 0xff; lt <<= 8; lt |= as_ba [2] & 0xff; lt <<= 8; lt |= as_ba [3] & 0xff; *as_l = lt; } sprdltob (as_l, as_ba) /* spread a long into 4 bytes */ long as_l; char as_ba []; { as_ba [0] = (char) ((as_l >> 24) & 0xff); as_ba [1] = (char) ((as_l >> 16) & 0xff); as_ba [2] = (char) ((as_l >> 8) & 0xff); as_ba [3] = (char) (as_l & 0xff); } lsh64 (lar, count) /* left shift a 64-bit quantity maintained */ long lar[]; /* in a 2-element long array. Assumes that */ int count; /* a long has at least 32 bits */ { int i; long t; for (i = 0; i < count; i++) { t = (lar [1] >> 31) & 0x1l; lar [1] <<= 1; lar [0] <<= 1; lar [0] |= t; } lar [0] &= 0xffffffffl; lar [1] &= 0xffffffffl; } rsh64 (lar, count) /* right shift a 64-bit quantity maintained */ long lar[]; /* in a 2-element long array. Assumes that */ int count; /* a long has at least 32 bits */ { int i; long t; for (i = 0; i < count; i++) { t = lar [0] & 0x1l; lar [1] >>= 1; lar [0] >>= 1; lar [1] |= (t << 31); } } rplr64 (base, modr, nbits) /* replace rightmost nbits of base */ long base[]; /* (64-bit qty in 2-elmt long array) */ long modr[]; /* with corresponding bits from modr */ int nbits; { /* works on architectures where a long is 32 bits or more */ long mask; long lmod; /* local copy of modr word */ mask = (nbits >= 32) ? 0xffffffffl : ((0x1l << nbits) - 1); /* mask = (0x1l << ((nbits > 32) ? 32 : nbits)) - 1; */ base [1] &= ~mask; /* wipe out existing low bits */ lmod = modr [1] & mask; base [1] |= lmod; nbits -= 32; if (nbits <= 0) return; mask = (0x1l << nbits) - 1; base [0] &= ~mask; lmod = modr [0] & mask; base [0] |= lmod; } cpy64 (src, dest) /* copy src 2-elmt long array to dest */ long src[]; long dest[]; { dest [0] = src [0]; dest [1] = src [1]; } #ifndef TIMEONLY main (argc,argv) int argc; char *argv []; { int argn; int dmode; int eofyet = FALSE; /* will set to TRUE when end of input */ int quant = 0; /* quantum size (in bits) for selected mode */ int flwid; /* size to display a 64-bit chunk of pt or ct */ int i, j; long iv [2], keyl [2]; unsigned inkey [8]; char inkeyc [8]; char inbbuf [8], otbbuf [8]; char iprline [80], ihxline [80], ohxline [80]; unsigned ks [16] [4]; long plain [2], crypt [2], cprbuf [2], cipher [2]; /* default key and IV to NBS sample values */ keyl [0] = 0x01234567l; keyl [1] = 0x89abcdefl; iv [0] = 0x12345678l; iv [1] = 0x90abcdefl; /* scan the command line */ for (argn = 1; argn <= argc; argn++) { if (seq_nocase (argv[argn], "-m")) /* mode specifier */ { /* one string argument expected */ argn++; if (seq_nocase (argv[argn], "ecb")) { dmode = ECB; quant = 64; } else if (seq_nocase (argv[argn], "cbc")) { dmode = CBC; quant = 64; } else if (seq_nocase (argv[argn], "ofb")) { dmode = OFB; if (quant == 0) quant = 64; /* may be overridden */ } else if (seq_nocase (argv[argn], "cfb")) { dmode = CFB; if (quant == 0) quant = 64; /* may be overridden */ } } else if (seq_nocase (argv[argn], "-k")) /* key specifier */ { /* two long hex numerics expected */ argn++; sscanf (argv[argn], "%lx", &keyl [0]); argn++; sscanf (argv[argn], "%lx", &keyl [1]); } else if (seq_nocase (argv[argn], "-iv")) /* IV specifier */ { /* two long hex numerics expected */ argn++; sscanf (argv[argn], "%lx", &iv [0]); argn++; sscanf (argv[argn], "%lx", &iv [1]); } else if (seq_nocase (argv[argn], "-q")) /* quantum specifier */ { /* one decimal number expected */ argn++; sscanf (argv[argn], "%d", &quant); } } if (((dmode == ECB) || (dmode == CBC)) && (quant != 64)) { printf ("Can't override quantum of 64 for ECB or CBC modes... aborting\n"); exit (1); } /* build key schedule (outside scanner, so default works) */ sprdltob (keyl [0], & inkeyc [0]); sprdltob (keyl [1], & inkeyc [4]); for (i = 0; i < 8; i++) inkey [i] = (unsigned) (inkeyc [i] & 0xff); if (ksmake (inkey, ks) != SUCCESS) { printf ("Bad parity on key... aborting...\n"); exit (1); } printf ("Mode is "); switch (dmode) { case ECB: printf ("ECB;"); break; case CBC: printf ("CBC;"); break; case OFB: printf ("OFB;"); printf (" Quantum is %d;", quant); break; case CFB: printf ("CFB;"); printf (" Quantum is %d;", quant); break; default: printf ("Unknown;"); break; } printf (" Key is %lx %lx;", keyl [0], keyl [1]); if (dmode != ECB) printf (" IV is %lx %lx;", iv [0], iv [1]); printf ("\n"); flwid = (8 * 2) + 1; /* 8 bytes, 2 chars/byte, and a delimiter */ while (eofyet == FALSE) /* until EOF detected on input */ { if (dmode == ECB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); des_encrypt (plain, crypt, ks); sprdltob (crypt[0], &otbbuf[0]); sprdltob (crypt[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } else if (dmode == CBC) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); plain [0] ^= iv [0]; /* XOR IV with input plaintext */ plain [1] ^= iv [1]; des_encrypt (plain, crypt, ks); sprdltob (crypt[0], &otbbuf[0]); sprdltob (crypt[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); iv [0] = crypt [0]; /* use ciphertext output as next IV */ iv [1] = crypt [1]; if (TRUE == eofyet) break; } } else if (dmode == CFB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ /* does file read and display in 64-bit units regardless of quantum */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); for (j = 0; j < 64; j+=quant) { des_encrypt (iv, crypt, ks); rsh64 (crypt, 64-quant); /* right-align active DES output bits */ cpy64 (plain, cprbuf); /* copy plaintext to scratch */ rsh64 (cprbuf, 64-(quant+j)); /* right-align active plaintext bits */ /* XOR them into DES output */ crypt [0] ^= cprbuf [0]; crypt [1] ^= cprbuf [1]; lsh64 (iv, quant); /* shift existing IV over */ rplr64 (iv, crypt, quant); /* replace LS IV bits with DES output */ lsh64 (cipher, quant); /* make space in cipher out array */ rplr64 (cipher, crypt, quant); /* insert new output bits */ } sprdltob (cipher[0], &otbbuf[0]); sprdltob (cipher[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } else if (dmode == OFB) { for (i = 0; i < 4; i++) /* 4 groups on a printable line */ { if (TRUE == g_inbytes (8, inbbuf)) eofyet = TRUE; di_bytes (8, inbbuf, &iprline [flwid*i], &ihxline [flwid*i]); packbtol (&inbbuf[0], &plain[0]); packbtol (&inbbuf[4], &plain[1]); for (j = 0; j < 64; j+=quant) { des_encrypt (iv, crypt, ks); rsh64 (crypt, 64-quant); /* right-align active DES output bits */ lsh64 (iv, quant); /* shift existing IV over */ rplr64 (iv, crypt, quant); /* replace LS IV bits with DES output */ cpy64 (plain, cprbuf); /* copy plaintext to scratch */ rsh64 (cprbuf, 64-(quant+j)); /* right-align active plaintext bits */ /* XOR them into DES output */ crypt [0] ^= cprbuf [0]; crypt [1] ^= cprbuf [1]; lsh64 (cipher, quant); /* make space in cipher out array */ rplr64 (cipher, crypt, quant); /* insert new output bits */ } sprdltob (cipher[0], &otbbuf[0]); sprdltob (cipher[1], &otbbuf[4]); di_bytes (8, otbbuf, NULL, &ohxline [flwid*i]); if (TRUE == eofyet) break; } } printf ("%s\n%s\n%s\n", iprline, ihxline, ohxline); } printf ("\n"); } #endif #ifdef TIMEONLY main () { int itnum, i; long plain [2], crypt [2], cprbuf [2]; long udiff, bitsdone, u_msec; unsigned ks [16] [4]; long keyl [2]; unsigned inkey [8]; char inkeyc [8]; /* default key to NBS sample value */ keyl [0] = 0x01234567l; keyl [1] = 0x89abcdefl; /* build key schedule (outside scanner, so default works) */ sprdltob (keyl [0], & inkeyc [0]); sprdltob (keyl [1], & inkeyc [4]); for (i = 0; i < 8; i++) inkey [i] = (unsigned) (inkeyc [i] & 0xff); if (ksmake (inkey, ks) != SUCCESS) { printf ("Bad parity on key... aborting...\n"); exit (1); } printf ("Enter number of test iterations [decimal]: "); scanf ("%d", &itnum); times (&t_before); for (i = 0; i < itnum; i++) { des_encrypt (plain, crypt, ks); des_decrypt (crypt, cprbuf, ks); if ((plain [0] != cprbuf [0]) || (plain [1] != cprbuf [1])) { printf ("Encrypt and decrypt disagree -- aborting!!\n"); exit (1); } } times (&t_after); printf ("All encryptions and decryptions verified consistent\n"); /* note: the following code won't work if one times a number of encryptions that take less than one tick, as can occur on a vax with a small number of tests */ udiff = t_after.proc_utime - t_before.proc_utime; printf ("user 1/60 sec ticks = %ld\n", udiff); bitsdone = 2 * (itnum * 64); u_msec = (udiff * 1000) / 60; printf ("%ld user msec/DES cycle\n", u_msec / ((long) 2 * itnum)); printf ("%ld bits/user second\n", (bitsdone * 1000) / u_msec); } #endif /* seq_nocase: */ /* perform case-insensitive comparison of null-terminated ASCII strings */ /* return 0 if not equal, 1 if equal */ /* BUG: shows a match when one string terminates as a subset of another, */ /* but this doesn't affect usability in this context */ int seq_nocase (str1, str2) char *str1, *str2; { char cv1, cv2; for ( ; ((*str1 != '\0') && (*str2 != '\0')); str1++, str2++) { cv1 = ((*str1 >= 'a') && (*str1 <= 'z')) ? (0X7F & (*str1 - ('a' - 'A'))) : *str1; cv2 = ((*str2 >= 'a') && (*str2 <= 'z')) ? (0X7F & (*str2 - ('a' - 'A'))) : *str2; if (cv1 != cv2) { /* chars unequal */ return (0); } } /* if we get here, all characters were equal */ return (1); }   Received: from louie.udel.edu by huey.udel.edu id aa28026; 4 May 89 18:53 EDT Received: from ccv.bbn.com by louie.udel.edu id aa17512; 4 May 89 18:51 EDT Date: Thu, 4 May 89 18:44:32 EDT From: Steve Kent To: Mills@udel.edu Subject: Re: DES routines Message-ID: <8905041851.aa17512@louie.udel.edu> Dave, Fell free to include it in NTP, just so long as the in-line acknowledgement is maintained. Steve  P.S. and be sure to tell all your friends ...