AppleCSP/MiscCSPAlgs/DES.c

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