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
xtime(unsigned x)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
compute_log(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
mult(unsigned a,unsigned b)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
invert(unsigned x)70 invert(unsigned x)
71 {
72 return x ? gf2_exp[0xff - gf2_log[x]] : 0;
73 }
74
75 static unsigned
affine(unsigned x)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
compute_sbox(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
compute_dtable(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
compute_itable(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
compute_mtable(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
display_byte_table(const char * name,unsigned char * table)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
display_table(const char * name,unsigned long table[][0x100])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
display_polynomial(const unsigned * p)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
main(int argc,char ** argv)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 }
316