--- /dev/null
+/* -*-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 <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <mLib/bits.h>
+
+/*----- 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 -------------------------------------------------*/
projects / u / mdw / catacomb / commitdiff