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