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

   1 /* -*-c-*-
   2  *
   3  * $Id: idea.c,v 1.2 2000/06/17 11:24:08 mdw Exp $
   4  *
   5  * Implementation of the IDEA cipher
   6  *
   7  * (c) 1999 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: idea.c,v $
  33  * Revision 1.2  2000/06/17 11:24:08  mdw
  34  * New key size interface.
  35  *
  36  * Revision 1.1  1999/09/03 08:41:12  mdw
  37  * Initial import.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <assert.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 #include <mLib/bits.h>
  49
  50 #include "blkc.h"
  51 #include "gcipher.h"
  52 #include "idea.h"
  53
  54 /*----- Global variables --------------------------------------------------*/
  55
  56 const octet idea_keysz[] = { KSZ_SET, IDEA_KEYSZ };
  57
  58 /*----- Main code ---------------------------------------------------------*/
  59
  60 /* --- @inv@ --- *
  61  *
  62  * Arguments:   @uint16 n@ = number to invert
  63  *
  64  * Returns:     Multiplicative inverse of @n@ %$\pmod{2^{16} + 1}$%.
  65  *
  66  * Use:         Computes multiplicative inverses.  This is handy for the
  67  *              decryption key scheduling.
  68  */
  69
  70 static uint16 inv(uint16 n)
  71 {
  72   uint32 m = 0x10001;
  73   uint32 a = 1, b = 0;
  74
  75   for (;;) {
  76     uint32 q, r, t;
  77     if (!(r = m % n))
  78       break;
  79     q = m / n;
  80     m = n; n = r;
  81     t = a; a = b - q * a; b = t;
  82   }
  83   if (a > MASK16)
  84     a += 1;
  85   return (U16(a));
  86 }
  87
  88 /* --- @MUL@ --- *
  89  *
  90  * Arguments @x@ and @y@ are two 32-bit values to multiply.  On exit, @x@ is
  91  * the product of the two arguments.  The result is not normalized back to 16
  92  * bits; the arguments are not expected to be normalized.
  93  */
  94
  95 #define MUL(x, y) do {                                                  \
  96   uint32 _mx, _my = (y);                                                \
  97   if ((_mx = U16(x)) == 0)                                              \
  98     (x) = 1 - _my;                                                      \
  99   else if (_my == 0)                                                    \
 100     (x) = 1 - _mx;                                                      \
 101   else {                                                                \
 102     _my *= _mx;                                                         \
 103     _mx = U16(_my); _my >>= 16;                                         \
 104     if (_mx < _my)                                                      \
 105       (x) = _mx - _my + 1;                                              \
 106     else                                                                \
 107       (x) = _mx - _my;                                                  \
 108   }                                                                     \
 109 } while (0)
 110
 111 /* --- @idea_init@ --- *
 112  *
 113  * Arguments:   @idea_ctx *k@ = pointer to key block
 114  *              @const void *buf@ = pointer to key buffer
 115  *              @size_t sz@ = size of key material
 116  *
 117  * Returns:     ---
 118  *
 119  * Use:         Initializes an IDEA key buffer.  The buffer must be exactly
 120  *              16 bytes in size, because IDEA is only defined with a key
 121  *              size of 128 bits.
 122  */
 123
 124 void idea_init(idea_ctx *k, const void *buf, size_t sz)
 125 {
 126   KSZ_ASSERT(idea, sz);
 127
 128   /* --- Unpack the encryption key --- */
 129
 130   {
 131     const octet *p = buf;
 132     uint16 *q = k->e;
 133     uint32 a = LOAD32(p +  0);
 134     uint32 b = LOAD32(p +  4);
 135     uint32 c = LOAD32(p +  8);
 136     uint32 d = LOAD32(p + 12);
 137     int i;
 138
 139     /* --- Main unpacking loop --- */
 140
 141     for (i = 0; i < 6; i++) {
 142
 143       /* --- Spit out the next 8 subkeys --- */
 144
 145       q[0] = U16(a >> 16);
 146       q[1] = U16(a >>  0);
 147       q[2] = U16(b >> 16);
 148       q[3] = U16(b >>  0);
 149       q[4] = U16(c >> 16);
 150       q[5] = U16(c >>  0);
 151       q[6] = U16(d >> 16);
 152       q[7] = U16(d >>  0);
 153       q += 8;
 154
 155       /* --- Rotate and permute the subkeys --- */
 156
 157       {
 158         uint32 t = a;
 159         a = U32((a << 25) | (b >> 7));
 160         b = U32((b << 25) | (c >> 7));
 161         c = U32((c << 25) | (d >> 7));
 162         d = U32((d << 25) | (t >> 7));
 163       }
 164     }
 165
 166     /* --- Write out the tail-enders --- */
 167
 168     q[0] = U16(a >> 16);
 169     q[1] = U16(a >>  0);
 170     q[2] = U16(b >> 16);
 171     q[3] = U16(b >>  0);
 172   }
 173
 174   /* --- Convert this into the decryption key --- */
 175
 176   {
 177     uint16 *p = k->e + 52;
 178     uint16 *q = k->d;
 179     int i;
 180
 181     /* --- Translate the main round keys --- */
 182
 183     for (i = 0; i < 8; i++) {
 184       p -= 6;
 185       q[4] = p[0];
 186       q[5] = p[1];
 187       q[0] = inv(p[2]);
 188       q[3] = inv(p[5]);
 189       if (i) {
 190         q[1] = 0x10000 - p[4];
 191         q[2] = 0x10000 - p[3];
 192       } else {
 193         q[1] = 0x10000 - p[3];
 194         q[2] = 0x10000 - p[4];
 195       }
 196       q += 6;
 197     }
 198
 199     /* --- Translate the tail-enders --- */
 200
 201     p -= 4;
 202     q[0] = inv(p[0]);
 203     q[1] = 0x10000 - p[1];
 204     q[2] = 0x10000 - p[2];
 205     q[3] = inv(p[3]);
 206   }
 207 }
 208
 209 /* --- @ROUND@ --- */
 210
 211 #define MIX(k, a, b, c, d) do {                                         \
 212   MUL(a, (k)[0]);                                                       \
 213   (b) += (k)[1];                                                        \
 214   (c) += (k)[2];                                                        \
 215   MUL(d, (k)[3]);                                                       \
 216 } while (0)
 217
 218 #define MA(k, a, b, c, d) do {                                          \
 219   unsigned _u = (a) ^ (c);                                              \
 220   unsigned _v = (b) ^ (d);                                              \
 221   MUL(_u, (k)[4]);                                                      \
 222   _v += _u;                                                             \
 223   MUL(_v, (k)[5]);                                                      \
 224   _u += _v;                                                             \
 225   (a) ^= _v;                                                            \
 226   (b) ^= _u;                                                            \
 227   (c) ^= _v;                                                            \
 228   (d) ^= _u;                                                            \
 229 } while (0);
 230
 231 #define ROUND(k, a, b, c, d) do {                                       \
 232   MIX((k), (a), (b), (c), (d));                                         \
 233   MA((k), (a), (b), (c), (d));                                          \
 234   (k) += 6;                                                             \
 235 } while (0)
 236
 237 /* --- Encryption --- */
 238
 239 #define EBLK(k, a, b, c, d) do {                                        \
 240   unsigned _a = U16(a >> 16);                                           \
 241   unsigned _b = U16(a >>  0);                                           \
 242   unsigned _c = U16(b >> 16);                                           \
 243   unsigned _d = U16(b >>  0);                                           \
 244   const uint16 *_k = (k);                                               \
 245                                                                         \
 246   ROUND(_k, _a, _b, _c, _d);                                            \
 247   ROUND(_k, _a, _c, _b, _d);                                            \
 248   ROUND(_k, _a, _b, _c, _d);                                            \
 249   ROUND(_k, _a, _c, _b, _d);                                            \
 250   ROUND(_k, _a, _b, _c, _d);                                            \
 251   ROUND(_k, _a, _c, _b, _d);                                            \
 252   ROUND(_k, _a, _b, _c, _d);                                            \
 253   ROUND(_k, _a, _c, _b, _d);                                            \
 254   MIX  (_k, _a, _c, _b, _d);                                            \
 255   (c) = (U16(_a) << 16) | U16(_c);                                      \
 256   (d) = (U16(_b) << 16) | U16(_d);                                      \
 257 } while (0)
 258
 259 #define DBLK(k, a, b) EBLK((k), (a), (b))
 260
 261 /* --- @idea_eblk@, @idea_dblk@ --- *
 262  *
 263  * Arguments:   @const idea_ctx *k@ = pointer to a key block
 264  *              @const uint32 s[2]@ = pointer to source block
 265  *              @uint32 d[2]@ = pointer to destination block
 266  *
 267  * Returns:     ---
 268  *
 269  * Use:         Low-level block encryption and decryption.
 270  */
 271
 272 void idea_eblk(const idea_ctx *k, const uint32 *s, uint32 *d)
 273 {
 274   EBLK(k->e, s[0], s[1], d[0], d[1]);
 275 }
 276
 277 void idea_dblk(const idea_ctx *k, const uint32 *s, uint32 *d)
 278 {
 279   EBLK(k->d, s[0], s[1], d[0], d[1]);
 280 }
 281
 282 BLKC_TEST(IDEA, idea)
 283
 284 /*----- That's all, folks -------------------------------------------------*/