3 * $Id: rijndael-mktab.c,v 1.3 2000/10/14 17:13:19 mdw Exp $
5 * Build precomputed tables for the Rijndael block cipher
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: rijndael-mktab.c,v $
33 * Revision 1.3 2000/10/14 17:13:19 mdw
34 * Fix some compile errors.
36 * Revision 1.2 2000/06/18 23:12:15 mdw
37 * Change typesetting of Galois Field names.
39 * Revision 1.1 2000/06/17 11:56:07 mdw
44 /*----- Header files ------------------------------------------------------*/
50 #include <mLib/bits.h>
52 /*----- Magic variables ---------------------------------------------------*/
54 static octet s
[256], si
[256];
55 static uint32 t
[4][256], ti
[4][256];
56 static uint32 u
[4][256];
59 /*----- Main code ---------------------------------------------------------*/
63 * Arguments: @unsigned x, y@ = polynomials over %$\gf{2^8}$%
64 * @unsigned m@ = modulus
66 * Returns: The product of two polynomials.
68 * Use: Computes a product of polynomials, quite slowly.
71 static unsigned mul(unsigned x
, unsigned y
, unsigned m
)
76 for (i
= 0; i
< 8; i
++) {
92 * This is built from inversion in the multiplicative group of
93 * %$\gf{2^8}[x]/(p(x))$%, where %$p(x) = x^8 + x^4 + x^3 + x + 1$%, followed
94 * by an affine transformation treating inputs as vectors over %$\gf{2}$%.
95 * The result is a horrible function.
97 * The inversion is done slightly sneakily, by building log and antilog
98 * tables. Let %$a$% be an element of the finite field. If the inverse of
99 * %$a$% is %$a^{-1}$%, then %$\log a a^{-1} = 0$%. Hence
100 * %$\log a = -\log a^{-1}$%. This saves fiddling about with Euclidean
106 static void sbox(void)
108 octet log
[256], alog
[256];
113 /* --- Find a suitable generator, and build log tables --- */
116 for (g
= 2; g
< 256; g
++) {
118 for (i
= 0; i
< 256; i
++) {
121 x
= mul(x
, g
, S_MOD
);
122 if (x
== 1 && i
!= 254)
128 fprintf(stderr
, "couldn't find generator\n");
132 /* --- Now grind through and do the affine transform --- *
134 * The matrix multiply is an AND and a parity op. The add is an XOR.
137 for (i
= 0; i
< 256; i
++) {
140 unsigned v
= i ? alog
[255 - log
[i
]] : 0;
142 assert(i
== 0 || mul(i
, v
, S_MOD
) == 1);
145 for (j
= 0; j
< 8; j
++) {
151 x
= (x
<< 1) | (r
& 1);
162 * Construct the t tables for doing the round function efficiently.
165 static void tbox(void)
169 for (i
= 0; i
< 256; i
++) {
173 /* --- Build a forwards t-box entry --- */
176 b
= a
<< 1; if (b
& 0x100) b
^= S_MOD
;
178 w
= (b
<< 0) | (a
<< 8) | (a
<< 16) | (c
<< 24);
180 t
[1][i
] = ROL32(w
, 8);
181 t
[2][i
] = ROL32(w
, 16);
182 t
[3][i
] = ROL32(w
, 24);
184 /* --- Build a backwards t-box entry --- */
186 a
= mul(si
[i
], 0x0e, S_MOD
);
187 b
= mul(si
[i
], 0x09, S_MOD
);
188 c
= mul(si
[i
], 0x0d, S_MOD
);
189 d
= mul(si
[i
], 0x0b, S_MOD
);
190 w
= (a
<< 0) | (b
<< 8) | (c
<< 16) | (d
<< 24);
192 ti
[1][i
] = ROL32(w
, 8);
193 ti
[2][i
] = ROL32(w
, 16);
194 ti
[3][i
] = ROL32(w
, 24);
200 * Construct the tables for performing the decryption key schedule.
203 static void ubox(void)
207 for (i
= 0; i
< 256; i
++) {
210 a
= mul(i
, 0x0e, S_MOD
);
211 b
= mul(i
, 0x09, S_MOD
);
212 c
= mul(i
, 0x0d, S_MOD
);
213 d
= mul(i
, 0x0b, S_MOD
);
214 w
= (a
<< 0) | (b
<< 8) | (c
<< 16) | (d
<< 24);
216 u
[1][i
] = ROL32(w
, 8);
217 u
[2][i
] = ROL32(w
, 16);
218 u
[3][i
] = ROL32(w
, 24);
222 /* --- Round constants --- */
224 static void rcon(void)
229 for (i
= 0; i
< sizeof(rc
); i
++) {
246 * Rijndael tables [generated]\n\
249 #ifndef CATACOMB_RIJNDAEL_TAB_H\n\
250 #define CATACOMB_RIJNDAEL_TAB_H\n\
253 /* --- Write out the S-box --- */
257 /* --- The byte substitution and its inverse --- */\n\
259 #define RIJNDAEL_S { \\\n\
261 for (i
= 0; i
< 256; i
++) {
262 printf("0x%02x", s
[i
]);
264 fputs(" \\\n}\n\n", stdout
);
266 fputs(", \\\n ", stdout
);
272 #define RIJNDAEL_SI { \\\n\
274 for (i
= 0; i
< 256; i
++) {
275 printf("0x%02x", si
[i
]);
277 fputs(" \\\n}\n\n", stdout
);
279 fputs(", \\\n ", stdout
);
284 /* --- Write out the big t tables --- */
288 /* --- The big round tables --- */\n\
290 #define RIJNDAEL_T { \\\n\
292 for (j
= 0; j
< 4; j
++) {
293 for (i
= 0; i
< 256; i
++) {
294 printf("0x%08lx", (unsigned long)t
[j
][i
]);
297 fputs(" } \\\n}\n\n", stdout
);
302 } else if (i
% 4 == 3)
303 fputs(", \\\n ", stdout
);
310 #define RIJNDAEL_TI { \\\n\
312 for (j
= 0; j
< 4; j
++) {
313 for (i
= 0; i
< 256; i
++) {
314 printf("0x%08lx", (unsigned long)ti
[j
][i
]);
317 fputs(" } \\\n}\n\n", stdout
);
322 } else if (i
% 4 == 3)
323 fputs(", \\\n ", stdout
);
329 /* --- Write out the big u tables --- */
333 /* --- The decryption key schedule tables --- */\n\
335 #define RIJNDAEL_U { \\\n\
337 for (j
= 0; j
< 4; j
++) {
338 for (i
= 0; i
< 256; i
++) {
339 printf("0x%08lx", (unsigned long)u
[j
][i
]);
342 fputs(" } \\\n}\n\n", stdout
);
347 } else if (i
% 4 == 3)
348 fputs(", \\\n ", stdout
);
354 /* --- Round constants --- */
358 /* --- The round constants --- */\n\
360 #define RIJNDAEL_RCON { \\\n\
362 for (i
= 0; i
< sizeof(rc
); i
++) {
363 printf("0x%02x", rc
[i
]);
364 if (i
== sizeof(rc
) - 1)
365 fputs(" \\\n}\n\n", stdout
);
367 fputs(", \\\n ", stdout
);
376 if (fclose(stdout
)) {
377 fprintf(stderr
, "error writing data\n");
384 /*----- That's all, folks -------------------------------------------------*/