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

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