Formatting fixes. Very boring.

[become] / src / idea.c

/* -*-c-*-
 *
 * $Id: idea.c,v 1.2 1997/08/04 10:24:22 mdw Exp $
 *
 * IDEA encryption routines
 *  Based on Straylight ARM assembler routines
 *
 * (c) 1996, 1997 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of `become'
 *
 * `Become' is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * `Become' is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with `become'; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------*
 *
 * $Log: idea.c,v $
 * Revision 1.2  1997/08/04 10:24:22  mdw
 * Sources placed under CVS control.
 *
 * Revision 1.1  1997/07/21  13:47:49  mdw
 * Initial revision
 *
 */

/*----- Notes -------------------------------------------------------------*
 *
 * This code is optimised for 32-bit processors with reasonable numbers of
 * registers.  Hopefully it should still work on a Spectrum, although rather
 * slowly.  I do assume two's complement arithmetic.
 *
 * Since this is actually /decompiled/, by hand, from some existing assembler
 * code, you can expect some parts to be a little strange.
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#include "config.h"
#include "idea.h"
#include "utils.h"

/*----- Low-level support functions ---------------------------------------*/

/* --- @idea__inv@ --- *
 *
 * Arguments:   @int n@ = number to invert
 *
 * Returns:     Multiplicative inverse of n, mod 2^{16} + 1
 */

static int idea__inv(int n)
{
  long m, a, b, q, r, t;

  /* --- Check the easy case --- */

  if (!n)
    return (0);

  /* --- Start off the loop --- */

  m = 0x10001L;
  a = 1;
  b = 0;
  for (;;) {
    q = m / n, r = m % n;
    if (!r)
      break;
    m = n, n = r;
    t = a, a = b - q * a, b = t;
  }

  /* --- Get return value in range --- */

  if (a < 0)
    a += 1;
  return ((int) a & 0xFFFF);
}

/* --- @_mul@ --- *
 *
 * An evil macro to do multiplication.  Satan lives here.
 */

#define _mul(x, y)							\
  (void)(								\
    x &= ffff, x ?							\
      ( y &= ffff, y ?							\
        ((y = x * y), x = y & ffff, y = y >> 16, x < y ?		\
          (x = x - y + 1) : (x = x - y)) :				\
      (x = 1 - x)) :							\
    (x = 1 - y)								\
  )

/*----- Key unpacking functions -------------------------------------------*/

/* --- @idea_ekeys@ --- *
 *
 * Arguments:   @idea_key *k@ = the expanded key buffer
 *		@const unsigned char *key@ = the user's key encryption key
 *
 * Returns:	---
 *
 * Use:         Unpacks an encryption key.
 */

void idea_ekeys(idea_key *k, const unsigned char *key)
{
  /* --- Convince compiler to do this properly --- */

  register const int ffff = 0xFFFF;

  uint_32 ka, kb, kc, kd;
  int count;
  int *p = k->k;

  /* --- Load the 4 words from the block --- *
   *
   * Don't ask.
   */

  ka = load32(key +  0);
  kb = load32(key +  4);
  kc = load32(key +  8);
  kd = load32(key + 12);

  for (count = 48; count > 0; count -= 8) {

    /* --- Unpack halfwords into the block --- */

    *p++ = (ka >> 16) & ffff;
    *p++ = ka & ffff;
    *p++ = (kb >> 16) & ffff;
    *p++ = kb & ffff;
    *p++ = (kc >> 16) & ffff;
    *p++ = kc & ffff;
    *p++ = (kd >> 16) & ffff;
    *p++ = kd & ffff;

    /* --- Now rotate the 128-bit key --- */

    {
      uint_32 kx = ka;
      ka = ((ka << 25) | (kb >> 7)) & 0xffffffffu;
      kb = ((kb << 25) | (kc >> 7)) & 0xffffffffu;
      kc = ((kc << 25) | (kd >> 7)) & 0xffffffffu;
      kd = ((kd << 25) | (kx >> 7)) & 0xffffffffu;
    }
  }

  /* --- Write the tail-enders over --- */

  *p++ = (ka >> 16) & ffff;
  *p++ = ka & ffff;
  *p++ = (kb >> 16) & ffff;
  *p++ = kb & ffff;
}

/* --- @idea_invertKey@ --- *
 *
 * Arguments:	@const idea_key *in@ = pointer to input expanded key buffer
 *		@idea_key *out@ = pointer to output expanded key buffer
 *
 * Returns:	---
 *
 * Use:		Computes the inverse (decryption) key given an expanded
 *		IDEA encryption key.
 */

void idea_invertKey(const idea_key *in, idea_key *out)
{
  int i;
  unsigned a, b, c, d, e, f;
  int *ibuf = in->k, *obuf = out->k;
  
  /* --- Deal with identical input and output buffers --- */

  if (in == out) {
    idea_key t;
    memcpy(&t, in, sizeof(t));
    idea_invertKey(&t, out);
    return;
  }

  /* --- Do the real work --- */

  ibuf += IDEA_EXPKEYSIZE;
  for (i = 8; i; i--) {
    ibuf -= 6;
    a = ibuf[0];
    b = ibuf[1];
    c = ibuf[2];
    d = ibuf[3];
    e = ibuf[4];
    f = ibuf[5];

    c = idea__inv(c);
    f = idea__inv(f);
    d = 0x10000 - d;
    e = 0x10000 - e;

    if (i < 8)
      d ^= e, e ^= d, d ^= e;

    obuf[0] = c;
    obuf[1] = d;
    obuf[2] = e;
    obuf[3] = f;
    obuf[4] = a;
    obuf[5] = b;
    obuf += 6;
  }

  /* --- Deal with the tail-enders --- */

  ibuf -= 4;
  c = ibuf[0];
  d = ibuf[1];
  e = ibuf[2];
  f = ibuf[3];

  c = idea__inv(c);
  f = idea__inv(f);
  d = 0x10000 - d;
  e = 0x10000 - e;

  obuf[0] = c;
  obuf[1] = d;
  obuf[2] = e;
  obuf[3] = f;
}

/* --- @idea_dkeys@ --- *
 *
 * Arguments:   @idea_key *k@ = the expanded key buffer
 *		@const unsigned char *key@ = the user's key encryption key
 *
 * Returns:     ---
 *
 * Use:         Unpacks a decryption key.
 */

void idea_dkeys(idea_key *k, const unsigned char *key)
{
  idea_key t;
  idea_ekeys(&t, key);
  idea_invertKey(&t, k);
}

/*----- Main IDEA cipher --------------------------------------------------*/

/* --- @idea_encrypt@ --- *
 *
 * Arguments:	@const idea_key *k@ = key to use
 *		@const void *src@ = block to encrypt
 *		@void *dest@ = where to store the result
 *
 * Returns:     ---
 *
 * Use:         Encrypts (or decrypts) a block, using the IDEA cryptosystem.
 *              Since the decryption operation is the same as encryption
 *              except that a different key buffer is used, this is all we
 *              need to complete the simple bits.
 *
 *              For people following this at home: I've been very sloppy
 *              about chopping off excess bits from the ints here.  Most of
 *              the time it doesn't matter, and when it does, in the
 *              multiplication stage, the macro does this for us.
 *
 *              Our @register const int ffff@ makes another appearance.  This
 *              might suggest to compilers that having this constant
 *              available would be beneficial.
 *
 *              Registers are in short supply here.  So is legibility.
 */

#if defined(TEST_RIG) && defined(DUMPROUNDS)
#  define _dump(a,b,c,d)						\
    printf("   %5lu %5lu %5lu %5lu\n",					\
	   a & ffff, b & ffff, c & ffff, d & ffff)
#else
#  define _dump(a,b,c,d) ((void)0)
#endif

#define _round(a, b, c, d) do {						\
  _dump(a, b, c, d);							\
  u = kp[0]; v = kp[1]; w = kp[2]; x = kp[3]; y = kp[4]; z = kp[5];	\
  kp += 6;								\
  _mul(a, u); b += v; c += w; _mul(d, x);				\
  u = a ^ c; v = b ^ d; _mul(u, y); v += u; _mul(v, z); u += v;		\
  a ^= v; b ^= u; c ^= v; d ^= u;					\
  _dump(a, b, c, d);							\
} while (0)								\

void idea_encrypt(const idea_key *k, const void *src, void *dest)
{
  register const int ffff = 0xFFFF;
  const unsigned char *usrc = src;
  unsigned char *udest = dest;
  int *kp = k->k;

  uint_32 a, b, c, d;
  uint_32 u, v, w, x, y, z;

  /* --- Unpack next block into registers --- */

  a = (usrc[0] << 8) | usrc[1];
  b = (usrc[2] << 8) | usrc[3];
  c = (usrc[4] << 8) | usrc[5];
  d = (usrc[6] << 8) | usrc[7];

  /* --- Now run the block through the eight rounds --- *
   *
   * Notice how the arguments swap around so as I don't have to move the
   * values about.
   */

  _round(a, b, c, d);
  _round(a, c, b, d);
  _round(a, b, c, d);
  _round(a, c, b, d);

  _round(a, b, c, d);
  _round(a, c, b, d);
  _round(a, b, c, d);
  _round(a, c, b, d);

  /* --- Do the output transformation --- */

  u = kp[0];
  v = kp[1];
  w = kp[2];
  x = kp[3];
  _mul(a, u);
  b += w;
  c += v;
  _mul(d, x);

  /* --- Repack and store the block --- */

  udest[0] = (a >> 8) & 0xFF; udest[1] = a & 0xFF;
  udest[2] = (c >> 8) & 0xFF; udest[3] = c & 0xFF;
  udest[4] = (b >> 8) & 0xFF; udest[5] = b & 0xFF;
  udest[6] = (d >> 8) & 0xFF; udest[7] = d & 0xFF;
}

/*----- Debugging driver --------------------------------------------------*/

#ifdef TEST_RIG

#define TESTENCRYPTION

void dumpbuf(int *k)
{
  int i;
  printf("Round ");
  for (i = 1; i <= 6; i++)
    printf("%5i ", i);
  for (i = 0; i < 52; i++) {
    if (i % 6 == 0)
      printf("\n  %i   ", i / 6 + 1);
    printf("%5i ", *k++);
  }
  printf("\n\n");
}

void dumpblk(char *bb)
{
  unsigned char *b = (unsigned char *)bb;
  printf("++ %5u %5u %5u %5u\n",
	 (b[0]<<8)|b[1],
	 (b[2]<<8)|b[3],
	 (b[4]<<8)|b[5],
	 (b[6]<<8)|b[7]);
}

int main(void)
{

#ifdef TESTMULTIPLY
  {
    unsigned int i, j;
    char buf[256];
    int ffff = 0xFFFF;
    for (;;) {
      gets(buf);
      if (!buf[0])
	break;
      sscanf(buf, "%u%u", &i, &j);
      _mul(i, j);
      printf("%u\n", i);
    }
  }
#endif

#ifdef TESTENCRYPTION
  {
    int i;
    int f;

    unsigned char k[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8 };
    idea_key e, d;
    unsigned char b[] = { 0, 0, 0, 1, 0, 2, 0, 3 };

    static idea_key correct_e = { {
	  1,	 2,	3,     4,     5,     6, 
	  7,	 8,  1024,  1536,  2048,  2560, 
       3072,  3584,  4096,   512,    16,    20, 
	 24,	28,    32,     4,     8,    12, 
      10240, 12288, 14336, 16384,  2048,  4096, 
       6144,  8192,   112,   128,    16,    32, 
	 48,	64,    80,    96,     0,  8192, 
      16384, 24576, 32768, 40960, 49152, 57345, 
	128,	192,   256,  320
    } };

    static idea_key correct_d = { {
      65025, 65344, 65280, 26010, 49152, 57345, 
      65533, 32768, 40960, 52428,     0,  8192, 
      42326, 65456, 65472, 21163,    16,    32, 
      21835, 65424, 57344, 65025,  2048,  4096, 
      13101, 51200, 53248, 65533,     8,    12, 
      19115, 65504, 65508, 49153,    16,    20, 
      43670, 61440, 61952, 65409,  2048,  2560, 
      18725, 64512, 65528, 21803,     5,     6, 
	  1, 65534, 65533, 49153
    } };

    static unsigned char correct_encrypt[] = {
      4603 / 256, 4603 % 256,
      60715 / 256, 60715 % 256,
      408 / 256, 408 % 256,
      28133 / 256, 28133 % 256
    };

    static unsigned char correct_decrypt[] = {
      0, 0, 0, 1, 0, 2, 0, 3
    };

    idea_ekeys(&e, k);
    dumpbuf(e.k);

    f = 1;
    for (i = 0; i < IDEA_EXPKEYSIZE; i++) {
      if (e.k[i] != correct_e.k[i]) {
	f = 0;
	printf("!!! bad encryption key values!\n\n");
      }
    }
    if (f)
      printf("*** expanded encryption key correct\n\n");

    idea_dkeys(&d, k);
    dumpbuf(d.k);

    f = 1;
    for (i = 0; i < IDEA_EXPKEYSIZE; i++) {
      if (d.k[i] != correct_d.k[i]) {
	f = 0;
	printf("!!! bad decryption key values!\n\n");
      }
    }
    if (f)
      printf("*** expanded decryption key correct\n\n");

    idea_encrypt(&e, b, b);
    dumpblk(b);
    if (memcmp(b, correct_encrypt, 8) == 0)
      printf("*** correct encipherment\n\n");
    else
      printf("!!! bad encipherment\n\n");

    idea_encrypt(&d, b, b);
    dumpblk(b);
    if (memcmp(b, correct_decrypt, 8) == 0)
      printf("*** correct decipherment\n");
    else
      printf("!!! bad decipherment\n");
  }
#endif

  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/