X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/83c017f3fb115a67734e94dca02095b62cae5e80..8dd8c294e9f330eb6b975c2b96cf9bbfcd087e5e:/twofish-mktab.c diff --git a/twofish-mktab.c b/twofish-mktab.c new file mode 100644 index 0000000..5a649f3 --- /dev/null +++ b/twofish-mktab.c @@ -0,0 +1,421 @@ +/* -*-c-*- + * + * $Id: twofish-mktab.c,v 1.1 2000/06/17 12:10:17 mdw Exp $ + * + * Build constant tables for Twofish + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: twofish-mktab.c,v $ + * Revision 1.1 2000/06/17 12:10:17 mdw + * New cipher. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include + +#include + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct { octet t[4][16]; } t_tab; +typedef struct { octet q[256]; } q_tab; + +/*----- Various Twofish tables --------------------------------------------*/ + +/* --- The t-tables --- */ + +static const t_tab qt0 = {{ + { 0x8, 0x1, 0x7, 0xd, 0x6, 0xf, 0x3, 0x2, + 0x0, 0xb, 0x5, 0x9, 0xe, 0xc, 0xa, 0x4 }, + { 0xe, 0xc, 0xb, 0x8, 0x1, 0x2, 0x3, 0x5, + 0xf, 0x4, 0xa, 0x6, 0x7, 0x0, 0x9, 0xd }, + { 0xb, 0xa, 0x5, 0xe, 0x6, 0xd, 0x9, 0x0, + 0xc, 0x8, 0xf, 0x3, 0x2, 0x4, 0x7, 0x1 }, + { 0xd, 0x7, 0xf, 0x4, 0x1, 0x2, 0x6, 0xe, + 0x9, 0xb, 0x3, 0x0, 0x8, 0x5, 0xc, 0xa } +}}; + +static const t_tab qt1 = {{ + { 0x2, 0x8, 0xb, 0xd, 0xf, 0x7, 0x6, 0xe, + 0x3, 0x1, 0x9, 0x4, 0x0, 0xa, 0xc, 0x5 }, + { 0x1, 0xe, 0x2, 0xb, 0x4, 0xc, 0x3, 0x7, + 0x6, 0xd, 0xa, 0x5, 0xf, 0x9, 0x0, 0x8 }, + { 0x4, 0xc, 0x7, 0x5, 0x1, 0x6, 0x9, 0xa, + 0x0, 0xe, 0xd, 0x8, 0x2, 0xb, 0x3, 0xf }, + { 0xb, 0x9, 0x5, 0x1, 0xc, 0x3, 0xd, 0xe, + 0x6, 0x4, 0x7, 0xf, 0x2, 0x0, 0x8, 0xa } +}}; + +static q_tab q0, q1; + +/* --- The MDS and Reed-Solomon matrices --- */ + +static const octet mds[16] = { + 0x01, 0xef, 0x5b, 0x5b, + 0x5b, 0xef, 0xef, 0x01, + 0xef, 0x5b, 0x01, 0xef, + 0xef, 0x01, 0xef, 0x5b +}; + +static const octet rs[32] = { + 0x01, 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e, + 0xa4, 0x56, 0x82, 0xf3, 0x1e, 0xc6, 0x68, 0xe5, + 0x02, 0xa1, 0xfc, 0xc1, 0x47, 0xae, 0x3d, 0x19, + 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e, 0x03 +}; + +/*----- Magic macros ------------------------------------------------------*/ + +#define ROR4(x) ((((x) >> 1) | ((x) << 3)) & 15) + +/*----- Building and printing @q@ tables ----------------------------------*/ + +/* --- @mkq@ --- * + * + * Arguments: @q_tab *q@ = pointer to output @q@ table + * @const t_tab *t@ = pointer to input @t@ table + * @const char *name@ = name of @q@ table + * + * Returns: --- + * + * Use: Constructs a 256-entry @q@-table. + */ + +static void mkq(q_tab *q, const t_tab *t, const char *name) +{ + int i; + int ok = 1; + + /* --- Ensure the t-table is well-formed --- */ + + for (i = 0; i < 4; i++) { + octet f[16] = { 0 }; + int j; + + for (j = 0; j < 16; j++) { + if (f[t->t[i][j]]) { + fprintf(stderr, "duplicate %i in %s[%i] (col %i and %i)\n", + t->t[i][j], name, i, j, f[t->t[i][j]]); + ok = 0; + } + f[t->t[i][j]] = j; + } + } + + if (!ok) + exit(EXIT_FAILURE); + + /* --- Construct the @q@ table --- */ + + for (i = 0; i < 256; i++) { + int a = i >> 4, b = i & 15; + int aa = t->t[0][a ^ b], bb = t->t[1][a ^ ((a << 3) & 15) ^ ROR4(b)]; + a = t->t[2][aa ^ bb], b = t->t[3][aa ^ ((aa << 3) & 15) ^ ROR4(bb)]; + q->q[i] = a | (b << 4); + } + + /* Consider testing @q@ for linear and differential properties here */ +} + +/* --- @printq@ --- * + * + * Arguments: @const q_tab *t@ = pointer to table + * @const char *name@ = pointer to table name + * + * Returns: --- + * + * Use: Prints a q table. + */ + +static void printq(const q_tab *q, const char *name) +{ + int i; + int j; + + printf("\ +#define TWOFISH_%s { \\\n\ + ", name); + j = 0; + for (i = 0; i < 256; i++) { + printf("0x%02x", q->q[i]); + j = (j + 1) & 7; + if (i == 255) + fputs(" \\\n}\n\n", stdout); + else if (j == 0) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } +} + +/*----- GF(2^8) arithmetic ------------------------------------------------*/ + +#define MDS_MOD 0x169 +#define RS_MOD 0x14d + +/* --- @mul@ --- * + * + * Arguments: @unsigned x, y@ = polynomials over %$\mathrm{GF}(2^8)$% + * @unsigned m@ = modulus + * + * Returns: The product of two polynomials. + * + * Use: Computes a product of polynomials, quite slowly. + */ + +static unsigned mul(unsigned x, unsigned y, unsigned m) +{ + unsigned a = 0; + unsigned i; + + for (i = 0; i < 8; i++) { + if (y & 1) + a ^= x; + y >>= 1; + x <<= 1; + if (x & 0x100) + x ^= m; + } + + return (a); +} + +/* --- @mmul@ --- * + * + * Arguments: @octet *d@ = destination vector + * @const octet *p@ = matrix of bytes + * @const octet *q@ = vector from somewhere else + * @size_t r@ = size of destination or number of rows in matrix + * @size_t n@ = length of row and vector + * @unsigned m@ = modulus polynomial + * + * Returns: --- + * + * Use: Computes an inner product of matrices over the finite field + * %$\mathrm{GF}(2^8)[x]/m(x)$%. This isn't particularly rapid. + */ + +static void mmul(octet *d, const octet *p, const octet *q, + size_t r, size_t n, unsigned m) +{ + while (r) { + const octet *qq = q; + unsigned a = 0; + unsigned i; + + for (i = 0; i < n; i++) + a ^= mul(*p++, *qq++, m); + *d++ = a; + r--; + } +} + +/* --- @qrds@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Prints the MDS/q table. + */ + +static void qmds(void) +{ + uint32 t[4][256]; + int i, j; + static const q_tab *q[4] = { &q1, &q0, &q1, &q0 }; + + for (i = 0; i < 4; i++) { + octet in[4] = { 0, 0, 0, 0 }; + octet out[4]; + + for (j = 0; j < 256; j++) { + in[i] = q[i]->q[j]; + mmul(out, mds, in, 4, 4, MDS_MOD); + t[i][j] = LOAD32_L(out); + } + } + + puts("\ +/* --- Expanded MDS tables --- *\n\ + *\n\ + * The table contains output vectors for computing the result of pushing\n\ + * bytes through appropriate @q@ tables and the MDS matrix.\n\ + */\n\ +\n\ +#define TWOFISH_QMDS { \\"); + for (i = 0; i < 4; i++) { + fputs(" { ", stdout); + for (j = 0; j < 256; j++) { + printf("0x%08lx", (unsigned long)t[i][j]); + if (j == 255) { + if (i == 3) + puts(" } \\\n}"); + else + puts(" }, \\\n\ + \\"); + } else if (j % 4 == 3) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + } + + putchar('\n'); +} + +/* --- @rslog@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Produces the log and antilog tables for doing the RS + * arithmetic efficiently. + */ + +static void rslog(void) +{ + octet rslog[256]; + octet rsexp[256]; + + unsigned x = 1; + unsigned i; + + rslog[0] = 0; + for (i = 0; i < 256; i++) { + rslog[x] = i; + rsexp[i] = x; + x <<= 1; + if (x & 0x100) + x ^= RS_MOD; + } + + x = 0; + for (i = 0; i < 32; i++) { + if (rslog[rs[i]] > x) + x = rslog[rs[i]]; + } + + fputs("\ +/* --- Reed-Solomon log tables --- *\n\ + *\n\ + * The Reed-Solomon multiplies are accelerated by using log tables.\n\ + */\n\ +\n\ +#define TWOFISH_RSLOG { \\\n\ + ", stdout); + + for (i = 0; i < 256; i++) { + printf("0x%02x", rslog[i]); + if (i == 255) + puts(" \\\n}\n"); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + + fputs("\ +#define TWOFISH_RSEXP { \\\n\ + ", stdout); + + for (i = 0; i < 255 + x + 1; i++) { + printf("0x%02x", rsexp[i % 255]); + if (i == 255 + x) + puts(" \\\n}\n"); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + + fputs("\ +/* --- Reed-Solomon matrix with log entries --- */\n\ +\n\ +#define TWOFISH_RS { \\\n\ + ", stdout); + + for (i = 0; i < 32; i++) { + printf("0x%02x", rslog[rs[i]]); + if (i == 31) + puts(" \\\n}\n"); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } +} + +/*----- Main program ------------------------------------------------------*/ + +/* --- @main@ --- */ + +int main(void) +{ + fputs("\ +/* -*-c-*- + * + * Twofish q tables [generated]\n\ + */ + +#ifndef CATACOMB_TWOFISH_TAB_H +#define CATACOMB_TWOFISH_TAB_H + +", stdout); + + /* --- The q tables --- */ + + puts("\ +/* --- Precomputed @q@ tables --- */\n\ +"); + mkq(&q0, &qt0, "qt0"); + mkq(&q1, &qt1, "qt1"); + printq(&q0, "Q0"); + printq(&q1, "Q1"); + + /* --- The MDS/q tables --- */ + + qmds(); + rslog(); + + /* --- Done --- */ + + puts("#endif"); + + if (fclose(stdout)) { + fprintf(stderr, "error writing data\n"); + exit(EXIT_FAILURE); + } + + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/