3 * Build precomputed tables for the Rijndael block cipher
5 * (c) 2000 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
34 #include <mLib/bits.h>
36 /*----- Magic variables ---------------------------------------------------*/
38 static octet s[256], si[256];
39 static uint32 t[4][256], ti[4][256];
40 static uint32 u[4][256];
43 /*----- Main code ---------------------------------------------------------*/
47 * Arguments: @unsigned x, y@ = polynomials over %$\gf{2^8}$%
48 * @unsigned m@ = modulus
50 * Returns: The product of two polynomials.
52 * Use: Computes a product of polynomials, quite slowly.
55 static unsigned mul(unsigned x, unsigned y, unsigned m)
60 for (i = 0; i < 8; i++) {
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.
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
90 static void sbox(void)
92 octet log[256], alog[256];
97 /* --- Find a suitable generator, and build log tables --- */
100 for (g = 2; g < 256; g++) {
102 for (i = 0; i < 256; i++) {
105 x = mul(x, g, S_MOD);
106 if (x == 1 && i != 254)
112 fprintf(stderr, "couldn't find generator\n");
116 /* --- Now grind through and do the affine transform --- *
118 * The matrix multiply is an AND and a parity op. The add is an XOR.
121 for (i = 0; i < 256; i++) {
124 unsigned v = i ? alog[255 - log[i]] : 0;
126 assert(i == 0 || mul(i, v, S_MOD) == 1);
129 for (j = 0; j < 8; j++) {
135 x = (x << 1) | (r & 1);
146 * Construct the t tables for doing the round function efficiently.
149 static void tbox(void)
153 for (i = 0; i < 256; i++) {
157 /* --- Build a forwards t-box entry --- */
160 b = a << 1; if (b & 0x100) b ^= S_MOD;
162 w = (c << 0) | (a << 8) | (a << 16) | (b << 24);
164 t[1][i] = ROR32(w, 8);
165 t[2][i] = ROR32(w, 16);
166 t[3][i] = ROR32(w, 24);
168 /* --- Build a backwards t-box entry --- */
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);
176 ti[1][i] = ROR32(w, 8);
177 ti[2][i] = ROR32(w, 16);
178 ti[3][i] = ROR32(w, 24);
184 * Construct the tables for performing the decryption key schedule.
187 static void ubox(void)
191 for (i = 0; i < 256; i++) {
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);
200 u[1][i] = ROR32(w, 8);
201 u[2][i] = ROR32(w, 16);
202 u[3][i] = ROR32(w, 24);
206 /* --- Round constants --- */
208 static void rcon(void)
213 for (i = 0; i < sizeof(rc); i++) {
230 * Rijndael tables [generated]\n\
233 #include \"rijndael-base.h\"\n\
236 /* --- Write out the S-box --- */
240 /* --- The byte substitution and its inverse --- */\n\
242 const octet rijndael_s[256] = {\n\
244 for (i = 0; i < 256; i++) {
245 printf("0x%02x", s[i]);
247 fputs("\n};\n\n", stdout);
249 fputs(",\n ", stdout);
255 const octet rijndael_si[256] = {\n\
257 for (i = 0; i < 256; i++) {
258 printf("0x%02x", si[i]);
260 fputs("\n};\n\n", stdout);
262 fputs(",\n ", stdout);
267 /* --- Write out the big t tables --- */
271 /* --- The big round tables --- */\n\
273 const uint32 rijndael_t[4][256] = {\n\
275 for (j = 0; j < 4; j++) {
276 for (i = 0; i < 256; i++) {
277 printf("0x%08lx", (unsigned long)t[j][i]);
280 fputs(" }\n};\n\n", stdout);
282 fputs(" },\n\n { ", stdout);
283 } else if (i % 4 == 3)
284 fputs(",\n ", stdout);
291 const uint32 rijndael_ti[4][256] = {\n\
293 for (j = 0; j < 4; j++) {
294 for (i = 0; i < 256; i++) {
295 printf("0x%08lx", (unsigned long)ti[j][i]);
298 fputs(" }\n};\n\n", stdout);
300 fputs(" },\n\n { ", stdout);
301 } else if (i % 4 == 3)
302 fputs(",\n ", stdout);
308 /* --- Write out the big u tables --- */
312 /* --- The decryption key schedule tables --- */\n\
314 const uint32 rijndael_u[4][256] = {\n\
316 for (j = 0; j < 4; j++) {
317 for (i = 0; i < 256; i++) {
318 printf("0x%08lx", (unsigned long)u[j][i]);
321 fputs(" }\n};\n\n", stdout);
323 fputs(" },\n\n { ", stdout);
324 } else if (i % 4 == 3)
325 fputs(",\n ", stdout);
331 /* --- Round constants --- */
335 /* --- The round constants --- */\n\
337 const octet rijndael_rcon[%u] = {\n\
338 ", (unsigned)sizeof(rc));
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);
344 fputs(",\n ", stdout);
351 if (fclose(stdout)) {
352 fprintf(stderr, "error writing data\n");
359 /*----- That's all, folks -------------------------------------------------*/