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

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