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

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