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

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