Include an IDEA implementation.
[libgcrypt.git] / cipher / idea.c
1 /* idea.c  -  IDEA function
2  *      Copyright (c) 1997, 1998, 1999, 2001 by Werner Koch (dd9jn)
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17  * WERNER KOCH BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20  *
21  * Except as contained in this notice, the name of Werner Koch shall not be
22  * used in advertising or otherwise to promote the sale, use or other dealings
23  * in this Software without prior written authorization from Werner Koch.
24  *
25  * DUE TO PATENT CLAIMS THE DISTRIBUTION OF THE SOFTWARE IS NOT ALLOWED IN
26  * THESE COUNTRIES:
27  *     AUSTRIA, FRANCE, GERMANY, ITALY, JAPAN, THE NETHERLANDS,
28  *     SPAIN, SWEDEN, SWITZERLAND, THE UK AND THE US.
29  */
30
31 /*
32  * Please see http://www.noepatents.org/ to learn why software patents
33  * are bad for society and what you can do to fight them.
34  *
35  * The code herein is based on the one from:
36  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
37  *    ISBN 0-471-11709-9. .
38  *
39  * How to compile:
40        gcc -Wall -O2 -shared -fPIC -o idea idea.c
41  *
42  * 2001-06-08 wk  Changed distribution conditions
43  * 2001-06-11 wk  Fixed invert_key (which is not used in CFB mode)
44  *                Thanks to Mark A. Borgerding.  Added defintion for
45  *                the PowerPC.
46  */
47
48
49 #include <stdio.h>
50 #include <stdlib.h>
51 #include <string.h>
52 #include <assert.h>
53
54 /* configuration stuff */
55 #ifdef __alpha__
56   #define SIZEOF_UNSIGNED_LONG 8
57 #else
58   #define SIZEOF_UNSIGNED_LONG 4
59 #endif
60
61 #if defined(__mc68000__) || defined (__sparc__) || defined (__PPC__) \
62     || (defined(__mips__) && (defined(MIPSEB) || defined (__MIPSEB__)) ) \
63     || defined(__powerpc__) \
64     || defined(__hpux__) /* should be replaced by the Macro for the PA */
65   #define BIG_ENDIAN_HOST 1
66 #else
67   #define LITTLE_ENDIAN_HOST 1
68 #endif
69
70 typedef unsigned long  ulong;
71 typedef unsigned short ushort;
72 typedef unsigned char  byte;
73
74 typedef unsigned short u16;
75 typedef unsigned long  u32;
76
77 /* end configurable stuff */
78
79 #ifndef DIM
80   #define DIM(v) (sizeof(v)/sizeof((v)[0]))
81   #define DIMof(type,member)   DIM(((type *)0)->member)
82 #endif
83
84 /* imports */
85 void g10_log_fatal( const char *fmt, ... );
86
87
88 /* local stuff */
89
90 #define FNCCAST_SETKEY(f)  ((int(*)(void*, byte*, unsigned))(f))
91 #define FNCCAST_CRYPT(f)   ((void(*)(void*, byte*, byte*))(f))
92
93 #define IDEA_KEYSIZE 16
94 #define IDEA_BLOCKSIZE 8
95 #define IDEA_ROUNDS 8
96 #define IDEA_KEYLEN (6*IDEA_ROUNDS+4)
97
98 typedef struct {
99     u16 ek[IDEA_KEYLEN];
100     u16 dk[IDEA_KEYLEN];
101     int have_dk;
102 } IDEA_context;
103
104
105 static int do_setkey( IDEA_context *c, byte *key, unsigned keylen );
106 static void encrypt_block( IDEA_context *bc, byte *outbuf, byte *inbuf );
107 static void decrypt_block( IDEA_context *bc, byte *outbuf, byte *inbuf );
108 static void selftest(int);
109
110
111
112 static u16
113 mul_inv( u16 x )
114 {
115     u16 t0, t1;
116     u16 q, y;
117
118     if( x < 2 )
119         return x;
120     t1 = 0x10001L / x;
121     y =  0x10001L % x;
122     if( y == 1 )
123         return (1-t1) & 0xffff;
124
125     t0 = 1;
126     do {
127         q = x / y;
128         x = x % y;
129         t0 += q * t1;
130         if( x == 1 )
131             return t0;
132         q = y / x;
133         y = y % x;
134         t1 += q * t0;
135     } while( y != 1 );
136     return (1-t1) & 0xffff;
137 }
138
139
140
141 static void
142 expand_key( byte *userkey, u16 *ek )
143 {
144     int i,j;
145
146     for(j=0; j < 8; j++ ) {
147         ek[j] = (*userkey << 8) + userkey[1];
148         userkey += 2;
149     }
150     for(i=0; j < IDEA_KEYLEN; j++ ) {
151         i++;
152         ek[i+7] = ek[i&7] << 9 | ek[(i+1)&7] >> 7;
153         ek += i & 8;
154         i &= 7;
155     }
156 }
157
158
159 static void
160 invert_key( u16 *ek, u16 dk[IDEA_KEYLEN] )
161 {
162     int i;
163     u16 t1, t2, t3;
164     u16 temp[IDEA_KEYLEN];
165     u16 *p = temp + IDEA_KEYLEN;
166
167     t1 = mul_inv( *ek++ );
168     t2 = -*ek++;
169     t3 = -*ek++;
170     *--p = mul_inv( *ek++ );
171     *--p = t3;
172     *--p = t2;
173     *--p = t1;
174
175     for(i=0; i < IDEA_ROUNDS-1; i++ ) {
176         t1 = *ek++;
177         *--p = *ek++;
178         *--p = t1;
179
180         t1 = mul_inv( *ek++ );
181         t2 = -*ek++;
182         t3 = -*ek++;
183         *--p = mul_inv( *ek++ );
184         *--p = t2;
185         *--p = t3;
186         *--p = t1;
187     }
188     t1 = *ek++;
189     *--p = *ek++;
190     *--p = t1;
191
192     t1 = mul_inv( *ek++ );
193     t2 = -*ek++;
194     t3 = -*ek++;
195     *--p = mul_inv( *ek++ );
196     *--p = t3;
197     *--p = t2;
198     *--p = t1;
199     memcpy(dk, temp, sizeof(temp) );
200     memset(temp, 0, sizeof(temp) );  /* burn temp */
201 }
202
203
204 static void
205 cipher( byte *outbuf, byte *inbuf, u16 *key )
206 {
207     u16 x1, x2, x3,x4, s2, s3;
208     u16 *in, *out;
209     int r = IDEA_ROUNDS;
210   #define MUL(x,y) \
211         do {u16 _t16; u32 _t32;                     \
212             if( (_t16 = (y)) ) {                    \
213                 if( (x = (x)&0xffff) ) {            \
214                     _t32 = (u32)x * _t16;           \
215                     x = _t32 & 0xffff;              \
216                     _t16 = _t32 >> 16;              \
217                     x = ((x)-_t16) + (x<_t16?1:0);  \
218                 }                                   \
219                 else {                              \
220                     x = 1 - _t16;                   \
221                 }                                   \
222             }                                       \
223             else {                                  \
224                 x = 1 - x;                          \
225             }                                       \
226         } while(0)
227
228     in = (u16*)inbuf;
229     x1 = *in++;
230     x2 = *in++;
231     x3 = *in++;
232     x4 = *in;
233   #ifdef LITTLE_ENDIAN_HOST
234     x1 = (x1>>8) | (x1<<8);
235     x2 = (x2>>8) | (x2<<8);
236     x3 = (x3>>8) | (x3<<8);
237     x4 = (x4>>8) | (x4<<8);
238   #endif
239     do {
240         MUL(x1, *key++);
241         x2 += *key++;
242         x3 += *key++;
243         MUL(x4, *key++ );
244
245         s3 = x3;
246         x3 ^= x1;
247         MUL(x3, *key++);
248         s2 = x2;
249         x2 ^=x4;
250         x2 += x3;
251         MUL(x2, *key++);
252         x3 += x2;
253
254         x1 ^= x2;
255         x4 ^= x3;
256
257         x2 ^= s3;
258         x3 ^= s2;
259     } while( --r );
260     MUL(x1, *key++);
261     x3 += *key++;
262     x2 += *key++;
263     MUL(x4, *key);
264
265     out = (u16*)outbuf;
266   #ifdef LITTLE_ENDIAN_HOST
267     *out++ = (x1>>8) | (x1<<8);
268     *out++ = (x3>>8) | (x3<<8);
269     *out++ = (x2>>8) | (x2<<8);
270     *out   = (x4>>8) | (x4<<8);
271   #else
272     *out++ = x1;
273     *out++ = x3;
274     *out++ = x2;
275     *out   = x4;
276   #endif
277   #undef MUL
278 }
279
280
281 static int
282 do_setkey( IDEA_context *c, byte *key, unsigned keylen )
283 {
284     static int initialized = 0;
285
286     if( !initialized ) {
287         initialized = 1;
288         selftest(0);
289     }
290     assert(keylen == 16);
291     c->have_dk = 0;
292     expand_key( key, c->ek );
293     invert_key( c->ek, c->dk );
294     return 0;
295 }
296
297 static void
298 encrypt_block( IDEA_context *c, byte *outbuf, byte *inbuf )
299 {
300     cipher( outbuf, inbuf, c->ek );
301 }
302
303 static void
304 decrypt_block( IDEA_context *c, byte *outbuf, byte *inbuf )
305 {
306     static int initialized;
307
308     if( !initialized ) {
309         initialized = 1;
310         selftest(1);
311     }
312     if( !c->have_dk ) {
313        c->have_dk = 1;
314        invert_key( c->ek, c->dk );
315     }
316     cipher( outbuf, inbuf, c->dk );
317 }
318
319
320 static void
321 selftest( int check_decrypt )
322 {
323 static struct {
324     byte key[16];
325     byte plain[8];
326     byte cipher[8];
327 } test_vectors[] = {
328     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
329         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
330       { 0x00, 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03 },
331       { 0x11, 0xFB, 0xED, 0x2B, 0x01, 0x98, 0x6D, 0xE5 } },
332     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
333         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
334       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
335       { 0x54, 0x0E, 0x5F, 0xEA, 0x18, 0xC2, 0xF8, 0xB1 } },
336     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
337         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
338       { 0x00, 0x19, 0x32, 0x4B, 0x64, 0x7D, 0x96, 0xAF },
339       { 0x9F, 0x0A, 0x0A, 0xB6, 0xE1, 0x0C, 0xED, 0x78 } },
340     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
341         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
342       { 0xF5, 0x20, 0x2D, 0x5B, 0x9C, 0x67, 0x1B, 0x08 },
343       { 0xCF, 0x18, 0xFD, 0x73, 0x55, 0xE2, 0xC5, 0xC5 } },
344     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
345         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
346       { 0xFA, 0xE6, 0xD2, 0xBE, 0xAA, 0x96, 0x82, 0x6E },
347       { 0x85, 0xDF, 0x52, 0x00, 0x56, 0x08, 0x19, 0x3D } },
348     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
349         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
350       { 0x0A, 0x14, 0x1E, 0x28, 0x32, 0x3C, 0x46, 0x50 },
351       { 0x2F, 0x7D, 0xE7, 0x50, 0x21, 0x2F, 0xB7, 0x34 } },
352     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
353         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
354       { 0x05, 0x0A, 0x0F, 0x14, 0x19, 0x1E, 0x23, 0x28 },
355       { 0x7B, 0x73, 0x14, 0x92, 0x5D, 0xE5, 0x9C, 0x09 } },
356     { { 0x00, 0x05, 0x00, 0x0A, 0x00, 0x0F, 0x00, 0x14,
357         0x00, 0x19, 0x00, 0x1E, 0x00, 0x23, 0x00, 0x28 },
358       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
359       { 0x3E, 0xC0, 0x47, 0x80, 0xBE, 0xFF, 0x6E, 0x20 } },
360     { { 0x3A, 0x98, 0x4E, 0x20, 0x00, 0x19, 0x5D, 0xB3,
361         0x2E, 0xE5, 0x01, 0xC8, 0xC4, 0x7C, 0xEA, 0x60 },
362       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
363       { 0x97, 0xBC, 0xD8, 0x20, 0x07, 0x80, 0xDA, 0x86 } },
364     { { 0x00, 0x64, 0x00, 0xC8, 0x01, 0x2C, 0x01, 0x90,
365         0x01, 0xF4, 0x02, 0x58, 0x02, 0xBC, 0x03, 0x20 },
366       { 0x05, 0x32, 0x0A, 0x64, 0x14, 0xC8, 0x19, 0xFA },
367       { 0x65, 0xBE, 0x87, 0xE7, 0xA2, 0x53, 0x8A, 0xED } },
368     { { 0x9D, 0x40, 0x75, 0xC1, 0x03, 0xBC, 0x32, 0x2A,
369         0xFB, 0x03, 0xE7, 0xBE, 0x6A, 0xB3, 0x00, 0x06 },
370       { 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 },
371       { 0xF5, 0xDB, 0x1A, 0xC4, 0x5E, 0x5E, 0xF9, 0xF9 } }
372 };
373     IDEA_context c;
374     byte buffer[8];
375     int i;
376
377     for(i=0; i < DIM(test_vectors); i++ ) {
378         do_setkey( &c, test_vectors[i].key, 16 );
379         if( !check_decrypt ) {
380             encrypt_block( &c, buffer, test_vectors[i].plain );
381             if( memcmp( buffer, test_vectors[i].cipher, 8 ) )
382                 g10_log_fatal("idea encryption (%d) failed\n", i);
383         }
384         else {
385             decrypt_block( &c, buffer, test_vectors[i].cipher );
386             if( memcmp( buffer, test_vectors[i].plain, 8 ) )
387                 g10_log_fatal("idea decryption (%d) failed\n", i);
388         }
389     }
390 }
391
392
393 /****************
394  * Return some information about the algorithm.  We need algo here to
395  * distinguish different flavors of the algorithm.
396  * Returns: A pointer to string describing the algorithm or NULL if
397  *          the ALGO is invalid.
398  */
399 const char *
400 idea_get_info( int algo, size_t *keylen,
401                    size_t *blocksize, size_t *contextsize,
402                    int  (**r_setkey)( void *c, byte *key, unsigned keylen ),
403                    void (**r_encrypt)( void *c, byte *outbuf, byte *inbuf ),
404                    void (**r_decrypt)( void *c, byte *outbuf, byte *inbuf )
405                  )
406 {
407     *keylen = 128;
408     *blocksize = 8;
409     *contextsize = sizeof(IDEA_context);
410     *r_setkey = FNCCAST_SETKEY(do_setkey);
411     *r_encrypt= FNCCAST_CRYPT(encrypt_block);
412     *r_decrypt= FNCCAST_CRYPT(decrypt_block);
413     if( algo == 1 )
414         return "IDEA";
415     return NULL;
416 }
417
418
419
420 const char * const gnupgext_version = "IDEA ($Revision: 1.11 $)";
421
422 static struct {
423     int class;
424     int version;
425     int  value;
426     void (*func)(void);
427 } func_table[] = {
428     { 20, 1, 0, (void(*)(void))idea_get_info },
429     { 21, 1, 1 },
430 };
431
432
433
434 /****************
435  * Enumerate the names of the functions together with informations about
436  * this function. Set sequence to an integer with a initial value of 0 and
437  * do not change it.
438  * If what is 0 all kind of functions are returned.
439  * Return values: class := class of function:
440  *                         10 = message digest algorithm info function
441  *                         11 = integer with available md algorithms
442  *                         20 = cipher algorithm info function
443  *                         21 = integer with available cipher algorithms
444  *                         30 = public key algorithm info function
445  *                         31 = integer with available pubkey algorithms
446  *                version = interface version of the function/pointer
447  *                          (currently this is 1 for all functions)
448  */
449 void *
450 gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
451 {
452     void *ret;
453     int i = *sequence;
454
455     do {
456         if( i >= DIM(func_table) || i < 0 ) {
457             return NULL;
458         }
459         *class = func_table[i].class;
460         *vers  = func_table[i].version;
461         switch( *class ) {
462           case 11:
463           case 21:
464           case 31:
465             ret = &func_table[i].value;
466             break;
467           default:
468             ret = func_table[i].func;
469             break;
470         }
471         i++;
472     } while( what && what != *class );
473
474     *sequence = i;
475     return ret;
476 }