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