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

   1 /* -*-c-*-
   2  *
   3  * $Id: rijndael-mktab.c,v 1.1 2000/06/17 11:56:07 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.1  2000/06/17 11:56:07  mdw
  34  * New cipher.
  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 %$\mathrm{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 multiplicative inversion in the group
  87  * %$\mathrm{GF}(2^8)[x]/p(x)$%, where %$p(x) = x^8 + x^4 + x^3 + x + 1$%,
  88  * followed by an affine transformation treating inputs as vectors over
  89  * %$\mathrm{GF}(2)$%.  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 0x11b
  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     unsigned m = 0xf8;
 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;
 142       r = (r >> 4) ^ r;
 143       r = (r >> 2) ^ r;
 144       r = (r >> 1) ^ r;
 145       x = (x << 1) | (r & 1);
 146       m = ROR8(m, 1);
 147     }
 148     x ^= 0x63;
 149     s[i] = x;
 150     si[x] = i;
 151   }
 152 }
 153
 154 /* --- @tbox@ --- *
 155  *
 156  * Construct the t tables for doing the round function efficiently.
 157  */
 158
 159 static void tbox(void)
 160 {
 161   unsigned i;
 162
 163   for (i = 0; i < 256; i++) {
 164     uint32 a, b, c, d;
 165     uint32 w;
 166
 167     /* --- Build a forwards t-box entry --- */
 168
 169     a = s[i];
 170     b = a << 1; if (b & 0x100) b ^= S_MOD;
 171     c = a ^ b;
 172     w = (b << 0) | (a << 8) | (a << 16) | (c << 24);
 173     t[0][i] = w;
 174     t[1][i] = ROL32(w, 8);
 175     t[2][i] = ROL32(w, 16);
 176     t[3][i] = ROL32(w, 24);
 177
 178     /* --- Build a backwards t-box entry --- */
 179
 180     a = mul(si[i], 0x0e, S_MOD);
 181     b = mul(si[i], 0x09, S_MOD);
 182     c = mul(si[i], 0x0d, S_MOD);
 183     d = mul(si[i], 0x0b, S_MOD);
 184     w = (a << 0) | (b << 8) | (c << 16) | (d << 24);
 185     ti[0][i] = w;
 186     ti[1][i] = ROL32(w, 8);
 187     ti[2][i] = ROL32(w, 16);
 188     ti[3][i] = ROL32(w, 24);
 189   }
 190 }
 191
 192 /* --- @ubox@ --- *
 193  *
 194  * Construct the tables for performing the decryption key schedule.
 195  */
 196
 197 static void ubox(void)
 198 {
 199   unsigned i;
 200
 201   for (i = 0; i < 256; i++) {
 202     uint32 a, b, c, d;
 203     uint32 w;
 204     a = mul(i, 0x0e, S_MOD);
 205     b = mul(i, 0x09, S_MOD);
 206     c = mul(i, 0x0d, S_MOD);
 207     d = mul(i, 0x0b, S_MOD);
 208     w = (a << 0) | (b << 8) | (c << 16) | (d << 24);
 209     u[0][i] = w;
 210     u[1][i] = ROL32(w, 8);
 211     u[2][i] = ROL32(w, 16);
 212     u[3][i] = ROL32(w, 24);
 213   }
 214 }
 215
 216 /* --- Round constants --- */
 217
 218 void rcon(void)
 219 {
 220   unsigned r = 1;
 221   int i;
 222
 223   for (i = 0; i < sizeof(rc); i++) {
 224     rc[i] = r;
 225     r <<= 1;
 226     if (r & 0x100)
 227       r ^= S_MOD;
 228   }
 229 }
 230
 231 /* --- @main@ --- */
 232
 233 int main(void)
 234 {
 235   int i, j;
 236
 237   puts("\
 238 /* -*-c-*-\n\
 239  *\n\
 240  * Rijndael tables [generated]\n\
 241  */\n\
 242 \n\
 243 #ifndef CATACOMB_RIJNDAEL_TAB_H\n\
 244 #define CATACOMB_RIJNDAEL_TAB_H\n\
 245 ");
 246
 247   /* --- Write out the S-box --- */
 248
 249   sbox();
 250   fputs("\
 251 /* --- The byte substitution and its inverse --- */\n\
 252 \n\
 253 #define RIJNDAEL_S {                                                    \\\n\
 254   ", stdout);
 255   for (i = 0; i < 256; i++) {
 256     printf("0x%02x", s[i]);
 257     if (i == 255)
 258       fputs("                   \\\n}\n\n", stdout);
 259     else if (i % 8 == 7)
 260       fputs(",                  \\\n  ", stdout);
 261     else
 262       fputs(", ", stdout);
 263   }
 264
 265   fputs("\
 266 #define RIJNDAEL_SI {                                                   \\\n\
 267   ", stdout);
 268   for (i = 0; i < 256; i++) {
 269     printf("0x%02x", si[i]);
 270     if (i == 255)
 271       fputs("                   \\\n}\n\n", stdout);
 272     else if (i % 8 == 7)
 273       fputs(",                  \\\n  ", stdout);
 274     else
 275       fputs(", ", stdout);
 276   }
 277
 278   /* --- Write out the big t tables --- */
 279
 280   tbox();
 281   fputs("\
 282 /* --- The big round tables --- */\n\
 283 \n\
 284 #define RIJNDAEL_T {                                                    \\\n\
 285   { ", stdout);
 286   for (j = 0; j < 4; j++) {
 287     for (i = 0; i < 256; i++) {
 288       printf("0x%08x", t[j][i]);
 289       if (i == 255) {
 290         if (j == 3)
 291           fputs(" }                     \\\n}\n\n", stdout);
 292         else
 293           fputs(" },                    \\\n\
 294                                                                         \\\n\
 295   { ", stdout);
 296       } else if (i % 4 == 3)
 297         fputs(",                        \\\n    ", stdout);
 298       else
 299         fputs(", ", stdout);
 300     }
 301   }
 302
 303   fputs("\
 304 #define RIJNDAEL_TI {                                                   \\\n\
 305   { ", stdout);
 306   for (j = 0; j < 4; j++) {
 307     for (i = 0; i < 256; i++) {
 308       printf("0x%08x", ti[j][i]);
 309       if (i == 255) {
 310         if (j == 3)
 311           fputs(" }                     \\\n}\n\n", stdout);
 312         else
 313           fputs(" },                    \\\n\
 314                                                                         \\\n\
 315   { ", stdout);
 316       } else if (i % 4 == 3)
 317         fputs(",                        \\\n    ", stdout);
 318       else
 319         fputs(", ", stdout);
 320     }
 321   }
 322
 323   /* --- Write out the big u tables --- */
 324
 325   ubox();
 326   fputs("\
 327 /* --- The decryption key schedule tables --- */\n\
 328 \n\
 329 #define RIJNDAEL_U {                                                    \\\n\
 330   { ", stdout);
 331   for (j = 0; j < 4; j++) {
 332     for (i = 0; i < 256; i++) {
 333       printf("0x%08x", u[j][i]);
 334       if (i == 255) {
 335         if (j == 3)
 336           fputs(" }                     \\\n}\n\n", stdout);
 337         else
 338           fputs(" },                    \\\n\
 339                                                                         \\\n\
 340   { ", stdout);
 341       } else if (i % 4 == 3)
 342         fputs(",                        \\\n    ", stdout);
 343       else
 344         fputs(", ", stdout);
 345     }
 346   }
 347
 348   /* --- Round constants --- */
 349
 350   rcon();
 351   fputs("\
 352 /* --- The round constants --- */\n\
 353 \n\
 354 #define RIJNDAEL_RCON {                                                 \\\n\
 355   ", stdout);
 356   for (i = 0; i < sizeof(rc); i++) {
 357     printf("0x%02x", rc[i]);
 358     if (i == sizeof(rc) - 1)
 359       fputs("                   \\\n}\n\n", stdout);
 360     else if (i % 8 == 7)
 361       fputs(",                  \\\n  ", stdout);
 362     else
 363       fputs(", ", stdout);
 364   }
 365
 366   /* --- Done --- */
 367
 368   puts("#endif");
 369
 370   if (fclose(stdout)) {
 371     fprintf(stderr, "error writing data\n");
 372     exit(EXIT_FAILURE);
 373   }
 374
 375   return (0);
 376 }
 377
 378 /*----- That's all, folks -------------------------------------------------*/