idea.c 5.81 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
/* $Id$
 *
 * The basic IDEA transformation
 *
 * This implementation is taken from pgp, see note below.
 *
 * Only primitive operations are done here, chaining modes etc
 * are implemented in a higher level program.
 *
 **********************************************************************
 *
 *    idea.c - C source code for IDEA block cipher.
 *      IDEA (International Data Encryption Algorithm), formerly known as 
 *      IPES (Improved Proposed Encryption Standard).
 *      Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
 *      This implementation modified and derived from original C code 
 *      developed by Xuejia Lai.  
 *      Zero-based indexing added, names changed from IPES to IDEA.
 *      CFB functions added.  Random number routines added.
 *
 *      Extensively optimized and restructured by Colin Plumb.
 *
 ***********************************************************************
 *
 * Some changes including endianness cleanup done by Niels Mller.
 *
 */

#include "crypto_types.h"
#include <idea.h>

#include <string.h>

/*-------------------------------------------------------------*/

#define low16(x)  ((x) & 0xffff)

/*
 *	Multiplication, modulo (2**16)+1
 * Note that this code is structured on the assumption that
 * untaken branches are cheaper than taken branches, and the
 * compiler doesn't schedule branches.
 */
#ifdef SMALL_CACHE
const static unsigned INT16
mul(unsigned INT16 a, unsigned INT16 b)
{
  register unsigned INT32 p;

  p = (unsigned INT32)a * b;
  if (p)
    {
      b = low16(p);
      a = p>>16;
      return (b - a) + (b < a);
    }
  else if (a)
    {
      return 1-b;
    }
  else
    {
      return 1-a;
    }
} /* mul */
#endif /* SMALL_CACHE */

/*
 * Compute the multiplicative inverse of x, modulo 65537, using Euclid's
 * algorithm. It is unrolled twice to avoid swapping the registers each
 * iteration, and some subtracts of t have been changed to adds.
 */
static const unsigned INT16
inv(unsigned INT16 x)     
{
  unsigned INT16 t0, t1;
  unsigned INT16 q, y;

  if (x <= 1)
    return x;	/* 0 and 1 are self-inverse */
  t1 = 0x10001L / x;	/* Since x >= 2, this fits into 16 bits */
  y = 0x10001L % x;
  if (y == 1)
    return low16(1-t1);
  t0 = 1;
  do
    {
      q = x / y;
      x = x % y;
      t0 += q * t1;
      if (x == 1)
	return t0;
      q = y / x;
      y = y % x;
      t1 += q * t0;
    }
  while (y != 1);
  return low16(1-t1);
} /* inv */

/*
 * Expand a 128-bit user key to a working encryption key ctx
 */
void
idea_expand(unsigned INT16 *ctx,
	    const unsigned INT8 *userkey)
{
  int i,j;
  
  for (j=0; j<8; j++) {
    ctx[j] = (userkey[0]<<8) + userkey[1];
    userkey += 2;
  }
  for (i=0; j < IDEA_KEYLEN; j++) {
    i++;
    ctx[i+7] = ctx[i & 7] << 9 | ctx[(i+1) & 7] >> 7;
    ctx += i & 8;
    i &= 7;
  }
} /* idea_expand */

/*
 * Compute IDEA decryption key DK from an expanded IDEA encryption key EK
 * Note that the input and output may be the same.  Thus, the key is
 * inverted into an internal buffer, and then copied to the output.
 */
void
idea_invert(unsigned INT16 *d,
	    const unsigned INT16 *e)
{
  int i;
  unsigned INT16 t1, t2, t3;
  unsigned INT16 temp[IDEA_KEYLEN];
  unsigned INT16 *p = temp + IDEA_KEYLEN;

  t1 = inv(*e++);
  t2 = -*e++;
  t3 = -*e++;
  *--p = inv(*e++);
  *--p = t3;
  *--p = t2;
  *--p = t1;

  for (i = 0; i < IDEA_ROUNDS-1; i++) {
    t1 = *e++;
    *--p = *e++;
    *--p = t1;

    t1 = inv(*e++);
    t2 = -*e++;
    t3 = -*e++;
    *--p = inv(*e++);
    *--p = t2;
    *--p = t3;
    *--p = t1;
  }
  t1 = *e++;
  *--p = *e++;
  *--p = t1;

  t1 = inv(*e++);
  t2 = -*e++;
  t3 = -*e++;
  *--p = inv(*e++);
  *--p = t3;
  *--p = t2;
  *--p = t1;
  /* Copy and destroy temp copy */
  memcpy(d, temp, sizeof(temp));
  memset(temp, 0, sizeof(temp));
} /* idea_invert */

/*
 * MUL(x,y) computes x = x*y, modulo 0x10001.  Requires two temps, 
 * t16 and t32.  x is modified, and must me a side-effect-free lvalue.
 * y may be anything, but unlike x, must be strictly 16 bits even if
 * low16() is #defined.
 * All of these are equivalent - see which is faster on your machine
 */
#ifdef SMALL_CACHE
#define MUL(x,y) (x = mul(low16(x),y))
#else /* !SMALL_CACHE */
#ifdef AVOID_JUMPS
#define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
		t32 = (unsigned INT32)x*t16 + x + t16 + 1, x = low16(t32), \
		t16 = t32>>16, x = (x-t16) + (x<t16) )
#else /* !AVOID_JUMPS (default) */
#define MUL(x,y) \
	((t16 = (y)) ? \
		(x=low16(x)) ? \
			t32 = (unsigned INT32)x*t16, \
			x = low16(t32), \
			t16 = t32>>16, \
			x = (x-t16)+(x<t16) \
		: \
			(x = 1-t16) \
	: \
		(x = 1-x))
#endif
#endif

/* Endian independent conversions */
#define char2word(dest, p) \
     do { \
	    (dest) = *(p)++ << 8; (dest) |= *(p)++; \
	} while(0)
     
#define word2char(src, p) \
     do { \
	    *(p)++ = (src) >> 8; *(p)++ = (src) & 0xff; \
	} while(0)
     
/*	IDEA encryption/decryption algorithm */
/* Note that in and out can be the same buffer */
void
idea_crypt(const unsigned INT16 *key,
	   unsigned INT8 *dest,
	   const unsigned INT8 *src)
{
  register unsigned INT16 x1, x2, x3, x4, s2, s3;
  
  /* Setup */
    
  char2word(x1, src); char2word(x2, src);
  char2word(x3, src); char2word(x4, src);
  
  /* Encrypt */
  {
#ifndef SMALL_CACHE
    register unsigned INT16 t16;	/* Temporaries needed by MUL macro */
    register unsigned INT32 t32;
#endif
    int r = IDEA_ROUNDS;
    do
      {
	MUL(x1,*key++);
	x2 += *key++;
	x3 += *key++;
	MUL(x4, *key++);

	s3 = x3;
	x3 ^= x1;
	MUL(x3, *key++);
	s2 = x2;
	x2 ^= x4;
	x2 += x3;
	MUL(x2, *key++);
	x3 += x2;

	x1 ^= x2;  x4 ^= x3;

	x2 ^= s3;  x3 ^= s2;
      }
    while (--r);
    MUL(x1, *key++);
    x3 += *key++;
    x2 += *key++;
    MUL(x4, *key);
  }
  word2char(x1, dest); word2char(x3, dest);
  word2char(x2, dest); word2char(x4, dest);
} /* idea_crypt */

/*-------------------------------------------------------------*/