git.distorted.org.uk Git - u/mdw/catacomb/blob - twofish-mktab.c

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