chiark - git - mdw - catacomb/blob - twofish-mktab.c

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