compress stuff implemented
[libgcrypt.git] / cipher / idea.c
1 /* idea.c  -  IDEA function
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * ATTENTION: This code patented and needs a license for any commercial use.
5  *
6  * The code herin is take from:
7  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
8  *   ISBN 0-471-11709-9. .
9  *
10  * This file is part of G10.
11  *
12  * G10 is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU General Public License as published by
14  * the Free Software Foundation; either version 2 of the License, or
15  * (at your option) any later version.
16  *
17  * G10 is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License
23  * along with this program; if not, write to the Free Software
24  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
25  */
26
27 #include <config.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include "util.h"
32 #include "types.h"
33 #include "idea.h"
34
35
36
37 static u16
38 mul_inv( u16 x )
39 {
40     u16 t0, t1;
41     u16 q, y;
42
43     if( x < 2 )
44         return x;
45     t1 = 0x10001L / x;
46     y =  0x10001L % x;
47     if( y == 1 )
48         return (1-t1) & 0xffff;
49
50     t0 = 1;
51     do {
52         q = x / y;
53         x = x % y;
54         t0 += q * t1;
55         if( x == 1 )
56             return t0;
57         q = y / x;
58         y = y % x;
59         t1 += q * t0;
60     } while( y != 1 );
61     return (1-t1) & 0xffff;
62 }
63
64
65
66 static void
67 expand_key( byte *userkey, u16 *ek )
68 {
69     int i,j;
70
71     for(j=0; j < 8; j++ ) {
72         ek[j] = (*userkey << 8) + userkey[1];
73         userkey += 2;
74     }
75     for(i=0; j < IDEA_KEYLEN; j++ ) {
76         i++;
77         ek[i+7] = ek[i&7] << 9 | ek[(i+1)&7] >> 7;
78         ek += i & 8;
79         i &= 7;
80     }
81 }
82
83
84 static void
85 invert_key( u16 *ek, u16 dk[IDEA_KEYLEN] )
86 {
87     int i;
88     u16 t1, t2, t3;
89     u16 temp[IDEA_KEYLEN];
90     u16 *p = temp + IDEA_KEYLEN;
91
92     t1 = mul_inv( *ek++ );
93     t2 = -*ek++;
94     t3 = -*ek++;
95     *--p = mul_inv( *ek++ );
96     *--p = t3;
97     *--p = t2;
98     *--p = t1;
99
100     for(i=0; i < IDEA_ROUNDS-1; i++ ) {
101         t1 = *ek++;
102         *--p = *ek++;
103         *--p = t1;
104
105         t1 = mul_inv( *ek++ );
106         t2 = -*ek++;
107         t3 = -*ek++;
108         *--p = mul_inv( *ek++ );
109         *--p = t3;
110         *--p = t2;
111         *--p = t1;
112     }
113     t1 = *ek++;
114     *--p = *ek++;
115     *--p = t1;
116
117     t1 = mul_inv( *ek++ );
118     t2 = -*ek++;
119     t3 = -*ek++;
120     *--p = mul_inv( *ek++ );
121     *--p = t3;
122     *--p = t2;
123     *--p = t1;
124     memcpy(dk, temp, sizeof(temp) );
125     memset(temp, 0, sizeof(temp) );  /* burn temp */
126 }
127
128
129 static void
130 cipher( byte *outbuf, byte *inbuf, u16 *key )
131 {
132     u16 x1, x2, x3,x4, s2, s3;
133     u16 *in, *out;
134     int r = IDEA_ROUNDS;
135   #define MUL(x,y) \
136         do {u16 _t16; u32 _t32;                     \
137             if( (_t16 = (y)) ) {                    \
138                 if( (x = (x)&0xffff) ) {            \
139                     _t32 = (u32)x * _t16;           \
140                     x = _t32 & 0xffff;              \
141                     _t16 = _t32 >> 16;              \
142                     x = ((x)-_t16) + (x<_t16?1:0);  \
143                 }                                   \
144                 else {                              \
145                     x = 1 - _t16;                   \
146                 }                                   \
147             }                                       \
148             else {                                  \
149                 x = 1 - x;                          \
150             }                                       \
151         } while(0)
152
153     in = (u16*)inbuf;
154     x1 = *in++;
155     x2 = *in++;
156     x3 = *in++;
157     x4 = *in;
158   #ifdef HAVE_LITTLE_ENDIAN
159     x1 = (x1>>8) | (x1<<8);
160     x2 = (x2>>8) | (x2<<8);
161     x3 = (x3>>8) | (x3<<8);
162     x4 = (x4>>8) | (x4<<8);
163   #endif
164     do {
165         MUL(x1, *key++);
166         x2 += *key++;
167         x3 += *key++;
168         MUL(x4, *key++ );
169
170         s3 = x3;
171         x3 ^= x1;
172         MUL(x3, *key++);
173         s2 = x2;
174         x2 ^=x4;
175         x2 += x3;
176         MUL(x2, *key++);
177         x3 += x2;
178
179         x1 ^= x2;
180         x4 ^= x3;
181
182         x2 ^= s3;
183         x3 ^= s2;
184     } while( --r );
185     MUL(x1, *key++);
186     x3 += *key++;
187     x2 += *key++;
188     MUL(x4, *key);
189
190     out = (u16*)outbuf;
191   #ifdef HAVE_LITTLE_ENDIAN
192     *out++ = (x1>>8) | (x1<<8);
193     *out++ = (x3>>8) | (x3<<8);
194     *out++ = (x2>>8) | (x2<<8);
195     *out   = (x4>>8) | (x4<<8);
196   #else
197     *out++ = x1;
198     *out++ = x3;
199     *out++ = x2;
200     *out   = x4;
201   #endif
202   #undef MUL
203 }
204
205
206 void
207 idea_setkey( IDEA_context *c, byte *key )
208 {
209     expand_key( key, c->ek );
210     invert_key( c->ek, c->dk );
211 }
212
213 void
214 idea_setiv( IDEA_context *c, byte *iv )
215 {
216     if( iv )
217         memcpy( c->iv, iv, IDEA_BLOCKSIZE );
218     else
219         memset( c->iv, 0, IDEA_BLOCKSIZE );
220     c->nleft = 0;
221 }
222
223
224 void
225 idea_encode( IDEA_context *c, byte *outbuf, byte *inbuf, unsigned nblocks )
226 {
227     unsigned n;
228
229     for(n=0; n < nblocks; n++ ) {
230         cipher( outbuf, inbuf, c->ek );
231         inbuf  += 8;
232         outbuf += 8;
233     }
234 }
235
236
237 void
238 idea_decode( IDEA_context *c, byte *outbuf, byte *inbuf, unsigned nblocks )
239 {
240     unsigned n;
241
242     for(n=0; n < nblocks; n++ ) {
243         cipher( outbuf, inbuf, c->dk );
244         inbuf  += 8;
245         outbuf += 8;
246     }
247 }
248
249
250 static void
251 cfbshift( byte *iv, byte *buf, unsigned count)
252 {
253     unsigned n;
254
255     if( count ) {
256         for( n = IDEA_BLOCKSIZE - count; n; n-- )
257             *iv++ = iv[count];
258         for( ; count; count-- )
259             *iv++ = *buf++;
260     }
261 }
262
263
264 /****************
265  * FIXME: Make use of bigger chunks
266  */
267 static void
268 xorblock( byte *out, byte *a, byte *b, unsigned count )
269 {
270     for( ; count ; count--, a++, b++ )
271         *out++ = *a ^ *b ;
272 }
273
274
275 void
276 idea_encode_cfb( IDEA_context *c, byte *outbuf, byte *inbuf, unsigned nbytes)
277 {
278     byte temp[IDEA_BLOCKSIZE];
279
280     while( nbytes >= IDEA_BLOCKSIZE ) {
281         cipher( temp, c->iv, c->ek );
282         xorblock( outbuf, inbuf, temp, IDEA_BLOCKSIZE);
283         cfbshift( c->iv, outbuf, IDEA_BLOCKSIZE );
284         nbytes -= IDEA_BLOCKSIZE;
285         inbuf += IDEA_BLOCKSIZE;
286         outbuf += IDEA_BLOCKSIZE;
287     }
288     if( nbytes ) {
289         cipher( temp, c->iv, c->ek );
290         xorblock( outbuf, inbuf, temp, nbytes );
291         cfbshift( c->iv, outbuf, nbytes );
292     }
293 }
294
295
296 void
297 idea_decode_cfb( IDEA_context *c, byte *outbuf, byte *inbuf, unsigned nbytes)
298 {
299     byte t, *ivptr;
300
301     ivptr = c->iv + IDEA_BLOCKSIZE - c->nleft;
302     if( nbytes <= c->nleft ) {
303         c->nleft -= nbytes;
304         for( ; nbytes ; nbytes--, ivptr++, inbuf++ ) {
305             t = *ivptr;
306             *outbuf++ = t ^ (*ivptr = *inbuf) ;
307         }
308         return;
309     }
310
311     nbytes -= c->nleft;
312     for( ; c->nleft ; c->nleft--, ivptr++, inbuf++ ) {
313         t = *ivptr;
314         *outbuf++ = t ^ (*ivptr = *inbuf) ;
315     }
316
317     while( nbytes >= IDEA_BLOCKSIZE ) {
318         memcpy(c->lastcipher, c->iv, IDEA_BLOCKSIZE);
319         cipher( c->iv, c->iv, c->ek );
320         c->nleft = IDEA_BLOCKSIZE;
321         nbytes -= IDEA_BLOCKSIZE;
322         ivptr = c->iv;
323         for( ; c->nleft; c->nleft--, ivptr++, inbuf++ ) {
324             t = *ivptr;
325             *outbuf++ = t ^ (*ivptr = *inbuf) ;
326         }
327     }
328     memcpy(c->lastcipher, c->iv, IDEA_BLOCKSIZE);
329     cipher( c->iv, c->iv, c->ek );
330     c->nleft = IDEA_BLOCKSIZE - nbytes;
331     ivptr = c->iv;
332     for( ; nbytes; nbytes--, ivptr++, inbuf++ ) {
333         t = *ivptr;
334         *outbuf++ = t ^ (*ivptr = *inbuf) ;
335     }
336 }
337
338
339 /****************
340  * This is used for the special way IDEA CFB is used in PGP
341  */
342 void
343 idea_sync_cfb( IDEA_context *c )
344 {
345     if( c->nleft ) {
346         memmove(c->iv + c->nleft, c->iv, IDEA_BLOCKSIZE - c->nleft );
347         memcpy(c->iv, c->lastcipher + IDEA_BLOCKSIZE - c->nleft, c->nleft);
348         c->nleft = 0;
349     }
350 }
351
352