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

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