3 * $Id: square-mktab.c,v 1.3 2004/04/08 01:36:15 mdw Exp $
5 * Build precomputed tables for the Square 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 /*----- Header files ------------------------------------------------------*/
36 #include <mLib/bits.h>
38 /*----- Magic variables ---------------------------------------------------*/
40 static octet s
[256], si
[256];
41 static uint32 t
[4][256], ti
[4][256];
42 static uint32 u
[4][256];
45 /*----- Main code ---------------------------------------------------------*/
49 * Arguments: @unsigned x, y@ = polynomials over %$\gf{2^8}$%
50 * @unsigned m@ = modulus
52 * Returns: The product of two polynomials.
54 * Use: Computes a product of polynomials, quite slowly.
57 static unsigned mul(unsigned x
, unsigned y
, unsigned m
)
62 for (i
= 0; i
< 8; i
++) {
78 * This is built from inversion in the multiplicative group of
79 * %$\gf{2^8}[x]/(p(x))$%, where %$p(x) = x^8+x^7+x^6+x^5+x^4+x^2+1$%,
80 * followed by an affine transformation treating inputs as vectors over
81 * %$\gf{2}$%. The result is a horrible function.
83 * The inversion is done slightly sneakily, by building log and antilog
84 * tables. Let %$a$% be an element of the finite field. If the inverse of
85 * %$a$% is %$a^{-1}$%, then %$\log a a^{-1} = 0$%. Hence
86 * %$\log a = -\log a^{-1}$%. This saves fiddling about with Euclidean
92 static void sbox(void)
94 octet log
[256], alog
[256];
99 /* --- Find a suitable generator, and build log tables --- */
102 for (g
= 2; g
< 256; g
++) {
104 for (i
= 0; i
< 256; i
++) {
107 x
= mul(x
, g
, S_MOD
);
108 if (x
== 1 && i
!= 254)
114 fprintf(stderr
, "couldn't find generator\n");
118 /* --- Now grind through and do the affine transform --- *
120 * The matrix multiply is an AND and a parity op. The add is an XOR.
123 for (i
= 0; i
< 256; i
++) {
125 octet m
[] = { 0xd6, 0x7b, 0x3d, 0x1f, 0x0f, 0x05, 0x03, 0x01 };
126 unsigned v
= i ? alog
[255 - log
[i
]] : 0;
128 assert(i
== 0 || mul(i
, v
, S_MOD
) == 1);
131 for (j
= 0; j
< 8; j
++) {
137 x
= (x
<< 1) | (r
& 1);
147 * Construct the t tables for doing the round function efficiently.
150 static void tbox(void)
154 for (i
= 0; i
< 256; i
++) {
158 /* --- Build a forwards t-box entry --- */
161 b
= a
<< 1; if (b
& 0x100) b
^= S_MOD
;
163 w
= (b
<< 0) | (a
<< 8) | (a
<< 16) | (c
<< 24);
165 t
[1][i
] = ROL32(w
, 8);
166 t
[2][i
] = ROL32(w
, 16);
167 t
[3][i
] = ROL32(w
, 24);
169 /* --- Build a backwards t-box entry --- */
171 a
= mul(si
[i
], 0x0e, S_MOD
);
172 b
= mul(si
[i
], 0x09, S_MOD
);
173 c
= mul(si
[i
], 0x0d, S_MOD
);
174 d
= mul(si
[i
], 0x0b, S_MOD
);
175 w
= (a
<< 0) | (b
<< 8) | (c
<< 16) | (d
<< 24);
177 ti
[1][i
] = ROL32(w
, 8);
178 ti
[2][i
] = ROL32(w
, 16);
179 ti
[3][i
] = ROL32(w
, 24);
185 * Construct the tables for performing the key schedule.
188 static void ubox(void)
192 for (i
= 0; i
< 256; i
++) {
196 b
= a
<< 1; if (b
& 0x100) b
^= S_MOD
;
198 w
= (b
<< 0) | (a
<< 8) | (a
<< 16) | (c
<< 24);
200 u
[1][i
] = ROL32(w
, 8);
201 u
[2][i
] = ROL32(w
, 16);
202 u
[3][i
] = ROL32(w
, 24);
206 /* --- Round constants --- */
213 for (i
= 0; i
< sizeof(rc
); i
++) {
230 * Square tables [generated]\n\
233 #ifndef CATACOMB_SQUARE_TAB_H\n\
234 #define CATACOMB_SQUARE_TAB_H\n\
237 /* --- Write out the S-box --- */
241 /* --- The byte substitution and its inverse --- */\n\
243 #define SQUARE_S { \\\n\
245 for (i
= 0; i
< 256; i
++) {
246 printf("0x%02x", s
[i
]);
248 fputs(" \\\n}\n\n", stdout
);
250 fputs(", \\\n ", stdout
);
256 #define SQUARE_SI { \\\n\
258 for (i
= 0; i
< 256; i
++) {
259 printf("0x%02x", si
[i
]);
261 fputs(" \\\n}\n\n", stdout
);
263 fputs(", \\\n ", stdout
);
268 /* --- Write out the big t tables --- */
272 /* --- The big round tables --- */\n\
274 #define SQUARE_T { \\\n\
276 for (j
= 0; j
< 4; j
++) {
277 for (i
= 0; i
< 256; i
++) {
278 printf("0x%08x", t
[j
][i
]);
281 fputs(" } \\\n}\n\n", stdout
);
286 } else if (i
% 4 == 3)
287 fputs(", \\\n ", stdout
);
294 #define SQUARE_TI { \\\n\
296 for (j
= 0; j
< 4; j
++) {
297 for (i
= 0; i
< 256; i
++) {
298 printf("0x%08x", ti
[j
][i
]);
301 fputs(" } \\\n}\n\n", stdout
);
306 } else if (i
% 4 == 3)
307 fputs(", \\\n ", stdout
);
313 /* --- Write out the big u tables --- */
317 /* --- The key schedule tables --- */\n\
319 #define SQUARE_U { \\\n\
321 for (j
= 0; j
< 4; j
++) {
322 for (i
= 0; i
< 256; i
++) {
323 printf("0x%08x", u
[j
][i
]);
326 fputs(" } \\\n}\n\n", stdout
);
331 } else if (i
% 4 == 3)
332 fputs(", \\\n ", stdout
);
338 /* --- Round constants --- */
342 /* --- The round constants --- */\n\
344 #define SQUARE_RCON { \\\n\
346 for (i
= 0; i
< sizeof(rc
); i
++) {
347 printf("0x%02x", rc
[i
]);
348 if (i
== sizeof(rc
) - 1)
349 fputs(" \\\n}\n\n", stdout
);
351 fputs(", \\\n ", stdout
);
360 if (fclose(stdout
)) {
361 fprintf(stderr
, "error writing data\n");
368 /*----- That's all, folks -------------------------------------------------*/