Add support for the IDEA cipher.
[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  * Patents on IDEA have expired:
26  *   Europe: EP0482154 on 2011-05-16,
27  *   Japan:  JP3225440 on 2011-05-16,
28  *   U.S.:   5,214,703 on 2012-01-07.
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
40
41 #include <config.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <assert.h>
46
47 #include "types.h"  /* for byte and u32 typedefs */
48 #include "g10lib.h"
49 #include "cipher.h"
50
51
52 #define FNCCAST_SETKEY(f)  ((int(*)(void*, byte*, unsigned int))(f))
53 #define FNCCAST_CRYPT(f)   ((void(*)(void*, byte*, byte*))(f))
54
55 #define IDEA_KEYSIZE 16
56 #define IDEA_BLOCKSIZE 8
57 #define IDEA_ROUNDS 8
58 #define IDEA_KEYLEN (6*IDEA_ROUNDS+4)
59
60 typedef struct {
61     u16 ek[IDEA_KEYLEN];
62     u16 dk[IDEA_KEYLEN];
63     int have_dk;
64 } IDEA_context;
65
66
67 static u16
68 mul_inv( u16 x )
69 {
70     u16 t0, t1;
71     u16 q, y;
72
73     if( x < 2 )
74         return x;
75     t1 = 0x10001L / x;
76     y =  0x10001L % x;
77     if( y == 1 )
78         return (1-t1) & 0xffff;
79
80     t0 = 1;
81     do {
82         q = x / y;
83         x = x % y;
84         t0 += q * t1;
85         if( x == 1 )
86             return t0;
87         q = y / x;
88         y = y % x;
89         t1 += q * t0;
90     } while( y != 1 );
91     return (1-t1) & 0xffff;
92 }
93
94
95
96 static void
97 expand_key( const byte *userkey, u16 *ek )
98 {
99     int i,j;
100
101     for(j=0; j < 8; j++ ) {
102         ek[j] = (*userkey << 8) + userkey[1];
103         userkey += 2;
104     }
105     for(i=0; j < IDEA_KEYLEN; j++ ) {
106         i++;
107         ek[i+7] = ek[i&7] << 9 | ek[(i+1)&7] >> 7;
108         ek += i & 8;
109         i &= 7;
110     }
111 }
112
113
114 static void
115 invert_key( u16 *ek, u16 dk[IDEA_KEYLEN] )
116 {
117     int i;
118     u16 t1, t2, t3;
119     u16 temp[IDEA_KEYLEN];
120     u16 *p = temp + IDEA_KEYLEN;
121
122     t1 = mul_inv( *ek++ );
123     t2 = -*ek++;
124     t3 = -*ek++;
125     *--p = mul_inv( *ek++ );
126     *--p = t3;
127     *--p = t2;
128     *--p = t1;
129
130     for(i=0; i < IDEA_ROUNDS-1; i++ ) {
131         t1 = *ek++;
132         *--p = *ek++;
133         *--p = t1;
134
135         t1 = mul_inv( *ek++ );
136         t2 = -*ek++;
137         t3 = -*ek++;
138         *--p = mul_inv( *ek++ );
139         *--p = t2;
140         *--p = t3;
141         *--p = t1;
142     }
143     t1 = *ek++;
144     *--p = *ek++;
145     *--p = t1;
146
147     t1 = mul_inv( *ek++ );
148     t2 = -*ek++;
149     t3 = -*ek++;
150     *--p = mul_inv( *ek++ );
151     *--p = t3;
152     *--p = t2;
153     *--p = t1;
154     memcpy(dk, temp, sizeof(temp) );
155     memset(temp, 0, sizeof(temp) );  /* burn temp */
156 }
157
158
159 static void
160 cipher( byte *outbuf, const byte *inbuf, u16 *key )
161 {
162     u16 x1, x2, x3,x4, s2, s3;
163     u16 *in, *out;
164     int r = IDEA_ROUNDS;
165   #define MUL(x,y) \
166         do {u16 _t16; u32 _t32;                     \
167             if( (_t16 = (y)) ) {                    \
168                 if( (x = (x)&0xffff) ) {            \
169                     _t32 = (u32)x * _t16;           \
170                     x = _t32 & 0xffff;              \
171                     _t16 = _t32 >> 16;              \
172                     x = ((x)-_t16) + (x<_t16?1:0);  \
173                 }                                   \
174                 else {                              \
175                     x = 1 - _t16;                   \
176                 }                                   \
177             }                                       \
178             else {                                  \
179                 x = 1 - x;                          \
180             }                                       \
181         } while(0)
182
183     in = (u16*)inbuf;
184     x1 = *in++;
185     x2 = *in++;
186     x3 = *in++;
187     x4 = *in;
188   #ifndef WORDS_BIGENDIAN
189     x1 = (x1>>8) | (x1<<8);
190     x2 = (x2>>8) | (x2<<8);
191     x3 = (x3>>8) | (x3<<8);
192     x4 = (x4>>8) | (x4<<8);
193   #endif
194     do {
195         MUL(x1, *key++);
196         x2 += *key++;
197         x3 += *key++;
198         MUL(x4, *key++ );
199
200         s3 = x3;
201         x3 ^= x1;
202         MUL(x3, *key++);
203         s2 = x2;
204         x2 ^=x4;
205         x2 += x3;
206         MUL(x2, *key++);
207         x3 += x2;
208
209         x1 ^= x2;
210         x4 ^= x3;
211
212         x2 ^= s3;
213         x3 ^= s2;
214     } while( --r );
215     MUL(x1, *key++);
216     x3 += *key++;
217     x2 += *key++;
218     MUL(x4, *key);
219
220     out = (u16*)outbuf;
221   #ifndef WORDS_BIGENDIAN
222     *out++ = (x1>>8) | (x1<<8);
223     *out++ = (x3>>8) | (x3<<8);
224     *out++ = (x2>>8) | (x2<<8);
225     *out   = (x4>>8) | (x4<<8);
226   #else
227     *out++ = x1;
228     *out++ = x3;
229     *out++ = x2;
230     *out   = x4;
231   #endif
232   #undef MUL
233 }
234
235
236 static int
237 do_setkey( IDEA_context *c, const byte *key, unsigned int keylen )
238 {
239 #if 0
240     static int initialized = 0;
241
242     if( !initialized ) {
243         initialized = 1;
244         selftest(0);
245     }
246 #endif
247     assert(keylen == 16);
248     c->have_dk = 0;
249     expand_key( key, c->ek );
250     invert_key( c->ek, c->dk );
251     return 0;
252 }
253
254 static gcry_err_code_t
255 idea_setkey (void *context, const byte *key, unsigned int keylen)
256 {
257     IDEA_context *ctx = context;
258     int rc = do_setkey (ctx, key, keylen);
259     _gcry_burn_stack (23+6*sizeof(void*));
260     return rc;
261 }
262
263 static void
264 encrypt_block( IDEA_context *c, byte *outbuf, const byte *inbuf )
265 {
266     cipher( outbuf, inbuf, c->ek );
267 }
268
269 static void
270 idea_encrypt (void *context, byte *out, const byte *in)
271 {
272     IDEA_context *ctx = context;
273     encrypt_block (ctx, out, in);
274     _gcry_burn_stack (24+3*sizeof (void*));
275 }
276
277 static void
278 decrypt_block( IDEA_context *c, byte *outbuf, const byte *inbuf )
279 {
280 #if 0
281     static int initialized;
282
283     if( !initialized ) {
284         initialized = 1;
285         selftest(1);
286     }
287 #endif
288     if( !c->have_dk ) {
289        c->have_dk = 1;
290        invert_key( c->ek, c->dk );
291     }
292     cipher( outbuf, inbuf, c->dk );
293 }
294
295 static void
296 idea_decrypt (void *context, byte *out, const byte *in)
297 {
298     IDEA_context *ctx = context;
299     decrypt_block (ctx, out, in);
300     _gcry_burn_stack (24+3*sizeof (void*));
301 }
302
303
304 #if 0
305 static void
306 selftest( int check_decrypt )
307 {
308 static struct {
309     byte key[16];
310     byte plain[8];
311     byte cipher[8];
312 } test_vectors[] = {
313     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
314         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
315       { 0x00, 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03 },
316       { 0x11, 0xFB, 0xED, 0x2B, 0x01, 0x98, 0x6D, 0xE5 } },
317     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
318         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
319       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
320       { 0x54, 0x0E, 0x5F, 0xEA, 0x18, 0xC2, 0xF8, 0xB1 } },
321     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
322         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
323       { 0x00, 0x19, 0x32, 0x4B, 0x64, 0x7D, 0x96, 0xAF },
324       { 0x9F, 0x0A, 0x0A, 0xB6, 0xE1, 0x0C, 0xED, 0x78 } },
325     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
326         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
327       { 0xF5, 0x20, 0x2D, 0x5B, 0x9C, 0x67, 0x1B, 0x08 },
328       { 0xCF, 0x18, 0xFD, 0x73, 0x55, 0xE2, 0xC5, 0xC5 } },
329     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
330         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
331       { 0xFA, 0xE6, 0xD2, 0xBE, 0xAA, 0x96, 0x82, 0x6E },
332       { 0x85, 0xDF, 0x52, 0x00, 0x56, 0x08, 0x19, 0x3D } },
333     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
334         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
335       { 0x0A, 0x14, 0x1E, 0x28, 0x32, 0x3C, 0x46, 0x50 },
336       { 0x2F, 0x7D, 0xE7, 0x50, 0x21, 0x2F, 0xB7, 0x34 } },
337     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
338         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
339       { 0x05, 0x0A, 0x0F, 0x14, 0x19, 0x1E, 0x23, 0x28 },
340       { 0x7B, 0x73, 0x14, 0x92, 0x5D, 0xE5, 0x9C, 0x09 } },
341     { { 0x00, 0x05, 0x00, 0x0A, 0x00, 0x0F, 0x00, 0x14,
342         0x00, 0x19, 0x00, 0x1E, 0x00, 0x23, 0x00, 0x28 },
343       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
344       { 0x3E, 0xC0, 0x47, 0x80, 0xBE, 0xFF, 0x6E, 0x20 } },
345     { { 0x3A, 0x98, 0x4E, 0x20, 0x00, 0x19, 0x5D, 0xB3,
346         0x2E, 0xE5, 0x01, 0xC8, 0xC4, 0x7C, 0xEA, 0x60 },
347       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
348       { 0x97, 0xBC, 0xD8, 0x20, 0x07, 0x80, 0xDA, 0x86 } },
349     { { 0x00, 0x64, 0x00, 0xC8, 0x01, 0x2C, 0x01, 0x90,
350         0x01, 0xF4, 0x02, 0x58, 0x02, 0xBC, 0x03, 0x20 },
351       { 0x05, 0x32, 0x0A, 0x64, 0x14, 0xC8, 0x19, 0xFA },
352       { 0x65, 0xBE, 0x87, 0xE7, 0xA2, 0x53, 0x8A, 0xED } },
353     { { 0x9D, 0x40, 0x75, 0xC1, 0x03, 0xBC, 0x32, 0x2A,
354         0xFB, 0x03, 0xE7, 0xBE, 0x6A, 0xB3, 0x00, 0x06 },
355       { 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 },
356       { 0xF5, 0xDB, 0x1A, 0xC4, 0x5E, 0x5E, 0xF9, 0xF9 } }
357 };
358     IDEA_context c;
359     byte buffer[8];
360     int i;
361
362     for(i=0; i < DIM(test_vectors); i++ ) {
363         do_setkey( &c, test_vectors[i].key, 16 );
364         if( !check_decrypt ) {
365             encrypt_block( &c, buffer, test_vectors[i].plain );
366             if( memcmp( buffer, test_vectors[i].cipher, 8 ) )
367                 g10_log_fatal("idea encryption (%d) failed\n", i);
368         }
369         else {
370             decrypt_block( &c, buffer, test_vectors[i].cipher );
371             if( memcmp( buffer, test_vectors[i].plain, 8 ) )
372                 g10_log_fatal("idea decryption (%d) failed\n", i);
373         }
374     }
375 }
376 #endif
377
378
379 gcry_cipher_spec_t _gcry_cipher_spec_idea =
380 {
381     "IDEA", NULL, NULL, IDEA_BLOCKSIZE, 128,
382     sizeof (IDEA_context),
383     idea_setkey, idea_encrypt, idea_decrypt
384 };