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

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