+++ /dev/null
-/* -*-c-*-
- *
- * $Id: square-mktab.c,v 1.3 2004/04/08 01:36:15 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.
- */
-
-/*----- 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^7+x^6+x^5+x^4+x^2+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 -------------------------------------------------*/