From 35682d2fa436ace2d7706fd6dcd852b497079860 Mon Sep 17 00:00:00 2001 From: mdw Date: Thu, 27 Jul 2000 18:10:27 +0000 Subject: [PATCH] Build precomuted tables for Square. --- square-mktab.c | 376 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 376 insertions(+) create mode 100644 square-mktab.c diff --git a/square-mktab.c b/square-mktab.c new file mode 100644 index 0000000..5c2610e --- /dev/null +++ b/square-mktab.c @@ -0,0 +1,376 @@ +/* -*-c-*- + * + * $Id: square-mktab.c,v 1.1 2000/07/27 18:10:27 mdw Exp $ + * + * Build precomputed tables for the Square block cipher + * + * (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: square-mktab.c,v $ + * Revision 1.1 2000/07/27 18:10:27 mdw + * Build precomuted tables for Square. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include + +/*----- Magic variables ---------------------------------------------------*/ + +static octet s[256], si[256]; +static uint32 t[4][256], ti[4][256]; +static uint32 u[4][256]; +static octet rc[32]; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @mul@ --- * + * + * Arguments: @unsigned x, y@ = polynomials over %$\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); +} + +/* --- @sbox@ --- * + * + * Build the S-box. + * + * This is built from inversion in the multiplicative group of + * %$\gf{2^8}[x]/(p(x))$%, where %$p(x) = x^8 + x^4 + x^3 + x + 1$%, followed + * by an affine transformation treating inputs as vectors over %$\gf{2}$%. + * The result is a horrible function. + * + * The inversion is done slightly sneakily, by building log and antilog + * tables. Let %$a$% be an element of the finite field. If the inverse of + * %$a$% is %$a^{-1}$%, then %$\log a a^{-1} = 0$%. Hence + * %$\log a = -\log a^{-1}$%. This saves fiddling about with Euclidean + * algorithm. + */ + +#define S_MOD 0x1f5 + +static void sbox(void) +{ + octet log[256], alog[256]; + unsigned x; + unsigned i; + unsigned g; + + /* --- Find a suitable generator, and build log tables --- */ + + log[0] = 0; + for (g = 2; g < 256; g++) { + x = 1; + for (i = 0; i < 256; i++) { + log[x] = i; + alog[i] = x; + x = mul(x, g, S_MOD); + if (x == 1 && i != 254) + goto again; + } + goto done; + again:; + } + fprintf(stderr, "couldn't find generator\n"); + exit(EXIT_FAILURE); +done:; + + /* --- Now grind through and do the affine transform --- * + * + * The matrix multiply is an AND and a parity op. The add is an XOR. + */ + + for (i = 0; i < 256; i++) { + unsigned j; + octet m[] = { 0xd6, 0x7b, 0x3d, 0x1f, 0x0f, 0x05, 0x03, 0x01 }; + unsigned v = i ? alog[255 - log[i]] : 0; + + assert(i == 0 || mul(i, v, S_MOD) == 1); + + x = 0; + for (j = 0; j < 8; j++) { + unsigned r; + r = v & m[j]; + r = (r >> 4) ^ r; + r = (r >> 2) ^ r; + r = (r >> 1) ^ r; + x = (x << 1) | (r & 1); + } + x ^= 0xb1; + s[i] = x; + si[x] = i; + } +} + +/* --- @tbox@ --- * + * + * Construct the t tables for doing the round function efficiently. + */ + +static void tbox(void) +{ + unsigned i; + + for (i = 0; i < 256; i++) { + uint32 a, b, c, d; + uint32 w; + + /* --- Build a forwards t-box entry --- */ + + a = s[i]; + b = a << 1; if (b & 0x100) b ^= S_MOD; + c = a ^ b; + w = (b << 0) | (a << 8) | (a << 16) | (c << 24); + t[0][i] = w; + t[1][i] = ROL32(w, 8); + t[2][i] = ROL32(w, 16); + t[3][i] = ROL32(w, 24); + + /* --- Build a backwards t-box entry --- */ + + a = mul(si[i], 0x0e, S_MOD); + b = mul(si[i], 0x09, S_MOD); + c = mul(si[i], 0x0d, S_MOD); + d = mul(si[i], 0x0b, S_MOD); + w = (a << 0) | (b << 8) | (c << 16) | (d << 24); + ti[0][i] = w; + ti[1][i] = ROL32(w, 8); + ti[2][i] = ROL32(w, 16); + ti[3][i] = ROL32(w, 24); + } +} + +/* --- @ubox@ --- * + * + * Construct the tables for performing the key schedule. + */ + +static void ubox(void) +{ + unsigned i; + + for (i = 0; i < 256; i++) { + uint32 a, b, c; + uint32 w; + a = i; + b = a << 1; if (b & 0x100) b ^= S_MOD; + c = a ^ b; + w = (b << 0) | (a << 8) | (a << 16) | (c << 24); + u[0][i] = w; + u[1][i] = ROL32(w, 8); + u[2][i] = ROL32(w, 16); + u[3][i] = ROL32(w, 24); + } +} + +/* --- Round constants --- */ + +void rcon(void) +{ + unsigned r = 1; + int i; + + for (i = 0; i < sizeof(rc); i++) { + rc[i] = r; + r <<= 1; + if (r & 0x100) + r ^= S_MOD; + } +} + +/* --- @main@ --- */ + +int main(void) +{ + int i, j; + + puts("\ +/* -*-c-*-\n\ + *\n\ + * Square tables [generated]\n\ + */\n\ +\n\ +#ifndef CATACOMB_SQUARE_TAB_H\n\ +#define CATACOMB_SQUARE_TAB_H\n\ +"); + + /* --- Write out the S-box --- */ + + sbox(); + fputs("\ +/* --- The byte substitution and its inverse --- */\n\ +\n\ +#define SQUARE_S { \\\n\ + ", stdout); + for (i = 0; i < 256; i++) { + printf("0x%02x", s[i]); + if (i == 255) + fputs(" \\\n}\n\n", stdout); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + + fputs("\ +#define SQUARE_SI { \\\n\ + ", stdout); + for (i = 0; i < 256; i++) { + printf("0x%02x", si[i]); + if (i == 255) + fputs(" \\\n}\n\n", stdout); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + + /* --- Write out the big t tables --- */ + + tbox(); + fputs("\ +/* --- The big round tables --- */\n\ +\n\ +#define SQUARE_T { \\\n\ + { ", stdout); + for (j = 0; j < 4; j++) { + for (i = 0; i < 256; i++) { + printf("0x%08x", t[j][i]); + if (i == 255) { + if (j == 3) + fputs(" } \\\n}\n\n", stdout); + else + fputs(" }, \\\n\ + \\\n\ + { ", stdout); + } else if (i % 4 == 3) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + } + + fputs("\ +#define SQUARE_TI { \\\n\ + { ", stdout); + for (j = 0; j < 4; j++) { + for (i = 0; i < 256; i++) { + printf("0x%08x", ti[j][i]); + if (i == 255) { + if (j == 3) + fputs(" } \\\n}\n\n", stdout); + else + fputs(" }, \\\n\ + \\\n\ + { ", stdout); + } else if (i % 4 == 3) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + } + + /* --- Write out the big u tables --- */ + + ubox(); + fputs("\ +/* --- The key schedule tables --- */\n\ +\n\ +#define SQUARE_U { \\\n\ + { ", stdout); + for (j = 0; j < 4; j++) { + for (i = 0; i < 256; i++) { + printf("0x%08x", u[j][i]); + if (i == 255) { + if (j == 3) + fputs(" } \\\n}\n\n", stdout); + else + fputs(" }, \\\n\ + \\\n\ + { ", stdout); + } else if (i % 4 == 3) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + } + + /* --- Round constants --- */ + + rcon(); + fputs("\ +/* --- The round constants --- */\n\ +\n\ +#define SQUARE_RCON { \\\n\ + ", stdout); + for (i = 0; i < sizeof(rc); i++) { + printf("0x%02x", rc[i]); + if (i == sizeof(rc) - 1) + fputs(" \\\n}\n\n", stdout); + else if (i % 8 == 7) + fputs(", \\\n ", stdout); + else + fputs(", ", stdout); + } + + /* --- Done --- */ + + puts("#endif"); + + if (fclose(stdout)) { + fprintf(stderr, "error writing data\n"); + exit(EXIT_FAILURE); + } + + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ -- 2.11.0