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

   1 /* -*-c-*-
   2  *
   3  * $Id: des-mktab.c,v 1.5 2004/04/08 01:36:15 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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdarg.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36
  37 #include <mLib/bits.h>
  38
  39 /*----- Static variables --------------------------------------------------*/
  40
  41 /* --- S boxes --- */
  42
  43 static const char s[8][4][16] = {
  44
  45   /* --- S1 --- */
  46
  47   { { 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 },
  48     {  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8 },
  49     {  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0 },
  50     { 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 } },
  51
  52   /* --- S2 --- */
  53
  54   { { 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 },
  55     {  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5 },
  56     {  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15 },
  57     { 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 } },
  58
  59   /* --- S3 --- */
  60
  61   { { 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 },
  62     { 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1 },
  63     { 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7 },
  64     {  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 } },
  65
  66   /* --- S4 --- */
  67
  68   { {  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 },
  69     { 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9 },
  70     { 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4 },
  71     {  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 } },
  72
  73   /* --- S5 --- */
  74
  75   { {  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 },
  76     { 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6 },
  77     {  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14 },
  78     { 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 } },
  79
  80   /* --- S6 --- */
  81
  82   { { 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 },
  83     { 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8 },
  84     {  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6 },
  85     {  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 } },
  86
  87   /* --- S7 --- */
  88
  89   { {  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 },
  90     { 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6 },
  91     {  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2 },
  92     {  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 } },
  93
  94   /* --- S8 --- */
  95
  96   { { 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 },
  97     {  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2 },
  98     {  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8 },
  99     {  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 } }
 100 };
 101
 102 /* --- P table --- */
 103
 104 static char p[32] = {
 105   16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 106    2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 107 };
 108
 109 /*----- Main code ---------------------------------------------------------*/
 110
 111 /* --- @unique@ --- *
 112  *
 113  * Arguments:   @const char *t@ = pointer to table
 114  *              @int base@ = base of the data
 115  *              @int sz@ = number of elements
 116  *              @const char *name@ = name of this table
 117  *              @...@ = things to fill in
 118  *
 119  * Returns:     Zero if it failed, nonzero if it didn't.
 120  *
 121  * Use:         Validates a table.  All the elements must be in range and
 122  *              unique.
 123  */
 124
 125 static int 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 #ifndef CATACOMB_DES_TAB_H\n\
 252 #define CATACOMB_DES_TAB_H\n\
 253 \n\
 254 #define DES_SP {                                                        \\\n\
 255 ", stdout);
 256   for (i = 0; i < 8; i++) {
 257     mangle(s[i], ss, 28 - 4 * i);
 258     printf("\
 259                                                                         \\\n\
 260   /* --- SP[%i] --- */                                                  \\\n\
 261                                                                         \\\n\
 262 ", i);
 263     sep = "  { ";
 264     for (j = 0; j < 64; j++) {
 265       printf("%s0x%08lx", sep, ss[j]);
 266       if (j % 4 == 3)
 267         sep = ",                        \\\n    ";
 268       else
 269         sep = ", ";
 270     }
 271     printf(" }%s                        \\\n", i == 7 ? "" : ",");
 272   }
 273   fputs("\
 274 }\n\
 275 \n\
 276 #endif\n\
 277 ", stdout);
 278
 279   if (fclose(stdout)) {
 280     fprintf(stderr, "error writing data\n");
 281     exit(EXIT_FAILURE);
 282   }
 283
 284   return (0);
 285 }
 286
 287 /*----- That's all, folks -------------------------------------------------*/