3 * Build precomputed tables for the Square 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^7+x^6+x^5+x^4+x^2+1$%,
78 * followed by an affine transformation treating inputs as vectors over
79 * %$\gf{2}$%. 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
++) {
123 octet m
[] = { 0xd6, 0x7b, 0x3d, 0x1f, 0x0f, 0x05, 0x03, 0x01 };
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);
145 * Construct the t tables for doing the round function efficiently.
148 static void tbox(void)
152 for (i
= 0; i
< 256; i
++) {
156 /* --- Build a forwards t-box entry --- */
159 b
= a
<< 1; if (b
& 0x100) b
^= S_MOD
;
161 w
= (b
<< 0) | (a
<< 8) | (a
<< 16) | (c
<< 24);
163 t
[1][i
] = ROL32(w
, 8);
164 t
[2][i
] = ROL32(w
, 16);
165 t
[3][i
] = ROL32(w
, 24);
167 /* --- Build a backwards t-box entry --- */
169 a
= mul(si
[i
], 0x0e, S_MOD
);
170 b
= mul(si
[i
], 0x09, S_MOD
);
171 c
= mul(si
[i
], 0x0d, S_MOD
);
172 d
= mul(si
[i
], 0x0b, S_MOD
);
173 w
= (a
<< 0) | (b
<< 8) | (c
<< 16) | (d
<< 24);
175 ti
[1][i
] = ROL32(w
, 8);
176 ti
[2][i
] = ROL32(w
, 16);
177 ti
[3][i
] = ROL32(w
, 24);
183 * Construct the tables for performing the key schedule.
186 static void ubox(void)
190 for (i
= 0; i
< 256; i
++) {
194 b
= a
<< 1; if (b
& 0x100) b
^= S_MOD
;
196 w
= (b
<< 0) | (a
<< 8) | (a
<< 16) | (c
<< 24);
198 u
[1][i
] = ROL32(w
, 8);
199 u
[2][i
] = ROL32(w
, 16);
200 u
[3][i
] = ROL32(w
, 24);
204 /* --- Round constants --- */
211 for (i
= 0; i
< sizeof(rc
); i
++) {
228 * Square tables [generated]\n\
231 #include <mLib/bits.h>\n\
235 /* --- Write out the S-box --- */
239 /* --- The byte substitution and its inverse --- */\n\
241 const octet square_s[256] = {\n\
243 for (i
= 0; i
< 256; i
++) {
244 printf("0x%02x", s
[i
]);
246 fputs("\n};\n\n", stdout
);
248 fputs(",\n ", stdout
);
254 const octet square_si[256] = {\n\
256 for (i
= 0; i
< 256; i
++) {
257 printf("0x%02x", si
[i
]);
259 fputs("\n};\n\n", stdout
);
261 fputs(",\n ", stdout
);
266 /* --- Write out the big t tables --- */
270 /* --- The big round tables --- */\n\
272 const uint32 square_t[4][256] = {\n\
274 for (j
= 0; j
< 4; j
++) {
275 for (i
= 0; i
< 256; i
++) {
276 printf("0x%08x", t
[j
][i
]);
279 fputs(" }\n};\n\n", stdout
);
281 fputs(" },\n\n { ", stdout
);
282 } else if (i
% 4 == 3)
283 fputs(",\n ", stdout
);
290 const uint32 square_ti[4][256] = {\n\
292 for (j
= 0; j
< 4; j
++) {
293 for (i
= 0; i
< 256; i
++) {
294 printf("0x%08x", ti
[j
][i
]);
297 fputs(" }\n};\n\n", stdout
);
299 fputs(" },\n\n { ", stdout
);
300 } else if (i
% 4 == 3)
301 fputs(",\n ", stdout
);
307 /* --- Write out the big u tables --- */
311 /* --- The key schedule tables --- */\n\
313 const uint32 square_u[4][256] = {\n\
315 for (j
= 0; j
< 4; j
++) {
316 for (i
= 0; i
< 256; i
++) {
317 printf("0x%08x", u
[j
][i
]);
320 fputs(" }\n};\n\n", stdout
);
322 fputs(" },\n\n { ", stdout
);
323 } else if (i
% 4 == 3)
324 fputs(",\n ", stdout
);
330 /* --- Round constants --- */
334 /* --- The round constants --- */\n\
336 const octet square_rcon[32] = {\n\
338 for (i
= 0; i
< sizeof(rc
); i
++) {
339 printf("0x%02x", rc
[i
]);
340 if (i
== sizeof(rc
) - 1)
341 fputs("\n};\n", stdout
);
343 fputs(",\n ", stdout
);
350 if (fclose(stdout
)) {
351 fprintf(stderr
, "error writing data\n");
358 /*----- That's all, folks -------------------------------------------------*/