aesdata.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5
   6 #if 1
   7 # define BYTE_FORMAT "0x%02x"
   8 # define BYTE_COLUMNS 8
   9 #else
  10 # define BYTE_FORMAT "%3d"
  11 # define BYTE_COLUMNS 0x10
  12 #endif
  13
  14 #define WORD_FORMAT "0x%08lx"
  15 #define WORD_COLUMNS 4
  16
  17 unsigned char sbox[0x100];
  18 unsigned char isbox[0x100];
  19
  20 unsigned char gf2_log[0x100];
  21 unsigned char gf2_exp[0x100];
  22
  23 unsigned long dtable[4][0x100];
  24 unsigned long itable[4][0x100];
  25 unsigned long mtable[4][0x100];
  26
  27 static unsigned
  28 xtime(unsigned x)
  29 {
  30   assert (x < 0x100);
  31
  32   x <<= 1;
  33   if (x & 0x100)
  34     x ^= 0x11b;
  35
  36   assert (x < 0x100);
  37
  38   return x;
  39 }
  40
  41 /* Computes the exponentiatiom and logarithm tables for GF_2, to the
  42  * base x+1 (0x03). The unit element is 1 (0x01).*/
  43 static void
  44 compute_log(void)
  45 {
  46   unsigned i = 0;
  47   unsigned x = 1;
  48
  49   memset(gf2_log, 0, 0x100);
  50
  51   for (i = 0; i < 0x100; i++, x = x ^ xtime(x))
  52     {
  53       gf2_exp[i] = x;
  54       gf2_log[x] = i;
  55     }
  56   /* Invalid. */
  57   gf2_log[0] = 0;
  58   /* The loop above sets gf2_log[1] = 0xff, which is correct,
  59    * but gf2_log[1] = 0 is nicer. */
  60   gf2_log[1] = 0;
  61 }
  62
  63 static unsigned
  64 mult(unsigned a, unsigned b)
  65 {
  66   return (a && b) ? gf2_exp[ (gf2_log[a] + gf2_log[b]) % 255] : 0;
  67 }
  68
  69 static unsigned
  70 invert(unsigned x)
  71 {
  72   return x ? gf2_exp[0xff - gf2_log[x]] : 0;
  73 }
  74
  75 static unsigned
  76 affine(unsigned x)
  77 {
  78   return 0xff &
  79     (0x63^x^(x>>4)^(x<<4)^(x>>5)^(x<<3)^(x>>6)^(x<<2)^(x>>7)^(x<<1));
  80 }
  81
  82 static void
  83 compute_sbox(void)
  84 {
  85   unsigned i;
  86   for (i = 0; i<0x100; i++)
  87     {
  88       sbox[i] = affine(invert(i));
  89       isbox[sbox[i]] = i;
  90     }
  91 }
  92
  93 /* Generate little endian tables, i.e. the first row of the AES state
  94  * arrays occupies the least significant byte of the words.
  95  *
  96  * The sbox values are multiplied with the column of GF2 coefficients
  97  * of the polynomial 03 x^3 + x^2 + x + 02. */
  98 static void
  99 compute_dtable(void)
 100 {
 101   unsigned i;
 102   for (i = 0; i<0x100; i++)
 103     {
 104       unsigned s = sbox[i];
 105       unsigned j;
 106       unsigned long t  =( ( (s ^ xtime(s)) << 24)
 107                      | (s << 16) | (s << 8)
 108                      | xtime(s) );
 109
 110       for (j = 0; j<4; j++, t = (t << 8) | (t >> 24))
 111         dtable[j][i] = t;
 112     }
 113 }
 114
 115 /* The inverse sbox values are multiplied with the column of GF2 coefficients
 116  * of the polynomial inverse 0b x^3 + 0d x^2 + 09 x + 0e. */
 117 static void
 118 compute_itable(void)
 119 {
 120   unsigned i;
 121   for (i = 0; i<0x100; i++)
 122     {
 123       unsigned s = isbox[i];
 124       unsigned j;
 125       unsigned long t = ( (mult(s, 0xb) << 24)
 126                         | (mult(s, 0xd) << 16)
 127                         | (mult(s, 0x9) << 8)
 128                         | (mult(s, 0xe) ));
 129
 130       for (j = 0; j<4; j++, t = (t << 8) | (t >> 24))
 131         itable[j][i] = t;
 132     }
 133 }
 134
 135 /* Used for key inversion, inverse mix column. No sbox. */
 136 static void
 137 compute_mtable(void)
 138 {
 139   unsigned i;
 140   for (i = 0; i<0x100; i++)
 141     {
 142       unsigned j;
 143       unsigned long t = ( (mult(i, 0xb) << 24)
 144                         | (mult(i, 0xd) << 16)
 145                         | (mult(i, 0x9) << 8)
 146                         | (mult(i, 0xe) ));
 147
 148       for (j = 0; j<4; j++, t = (t << 8) | (t >> 24))
 149         mtable[j][i] = t;
 150     }
 151 }
 152
 153 static void
 154 display_byte_table(const char *name, unsigned char *table)
 155 {
 156   unsigned i, j;
 157
 158   printf("uint8_t %s[0x100] =\n{", name);
 159
 160   for (i = 0; i<0x100; i+= BYTE_COLUMNS)
 161     {
 162       printf("\n  ");
 163       for (j = 0; j<BYTE_COLUMNS; j++)
 164         printf(BYTE_FORMAT ",", table[i + j]);
 165     }
 166
 167   printf("\n};\n\n");
 168 }
 169
 170 static void
 171 display_table(const char *name, unsigned long table[][0x100])
 172 {
 173   unsigned i, j, k;
 174
 175   printf("uint32_t %s[4][0x100] =\n{\n  ", name);
 176
 177   for (k = 0; k<4; k++)
 178     {
 179       printf("{ ");
 180       for (i = 0; i<0x100; i+= WORD_COLUMNS)
 181         {
 182           printf("\n    ");
 183           for (j = 0; j<WORD_COLUMNS; j++)
 184             printf(WORD_FORMAT ",", table[k][i + j]);
 185         }
 186       printf("\n  },");
 187     }
 188   printf("\n};\n\n");
 189 }
 190
 191 static void
 192 display_polynomial(const unsigned *p)
 193 {
 194   printf("(%x x^3 + %x x^2 + %x x + %x)",
 195          p[3], p[2], p[1], p[0]);
 196 }
 197
 198 int
 199 main(int argc, char **argv)
 200 {
 201   compute_log();
 202   if (argc == 1)
 203     {
 204       display_byte_table("gf2_log", gf2_log);
 205       display_byte_table("gf2_exp", gf2_exp);
 206
 207       compute_sbox();
 208       display_byte_table("sbox", sbox);
 209       display_byte_table("isbox", isbox);
 210
 211       compute_dtable();
 212       display_table("dtable", dtable);
 213
 214       compute_itable();
 215       display_table("itable", itable);
 216
 217       compute_mtable();
 218       display_table("mtable", mtable);
 219
 220       return 0;
 221     }
 222   else if (argc == 2)
 223     {
 224       unsigned a;
 225       for (a = 1; a<0x100; a++)
 226         {
 227           unsigned a1 = invert(a);
 228           unsigned b;
 229           unsigned u;
 230           if (a1 == 0)
 231             printf("invert(%x) = 0 !\n", a);
 232
 233           u = mult(a, a1);
 234           if (u != 1)
 235             printf("invert(%x) = %x; product = %x\n",
 236                    a, a1, u);
 237
 238           for (b = 1; b<0x100; b++)
 239             {
 240               unsigned b1 = invert(b);
 241               unsigned c = mult(a, b);
 242
 243               if (c == 0)
 244                 printf("%x x %x = 0\n", a, b);
 245
 246               u = mult(c, a1);
 247               if (u != b)
 248                 printf("%x x %x = %x, invert(%x) = %x, %x x %x = %x\n",
 249                        a, b, c, a, a1, c, a1, u);
 250
 251               u = mult(c, b1);
 252               if (u != a)
 253                 printf("%x x %x = %x, invert(%x) = %x, %x x %x = %x\n",
 254                        a, b, c, b, b1, c, b1, u);
 255             }
 256         }
 257       return 0;
 258     }
 259   else if (argc == 4)
 260     {
 261       unsigned a, b, c;
 262       int op = argv[2][0];
 263       a = strtoul(argv[1], NULL, 16);
 264       b = strtoul(argv[3], NULL, 16);
 265       switch (op)
 266         {
 267         case '+':
 268           c = a ^ b;
 269           break;
 270         case '*':
 271         case 'x':
 272           c = mult(a,b);
 273           break;
 274         case '/':
 275           c = mult(a, invert(b));
 276           break;
 277         default:
 278           return 1;
 279         }
 280       printf("%x %c %x = %x\n", a, op, b, c);
 281       return 0;
 282     }
 283 #if 0
 284   else if (argc == 5)
 285     {
 286       /* Compute gcd(a, x^4+1) */
 287       unsigned d[4];
 288       unsigned u[4];
 289
 290       for (i = 0; i<4; i++)
 291         a[i] = strtoul(argv[1+i], NULL, 16);
 292     }
 293 #endif
 294   else if (argc == 9)
 295     {
 296       unsigned a[4];
 297       unsigned b[4];
 298       unsigned c[4];
 299       unsigned i;
 300       for (i = 0; i<4; i++)
 301         {
 302           a[i] = strtoul(argv[1+i], NULL, 16);
 303           b[i] = strtoul(argv[5+i], NULL, 16);
 304         }
 305
 306       c[0] = mult(a[0],b[0])^mult(a[3],b[1])^mult(a[2],b[2])^mult(a[1],b[3]);
 307       c[1] = mult(a[1],b[0])^mult(a[0],b[1])^mult(a[3],b[2])^mult(a[2],b[3]);
 308       c[2] = mult(a[2],b[0])^mult(a[1],b[1])^mult(a[0],b[2])^mult(a[3],b[3]);
 309       c[3] = mult(a[3],b[0])^mult(a[2],b[1])^mult(a[1],b[2])^mult(a[0],b[3]);
 310
 311       display_polynomial(a); printf(" * "); display_polynomial(b);
 312       printf(" = "); display_polynomial(c); printf("\n");
 313     }
 314   return 1;
 315 }