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

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