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

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