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[32] = {\n\
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 -------------------------------------------------*/