See ChangeLog: Sat Nov 13 17:44:23 CET 1999 Werner Koch
[gnupg.git] / cipher / elgamal.c
1 /* elgamal.c  -  ElGamal Public Key encryption
2  *      Copyright (C) 1998 Free Software Foundation, Inc.
3  *
4  * For a description of the algorithm, see:
5  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
6  *   ISBN 0-471-11709-9. Pages 476 ff.
7  *
8  * This file is part of GnuPG.
9  *
10  * GnuPG 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  * GnuPG 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 "g10lib.h"
30 #include "util.h"
31 #include "mpi.h"
32 #include "cipher.h"
33 #include "elgamal.h"
34
35 typedef struct {
36     MPI p;          /* prime */
37     MPI g;          /* group generator */
38     MPI y;          /* g^x mod p */
39 } ELG_public_key;
40
41
42 typedef struct {
43     MPI p;          /* prime */
44     MPI g;          /* group generator */
45     MPI y;          /* g^x mod p */
46     MPI x;          /* secret exponent */
47 } ELG_secret_key;
48
49
50 static void test_keys( ELG_secret_key *sk, unsigned nbits );
51 static MPI gen_k( MPI p );
52 static void generate( ELG_secret_key *sk, unsigned nbits, MPI **factors );
53 static int  check_secret_key( ELG_secret_key *sk );
54 static void encrypt(MPI a, MPI b, MPI input, ELG_public_key *pkey );
55 static void decrypt(MPI output, MPI a, MPI b, ELG_secret_key *skey );
56 static void sign(MPI a, MPI b, MPI input, ELG_secret_key *skey);
57 static int  verify(MPI a, MPI b, MPI input, ELG_public_key *pkey);
58
59
60 static void
61 progress( int c )
62 {
63     fputc( c, stderr );
64 }
65
66
67 static void
68 test_keys( ELG_secret_key *sk, unsigned nbits )
69 {
70     ELG_public_key pk;
71     MPI test = mpi_alloc( 0 );
72     MPI out1_a = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
73     MPI out1_b = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
74     MPI out2 = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
75
76     pk.p = sk->p;
77     pk.g = sk->g;
78     pk.y = sk->y;
79
80     /*mpi_set_bytes( test, nbits, get_random_byte, 0 );*/
81     {   char *p = get_random_bits( nbits, 0, 0 );
82         mpi_set_buffer( test, p, (nbits+7)/8, 0 );
83         g10_free(p);
84     }
85
86     encrypt( out1_a, out1_b, test, &pk );
87     decrypt( out2, out1_a, out1_b, sk );
88     if( mpi_cmp( test, out2 ) )
89         log_fatal("ElGamal operation: encrypt, decrypt failed\n");
90
91     sign( out1_a, out1_b, test, sk );
92     if( !verify( out1_a, out1_b, test, &pk ) )
93         log_fatal("ElGamal operation: sign, verify failed\n");
94
95     mpi_free( test );
96     mpi_free( out1_a );
97     mpi_free( out1_b );
98     mpi_free( out2 );
99 }
100
101
102 /****************
103  * generate a random secret exponent k from prime p, so
104  * that k is relatively prime to p-1
105  */
106 static MPI
107 gen_k( MPI p )
108 {
109     MPI k = mpi_alloc_secure( 0 );
110     MPI temp = mpi_alloc( mpi_get_nlimbs(p) );
111     MPI p_1 = mpi_copy(p);
112     unsigned int nbits = mpi_get_nbits(p);
113     unsigned int nbytes = (nbits+7)/8;
114     char *rndbuf = NULL;
115
116     if( DBG_CIPHER )
117         log_debug("choosing a random k ");
118     mpi_sub_ui( p_1, p, 1);
119     for(;;) {
120         if( DBG_CIPHER )
121             progress('.');
122         if( !rndbuf || nbits < 32 ) {
123             g10_free(rndbuf);
124             rndbuf = get_random_bits( nbits, 1, 1 );
125         }
126         else { /* change only some of the higher bits */
127             /* we could imporove this by directly requesting more memory
128              * at the first call to get_random_bits() and use this the here
129              * maybe it is easier to do this directly in random.c */
130             char *pp = get_random_bits( 32, 1, 1 );
131             memcpy( rndbuf,pp, 4 );
132             g10_free(pp);
133         }
134         mpi_set_buffer( k, rndbuf, nbytes, 0 );
135
136         for(;;) {
137             /* make sure that the number is of the exact lenght */
138             if( mpi_test_bit( k, nbits-1 ) )
139                 mpi_set_highbit( k, nbits-1 );
140             else {
141                 mpi_set_highbit( k, nbits-1 );
142                 mpi_clear_bit( k, nbits-1 );
143             }
144             if( !(mpi_cmp( k, p_1 ) < 0) ) {  /* check: k < (p-1) */
145                 if( DBG_CIPHER )
146                     progress('+');
147                 break; /* no  */
148             }
149             if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */
150                 if( DBG_CIPHER )
151                     progress('-');
152                 break; /* no */
153             }
154             if( mpi_gcd( temp, k, p_1 ) )
155                 goto found;  /* okay, k is relatively prime to (p-1) */
156             mpi_add_ui( k, k, 1 );
157         }
158     }
159   found:
160     g10_free(rndbuf);
161     if( DBG_CIPHER )
162         progress('\n');
163     mpi_free(p_1);
164     mpi_free(temp);
165
166     return k;
167 }
168
169 /****************
170  * Generate a key pair with a key of size NBITS
171  * Returns: 2 structures filles with all needed values
172  *          and an array with n-1 factors of (p-1)
173  */
174 static void
175 generate(  ELG_secret_key *sk, unsigned nbits, MPI **ret_factors )
176 {
177     MPI p;    /* the prime */
178     MPI p_min1;
179     MPI g;
180     MPI x;    /* the secret exponent */
181     MPI y;
182     MPI temp;
183     unsigned qbits;
184     byte *rndbuf;
185
186     p_min1 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
187     temp   = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
188     if( nbits < 512 )
189         qbits = 120;
190     else if( nbits <= 1024 )
191         qbits = 160;
192     else if( nbits <= 2048 )
193         qbits = 200;
194     else
195         qbits = 240;
196     g = mpi_alloc(1);
197     p = generate_elg_prime( 0, nbits, qbits, g, ret_factors );
198     mpi_sub_ui(p_min1, p, 1);
199
200
201     /* select a random number which has these properties:
202      *   0 < x < p-1
203      * This must be a very good random number because this is the
204      * secret part.  The prime is public and may be shared anyway,
205      * so a random generator level of 1 is used for the prime.
206      */
207     x = mpi_alloc_secure( nbits/BITS_PER_MPI_LIMB );
208     if( DBG_CIPHER )
209         log_debug("choosing a random x ");
210     rndbuf = NULL;
211     do {
212         if( DBG_CIPHER )
213             progress('.');
214         if( rndbuf ) { /* change only some of the higher bits */
215             if( nbits < 16 ) {/* should never happen ... */
216                 g10_free(rndbuf);
217                 rndbuf = get_random_bits( nbits, 2, 1 );
218             }
219             else {
220                 char *r = get_random_bits( 16, 2, 1 );
221                 memcpy(rndbuf, r, 16/8 );
222                 g10_free(r);
223             }
224         }
225         else
226             rndbuf = get_random_bits( nbits, 2, 1 );
227         mpi_set_buffer( x, rndbuf, (nbits+7)/8, 0 );
228         mpi_clear_highbit( x, nbits+1 );
229     } while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, p_min1 )<0 ) );
230     g10_free(rndbuf);
231
232     y = mpi_alloc(nbits/BITS_PER_MPI_LIMB);
233     mpi_powm( y, g, x, p );
234
235     if( DBG_CIPHER ) {
236         progress('\n');
237         log_mpidump("elg  p= ", p );
238         log_mpidump("elg  g= ", g );
239         log_mpidump("elg  y= ", y );
240         log_mpidump("elg  x= ", x );
241     }
242
243     /* copy the stuff to the key structures */
244     sk->p = p;
245     sk->g = g;
246     sk->y = y;
247     sk->x = x;
248
249     /* now we can test our keys (this should never fail!) */
250     test_keys( sk, nbits - 64 );
251
252     mpi_free( p_min1 );
253     mpi_free( temp   );
254 }
255
256
257 /****************
258  * Test whether the secret key is valid.
259  * Returns: if this is a valid key.
260  */
261 static int
262 check_secret_key( ELG_secret_key *sk )
263 {
264     int rc;
265     MPI y = mpi_alloc( mpi_get_nlimbs(sk->y) );
266
267     mpi_powm( y, sk->g, sk->x, sk->p );
268     rc = !mpi_cmp( y, sk->y );
269     mpi_free( y );
270     return rc;
271 }
272
273
274 static void
275 encrypt(MPI a, MPI b, MPI input, ELG_public_key *pkey )
276 {
277     MPI k;
278
279     /* Note: maybe we should change the interface, so that it
280      * is possible to check that input is < p and return an
281      * error code.
282      */
283
284     k = gen_k( pkey->p );
285     mpi_powm( a, pkey->g, k, pkey->p );
286     /* b = (y^k * input) mod p
287      *   = ((y^k mod p) * (input mod p)) mod p
288      * and because input is < p
289      *   = ((y^k mod p) * input) mod p
290      */
291     mpi_powm( b, pkey->y, k, pkey->p );
292     mpi_mulm( b, b, input, pkey->p );
293   #if 0
294     if( DBG_CIPHER ) {
295         log_mpidump("elg encrypted y= ", pkey->y);
296         log_mpidump("elg encrypted p= ", pkey->p);
297         log_mpidump("elg encrypted k= ", k);
298         log_mpidump("elg encrypted M= ", input);
299         log_mpidump("elg encrypted a= ", a);
300         log_mpidump("elg encrypted b= ", b);
301     }
302   #endif
303     mpi_free(k);
304 }
305
306
307
308
309 static void
310 decrypt(MPI output, MPI a, MPI b, ELG_secret_key *skey )
311 {
312     MPI t1 = mpi_alloc_secure( mpi_get_nlimbs( skey->p ) );
313
314     /* output = b/(a^x) mod p */
315
316     mpi_powm( t1, a, skey->x, skey->p );
317     mpi_invm( t1, t1, skey->p );
318     mpi_mulm( output, b, t1, skey->p );
319   #if 0
320     if( DBG_CIPHER ) {
321         log_mpidump("elg decrypted x= ", skey->x);
322         log_mpidump("elg decrypted p= ", skey->p);
323         log_mpidump("elg decrypted a= ", a);
324         log_mpidump("elg decrypted b= ", b);
325         log_mpidump("elg decrypted M= ", output);
326     }
327   #endif
328     mpi_free(t1);
329 }
330
331
332 /****************
333  * Make an Elgamal signature out of INPUT
334  */
335
336 static void
337 sign(MPI a, MPI b, MPI input, ELG_secret_key *skey )
338 {
339     MPI k;
340     MPI t   = mpi_alloc( mpi_get_nlimbs(a) );
341     MPI inv = mpi_alloc( mpi_get_nlimbs(a) );
342     MPI p_1 = mpi_copy(skey->p);
343
344    /*
345     * b = (t * inv) mod (p-1)
346     * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
347     * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
348     *
349     */
350     mpi_sub_ui(p_1, p_1, 1);
351     k = gen_k( skey->p );
352     mpi_powm( a, skey->g, k, skey->p );
353     mpi_mul(t, skey->x, a );
354     mpi_subm(t, input, t, p_1 );
355     while( mpi_is_neg(t) ) {
356         BUG();  /* That is nonsense code - left over from a very early test?*/
357         mpi_add(t, t, p_1);
358     }
359     mpi_invm(inv, k, p_1 );
360     mpi_mulm(b, t, inv, p_1 );
361
362   #if 0
363     if( DBG_CIPHER ) {
364         log_mpidump("elg sign p= ", skey->p);
365         log_mpidump("elg sign g= ", skey->g);
366         log_mpidump("elg sign y= ", skey->y);
367         log_mpidump("elg sign x= ", skey->x);
368         log_mpidump("elg sign k= ", k);
369         log_mpidump("elg sign M= ", input);
370         log_mpidump("elg sign a= ", a);
371         log_mpidump("elg sign b= ", b);
372     }
373   #endif
374     mpi_free(k);
375     mpi_free(t);
376     mpi_free(inv);
377     mpi_free(p_1);
378 }
379
380
381 /****************
382  * Returns true if the signature composed of A and B is valid.
383  */
384 static int
385 verify(MPI a, MPI b, MPI input, ELG_public_key *pkey )
386 {
387     int rc;
388     MPI t1;
389     MPI t2;
390     MPI base[4];
391     MPI exp[4];
392
393     if( !(mpi_cmp_ui( a, 0 ) > 0 && mpi_cmp( a, pkey->p ) < 0) )
394         return 0; /* assertion  0 < a < p  failed */
395
396     t1 = mpi_alloc( mpi_get_nlimbs(a) );
397     t2 = mpi_alloc( mpi_get_nlimbs(a) );
398
399   #if 0
400     /* t1 = (y^a mod p) * (a^b mod p) mod p */
401     mpi_powm( t1, pkey->y, a, pkey->p );
402     mpi_powm( t2, a, b, pkey->p );
403     mpi_mulm( t1, t1, t2, pkey->p );
404
405     /* t2 = g ^ input mod p */
406     mpi_powm( t2, pkey->g, input, pkey->p );
407
408     rc = !mpi_cmp( t1, t2 );
409   #elif 0
410     /* t1 = (y^a mod p) * (a^b mod p) mod p */
411     base[0] = pkey->y; exp[0] = a;
412     base[1] = a;       exp[1] = b;
413     base[2] = NULL;    exp[2] = NULL;
414     mpi_mulpowm( t1, base, exp, pkey->p );
415
416     /* t2 = g ^ input mod p */
417     mpi_powm( t2, pkey->g, input, pkey->p );
418
419     rc = !mpi_cmp( t1, t2 );
420   #else
421     /* t1 = g ^ - input * y ^ a * a ^ b  mod p */
422     mpi_invm(t2, pkey->g, pkey->p );
423     base[0] = t2     ; exp[0] = input;
424     base[1] = pkey->y; exp[1] = a;
425     base[2] = a;       exp[2] = b;
426     base[3] = NULL;    exp[3] = NULL;
427     mpi_mulpowm( t1, base, exp, pkey->p );
428     rc = !mpi_cmp_ui( t1, 1 );
429
430   #endif
431
432     mpi_free(t1);
433     mpi_free(t2);
434     return rc;
435 }
436
437 /*********************************************
438  **************  interface  ******************
439  *********************************************/
440
441 int
442 elg_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
443 {
444     ELG_secret_key sk;
445
446     if( !is_ELGAMAL(algo) )
447         return GCRYERR_INV_PK_ALGO;
448
449     generate( &sk, nbits, retfactors );
450     skey[0] = sk.p;
451     skey[1] = sk.g;
452     skey[2] = sk.y;
453     skey[3] = sk.x;
454     return 0;
455 }
456
457
458 int
459 elg_check_secret_key( int algo, MPI *skey )
460 {
461     ELG_secret_key sk;
462
463     if( !is_ELGAMAL(algo) )
464         return GCRYERR_INV_PK_ALGO;
465     if( !skey[0] || !skey[1] || !skey[2] || !skey[3] )
466         return GCRYERR_BAD_MPI;
467
468     sk.p = skey[0];
469     sk.g = skey[1];
470     sk.y = skey[2];
471     sk.x = skey[3];
472     if( !check_secret_key( &sk ) )
473         return GCRYERR_BAD_SECRET_KEY;
474
475     return 0;
476 }
477
478
479
480 int
481 elg_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
482 {
483     ELG_public_key pk;
484
485     if( !is_ELGAMAL(algo) )
486         return GCRYERR_INV_PK_ALGO;
487     if( !data || !pkey[0] || !pkey[1] || !pkey[2] )
488         return GCRYERR_BAD_MPI;
489
490     pk.p = pkey[0];
491     pk.g = pkey[1];
492     pk.y = pkey[2];
493     resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.p ) );
494     resarr[1] = mpi_alloc( mpi_get_nlimbs( pk.p ) );
495     encrypt( resarr[0], resarr[1], data, &pk );
496     return 0;
497 }
498
499 int
500 elg_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
501 {
502     ELG_secret_key sk;
503
504     if( !is_ELGAMAL(algo) )
505         return GCRYERR_INV_PK_ALGO;
506     if( !data[0] || !data[1]
507         || !skey[0] || !skey[1] || !skey[2] || !skey[3] )
508         return GCRYERR_BAD_MPI;
509
510     sk.p = skey[0];
511     sk.g = skey[1];
512     sk.y = skey[2];
513     sk.x = skey[3];
514     *result = mpi_alloc_secure( mpi_get_nlimbs( sk.p ) );
515     decrypt( *result, data[0], data[1], &sk );
516     return 0;
517 }
518
519 int
520 elg_sign( int algo, MPI *resarr, MPI data, MPI *skey )
521 {
522     ELG_secret_key sk;
523
524     if( !is_ELGAMAL(algo) )
525         return GCRYERR_INV_PK_ALGO;
526     if( !data || !skey[0] || !skey[1] || !skey[2] || !skey[3] )
527         return GCRYERR_BAD_MPI;
528
529     sk.p = skey[0];
530     sk.g = skey[1];
531     sk.y = skey[2];
532     sk.x = skey[3];
533     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
534     resarr[1] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
535     sign( resarr[0], resarr[1], data, &sk );
536     return 0;
537 }
538
539 int
540 elg_verify( int algo, MPI hash, MPI *data, MPI *pkey,
541                     int (*cmp)(void *, MPI), void *opaquev )
542 {
543     ELG_public_key pk;
544
545     if( !is_ELGAMAL(algo) )
546         return GCRYERR_INV_PK_ALGO;
547     if( !data[0] || !data[1] || !hash
548         || !pkey[0] || !pkey[1] || !pkey[2] )
549         return GCRYERR_BAD_MPI;
550
551     pk.p = pkey[0];
552     pk.g = pkey[1];
553     pk.y = pkey[2];
554     if( !verify( data[0], data[1], hash, &pk ) )
555         return GCRYERR_BAD_SIGNATURE;
556     return 0;
557 }
558
559
560
561 unsigned
562 elg_get_nbits( int algo, MPI *pkey )
563 {
564     if( !is_ELGAMAL(algo) )
565         return 0;
566     return mpi_get_nbits( pkey[0] );
567 }
568
569
570 /****************
571  * Return some information about the algorithm.  We need algo here to
572  * distinguish different flavors of the algorithm.
573  * Returns: A pointer to string describing the algorithm or NULL if
574  *          the ALGO is invalid.
575  * Usage: Bit 0 set : allows signing
576  *            1 set : allows encryption
577  * NOTE: This function allows signing also for ELG-E, which is not
578  * okay but a bad hack to allow to work with old gpg keys. The real check
579  * is done in the gnupg ocde depending on the packet version.
580  */
581 const char *
582 elg_get_info( int algo, int *npkey, int *nskey, int *nenc, int *nsig,
583                                                          int *use )
584 {
585     *npkey = 3;
586     *nskey = 4;
587     *nenc = 2;
588     *nsig = 2;
589
590     switch( algo ) {
591       case PUBKEY_ALGO_ELGAMAL:
592         *use = PUBKEY_USAGE_SIG|PUBKEY_USAGE_ENC;
593         return "ELG";
594       case PUBKEY_ALGO_ELGAMAL_E:
595         *use = PUBKEY_USAGE_SIG|PUBKEY_USAGE_ENC;
596         return "ELG-E";
597       default: *use = 0; return NULL;
598     }
599 }
600
601