chiark - git - mdw - catacomb/blob - symm/des-mktab.c

   1 /* -*-c-*-
   2  *
   3  * Build combined S-P tables for DES
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <stdarg.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <mLib/bits.h>
  36 #include <mLib/macros.h>
  37
  38 /*----- Static variables --------------------------------------------------*/
  39
  40 /* --- S boxes --- */
  41
  42 static const char s[8][4][16] = {
  43
  44   /* --- S1 --- */
  45
  46   { { 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 },
  47     {  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8 },
  48     {  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0 },
  49     { 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 } },
  50
  51   /* --- S2 --- */
  52
  53   { { 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 },
  54     {  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5 },
  55     {  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15 },
  56     { 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 } },
  57
  58   /* --- S3 --- */
  59
  60   { { 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 },
  61     { 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1 },
  62     { 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7 },
  63     {  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 } },
  64
  65   /* --- S4 --- */
  66
  67   { {  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 },
  68     { 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9 },
  69     { 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4 },
  70     {  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 } },
  71
  72   /* --- S5 --- */
  73
  74   { {  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 },
  75     { 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6 },
  76     {  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14 },
  77     { 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 } },
  78
  79   /* --- S6 --- */
  80
  81   { { 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 },
  82     { 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8 },
  83     {  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6 },
  84     {  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 } },
  85
  86   /* --- S7 --- */
  87
  88   { {  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 },
  89     { 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6 },
  90     {  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2 },
  91     {  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 } },
  92
  93   /* --- S8 --- */
  94
  95   { { 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 },
  96     {  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2 },
  97     {  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8 },
  98     {  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 } }
  99 };
 100
 101 /* --- P table --- */
 102
 103 static char p[32] = {
 104   16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 105    2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 106 };
 107
 108 /*----- Main code ---------------------------------------------------------*/
 109
 110 /* --- @unique@ --- *
 111  *
 112  * Arguments:   @const char *t@ = pointer to table
 113  *              @int base@ = base of the data
 114  *              @int sz@ = number of elements
 115  *              @const char *name@ = name of this table
 116  *              @...@ = things to fill in
 117  *
 118  * Returns:     Zero if it failed, nonzero if it didn't.
 119  *
 120  * Use:         Validates a table.  All the elements must be in range and
 121  *              unique.
 122  */
 123
 124 static int PRINTF_LIKE(4, 5)
 125   unique(const char *t, int base, int sz, const char *name, ...)
 126 {
 127   char u[32];
 128   char nbuf[128];
 129   int i;
 130   int ok = 1;
 131
 132   {
 133     va_list ap;
 134     va_start(ap, name);
 135     vsprintf(nbuf, name, ap);
 136     va_end(ap);
 137   }
 138
 139   if (sz > sizeof(u)) {
 140     fprintf(stderr, "internal error: table `%s' too large\n", nbuf);
 141     exit(EXIT_FAILURE);
 142   }
 143   memset(u, 0, sizeof(u));
 144   for (i = 0; i < sz; i++) {
 145     int x = t[i] - base;
 146     if (x >= sz) {
 147       fprintf(stderr, "validation error: %i too big (index %i) in %s\n",
 148               x + base, i, nbuf);
 149       ok = 0;
 150     } else if (u[x]) {
 151       fprintf(stderr, "validation error: duplicate %i (index %i) in %s\n",
 152               x + base, i, nbuf);
 153       ok = 0;
 154     }
 155     u[x] = 1;
 156   }
 157   for (i = 0; i < sz; i++) {
 158     if (!u[i]) {
 159       fprintf(stderr, "validation error: missing %i in %s\n",
 160               i + base, nbuf);
 161       ok = 0;
 162     }
 163   }
 164
 165   return (ok);
 166 }
 167
 168 /* --- @validate@ --- *
 169  *
 170  * Arguments:   ---
 171  *
 172  * Returns:     Only if everything's OK.
 173  *
 174  * Use:         Validates the tables.  A bit.  Not much at all...
 175  */
 176
 177 static void validate(void)
 178 {
 179   int i, j;
 180   int ok = 1;
 181
 182   for (i = 0; i < 8; i++) for (j = 0; j < 4; j++)
 183     if (!unique(s[i][j], 0, 16, "sbox %i, row %i", i, j)) ok = 0;
 184   if (!unique(p, 1, 32, "p")) ok = 0;
 185   if (!ok)
 186     exit(EXIT_FAILURE);
 187 }
 188
 189 /* --- @permute@ --- *
 190  *
 191  * Arguments:   @unsigned long x@ = value to permute
 192  *
 193  * Returns:     Permuted version of @x@.
 194  *
 195  * Use:         Permutes a number.  The result is the input value after
 196  *              having been spewed through the @P@ permutation, and then
 197  *              (and this is important) rotated left one place.
 198  */
 199
 200 static unsigned long permute(unsigned long x)
 201 {
 202   unsigned long y = 0;
 203   unsigned i;
 204
 205   for (i = 0; i < 32; i++) {
 206     if (x & (1 << (32 - p[i])))
 207       y |= (1 << (31 - i));
 208   }
 209   return (ROL32(y, 1));
 210 }
 211
 212 /* --- @mangle@ --- *
 213  *
 214  * Arguments:   @const char s[4][16]@ = an s-box
 215  *              @unsigned long ss[64]@ = output buffer
 216  *              @int bitoff@ = bit offset to use
 217  *
 218  * Returns:     ---
 219  *
 220  * Use:         Mangles the s-box.  Specifically, the bizarre indexing is
 221  *              transformed into something sensible, and the result is
 222  *              permuted according to the @p@ table.
 223  */
 224
 225 static void mangle(const char s[4][16], unsigned long *ss, int bitoff)
 226 {
 227   unsigned i;
 228   for (i = 0; i < 64; i++) {
 229     unsigned row = ((i & 0x20) >> 4) | (i & 0x01);
 230     unsigned col = (i & 0x1e) >> 1;
 231     ss[i] = permute(s[row][col] << bitoff);
 232   }
 233 }
 234
 235 /* --- @main@ --- */
 236
 237 int main(void)
 238 {
 239   int i, j;
 240   unsigned long ss[64];
 241   const char *sep;
 242
 243   validate();
 244
 245   fputs("\
 246 /* -*-c-*-\n\
 247  *\n\
 248  * DES tables [generated]\n\
 249  */\n\
 250 \n\
 251 #include \"des-base.h\"\n\
 252 \n\
 253 const uint32 des_sp[8][64] = {\n\
 254 ", stdout);
 255   for (i = 0; i < 8; i++) {
 256     mangle(s[i], ss, 28 - 4 * i);
 257     printf("\n  /* --- SP[%i] --- */\n\n", i);
 258     sep = "  { ";
 259     for (j = 0; j < 64; j++) {
 260       printf("%s0x%08lx", sep, ss[j]);
 261       if (j % 4 == 3)
 262         sep = ",\n    ";
 263       else
 264         sep = ", ";
 265     }
 266     printf(" }%s\n", i == 7 ? "" : ",");
 267   }
 268   fputs("};\n", stdout);
 269
 270   if (fclose(stdout)) {
 271     fprintf(stderr, "error writing data\n");
 272     exit(EXIT_FAILURE);
 273   }
 274
 275   return (0);
 276 }
 277
 278 /*----- That's all, folks -------------------------------------------------*/