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

   1 /* -*-c-*-
   2  *
   3  * $Id: square-mktab.c,v 1.1 2000/07/27 18:10:27 mdw Exp $
   4  *
   5  * Build precomputed tables for the Square block cipher
   6  *
   7  * (c) 2000 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: square-mktab.c,v $
  33  * Revision 1.1  2000/07/27 18:10:27  mdw
  34  * Build precomuted tables for Square.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <assert.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43
  44 #include <mLib/bits.h>
  45
  46 /*----- Magic variables ---------------------------------------------------*/
  47
  48 static octet s[256], si[256];
  49 static uint32 t[4][256], ti[4][256];
  50 static uint32 u[4][256];
  51 static octet rc[32];
  52
  53 /*----- Main code ---------------------------------------------------------*/
  54
  55 /* --- @mul@ --- *
  56  *
  57  * Arguments:   @unsigned x, y@ = polynomials over %$\gf{2^8}$%
  58  *              @unsigned m@ = modulus
  59  *
  60  * Returns:     The product of two polynomials.
  61  *
  62  * Use:         Computes a product of polynomials, quite slowly.
  63  */
  64
  65 static unsigned mul(unsigned x, unsigned y, unsigned m)
  66 {
  67   unsigned a = 0;
  68   unsigned i;
  69
  70   for (i = 0; i < 8; i++) {
  71     if (y & 1)
  72       a ^= x;
  73     y >>= 1;
  74     x <<= 1;
  75     if (x & 0x100)
  76       x ^= m;
  77   }
  78
  79   return (a);
  80 }
  81
  82 /* --- @sbox@ --- *
  83  *
  84  * Build the S-box.
  85  *
  86  * This is built from inversion in the multiplicative group of
  87  * %$\gf{2^8}[x]/(p(x))$%, where %$p(x) = x^8 + x^4 + x^3 + x + 1$%, followed
  88  * by an affine transformation treating inputs as vectors over %$\gf{2}$%.
  89  * The result is a horrible function.
  90  *
  91  * The inversion is done slightly sneakily, by building log and antilog
  92  * tables.  Let %$a$% be an element of the finite field.  If the inverse of
  93  * %$a$% is %$a^{-1}$%, then %$\log a a^{-1} = 0$%.  Hence
  94  * %$\log a = -\log a^{-1}$%.  This saves fiddling about with Euclidean
  95  * algorithm.
  96  */
  97
  98 #define S_MOD 0x1f5
  99
 100 static void sbox(void)
 101 {
 102   octet log[256], alog[256];
 103   unsigned x;
 104   unsigned i;
 105   unsigned g;
 106
 107   /* --- Find a suitable generator, and build log tables --- */
 108
 109   log[0] = 0;
 110   for (g = 2; g < 256; g++) {
 111     x = 1;
 112     for (i = 0; i < 256; i++) {
 113       log[x] = i;
 114       alog[i] = x;
 115       x = mul(x, g, S_MOD);
 116       if (x == 1 && i != 254)
 117         goto again;
 118     }
 119     goto done;
 120   again:;
 121   }
 122   fprintf(stderr, "couldn't find generator\n");
 123   exit(EXIT_FAILURE);
 124 done:;
 125
 126   /* --- Now grind through and do the affine transform --- *
 127    *
 128    * The matrix multiply is an AND and a parity op.  The add is an XOR.
 129    */
 130
 131   for (i = 0; i < 256; i++) {
 132     unsigned j;
 133     octet m[] = { 0xd6, 0x7b, 0x3d, 0x1f, 0x0f, 0x05, 0x03, 0x01 };
 134     unsigned v = i ? alog[255 - log[i]] : 0;
 135
 136     assert(i == 0 || mul(i, v, S_MOD) == 1);
 137
 138     x = 0;
 139     for (j = 0; j < 8; j++) {
 140       unsigned r;
 141       r = v & m[j];
 142       r = (r >> 4) ^ r;
 143       r = (r >> 2) ^ r;
 144       r = (r >> 1) ^ r;
 145       x = (x << 1) | (r & 1);
 146     }
 147     x ^= 0xb1;
 148     s[i] = x;
 149     si[x] = i;
 150   }
 151 }
 152
 153 /* --- @tbox@ --- *
 154  *
 155  * Construct the t tables for doing the round function efficiently.
 156  */
 157
 158 static void tbox(void)
 159 {
 160   unsigned i;
 161
 162   for (i = 0; i < 256; i++) {
 163     uint32 a, b, c, d;
 164     uint32 w;
 165
 166     /* --- Build a forwards t-box entry --- */
 167
 168     a = s[i];
 169     b = a << 1; if (b & 0x100) b ^= S_MOD;
 170     c = a ^ b;
 171     w = (b << 0) | (a << 8) | (a << 16) | (c << 24);
 172     t[0][i] = w;
 173     t[1][i] = ROL32(w, 8);
 174     t[2][i] = ROL32(w, 16);
 175     t[3][i] = ROL32(w, 24);
 176
 177     /* --- Build a backwards t-box entry --- */
 178
 179     a = mul(si[i], 0x0e, S_MOD);
 180     b = mul(si[i], 0x09, S_MOD);
 181     c = mul(si[i], 0x0d, S_MOD);
 182     d = mul(si[i], 0x0b, S_MOD);
 183     w = (a << 0) | (b << 8) | (c << 16) | (d << 24);
 184     ti[0][i] = w;
 185     ti[1][i] = ROL32(w, 8);
 186     ti[2][i] = ROL32(w, 16);
 187     ti[3][i] = ROL32(w, 24);
 188   }
 189 }
 190
 191 /* --- @ubox@ --- *
 192  *
 193  * Construct the tables for performing the key schedule.
 194  */
 195
 196 static void ubox(void)
 197 {
 198   unsigned i;
 199
 200   for (i = 0; i < 256; i++) {
 201     uint32 a, b, c;
 202     uint32 w;
 203     a = i;
 204     b = a << 1; if (b & 0x100) b ^= S_MOD;
 205     c = a ^ b;
 206     w = (b << 0) | (a << 8) | (a << 16) | (c << 24);
 207     u[0][i] = w;
 208     u[1][i] = ROL32(w, 8);
 209     u[2][i] = ROL32(w, 16);
 210     u[3][i] = ROL32(w, 24);
 211   }
 212 }
 213
 214 /* --- Round constants --- */
 215
 216 void rcon(void)
 217 {
 218   unsigned r = 1;
 219   int i;
 220
 221   for (i = 0; i < sizeof(rc); i++) {
 222     rc[i] = r;
 223     r <<= 1;
 224     if (r & 0x100)
 225       r ^= S_MOD;
 226   }
 227 }
 228
 229 /* --- @main@ --- */
 230
 231 int main(void)
 232 {
 233   int i, j;
 234
 235   puts("\
 236 /* -*-c-*-\n\
 237  *\n\
 238  * Square tables [generated]\n\
 239  */\n\
 240 \n\
 241 #ifndef CATACOMB_SQUARE_TAB_H\n\
 242 #define CATACOMB_SQUARE_TAB_H\n\
 243 ");
 244
 245   /* --- Write out the S-box --- */
 246
 247   sbox();
 248   fputs("\
 249 /* --- The byte substitution and its inverse --- */\n\
 250 \n\
 251 #define SQUARE_S {                                                      \\\n\
 252   ", stdout);
 253   for (i = 0; i < 256; i++) {
 254     printf("0x%02x", s[i]);
 255     if (i == 255)
 256       fputs("                   \\\n}\n\n", stdout);
 257     else if (i % 8 == 7)
 258       fputs(",                  \\\n  ", stdout);
 259     else
 260       fputs(", ", stdout);
 261   }
 262
 263   fputs("\
 264 #define SQUARE_SI {                                                     \\\n\
 265   ", stdout);
 266   for (i = 0; i < 256; i++) {
 267     printf("0x%02x", si[i]);
 268     if (i == 255)
 269       fputs("                   \\\n}\n\n", stdout);
 270     else if (i % 8 == 7)
 271       fputs(",                  \\\n  ", stdout);
 272     else
 273       fputs(", ", stdout);
 274   }
 275
 276   /* --- Write out the big t tables --- */
 277
 278   tbox();
 279   fputs("\
 280 /* --- The big round tables --- */\n\
 281 \n\
 282 #define SQUARE_T {                                                      \\\n\
 283   { ", stdout);
 284   for (j = 0; j < 4; j++) {
 285     for (i = 0; i < 256; i++) {
 286       printf("0x%08x", t[j][i]);
 287       if (i == 255) {
 288         if (j == 3)
 289           fputs(" }                     \\\n}\n\n", stdout);
 290         else
 291           fputs(" },                    \\\n\
 292                                                                         \\\n\
 293   { ", stdout);
 294       } else if (i % 4 == 3)
 295         fputs(",                        \\\n    ", stdout);
 296       else
 297         fputs(", ", stdout);
 298     }
 299   }
 300
 301   fputs("\
 302 #define SQUARE_TI {                                                     \\\n\
 303   { ", stdout);
 304   for (j = 0; j < 4; j++) {
 305     for (i = 0; i < 256; i++) {
 306       printf("0x%08x", ti[j][i]);
 307       if (i == 255) {
 308         if (j == 3)
 309           fputs(" }                     \\\n}\n\n", stdout);
 310         else
 311           fputs(" },                    \\\n\
 312                                                                         \\\n\
 313   { ", stdout);
 314       } else if (i % 4 == 3)
 315         fputs(",                        \\\n    ", stdout);
 316       else
 317         fputs(", ", stdout);
 318     }
 319   }
 320
 321   /* --- Write out the big u tables --- */
 322
 323   ubox();
 324   fputs("\
 325 /* --- The key schedule tables --- */\n\
 326 \n\
 327 #define SQUARE_U {                                                      \\\n\
 328   { ", stdout);
 329   for (j = 0; j < 4; j++) {
 330     for (i = 0; i < 256; i++) {
 331       printf("0x%08x", u[j][i]);
 332       if (i == 255) {
 333         if (j == 3)
 334           fputs(" }                     \\\n}\n\n", stdout);
 335         else
 336           fputs(" },                    \\\n\
 337                                                                         \\\n\
 338   { ", stdout);
 339       } else if (i % 4 == 3)
 340         fputs(",                        \\\n    ", stdout);
 341       else
 342         fputs(", ", stdout);
 343     }
 344   }
 345
 346   /* --- Round constants --- */
 347
 348   rcon();
 349   fputs("\
 350 /* --- The round constants --- */\n\
 351 \n\
 352 #define SQUARE_RCON {                                                   \\\n\
 353   ", stdout);
 354   for (i = 0; i < sizeof(rc); i++) {
 355     printf("0x%02x", rc[i]);
 356     if (i == sizeof(rc) - 1)
 357       fputs("                   \\\n}\n\n", stdout);
 358     else if (i % 8 == 7)
 359       fputs(",                  \\\n  ", stdout);
 360     else
 361       fputs(", ", stdout);
 362   }
 363
 364   /* --- Done --- */
 365
 366   puts("#endif");
 367
 368   if (fclose(stdout)) {
 369     fprintf(stderr, "error writing data\n");
 370     exit(EXIT_FAILURE);
 371   }
 372
 373   return (0);
 374 }
 375
 376 /*----- That's all, folks -------------------------------------------------*/