git.distorted.org.uk Git - u/mdw/catacomb/blob - des-mktab.c

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