util/gdss/lib/crypto/algorithm/gentables.c

   1 /*
   2  * COPYRIGHT (C) 1990 DIGITAL EQUIPMENT CORPORATION
   3  * ALL RIGHTS RESERVED
   4  *
   5  * "Digital Equipment Corporation authorizes the reproduction,
   6  * distribution and modification of this software subject to the following
   7  * restrictions:
   8  *
   9  * 1.  Any partial or whole copy of this software, or any modification
  10  * thereof, must include this copyright notice in its entirety.
  11  *
  12  * 2.  This software is supplied "as is" with no warranty of any kind,
  13  * expressed or implied, for any purpose, including any warranty of fitness
  14  * or merchantibility.  DIGITAL assumes no responsibility for the use or
  15  * reliability of this software, nor promises to provide any form of
  16  * support for it on any basis.
  17  *
  18  * 3.  Distribution of this software is authorized only if no profit or
  19  * remuneration of any kind is received in exchange for such distribution.
  20  *
  21  * 4.  This software produces public key authentication certificates
  22  * bearing an expiration date established by DIGITAL and RSA Data
  23  * Security, Inc.  It may cease to generate certificates after the expiration
  24  * date.  Any modification of this software that changes or defeats
  25  * the expiration date or its effect is unauthorized.
  26  *
  27  * 5.  Software that will renew or extend the expiration date of
  28  * authentication certificates produced by this software may be obtained
  29  * from RSA Data Security, Inc., 10 Twin Dolphin Drive, Redwood City, CA
  30  * 94065, (415)595-8782, or from DIGITAL"
  31  *
  32  */
  33
  34 #ifndef SPHINX_ITAR
  35 #define SPHINX_ITAR
  36 static char copyright[] = "\n Copyright, 1989, 1990, Digital Equipment Corporation \n";
  37 static char warning[]= "\n  This software is subject to export restrictions under \
  38 \n  the U.S. Department of State's International Traffic in Arms \
  39 \n  Regulations (ITAR).  This software must not be transmitted \
  40 \n  in source form outside the United States or to a foreign \
  41 \n  national in the United States without a valid U.S. State \
  42 \n  Department export license. ";
  43 #endif
  44
  45 /*
  46  * Generate the permutation tables for a software implementation of DES.
  47  */
  48 #include <stdio.h>
  49
  50 #define FILENAME        "tables.h"
  51 #define EFILE           "endian.h"
  52
  53 typedef unsigned long   INT32;   /* generic type for 32-bit integer */
  54
  55 /*
  56  * The following tables are based on those in the Data Encryption
  57  * Standard document (FIPS PUB 46).
  58  */
  59
  60 /*
  61  * Initial permutation IP
  62  */
  63 static char ip[] = { 2, 4, 6, 8, 1, 3, 5, 7 };
  64
  65 /*
  66  * Final permutation IP^-1
  67  */
  68 static char fp[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
  69
  70 /*
  71  * The (in)famous S-boxes
  72  */
  73 static char si[8][64] = {
  74         /*
  75          * S1
  76          */
  77         14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
  78          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
  79          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
  80         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,
  81
  82         /*
  83          * S2
  84          */
  85         15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
  86          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
  87          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
  88         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,
  89
  90         /*
  91          * S3
  92          */
  93         10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
  94         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
  95         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
  96          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,
  97
  98         /*
  99          * S4
 100          */
 101          7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
 102         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
 103         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
 104          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,
 105
 106         /*
 107          * S5
 108          */
 109          2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
 110         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
 111          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
 112         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,
 113
 114         /*
 115          * S6
 116          */
 117         12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
 118         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
 119          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
 120          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,
 121
 122         /*
 123          * S7
 124          */
 125          4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
 126         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
 127          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
 128          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,
 129
 130         /*
 131          * S8
 132          */
 133         13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
 134          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
 135          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
 136          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
 137 };
 138
 139 /*
 140  * 32-bit permutation function P used on the output of the S-boxes
 141  */
 142 static char p32i[] = {
 143         16,  7, 20, 21,
 144         29, 12, 28, 17,
 145          1, 15, 23, 26,
 146          5, 18, 31, 10,
 147          2,  8, 24, 14,
 148         32, 27,  3,  9,
 149         19, 13, 30,  6,
 150         22, 11,  4, 25
 151 };
 152
 153 static char ei[] = {
 154         32,  1,  2,  3,  4,  5,
 155          4,  5,  6,  7,  8,  9,
 156          8,  9, 10, 11, 12, 13,
 157         12, 13, 14, 15, 16, 17,
 158         16, 17, 18, 19, 20, 21,
 159         20, 21, 22, 23, 24, 25,
 160         24, 25, 26, 27, 28, 29,
 161         28, 29, 30, 31, 32,  1
 162 };
 163
 164 /*
 165  * Permuted choice table (key)
 166  */
 167 static char pc1[] = {
 168         57, 49, 41, 33, 25, 17,  9,
 169          1, 58, 50, 42, 34, 26, 18,
 170         10,  2, 59, 51, 43, 35, 27,
 171         19, 11,  3, 60, 52, 44, 36,
 172
 173         63, 55, 47, 39, 31, 23, 15,
 174          7, 62, 54, 46, 38, 30, 22,
 175         14,  6, 61, 53, 45, 37, 29,
 176         21, 13,  5, 28, 20, 12,  4
 177 };
 178
 179 /*
 180  * Permuted choice key (table)
 181  */
 182 static char pc2[] = {
 183         14, 17, 11, 24,  1,  5,
 184          3, 28, 15,  6, 21, 10,
 185         23, 19, 12,  4, 26,  8,
 186         16,  7, 27, 20, 13,  2,
 187         41, 52, 31, 37, 47, 55,
 188         30, 40, 51, 45, 33, 48,
 189         44, 49, 39, 56, 34, 53,
 190         46, 42, 50, 36, 29, 32
 191 };
 192
 193 /*
 194  * Note that the Standard is written in Big Endian terms so bit 1 is the
 195  * high bit of the byte.
 196  */
 197 static int bytebit[] = {
 198     0200, 0100, 040, 020, 010, 04, 02, 01
 199 };
 200
 201 /*
 202  * Generated tables
 203  */
 204 static INT32 iperma[256],ipermb[256];
 205 static INT32 fperma[256],fpermb[256];
 206 static INT32 sp[8][64];
 207 static char pc1bit[56],pc1byte[56];
 208
 209 static FILE *tables;
 210 static FILE *endian;
 211
 212 /*
 213  * Initialize a permutation array.
 214  */
 215 static perminit( perma,permb,p )
 216 INT32 perma[256],permb[256];
 217 char p[8];
 218 {
 219     register int i,j;
 220
 221     /*
 222      * Clear out the permutation array.
 223      */
 224     memset(perma, 0, sizeof(perma));
 225     memset(permb, 0, sizeof(permb));
 226
 227     /*
 228      * Now produce the table.
 229      */
 230     for (i = 0; i < 4; i++)
 231         for (j = 0; j < 256; j++)
 232         {
 233             if ((j & bytebit[p[i] - 1]) != 0)
 234                 perma[j] |= 1L << (8 * (3 - i));
 235             if ((j & bytebit[p[i+4] - 1]) != 0)
 236                 permb[j] |= 1L << (8 * (3 - i));
 237         }
 238 }
 239
 240 outperm( perma,permb,name,comment )
 241 INT32 perma[256],permb[256];
 242 char *name,*comment;
 243 {
 244     register int i, j;
 245
 246     fprintf(tables, "/*\n * %s\n */\n", comment);
 247     fprintf(tables, "static INT32 %sa[256] = {", name);
 248     for (i = 0; i < 64; i++)
 249     {
 250         fprintf(tables, "\n    ");
 251         for (j = 0; j < 4; j++)
 252             fprintf(tables, "0x%lx, ", (long)perma[(i * 4) + j]);
 253     }
 254
 255     fprintf(tables, "\n};\n\nstatic INT32 %sb[256] = {", name);
 256     for (i = 0; i < 64; i++)
 257     {
 258         fprintf(tables, "\n    ");
 259         for (j = 0; j < 4; j++)
 260             fprintf(tables, "0x%lx, ", (long)permb[(i * 4) + j]);
 261     }
 262     fprintf(tables, "\n};\n\n");
 263 }
 264
 265 /*
 266  * Intialize the combined S and P boxes
 267  */
 268 static spinit()
 269 {
 270     register int i,j,k,l;
 271     INT32 perm;
 272     unsigned char inv[32];
 273
 274     /*
 275      * Invert the pbox array.
 276      */
 277     for (i = 0; i < 32; i++)
 278         inv[p32i[i] - 1] = i;
 279
 280     /*
 281      * Now build a combination of the p and s boxes.
 282      */
 283     for (i = 0; i < 8; i++)
 284         for (j = 0; j < 64; j++)
 285         {
 286             perm = 0;
 287
 288             /*
 289              * Compute the index into the sbox table. The row number is
 290              * formed from bits 0 and 5 (VAX terminology) and the column
 291              * number from the middle 4 bits.
 292              */
 293             l = (j & 0x20) | ((j & 1) ? 0x10 : 0) | ((j >> 1) & 0xF);
 294
 295             /*
 296              * Each sbox entry gives us 4 bits which must be merged into
 297              * the final table.
 298              */
 299             for (k = 0; k < 4; k++)
 300             {
 301                 if ((si[i][l] & (8 >> k)) != 0)
 302                     perm |= 1L << (31 - inv[(i * 4) + k]);
 303             }
 304             sp[i][j] = perm;
 305         }
 306 }
 307
 308 outsp()
 309 {
 310     register int i,j,k;
 311
 312     fprintf(tables, "/*\n * Combined s and p boxes\n */\n");
 313     fprintf(tables, "static INT32 sp[8][64] = {");
 314
 315     for (i = 0; i < 8; i++)
 316     {
 317         fprintf(tables, "\n    /*\n     * Permuted S box %d\n     */", i);
 318         for (j = 0; j < 16; j++)
 319         {
 320             fprintf(tables, "\n    ");
 321             for (k = 0; k < 4; k++)
 322                 fprintf(tables, "0x%lx, ", (long)(sp[i][(j * 4) + k]));
 323         }
 324     }
 325     fprintf(tables, "\n};\n\n");
 326 }
 327
 328 choiceinit( pc,bit,byte )
 329 char pc[],bit[],byte[];
 330 {
 331     register int i;
 332
 333     /*
 334      * Convert a permuted choice table from bit addressing to 2 tables
 335      * giving the byte and bit within the byte address.
 336      */
 337     for (i = 0; i < 56; i++)
 338     {
 339         bit[i] = bytebit[(pc[i] - 1) & 07];
 340         byte[i] = (pc[i] - 1) >> 3;
 341     }
 342 }
 343
 344 outchoice( bit,byte,name,comment )
 345 char bit[],byte[],*name,*comment;
 346 {
 347     register int i,j;
 348
 349     fprintf(tables, "/*\n * %s\n */\n", comment);
 350     fprintf(tables, "static unsigned char %sbit[56] = {", name);
 351     for (i = 0; i < 7; i++)
 352     {
 353         fprintf(tables, "\n    ");
 354         for (j = 0; j < 8; j++)
 355             fprintf(tables, "0x%x, ", bit[(i * 8) + j] & 0xFF);
 356     }
 357     fprintf(tables, "\n};\n\n");
 358
 359     fprintf(tables, "static unsigned char %sbyte[56] = {", name);
 360     for (i = 0; i < 7; i++)
 361     {
 362         fprintf(tables, "\n    ");
 363         for (j = 0; j < 8; j++)
 364             fprintf(tables, "%2d, ", byte[(i * 8) + j]);
 365     }
 366     fprintf(tables, "\n};\n\n");
 367
 368 }
 369
 370 INT32 swap( x )
 371 INT32 x;
 372 {
 373     register char *cp,temp;
 374
 375     cp = (char *)&x;
 376     temp = cp[3];
 377     cp[3] = cp[0];
 378     cp[0] = temp;
 379
 380     temp = cp[2];
 381     cp[2] = cp[1];
 382     cp[1] = temp;
 383
 384     return (x);
 385 }
 386
 387 main( argc,argv )
 388 int argc;
 389 char *argv[];
 390 {
 391     register int i;
 392     union { char bytes [ sizeof(long) ];
 393             long longs; } testword ;
 394     long now;
 395
 396     time(&now);
 397
 398     testword.longs = 1;
 399
 400     if ((endian = fopen(EFILE, "w")) == NULL)
 401     {
 402         perror("endian");
 403         exit(2);
 404     }
 405
 406     fprintf(endian, "/* endian.h */\n");
 407     fprintf(endian, "/*\n * Machine generated on %s */\n", ctime(&now));
 408     fprintf(endian, "\n#ifndef SPHINX_ENDIAN\n\n");
 409     fprintf(endian, "/*\n");
 410     fprintf(endian, " * Little endian machines are DEC/Intel like\n");
 411     fprintf(endian, " * Big endian machines are IBM/SPARC/Motorola like\n *\n");
 412     fprintf(endian, " * This machine is ");
 413     if (testword.bytes[0]) fprintf (endian,"little "); else fprintf(endian,"big ");
 414     fprintf(endian, "endian since the value of SPHINX_ENDIAN is %u\n", testword.bytes[0]);
 415     fprintf(endian, " *\n */\n\n");
 416     fprintf(endian, "\n#define SPHINX_ENDIAN %u\n\n", testword.bytes[0]);
 417     fprintf(endian, "\n#endif\n\n\n");
 418
 419     if ((tables = fopen(FILENAME, "w")) == NULL)
 420     {
 421         perror("gentables");
 422         exit(2);
 423     }
 424
 425     fprintf(tables, "/*\n * Machine generated tables for DES encryption %s */\n\n",
 426                                         ctime(&now));
 427     if (testword.bytes[0])
 428          fprintf(tables, "/*\n * Little Endian (DEC/Intel like)\n */\n\n");
 429     else fprintf(tables, "/*\n * Big Endian (IBM/SPARC/Motorola like)\n */\n\n");
 430
 431     perminit(iperma, ipermb, ip);
 432     perminit(fperma, fpermb, fp);
 433
 434     if (testword.bytes[0]) /* little endian */
 435     /*
 436      * Perform a byte swap on the final permutation table.
 437      */
 438     for (i = 0; i < 256; i++)
 439     {
 440         fperma[i] = swap(fperma[i]);
 441         fpermb[i] = swap(fpermb[i]);
 442     }
 443
 444     outperm(iperma, ipermb, "iperm", "Initial permutation");
 445     outperm(fperma, fpermb, "fperm", "Final permutation");
 446     spinit();
 447     outsp();
 448     choiceinit(pc1, pc1bit, pc1byte);
 449     outchoice(pc1bit, pc1byte, "pc1", "Permuted choice 1 table");
 450     exit(0);
 451 }