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

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