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

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