Commit | Line | Data |
---|---|---|
8dd8c294 | 1 | /* -*-c-*- |
8dd8c294 | 2 | * |
3 | * Build constant tables for Twofish | |
4 | * | |
5 | * (c) 2000 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
8dd8c294 | 9 | * |
10 | * This file is part of Catacomb. | |
11 | * | |
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. | |
45c0fd36 | 16 | * |
8dd8c294 | 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. | |
45c0fd36 | 21 | * |
8dd8c294 | 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, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
8dd8c294 | 28 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
30 | #include <stdio.h> | |
31 | #include <stdlib.h> | |
32 | ||
33 | #include <mLib/bits.h> | |
34 | ||
35 | /*----- Data structures ---------------------------------------------------*/ | |
36 | ||
37 | typedef struct { octet t[4][16]; } t_tab; | |
38 | typedef struct { octet q[256]; } q_tab; | |
39 | ||
40 | /*----- Various Twofish tables --------------------------------------------*/ | |
41 | ||
42 | /* --- The t-tables --- */ | |
43 | ||
44 | static const t_tab qt0 = {{ | |
45 | { 0x8, 0x1, 0x7, 0xd, 0x6, 0xf, 0x3, 0x2, | |
46 | 0x0, 0xb, 0x5, 0x9, 0xe, 0xc, 0xa, 0x4 }, | |
47 | { 0xe, 0xc, 0xb, 0x8, 0x1, 0x2, 0x3, 0x5, | |
48 | 0xf, 0x4, 0xa, 0x6, 0x7, 0x0, 0x9, 0xd }, | |
49 | { 0xb, 0xa, 0x5, 0xe, 0x6, 0xd, 0x9, 0x0, | |
50 | 0xc, 0x8, 0xf, 0x3, 0x2, 0x4, 0x7, 0x1 }, | |
51 | { 0xd, 0x7, 0xf, 0x4, 0x1, 0x2, 0x6, 0xe, | |
52 | 0x9, 0xb, 0x3, 0x0, 0x8, 0x5, 0xc, 0xa } | |
53 | }}; | |
54 | ||
55 | static const t_tab qt1 = {{ | |
56 | { 0x2, 0x8, 0xb, 0xd, 0xf, 0x7, 0x6, 0xe, | |
57 | 0x3, 0x1, 0x9, 0x4, 0x0, 0xa, 0xc, 0x5 }, | |
58 | { 0x1, 0xe, 0x2, 0xb, 0x4, 0xc, 0x3, 0x7, | |
59 | 0x6, 0xd, 0xa, 0x5, 0xf, 0x9, 0x0, 0x8 }, | |
60 | { 0x4, 0xc, 0x7, 0x5, 0x1, 0x6, 0x9, 0xa, | |
61 | 0x0, 0xe, 0xd, 0x8, 0x2, 0xb, 0x3, 0xf }, | |
62 | { 0xb, 0x9, 0x5, 0x1, 0xc, 0x3, 0xd, 0xe, | |
63 | 0x6, 0x4, 0x7, 0xf, 0x2, 0x0, 0x8, 0xa } | |
64 | }}; | |
65 | ||
66 | static q_tab q0, q1; | |
67 | ||
68 | /* --- The MDS and Reed-Solomon matrices --- */ | |
69 | ||
70 | static const octet mds[16] = { | |
71 | 0x01, 0xef, 0x5b, 0x5b, | |
72 | 0x5b, 0xef, 0xef, 0x01, | |
73 | 0xef, 0x5b, 0x01, 0xef, | |
74 | 0xef, 0x01, 0xef, 0x5b | |
75 | }; | |
76 | ||
77 | static const octet rs[32] = { | |
78 | 0x01, 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e, | |
79 | 0xa4, 0x56, 0x82, 0xf3, 0x1e, 0xc6, 0x68, 0xe5, | |
80 | 0x02, 0xa1, 0xfc, 0xc1, 0x47, 0xae, 0x3d, 0x19, | |
81 | 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e, 0x03 | |
82 | }; | |
83 | ||
84 | /*----- Magic macros ------------------------------------------------------*/ | |
85 | ||
86 | #define ROR4(x) ((((x) >> 1) | ((x) << 3)) & 15) | |
87 | ||
88 | /*----- Building and printing @q@ tables ----------------------------------*/ | |
89 | ||
90 | /* --- @mkq@ --- * | |
91 | * | |
92 | * Arguments: @q_tab *q@ = pointer to output @q@ table | |
93 | * @const t_tab *t@ = pointer to input @t@ table | |
94 | * @const char *name@ = name of @q@ table | |
95 | * | |
96 | * Returns: --- | |
97 | * | |
98 | * Use: Constructs a 256-entry @q@-table. | |
99 | */ | |
100 | ||
101 | static void mkq(q_tab *q, const t_tab *t, const char *name) | |
102 | { | |
103 | int i; | |
104 | int ok = 1; | |
105 | ||
106 | /* --- Ensure the t-table is well-formed --- */ | |
107 | ||
108 | for (i = 0; i < 4; i++) { | |
109 | octet f[16] = { 0 }; | |
110 | int j; | |
111 | ||
112 | for (j = 0; j < 16; j++) { | |
113 | if (f[t->t[i][j]]) { | |
114 | fprintf(stderr, "duplicate %i in %s[%i] (col %i and %i)\n", | |
115 | t->t[i][j], name, i, j, f[t->t[i][j]]); | |
116 | ok = 0; | |
117 | } | |
118 | f[t->t[i][j]] = j; | |
119 | } | |
120 | } | |
121 | ||
122 | if (!ok) | |
123 | exit(EXIT_FAILURE); | |
124 | ||
125 | /* --- Construct the @q@ table --- */ | |
126 | ||
127 | for (i = 0; i < 256; i++) { | |
128 | int a = i >> 4, b = i & 15; | |
129 | int aa = t->t[0][a ^ b], bb = t->t[1][a ^ ((a << 3) & 15) ^ ROR4(b)]; | |
130 | a = t->t[2][aa ^ bb], b = t->t[3][aa ^ ((aa << 3) & 15) ^ ROR4(bb)]; | |
131 | q->q[i] = a | (b << 4); | |
132 | } | |
133 | ||
134 | /* Consider testing @q@ for linear and differential properties here */ | |
135 | } | |
136 | ||
137 | /* --- @printq@ --- * | |
138 | * | |
139 | * Arguments: @const q_tab *t@ = pointer to table | |
140 | * @const char *name@ = pointer to table name | |
141 | * | |
142 | * Returns: --- | |
143 | * | |
144 | * Use: Prints a q table. | |
145 | */ | |
146 | ||
147 | static void printq(const q_tab *q, const char *name) | |
148 | { | |
149 | int i; | |
150 | int j; | |
151 | ||
152 | printf("\ | |
e5b61a8d | 153 | const octet twofish_%s[256] = {\n\ |
8dd8c294 | 154 | ", name); |
155 | j = 0; | |
156 | for (i = 0; i < 256; i++) { | |
157 | printf("0x%02x", q->q[i]); | |
158 | j = (j + 1) & 7; | |
159 | if (i == 255) | |
e5b61a8d | 160 | fputs("\n};\n\n", stdout); |
8dd8c294 | 161 | else if (j == 0) |
e5b61a8d | 162 | fputs(",\n ", stdout); |
8dd8c294 | 163 | else |
164 | fputs(", ", stdout); | |
165 | } | |
166 | } | |
167 | ||
4d47e157 | 168 | /*----- %$\gf{2^8}$% arithmetic -------------------------------------------*/ |
8dd8c294 | 169 | |
170 | #define MDS_MOD 0x169 | |
171 | #define RS_MOD 0x14d | |
172 | ||
173 | /* --- @mul@ --- * | |
174 | * | |
4d47e157 | 175 | * Arguments: @unsigned x, y@ = polynomials over %$\gf{2^8}$% |
8dd8c294 | 176 | * @unsigned m@ = modulus |
177 | * | |
178 | * Returns: The product of two polynomials. | |
179 | * | |
180 | * Use: Computes a product of polynomials, quite slowly. | |
181 | */ | |
182 | ||
183 | static unsigned mul(unsigned x, unsigned y, unsigned m) | |
184 | { | |
185 | unsigned a = 0; | |
186 | unsigned i; | |
187 | ||
188 | for (i = 0; i < 8; i++) { | |
189 | if (y & 1) | |
190 | a ^= x; | |
191 | y >>= 1; | |
192 | x <<= 1; | |
193 | if (x & 0x100) | |
194 | x ^= m; | |
195 | } | |
196 | ||
197 | return (a); | |
198 | } | |
199 | ||
200 | /* --- @mmul@ --- * | |
201 | * | |
202 | * Arguments: @octet *d@ = destination vector | |
203 | * @const octet *p@ = matrix of bytes | |
204 | * @const octet *q@ = vector from somewhere else | |
205 | * @size_t r@ = size of destination or number of rows in matrix | |
206 | * @size_t n@ = length of row and vector | |
207 | * @unsigned m@ = modulus polynomial | |
208 | * | |
209 | * Returns: --- | |
210 | * | |
211 | * Use: Computes an inner product of matrices over the finite field | |
4d47e157 | 212 | * %$\gf{2^8}[x]/(m(x))$%. This isn't particularly rapid. |
8dd8c294 | 213 | */ |
214 | ||
215 | static void mmul(octet *d, const octet *p, const octet *q, | |
216 | size_t r, size_t n, unsigned m) | |
217 | { | |
218 | while (r) { | |
219 | const octet *qq = q; | |
220 | unsigned a = 0; | |
221 | unsigned i; | |
222 | ||
223 | for (i = 0; i < n; i++) | |
224 | a ^= mul(*p++, *qq++, m); | |
225 | *d++ = a; | |
226 | r--; | |
227 | } | |
228 | } | |
229 | ||
230 | /* --- @qrds@ --- * | |
231 | * | |
232 | * Arguments: --- | |
233 | * | |
234 | * Returns: --- | |
235 | * | |
236 | * Use: Prints the MDS/q table. | |
237 | */ | |
238 | ||
239 | static void qmds(void) | |
240 | { | |
241 | uint32 t[4][256]; | |
242 | int i, j; | |
243 | static const q_tab *q[4] = { &q1, &q0, &q1, &q0 }; | |
244 | ||
245 | for (i = 0; i < 4; i++) { | |
246 | octet in[4] = { 0, 0, 0, 0 }; | |
247 | octet out[4]; | |
248 | ||
249 | for (j = 0; j < 256; j++) { | |
250 | in[i] = q[i]->q[j]; | |
251 | mmul(out, mds, in, 4, 4, MDS_MOD); | |
252 | t[i][j] = LOAD32_L(out); | |
253 | } | |
254 | } | |
255 | ||
256 | puts("\ | |
257 | /* --- Expanded MDS tables --- *\n\ | |
258 | *\n\ | |
259 | * The table contains output vectors for computing the result of pushing\n\ | |
260 | * bytes through appropriate @q@ tables and the MDS matrix.\n\ | |
261 | */\n\ | |
262 | \n\ | |
e5b61a8d MW |
263 | const uint32 twofish_qmds[4][256] = {\ |
264 | "); | |
8dd8c294 | 265 | for (i = 0; i < 4; i++) { |
266 | fputs(" { ", stdout); | |
267 | for (j = 0; j < 256; j++) { | |
268 | printf("0x%08lx", (unsigned long)t[i][j]); | |
269 | if (j == 255) { | |
270 | if (i == 3) | |
e5b61a8d | 271 | puts(" }\n};"); |
8dd8c294 | 272 | else |
e5b61a8d | 273 | puts(" },\n"); |
8dd8c294 | 274 | } else if (j % 4 == 3) |
e5b61a8d | 275 | fputs(",\n ", stdout); |
8dd8c294 | 276 | else |
277 | fputs(", ", stdout); | |
278 | } | |
279 | } | |
280 | ||
281 | putchar('\n'); | |
282 | } | |
283 | ||
284 | /* --- @rslog@ --- * | |
285 | * | |
286 | * Arguments: --- | |
287 | * | |
288 | * Returns: --- | |
289 | * | |
290 | * Use: Produces the log and antilog tables for doing the RS | |
291 | * arithmetic efficiently. | |
292 | */ | |
293 | ||
294 | static void rslog(void) | |
295 | { | |
296 | octet rslog[256]; | |
297 | octet rsexp[256]; | |
298 | ||
299 | unsigned x = 1; | |
300 | unsigned i; | |
301 | ||
302 | rslog[0] = 0; | |
a9f7f3b2 | 303 | for (i = 0; i < 255; i++) { |
8dd8c294 | 304 | rslog[x] = i; |
305 | rsexp[i] = x; | |
306 | x <<= 1; | |
307 | if (x & 0x100) | |
308 | x ^= RS_MOD; | |
309 | } | |
310 | ||
311 | x = 0; | |
312 | for (i = 0; i < 32; i++) { | |
313 | if (rslog[rs[i]] > x) | |
314 | x = rslog[rs[i]]; | |
315 | } | |
316 | ||
317 | fputs("\ | |
318 | /* --- Reed-Solomon log tables --- *\n\ | |
319 | *\n\ | |
320 | * The Reed-Solomon multiplies are accelerated by using log tables.\n\ | |
321 | */\n\ | |
322 | \n\ | |
e5b61a8d | 323 | const octet twofish_rslog[256] = {\n\ |
8dd8c294 | 324 | ", stdout); |
325 | ||
326 | for (i = 0; i < 256; i++) { | |
327 | printf("0x%02x", rslog[i]); | |
328 | if (i == 255) | |
e5b61a8d | 329 | puts("\n};\n"); |
8dd8c294 | 330 | else if (i % 8 == 7) |
e5b61a8d | 331 | fputs(",\n ", stdout); |
8dd8c294 | 332 | else |
333 | fputs(", ", stdout); | |
334 | } | |
335 | ||
e5b61a8d MW |
336 | printf("\ |
337 | const octet twofish_rsexp[%d] = {\n\ | |
338 | ", 255 + x + 1); | |
8dd8c294 | 339 | |
340 | for (i = 0; i < 255 + x + 1; i++) { | |
341 | printf("0x%02x", rsexp[i % 255]); | |
342 | if (i == 255 + x) | |
e5b61a8d | 343 | puts("\n};\n"); |
8dd8c294 | 344 | else if (i % 8 == 7) |
e5b61a8d | 345 | fputs(",\n ", stdout); |
8dd8c294 | 346 | else |
347 | fputs(", ", stdout); | |
348 | } | |
349 | ||
350 | fputs("\ | |
351 | /* --- Reed-Solomon matrix with log entries --- */\n\ | |
352 | \n\ | |
e5b61a8d | 353 | const octet twofish_rs[32] = {\n\ |
8dd8c294 | 354 | ", stdout); |
355 | ||
356 | for (i = 0; i < 32; i++) { | |
357 | printf("0x%02x", rslog[rs[i]]); | |
358 | if (i == 31) | |
e5b61a8d | 359 | puts("\n};"); |
8dd8c294 | 360 | else if (i % 8 == 7) |
e5b61a8d | 361 | fputs(",\n ", stdout); |
8dd8c294 | 362 | else |
363 | fputs(", ", stdout); | |
364 | } | |
365 | } | |
366 | ||
367 | /*----- Main program ------------------------------------------------------*/ | |
368 | ||
369 | /* --- @main@ --- */ | |
370 | ||
371 | int main(void) | |
372 | { | |
373 | fputs("\ | |
5292d76e | 374 | /* -*-c-*-\n\ |
375 | *\n\ | |
8dd8c294 | 376 | * Twofish q tables [generated]\n\ |
5292d76e | 377 | */\n\ |
378 | \n\ | |
e5b61a8d | 379 | #include <mLib/bits.h>\n\ |
5292d76e | 380 | \n\ |
8dd8c294 | 381 | ", stdout); |
382 | ||
383 | /* --- The q tables --- */ | |
384 | ||
385 | puts("\ | |
386 | /* --- Precomputed @q@ tables --- */\n\ | |
387 | "); | |
388 | mkq(&q0, &qt0, "qt0"); | |
389 | mkq(&q1, &qt1, "qt1"); | |
e5b61a8d MW |
390 | printq(&q0, "q0"); |
391 | printq(&q1, "q1"); | |
8dd8c294 | 392 | |
393 | /* --- The MDS/q tables --- */ | |
394 | ||
395 | qmds(); | |
396 | rslog(); | |
397 | ||
398 | /* --- Done --- */ | |
399 | ||
8dd8c294 | 400 | if (fclose(stdout)) { |
401 | fprintf(stderr, "error writing data\n"); | |
402 | exit(EXIT_FAILURE); | |
403 | } | |
404 | ||
405 | return (0); | |
406 | } | |
407 | ||
408 | /*----- That's all, folks -------------------------------------------------*/ |