chiark - git - mdw - become/blob - src/idea.c

   1 /* -*-c-*-
   2  *
   3  * $Id: idea.c,v 1.2 1997/08/04 10:24:22 mdw Exp $
   4  *
   5  * IDEA encryption routines
   6  *  Based on Straylight ARM assembler routines
   7  *
   8  * (c) 1996, 1997 Mark Wooding
   9  */
  10
  11 /*----- Licensing notice --------------------------------------------------*
  12  *
  13  * This file is part of `become'
  14  *
  15  * `Become' is free software; you can redistribute it and/or modify
  16  * it under the terms of the GNU General Public License as published by
  17  * the Free Software Foundation; either version 2 of the License, or
  18  * (at your option) any later version.
  19  *
  20  * `Become' is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License
  26  * along with `become'; if not, write to the Free Software Foundation,
  27  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: idea.c,v $
  33  * Revision 1.2  1997/08/04 10:24:22  mdw
  34  * Sources placed under CVS control.
  35  *
  36  * Revision 1.1  1997/07/21  13:47:49  mdw
  37  * Initial revision
  38  *
  39  */
  40
  41 /*----- Notes -------------------------------------------------------------*
  42  *
  43  * This code is optimised for 32-bit processors with reasonable numbers of
  44  * registers.  Hopefully it should still work on a Spectrum, although rather
  45  * slowly.  I do assume two's complement arithmetic.
  46  *
  47  * Since this is actually /decompiled/, by hand, from some existing assembler
  48  * code, you can expect some parts to be a little strange.
  49  */
  50
  51 /*----- Header files ------------------------------------------------------*/
  52
  53 #include <stdio.h>
  54 #include <string.h>
  55
  56 #include "config.h"
  57 #include "idea.h"
  58 #include "utils.h"
  59
  60 /*----- Low-level support functions ---------------------------------------*/
  61
  62 /* --- @idea__inv@ --- *
  63  *
  64  * Arguments:   @int n@ = number to invert
  65  *
  66  * Returns:     Multiplicative inverse of n, mod 2^{16} + 1
  67  */
  68
  69 static int idea__inv(int n)
  70 {
  71   long m, a, b, q, r, t;
  72
  73   /* --- Check the easy case --- */
  74
  75   if (!n)
  76     return (0);
  77
  78   /* --- Start off the loop --- */
  79
  80   m = 0x10001L;
  81   a = 1;
  82   b = 0;
  83   for (;;) {
  84     q = m / n, r = m % n;
  85     if (!r)
  86       break;
  87     m = n, n = r;
  88     t = a, a = b - q * a, b = t;
  89   }
  90
  91   /* --- Get return value in range --- */
  92
  93   if (a < 0)
  94     a += 1;
  95   return ((int) a & 0xFFFF);
  96 }
  97
  98 /* --- @_mul@ --- *
  99  *
 100  * An evil macro to do multiplication.  Satan lives here.
 101  */
 102
 103 #define _mul(x, y)                                                      \
 104   (void)(                                                               \
 105     x &= ffff, x ?                                                      \
 106       ( y &= ffff, y ?                                                  \
 107         ((y = x * y), x = y & ffff, y = y >> 16, x < y ?                \
 108           (x = x - y + 1) : (x = x - y)) :                              \
 109       (x = 1 - x)) :                                                    \
 110     (x = 1 - y)                                                         \
 111   )
 112
 113 /*----- Key unpacking functions -------------------------------------------*/
 114
 115 /* --- @idea_ekeys@ --- *
 116  *
 117  * Arguments:   @idea_key *k@ = the expanded key buffer
 118  *              @const unsigned char *key@ = the user's key encryption key
 119  *
 120  * Returns:     ---
 121  *
 122  * Use:         Unpacks an encryption key.
 123  */
 124
 125 void idea_ekeys(idea_key *k, const unsigned char *key)
 126 {
 127   /* --- Convince compiler to do this properly --- */
 128
 129   register const int ffff = 0xFFFF;
 130
 131   uint_32 ka, kb, kc, kd;
 132   int count;
 133   int *p = k->k;
 134
 135   /* --- Load the 4 words from the block --- *
 136    *
 137    * Don't ask.
 138    */
 139
 140   ka = load32(key +  0);
 141   kb = load32(key +  4);
 142   kc = load32(key +  8);
 143   kd = load32(key + 12);
 144
 145   for (count = 48; count > 0; count -= 8) {
 146
 147     /* --- Unpack halfwords into the block --- */
 148
 149     *p++ = (ka >> 16) & ffff;
 150     *p++ = ka & ffff;
 151     *p++ = (kb >> 16) & ffff;
 152     *p++ = kb & ffff;
 153     *p++ = (kc >> 16) & ffff;
 154     *p++ = kc & ffff;
 155     *p++ = (kd >> 16) & ffff;
 156     *p++ = kd & ffff;
 157
 158     /* --- Now rotate the 128-bit key --- */
 159
 160     {
 161       uint_32 kx = ka;
 162       ka = ((ka << 25) | (kb >> 7)) & 0xffffffffu;
 163       kb = ((kb << 25) | (kc >> 7)) & 0xffffffffu;
 164       kc = ((kc << 25) | (kd >> 7)) & 0xffffffffu;
 165       kd = ((kd << 25) | (kx >> 7)) & 0xffffffffu;
 166     }
 167   }
 168
 169   /* --- Write the tail-enders over --- */
 170
 171   *p++ = (ka >> 16) & ffff;
 172   *p++ = ka & ffff;
 173   *p++ = (kb >> 16) & ffff;
 174   *p++ = kb & ffff;
 175 }
 176
 177 /* --- @idea_invertKey@ --- *
 178  *
 179  * Arguments:   @const idea_key *in@ = pointer to input expanded key buffer
 180  *              @idea_key *out@ = pointer to output expanded key buffer
 181  *
 182  * Returns:     ---
 183  *
 184  * Use:         Computes the inverse (decryption) key given an expanded
 185  *              IDEA encryption key.
 186  */
 187
 188 void idea_invertKey(const idea_key *in, idea_key *out)
 189 {
 190   int i;
 191   unsigned a, b, c, d, e, f;
 192   int *ibuf = in->k, *obuf = out->k;
 193
 194   /* --- Deal with identical input and output buffers --- */
 195
 196   if (in == out) {
 197     idea_key t;
 198     memcpy(&t, in, sizeof(t));
 199     idea_invertKey(&t, out);
 200     return;
 201   }
 202
 203   /* --- Do the real work --- */
 204
 205   ibuf += IDEA_EXPKEYSIZE;
 206   for (i = 8; i; i--) {
 207     ibuf -= 6;
 208     a = ibuf[0];
 209     b = ibuf[1];
 210     c = ibuf[2];
 211     d = ibuf[3];
 212     e = ibuf[4];
 213     f = ibuf[5];
 214
 215     c = idea__inv(c);
 216     f = idea__inv(f);
 217     d = 0x10000 - d;
 218     e = 0x10000 - e;
 219
 220     if (i < 8)
 221       d ^= e, e ^= d, d ^= e;
 222
 223     obuf[0] = c;
 224     obuf[1] = d;
 225     obuf[2] = e;
 226     obuf[3] = f;
 227     obuf[4] = a;
 228     obuf[5] = b;
 229     obuf += 6;
 230   }
 231
 232   /* --- Deal with the tail-enders --- */
 233
 234   ibuf -= 4;
 235   c = ibuf[0];
 236   d = ibuf[1];
 237   e = ibuf[2];
 238   f = ibuf[3];
 239
 240   c = idea__inv(c);
 241   f = idea__inv(f);
 242   d = 0x10000 - d;
 243   e = 0x10000 - e;
 244
 245   obuf[0] = c;
 246   obuf[1] = d;
 247   obuf[2] = e;
 248   obuf[3] = f;
 249 }
 250
 251 /* --- @idea_dkeys@ --- *
 252  *
 253  * Arguments:   @idea_key *k@ = the expanded key buffer
 254  *              @const unsigned char *key@ = the user's key encryption key
 255  *
 256  * Returns:     ---
 257  *
 258  * Use:         Unpacks a decryption key.
 259  */
 260
 261 void idea_dkeys(idea_key *k, const unsigned char *key)
 262 {
 263   idea_key t;
 264   idea_ekeys(&t, key);
 265   idea_invertKey(&t, k);
 266 }
 267
 268 /*----- Main IDEA cipher --------------------------------------------------*/
 269
 270 /* --- @idea_encrypt@ --- *
 271  *
 272  * Arguments:   @const idea_key *k@ = key to use
 273  *              @const void *src@ = block to encrypt
 274  *              @void *dest@ = where to store the result
 275  *
 276  * Returns:     ---
 277  *
 278  * Use:         Encrypts (or decrypts) a block, using the IDEA cryptosystem.
 279  *              Since the decryption operation is the same as encryption
 280  *              except that a different key buffer is used, this is all we
 281  *              need to complete the simple bits.
 282  *
 283  *              For people following this at home: I've been very sloppy
 284  *              about chopping off excess bits from the ints here.  Most of
 285  *              the time it doesn't matter, and when it does, in the
 286  *              multiplication stage, the macro does this for us.
 287  *
 288  *              Our @register const int ffff@ makes another appearance.  This
 289  *              might suggest to compilers that having this constant
 290  *              available would be beneficial.
 291  *
 292  *              Registers are in short supply here.  So is legibility.
 293  */
 294
 295 #if defined(TEST_RIG) && defined(DUMPROUNDS)
 296 #  define _dump(a,b,c,d)                                                \
 297     printf("   %5lu %5lu %5lu %5lu\n",                                  \
 298            a & ffff, b & ffff, c & ffff, d & ffff)
 299 #else
 300 #  define _dump(a,b,c,d) ((void)0)
 301 #endif
 302
 303 #define _round(a, b, c, d) do {                                         \
 304   _dump(a, b, c, d);                                                    \
 305   u = kp[0]; v = kp[1]; w = kp[2]; x = kp[3]; y = kp[4]; z = kp[5];     \
 306   kp += 6;                                                              \
 307   _mul(a, u); b += v; c += w; _mul(d, x);                               \
 308   u = a ^ c; v = b ^ d; _mul(u, y); v += u; _mul(v, z); u += v;         \
 309   a ^= v; b ^= u; c ^= v; d ^= u;                                       \
 310   _dump(a, b, c, d);                                                    \
 311 } while (0)                                                             \
 312
 313 void idea_encrypt(const idea_key *k, const void *src, void *dest)
 314 {
 315   register const int ffff = 0xFFFF;
 316   const unsigned char *usrc = src;
 317   unsigned char *udest = dest;
 318   int *kp = k->k;
 319
 320   uint_32 a, b, c, d;
 321   uint_32 u, v, w, x, y, z;
 322
 323   /* --- Unpack next block into registers --- */
 324
 325   a = (usrc[0] << 8) | usrc[1];
 326   b = (usrc[2] << 8) | usrc[3];
 327   c = (usrc[4] << 8) | usrc[5];
 328   d = (usrc[6] << 8) | usrc[7];
 329
 330   /* --- Now run the block through the eight rounds --- *
 331    *
 332    * Notice how the arguments swap around so as I don't have to move the
 333    * values about.
 334    */
 335
 336   _round(a, b, c, d);
 337   _round(a, c, b, d);
 338   _round(a, b, c, d);
 339   _round(a, c, b, d);
 340
 341   _round(a, b, c, d);
 342   _round(a, c, b, d);
 343   _round(a, b, c, d);
 344   _round(a, c, b, d);
 345
 346   /* --- Do the output transformation --- */
 347
 348   u = kp[0];
 349   v = kp[1];
 350   w = kp[2];
 351   x = kp[3];
 352   _mul(a, u);
 353   b += w;
 354   c += v;
 355   _mul(d, x);
 356
 357   /* --- Repack and store the block --- */
 358
 359   udest[0] = (a >> 8) & 0xFF; udest[1] = a & 0xFF;
 360   udest[2] = (c >> 8) & 0xFF; udest[3] = c & 0xFF;
 361   udest[4] = (b >> 8) & 0xFF; udest[5] = b & 0xFF;
 362   udest[6] = (d >> 8) & 0xFF; udest[7] = d & 0xFF;
 363 }
 364
 365 /*----- Debugging driver --------------------------------------------------*/
 366
 367 #ifdef TEST_RIG
 368
 369 #define TESTENCRYPTION
 370
 371 void dumpbuf(int *k)
 372 {
 373   int i;
 374   printf("Round ");
 375   for (i = 1; i <= 6; i++)
 376     printf("%5i ", i);
 377   for (i = 0; i < 52; i++) {
 378     if (i % 6 == 0)
 379       printf("\n  %i   ", i / 6 + 1);
 380     printf("%5i ", *k++);
 381   }
 382   printf("\n\n");
 383 }
 384
 385 void dumpblk(char *bb)
 386 {
 387   unsigned char *b = (unsigned char *)bb;
 388   printf("++ %5u %5u %5u %5u\n",
 389          (b[0]<<8)|b[1],
 390          (b[2]<<8)|b[3],
 391          (b[4]<<8)|b[5],
 392          (b[6]<<8)|b[7]);
 393 }
 394
 395 int main(void)
 396 {
 397
 398 #ifdef TESTMULTIPLY
 399   {
 400     unsigned int i, j;
 401     char buf[256];
 402     int ffff = 0xFFFF;
 403     for (;;) {
 404       gets(buf);
 405       if (!buf[0])
 406         break;
 407       sscanf(buf, "%u%u", &i, &j);
 408       _mul(i, j);
 409       printf("%u\n", i);
 410     }
 411   }
 412 #endif
 413
 414 #ifdef TESTENCRYPTION
 415   {
 416     int i;
 417     int f;
 418
 419     unsigned char k[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8 };
 420     idea_key e, d;
 421     unsigned char b[] = { 0, 0, 0, 1, 0, 2, 0, 3 };
 422
 423     static idea_key correct_e = { {
 424           1,     2,     3,     4,     5,     6,
 425           7,     8,  1024,  1536,  2048,  2560,
 426        3072,  3584,  4096,   512,    16,    20,
 427          24,    28,    32,     4,     8,    12,
 428       10240, 12288, 14336, 16384,  2048,  4096,
 429        6144,  8192,   112,   128,    16,    32,
 430          48,    64,    80,    96,     0,  8192,
 431       16384, 24576, 32768, 40960, 49152, 57345,
 432         128,    192,   256,  320
 433     } };
 434
 435     static idea_key correct_d = { {
 436       65025, 65344, 65280, 26010, 49152, 57345,
 437       65533, 32768, 40960, 52428,     0,  8192,
 438       42326, 65456, 65472, 21163,    16,    32,
 439       21835, 65424, 57344, 65025,  2048,  4096,
 440       13101, 51200, 53248, 65533,     8,    12,
 441       19115, 65504, 65508, 49153,    16,    20,
 442       43670, 61440, 61952, 65409,  2048,  2560,
 443       18725, 64512, 65528, 21803,     5,     6,
 444           1, 65534, 65533, 49153
 445     } };
 446
 447     static unsigned char correct_encrypt[] = {
 448       4603 / 256, 4603 % 256,
 449       60715 / 256, 60715 % 256,
 450       408 / 256, 408 % 256,
 451       28133 / 256, 28133 % 256
 452     };
 453
 454     static unsigned char correct_decrypt[] = {
 455       0, 0, 0, 1, 0, 2, 0, 3
 456     };
 457
 458     idea_ekeys(&e, k);
 459     dumpbuf(e.k);
 460
 461     f = 1;
 462     for (i = 0; i < IDEA_EXPKEYSIZE; i++) {
 463       if (e.k[i] != correct_e.k[i]) {
 464         f = 0;
 465         printf("!!! bad encryption key values!\n\n");
 466       }
 467     }
 468     if (f)
 469       printf("*** expanded encryption key correct\n\n");
 470
 471     idea_dkeys(&d, k);
 472     dumpbuf(d.k);
 473
 474     f = 1;
 475     for (i = 0; i < IDEA_EXPKEYSIZE; i++) {
 476       if (d.k[i] != correct_d.k[i]) {
 477         f = 0;
 478         printf("!!! bad decryption key values!\n\n");
 479       }
 480     }
 481     if (f)
 482       printf("*** expanded decryption key correct\n\n");
 483
 484     idea_encrypt(&e, b, b);
 485     dumpblk(b);
 486     if (memcmp(b, correct_encrypt, 8) == 0)
 487       printf("*** correct encipherment\n\n");
 488     else
 489       printf("!!! bad encipherment\n\n");
 490
 491     idea_encrypt(&d, b, b);
 492     dumpblk(b);
 493     if (memcmp(b, correct_decrypt, 8) == 0)
 494       printf("*** correct decipherment\n");
 495     else
 496       printf("!!! bad decipherment\n");
 497   }
 498 #endif
 499
 500   return (0);
 501 }
 502
 503 #endif
 504
 505 /*----- That's all, folks -------------------------------------------------*/