mac: Fix gcry_mac_close to allow for a NULL handle.
[libgcrypt.git] / cipher / elgamal.c
1 /* Elgamal.c  -  Elgamal Public Key encryption
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3  *               2008  Free Software Foundation, Inc.
4  * Copyright (C) 2013 g10 Code GmbH
5  *
6  * This file is part of Libgcrypt.
7  *
8  * Libgcrypt is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as
10  * published by the Free Software Foundation; either version 2.1 of
11  * the License, or (at your option) any later version.
12  *
13  * Libgcrypt is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20  *
21  * For a description of the algorithm, see:
22  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
23  *   ISBN 0-471-11709-9. Pages 476 ff.
24  */
25
26 #include <config.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include "g10lib.h"
31 #include "mpi.h"
32 #include "cipher.h"
33 #include "pubkey-internal.h"
34
35
36 typedef struct
37 {
38   gcry_mpi_t p;     /* prime */
39   gcry_mpi_t g;     /* group generator */
40   gcry_mpi_t y;     /* g^x mod p */
41 } ELG_public_key;
42
43
44 typedef struct
45 {
46   gcry_mpi_t p;     /* prime */
47   gcry_mpi_t g;     /* group generator */
48   gcry_mpi_t y;     /* g^x mod p */
49   gcry_mpi_t x;     /* secret exponent */
50 } ELG_secret_key;
51
52
53 static const char *elg_names[] =
54   {
55     "elg",
56     "openpgp-elg",
57     "openpgp-elg-sig",
58     NULL,
59   };
60
61
62 static int test_keys (ELG_secret_key *sk, unsigned int nbits, int nodie);
63 static gcry_mpi_t gen_k (gcry_mpi_t p, int small_k);
64 static gcry_err_code_t generate (ELG_secret_key *sk, unsigned nbits,
65                                  gcry_mpi_t **factors);
66 static int  check_secret_key (ELG_secret_key *sk);
67 static void do_encrypt (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
68                         ELG_public_key *pkey);
69 static void decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b,
70                      ELG_secret_key *skey);
71 static void sign (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
72                   ELG_secret_key *skey);
73 static int  verify (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
74                     ELG_public_key *pkey);
75 static unsigned int elg_get_nbits (gcry_sexp_t parms);
76
77
78 static void (*progress_cb) (void *, const char *, int, int, int);
79 static void *progress_cb_data;
80
81 void
82 _gcry_register_pk_elg_progress (void (*cb) (void *, const char *,
83                                             int, int, int),
84                                 void *cb_data)
85 {
86   progress_cb = cb;
87   progress_cb_data = cb_data;
88 }
89
90
91 static void
92 progress (int c)
93 {
94   if (progress_cb)
95     progress_cb (progress_cb_data, "pk_elg", c, 0, 0);
96 }
97
98
99 /****************
100  * Michael Wiener's table on subgroup sizes to match field sizes.
101  * (floating around somewhere, probably based on the paper from
102  * Eurocrypt 96, page 332)
103  */
104 static unsigned int
105 wiener_map( unsigned int n )
106 {
107   static struct { unsigned int p_n, q_n; } t[] =
108     { /*   p      q      attack cost */
109       {  512, 119 },    /* 9 x 10^17 */
110       {  768, 145 },    /* 6 x 10^21 */
111       { 1024, 165 },    /* 7 x 10^24 */
112       { 1280, 183 },    /* 3 x 10^27 */
113       { 1536, 198 },    /* 7 x 10^29 */
114       { 1792, 212 },    /* 9 x 10^31 */
115       { 2048, 225 },    /* 8 x 10^33 */
116       { 2304, 237 },    /* 5 x 10^35 */
117       { 2560, 249 },    /* 3 x 10^37 */
118       { 2816, 259 },    /* 1 x 10^39 */
119       { 3072, 269 },    /* 3 x 10^40 */
120       { 3328, 279 },    /* 8 x 10^41 */
121       { 3584, 288 },    /* 2 x 10^43 */
122       { 3840, 296 },    /* 4 x 10^44 */
123       { 4096, 305 },    /* 7 x 10^45 */
124       { 4352, 313 },    /* 1 x 10^47 */
125       { 4608, 320 },    /* 2 x 10^48 */
126       { 4864, 328 },    /* 2 x 10^49 */
127       { 5120, 335 },    /* 3 x 10^50 */
128       { 0, 0 }
129     };
130   int i;
131
132   for(i=0; t[i].p_n; i++ )
133     {
134       if( n <= t[i].p_n )
135         return t[i].q_n;
136     }
137   /* Not in table - use an arbitrary high number. */
138   return  n / 8 + 200;
139 }
140
141 static int
142 test_keys ( ELG_secret_key *sk, unsigned int nbits, int nodie )
143 {
144   ELG_public_key pk;
145   gcry_mpi_t test   = mpi_new ( 0 );
146   gcry_mpi_t out1_a = mpi_new ( nbits );
147   gcry_mpi_t out1_b = mpi_new ( nbits );
148   gcry_mpi_t out2   = mpi_new ( nbits );
149   int failed = 0;
150
151   pk.p = sk->p;
152   pk.g = sk->g;
153   pk.y = sk->y;
154
155   _gcry_mpi_randomize ( test, nbits, GCRY_WEAK_RANDOM );
156
157   do_encrypt ( out1_a, out1_b, test, &pk );
158   decrypt ( out2, out1_a, out1_b, sk );
159   if ( mpi_cmp( test, out2 ) )
160     failed |= 1;
161
162   sign ( out1_a, out1_b, test, sk );
163   if ( !verify( out1_a, out1_b, test, &pk ) )
164     failed |= 2;
165
166   _gcry_mpi_release ( test );
167   _gcry_mpi_release ( out1_a );
168   _gcry_mpi_release ( out1_b );
169   _gcry_mpi_release ( out2 );
170
171   if (failed && !nodie)
172     log_fatal ("Elgamal test key for %s %s failed\n",
173                (failed & 1)? "encrypt+decrypt":"",
174                (failed & 2)? "sign+verify":"");
175   if (failed && DBG_CIPHER)
176     log_debug ("Elgamal test key for %s %s failed\n",
177                (failed & 1)? "encrypt+decrypt":"",
178                (failed & 2)? "sign+verify":"");
179
180   return failed;
181 }
182
183
184 /****************
185  * Generate a random secret exponent k from prime p, so that k is
186  * relatively prime to p-1.  With SMALL_K set, k will be selected for
187  * better encryption performance - this must never be used signing!
188  */
189 static gcry_mpi_t
190 gen_k( gcry_mpi_t p, int small_k )
191 {
192   gcry_mpi_t k = mpi_alloc_secure( 0 );
193   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(p) );
194   gcry_mpi_t p_1 = mpi_copy(p);
195   unsigned int orig_nbits = mpi_get_nbits(p);
196   unsigned int nbits, nbytes;
197   char *rndbuf = NULL;
198
199   if (small_k)
200     {
201       /* Using a k much lesser than p is sufficient for encryption and
202        * it greatly improves the encryption performance.  We use
203        * Wiener's table and add a large safety margin. */
204       nbits = wiener_map( orig_nbits ) * 3 / 2;
205       if( nbits >= orig_nbits )
206         BUG();
207     }
208   else
209     nbits = orig_nbits;
210
211
212   nbytes = (nbits+7)/8;
213   if( DBG_CIPHER )
214     log_debug("choosing a random k\n");
215   mpi_sub_ui( p_1, p, 1);
216   for(;;)
217     {
218       if( !rndbuf || nbits < 32 )
219         {
220           xfree(rndbuf);
221           rndbuf = _gcry_random_bytes_secure( nbytes, GCRY_STRONG_RANDOM );
222         }
223       else
224         {
225           /* Change only some of the higher bits.  We could improve
226              this by directly requesting more memory at the first call
227              to get_random_bytes() and use this the here maybe it is
228              easier to do this directly in random.c Anyway, it is
229              highly inlikely that we will ever reach this code. */
230           char *pp = _gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
231           memcpy( rndbuf, pp, 4 );
232           xfree(pp);
233         }
234       _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
235
236       for(;;)
237         {
238           if( !(mpi_cmp( k, p_1 ) < 0) )  /* check: k < (p-1) */
239             {
240               if( DBG_CIPHER )
241                 progress('+');
242               break; /* no  */
243             }
244           if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
245             {
246               if( DBG_CIPHER )
247                 progress('-');
248               break; /* no */
249             }
250           if (mpi_gcd( temp, k, p_1 ))
251             goto found;  /* okay, k is relative prime to (p-1) */
252           mpi_add_ui( k, k, 1 );
253           if( DBG_CIPHER )
254             progress('.');
255         }
256     }
257  found:
258   xfree (rndbuf);
259   if( DBG_CIPHER )
260     progress('\n');
261   mpi_free(p_1);
262   mpi_free(temp);
263
264   return k;
265 }
266
267 /****************
268  * Generate a key pair with a key of size NBITS
269  * Returns: 2 structures filled with all needed values
270  *          and an array with n-1 factors of (p-1)
271  */
272 static gcry_err_code_t
273 generate ( ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t **ret_factors )
274 {
275   gcry_err_code_t rc;
276   gcry_mpi_t p;    /* the prime */
277   gcry_mpi_t p_min1;
278   gcry_mpi_t g;
279   gcry_mpi_t x;    /* the secret exponent */
280   gcry_mpi_t y;
281   unsigned int qbits;
282   unsigned int xbits;
283   byte *rndbuf;
284
285   p_min1 = mpi_new ( nbits );
286   qbits = wiener_map( nbits );
287   if( qbits & 1 ) /* better have a even one */
288     qbits++;
289   g = mpi_alloc(1);
290   rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors);
291   if (rc)
292     {
293       mpi_free (p_min1);
294       mpi_free (g);
295       return rc;
296     }
297   mpi_sub_ui(p_min1, p, 1);
298
299
300   /* Select a random number which has these properties:
301    *     0 < x < p-1
302    * This must be a very good random number because this is the
303    * secret part.  The prime is public and may be shared anyway,
304    * so a random generator level of 1 is used for the prime.
305    *
306    * I don't see a reason to have a x of about the same size
307    * as the p.  It should be sufficient to have one about the size
308    * of q or the later used k plus a large safety margin. Decryption
309    * will be much faster with such an x.
310    */
311   xbits = qbits * 3 / 2;
312   if( xbits >= nbits )
313     BUG();
314   x = mpi_snew ( xbits );
315   if( DBG_CIPHER )
316     log_debug("choosing a random x of size %u\n", xbits );
317   rndbuf = NULL;
318   do
319     {
320       if( DBG_CIPHER )
321         progress('.');
322       if( rndbuf )
323         { /* Change only some of the higher bits */
324           if( xbits < 16 ) /* should never happen ... */
325             {
326               xfree(rndbuf);
327               rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
328                                                   GCRY_VERY_STRONG_RANDOM);
329             }
330           else
331             {
332               char *r = _gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
333               memcpy(rndbuf, r, 2 );
334               xfree (r);
335             }
336         }
337       else
338         {
339           rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
340                                               GCRY_VERY_STRONG_RANDOM );
341         }
342       _gcry_mpi_set_buffer( x, rndbuf, (xbits+7)/8, 0 );
343       mpi_clear_highbit( x, xbits+1 );
344     }
345   while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, p_min1 )<0 ) );
346   xfree(rndbuf);
347
348   y = mpi_new (nbits);
349   mpi_powm( y, g, x, p );
350
351   if( DBG_CIPHER )
352     {
353       progress ('\n');
354       log_mpidump ("elg  p", p );
355       log_mpidump ("elg  g", g );
356       log_mpidump ("elg  y", y );
357       log_mpidump ("elg  x", x );
358     }
359
360   /* Copy the stuff to the key structures */
361   sk->p = p;
362   sk->g = g;
363   sk->y = y;
364   sk->x = x;
365
366   _gcry_mpi_release ( p_min1 );
367
368   /* Now we can test our keys (this should never fail!) */
369   test_keys ( sk, nbits - 64, 0 );
370
371   return 0;
372 }
373
374
375 /* Generate a key pair with a key of size NBITS not using a random
376    value for the secret key but the one given as X.  This is useful to
377    implement a passphrase based decryption for a public key based
378    encryption.  It has appliactions in backup systems.
379
380    Returns: A structure filled with all needed values and an array
381             with n-1 factors of (p-1).  */
382 static gcry_err_code_t
383 generate_using_x (ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t x,
384                   gcry_mpi_t **ret_factors )
385 {
386   gcry_err_code_t rc;
387   gcry_mpi_t p;      /* The prime.  */
388   gcry_mpi_t p_min1; /* The prime minus 1.  */
389   gcry_mpi_t g;      /* The generator.  */
390   gcry_mpi_t y;      /* g^x mod p.  */
391   unsigned int qbits;
392   unsigned int xbits;
393
394   sk->p = NULL;
395   sk->g = NULL;
396   sk->y = NULL;
397   sk->x = NULL;
398
399   /* Do a quick check to see whether X is suitable.  */
400   xbits = mpi_get_nbits (x);
401   if ( xbits < 64 || xbits >= nbits )
402     return GPG_ERR_INV_VALUE;
403
404   p_min1 = mpi_new ( nbits );
405   qbits  = wiener_map ( nbits );
406   if ( (qbits & 1) ) /* Better have an even one.  */
407     qbits++;
408   g = mpi_alloc (1);
409   rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors );
410   if (rc)
411     {
412       mpi_free (p_min1);
413       mpi_free (g);
414       return rc;
415     }
416   mpi_sub_ui (p_min1, p, 1);
417
418   if (DBG_CIPHER)
419     log_debug ("using a supplied x of size %u", xbits );
420   if ( !(mpi_cmp_ui ( x, 0 ) > 0 && mpi_cmp ( x, p_min1 ) <0 ) )
421     {
422       _gcry_mpi_release ( p_min1 );
423       _gcry_mpi_release ( p );
424       _gcry_mpi_release ( g );
425       return GPG_ERR_INV_VALUE;
426     }
427
428   y = mpi_new (nbits);
429   mpi_powm ( y, g, x, p );
430
431   if ( DBG_CIPHER )
432     {
433       progress ('\n');
434       log_mpidump ("elg  p", p );
435       log_mpidump ("elg  g", g );
436       log_mpidump ("elg  y", y );
437       log_mpidump ("elg  x", x );
438     }
439
440   /* Copy the stuff to the key structures */
441   sk->p = p;
442   sk->g = g;
443   sk->y = y;
444   sk->x = mpi_copy (x);
445
446   _gcry_mpi_release ( p_min1 );
447
448   /* Now we can test our keys. */
449   if ( test_keys ( sk, nbits - 64, 1 ) )
450     {
451       _gcry_mpi_release ( sk->p ); sk->p = NULL;
452       _gcry_mpi_release ( sk->g ); sk->g = NULL;
453       _gcry_mpi_release ( sk->y ); sk->y = NULL;
454       _gcry_mpi_release ( sk->x ); sk->x = NULL;
455       return GPG_ERR_BAD_SECKEY;
456     }
457
458   return 0;
459 }
460
461
462 /****************
463  * Test whether the secret key is valid.
464  * Returns: if this is a valid key.
465  */
466 static int
467 check_secret_key( ELG_secret_key *sk )
468 {
469   int rc;
470   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
471
472   mpi_powm (y, sk->g, sk->x, sk->p);
473   rc = !mpi_cmp( y, sk->y );
474   mpi_free( y );
475   return rc;
476 }
477
478
479 static void
480 do_encrypt(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
481 {
482   gcry_mpi_t k;
483
484   /* Note: maybe we should change the interface, so that it
485    * is possible to check that input is < p and return an
486    * error code.
487    */
488
489   k = gen_k( pkey->p, 1 );
490   mpi_powm (a, pkey->g, k, pkey->p);
491
492   /* b = (y^k * input) mod p
493    *     = ((y^k mod p) * (input mod p)) mod p
494    * and because input is < p
495    *     = ((y^k mod p) * input) mod p
496    */
497   mpi_powm (b, pkey->y, k, pkey->p);
498   mpi_mulm (b, b, input, pkey->p);
499 #if 0
500   if( DBG_CIPHER )
501     {
502       log_mpidump("elg encrypted y", pkey->y);
503       log_mpidump("elg encrypted p", pkey->p);
504       log_mpidump("elg encrypted k", k);
505       log_mpidump("elg encrypted M", input);
506       log_mpidump("elg encrypted a", a);
507       log_mpidump("elg encrypted b", b);
508     }
509 #endif
510   mpi_free(k);
511 }
512
513
514
515
516 static void
517 decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
518 {
519   gcry_mpi_t t1 = mpi_alloc_secure( mpi_get_nlimbs( skey->p ) );
520
521   mpi_normalize (a);
522   mpi_normalize (b);
523
524   /* output = b/(a^x) mod p */
525   mpi_powm( t1, a, skey->x, skey->p );
526   mpi_invm( t1, t1, skey->p );
527   mpi_mulm( output, b, t1, skey->p );
528 #if 0
529   if( DBG_CIPHER )
530     {
531       log_mpidump ("elg decrypted x", skey->x);
532       log_mpidump ("elg decrypted p", skey->p);
533       log_mpidump ("elg decrypted a", a);
534       log_mpidump ("elg decrypted b", b);
535       log_mpidump ("elg decrypted M", output);
536     }
537 #endif
538   mpi_free(t1);
539 }
540
541
542 /****************
543  * Make an Elgamal signature out of INPUT
544  */
545
546 static void
547 sign(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_secret_key *skey )
548 {
549     gcry_mpi_t k;
550     gcry_mpi_t t   = mpi_alloc( mpi_get_nlimbs(a) );
551     gcry_mpi_t inv = mpi_alloc( mpi_get_nlimbs(a) );
552     gcry_mpi_t p_1 = mpi_copy(skey->p);
553
554    /*
555     * b = (t * inv) mod (p-1)
556     * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
557     * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
558     *
559     */
560     mpi_sub_ui(p_1, p_1, 1);
561     k = gen_k( skey->p, 0 /* no small K ! */ );
562     mpi_powm( a, skey->g, k, skey->p );
563     mpi_mul(t, skey->x, a );
564     mpi_subm(t, input, t, p_1 );
565     mpi_invm(inv, k, p_1 );
566     mpi_mulm(b, t, inv, p_1 );
567
568 #if 0
569     if( DBG_CIPHER )
570       {
571         log_mpidump ("elg sign p", skey->p);
572         log_mpidump ("elg sign g", skey->g);
573         log_mpidump ("elg sign y", skey->y);
574         log_mpidump ("elg sign x", skey->x);
575         log_mpidump ("elg sign k", k);
576         log_mpidump ("elg sign M", input);
577         log_mpidump ("elg sign a", a);
578         log_mpidump ("elg sign b", b);
579       }
580 #endif
581     mpi_free(k);
582     mpi_free(t);
583     mpi_free(inv);
584     mpi_free(p_1);
585 }
586
587
588 /****************
589  * Returns true if the signature composed of A and B is valid.
590  */
591 static int
592 verify(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
593 {
594   int rc;
595   gcry_mpi_t t1;
596   gcry_mpi_t t2;
597   gcry_mpi_t base[4];
598   gcry_mpi_t ex[4];
599
600   if( !(mpi_cmp_ui( a, 0 ) > 0 && mpi_cmp( a, pkey->p ) < 0) )
601     return 0; /* assertion      0 < a < p  failed */
602
603   t1 = mpi_alloc( mpi_get_nlimbs(a) );
604   t2 = mpi_alloc( mpi_get_nlimbs(a) );
605
606 #if 0
607   /* t1 = (y^a mod p) * (a^b mod p) mod p */
608   gcry_mpi_powm( t1, pkey->y, a, pkey->p );
609   gcry_mpi_powm( t2, a, b, pkey->p );
610   mpi_mulm( t1, t1, t2, pkey->p );
611
612   /* t2 = g ^ input mod p */
613   gcry_mpi_powm( t2, pkey->g, input, pkey->p );
614
615   rc = !mpi_cmp( t1, t2 );
616 #elif 0
617   /* t1 = (y^a mod p) * (a^b mod p) mod p */
618   base[0] = pkey->y; ex[0] = a;
619   base[1] = a;       ex[1] = b;
620   base[2] = NULL;    ex[2] = NULL;
621   mpi_mulpowm( t1, base, ex, pkey->p );
622
623   /* t2 = g ^ input mod p */
624   gcry_mpi_powm( t2, pkey->g, input, pkey->p );
625
626   rc = !mpi_cmp( t1, t2 );
627 #else
628   /* t1 = g ^ - input * y ^ a * a ^ b  mod p */
629   mpi_invm(t2, pkey->g, pkey->p );
630   base[0] = t2     ; ex[0] = input;
631   base[1] = pkey->y; ex[1] = a;
632   base[2] = a;       ex[2] = b;
633   base[3] = NULL;    ex[3] = NULL;
634   mpi_mulpowm( t1, base, ex, pkey->p );
635   rc = !mpi_cmp_ui( t1, 1 );
636
637 #endif
638
639   mpi_free(t1);
640   mpi_free(t2);
641   return rc;
642 }
643
644 /*********************************************
645  **************  interface  ******************
646  *********************************************/
647
648 static gpg_err_code_t
649 elg_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
650 {
651   gpg_err_code_t rc;
652   unsigned int nbits;
653   ELG_secret_key sk;
654   gcry_mpi_t xvalue = NULL;
655   gcry_sexp_t l1;
656   gcry_mpi_t *factors = NULL;
657   gcry_sexp_t misc_info = NULL;
658
659   memset (&sk, 0, sizeof sk);
660
661   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
662   if (rc)
663     return rc;
664
665   /* Parse the optional xvalue element. */
666   l1 = sexp_find_token (genparms, "xvalue", 0);
667   if (l1)
668     {
669       xvalue = sexp_nth_mpi (l1, 1, 0);
670       sexp_release (l1);
671       if (!xvalue)
672         return GPG_ERR_BAD_MPI;
673     }
674
675   if (xvalue)
676     {
677       rc = generate_using_x (&sk, nbits, xvalue, &factors);
678       mpi_free (xvalue);
679     }
680   else
681     {
682       rc = generate (&sk, nbits, &factors);
683     }
684   if (rc)
685     goto leave;
686
687   if (factors && factors[0])
688     {
689       int nfac;
690       void **arg_list;
691       char *buffer, *p;
692
693       for (nfac = 0; factors[nfac]; nfac++)
694         ;
695       arg_list = xtrycalloc (nfac+1, sizeof *arg_list);
696       if (!arg_list)
697         {
698           rc = gpg_err_code_from_syserror ();
699           goto leave;
700         }
701       buffer = xtrymalloc (30 + nfac*2 + 2 + 1);
702       if (!buffer)
703         {
704           rc = gpg_err_code_from_syserror ();
705           xfree (arg_list);
706           goto leave;
707         }
708       p = stpcpy (buffer, "(misc-key-info(pm1-factors");
709       for(nfac = 0; factors[nfac]; nfac++)
710         {
711           p = stpcpy (p, "%m");
712           arg_list[nfac] = factors + nfac;
713         }
714       p = stpcpy (p, "))");
715       rc = sexp_build_array (&misc_info, NULL, buffer, arg_list);
716       xfree (arg_list);
717       xfree (buffer);
718       if (rc)
719         goto leave;
720     }
721
722   rc = sexp_build (r_skey, NULL,
723                    "(key-data"
724                    " (public-key"
725                    "  (elg(p%m)(g%m)(y%m)))"
726                    " (private-key"
727                    "  (elg(p%m)(g%m)(y%m)(x%m)))"
728                    " %S)",
729                    sk.p, sk.g, sk.y,
730                    sk.p, sk.g, sk.y, sk.x,
731                    misc_info);
732
733  leave:
734   mpi_free (sk.p);
735   mpi_free (sk.g);
736   mpi_free (sk.y);
737   mpi_free (sk.x);
738   sexp_release (misc_info);
739   if (factors)
740     {
741       gcry_mpi_t *mp;
742       for (mp = factors; *mp; mp++)
743         mpi_free (*mp);
744       xfree (factors);
745     }
746
747   return rc;
748 }
749
750
751 static gcry_err_code_t
752 elg_check_secret_key (gcry_sexp_t keyparms)
753 {
754   gcry_err_code_t rc;
755   ELG_secret_key sk = {NULL, NULL, NULL, NULL};
756
757   rc = sexp_extract_param (keyparms, NULL, "pgyx",
758                            &sk.p, &sk.g, &sk.y, &sk.x,
759                            NULL);
760   if (rc)
761     goto leave;
762
763   if (!check_secret_key (&sk))
764     rc = GPG_ERR_BAD_SECKEY;
765
766  leave:
767   _gcry_mpi_release (sk.p);
768   _gcry_mpi_release (sk.g);
769   _gcry_mpi_release (sk.y);
770   _gcry_mpi_release (sk.x);
771   if (DBG_CIPHER)
772     log_debug ("elg_testkey    => %s\n", gpg_strerror (rc));
773   return rc;
774 }
775
776
777 static gcry_err_code_t
778 elg_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
779 {
780   gcry_err_code_t rc;
781   struct pk_encoding_ctx ctx;
782   gcry_mpi_t mpi_a = NULL;
783   gcry_mpi_t mpi_b = NULL;
784   gcry_mpi_t data = NULL;
785   ELG_public_key pk = { NULL, NULL, NULL };
786
787   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
788                                    elg_get_nbits (keyparms));
789
790   /* Extract the data.  */
791   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
792   if (rc)
793     goto leave;
794   if (DBG_CIPHER)
795     log_mpidump ("elg_encrypt data", data);
796   if (mpi_is_opaque (data))
797     {
798       rc = GPG_ERR_INV_DATA;
799       goto leave;
800     }
801
802   /* Extract the key.  */
803   rc = sexp_extract_param (keyparms, NULL, "pgy",
804                            &pk.p, &pk.g, &pk.y, NULL);
805   if (rc)
806     goto leave;
807   if (DBG_CIPHER)
808     {
809       log_mpidump ("elg_encrypt  p", pk.p);
810       log_mpidump ("elg_encrypt  g", pk.g);
811       log_mpidump ("elg_encrypt  y", pk.y);
812     }
813
814   /* Do Elgamal computation and build result.  */
815   mpi_a = mpi_new (0);
816   mpi_b = mpi_new (0);
817   do_encrypt (mpi_a, mpi_b, data, &pk);
818   rc = sexp_build (r_ciph, NULL, "(enc-val(elg(a%m)(b%m)))", mpi_a, mpi_b);
819
820  leave:
821   _gcry_mpi_release (mpi_a);
822   _gcry_mpi_release (mpi_b);
823   _gcry_mpi_release (pk.p);
824   _gcry_mpi_release (pk.g);
825   _gcry_mpi_release (pk.y);
826   _gcry_mpi_release (data);
827   _gcry_pk_util_free_encoding_ctx (&ctx);
828   if (DBG_CIPHER)
829     log_debug ("elg_encrypt   => %s\n", gpg_strerror (rc));
830   return rc;
831 }
832
833
834 static gcry_err_code_t
835 elg_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
836 {
837   gpg_err_code_t rc;
838   struct pk_encoding_ctx ctx;
839   gcry_sexp_t l1 = NULL;
840   gcry_mpi_t data_a = NULL;
841   gcry_mpi_t data_b = NULL;
842   ELG_secret_key sk = {NULL, NULL, NULL, NULL};
843   gcry_mpi_t plain = NULL;
844   unsigned char *unpad = NULL;
845   size_t unpadlen = 0;
846
847   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
848                                    elg_get_nbits (keyparms));
849
850   /* Extract the data.  */
851   rc = _gcry_pk_util_preparse_encval (s_data, elg_names, &l1, &ctx);
852   if (rc)
853     goto leave;
854   rc = sexp_extract_param (l1, NULL, "ab", &data_a, &data_b, NULL);
855   if (rc)
856     goto leave;
857   if (DBG_CIPHER)
858     {
859       log_printmpi ("elg_decrypt  d_a", data_a);
860       log_printmpi ("elg_decrypt  d_b", data_b);
861     }
862   if (mpi_is_opaque (data_a) || mpi_is_opaque (data_b))
863     {
864       rc = GPG_ERR_INV_DATA;
865       goto leave;
866     }
867
868   /* Extract the key.  */
869   rc = sexp_extract_param (keyparms, NULL, "pgyx",
870                            &sk.p, &sk.g, &sk.y, &sk.x,
871                            NULL);
872   if (rc)
873     goto leave;
874   if (DBG_CIPHER)
875     {
876       log_printmpi ("elg_decrypt    p", sk.p);
877       log_printmpi ("elg_decrypt    g", sk.g);
878       log_printmpi ("elg_decrypt    y", sk.y);
879       if (!fips_mode ())
880         log_printmpi ("elg_decrypt    x", sk.x);
881     }
882
883   plain = mpi_snew (ctx.nbits);
884   decrypt (plain, data_a, data_b, &sk);
885   if (DBG_CIPHER)
886     log_printmpi ("elg_decrypt  res", plain);
887
888   /* Reverse the encoding and build the s-expression.  */
889   switch (ctx.encoding)
890     {
891     case PUBKEY_ENC_PKCS1:
892       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
893       mpi_free (plain); plain = NULL;
894       if (!rc)
895         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
896       break;
897
898     case PUBKEY_ENC_OAEP:
899       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
900                                   ctx.nbits, ctx.hash_algo, plain,
901                                   ctx.label, ctx.labellen);
902       mpi_free (plain); plain = NULL;
903       if (!rc)
904         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
905       break;
906
907     default:
908       /* Raw format.  For backward compatibility we need to assume a
909          signed mpi by using the sexp format string "%m".  */
910       rc = sexp_build (r_plain, NULL,
911                        (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
912                        ? "%m" : "(value %m)",
913                        plain);
914       break;
915     }
916
917
918  leave:
919   xfree (unpad);
920   _gcry_mpi_release (plain);
921   _gcry_mpi_release (sk.p);
922   _gcry_mpi_release (sk.g);
923   _gcry_mpi_release (sk.y);
924   _gcry_mpi_release (sk.x);
925   _gcry_mpi_release (data_a);
926   _gcry_mpi_release (data_b);
927   sexp_release (l1);
928   _gcry_pk_util_free_encoding_ctx (&ctx);
929   if (DBG_CIPHER)
930     log_debug ("elg_decrypt    => %s\n", gpg_strerror (rc));
931   return rc;
932 }
933
934
935 static gcry_err_code_t
936 elg_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
937 {
938   gcry_err_code_t rc;
939   struct pk_encoding_ctx ctx;
940   gcry_mpi_t data = NULL;
941   ELG_secret_key sk = {NULL, NULL, NULL, NULL};
942   gcry_mpi_t sig_r = NULL;
943   gcry_mpi_t sig_s = NULL;
944
945   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
946                                    elg_get_nbits (keyparms));
947
948   /* Extract the data.  */
949   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
950   if (rc)
951     goto leave;
952   if (DBG_CIPHER)
953     log_mpidump ("elg_sign   data", data);
954   if (mpi_is_opaque (data))
955     {
956       rc = GPG_ERR_INV_DATA;
957       goto leave;
958     }
959
960   /* Extract the key.  */
961   rc = sexp_extract_param (keyparms, NULL, "pgyx",
962                            &sk.p, &sk.g, &sk.y, &sk.x, NULL);
963   if (rc)
964     goto leave;
965   if (DBG_CIPHER)
966     {
967       log_mpidump ("elg_sign      p", sk.p);
968       log_mpidump ("elg_sign      g", sk.g);
969       log_mpidump ("elg_sign      y", sk.y);
970       if (!fips_mode ())
971         log_mpidump ("elg_sign      x", sk.x);
972     }
973
974   sig_r = mpi_new (0);
975   sig_s = mpi_new (0);
976   sign (sig_r, sig_s, data, &sk);
977   if (DBG_CIPHER)
978     {
979       log_mpidump ("elg_sign  sig_r", sig_r);
980       log_mpidump ("elg_sign  sig_s", sig_s);
981     }
982   rc = sexp_build (r_sig, NULL, "(sig-val(elg(r%M)(s%M)))", sig_r, sig_s);
983
984  leave:
985   _gcry_mpi_release (sig_r);
986   _gcry_mpi_release (sig_s);
987   _gcry_mpi_release (sk.p);
988   _gcry_mpi_release (sk.g);
989   _gcry_mpi_release (sk.y);
990   _gcry_mpi_release (sk.x);
991   _gcry_mpi_release (data);
992   _gcry_pk_util_free_encoding_ctx (&ctx);
993   if (DBG_CIPHER)
994     log_debug ("elg_sign      => %s\n", gpg_strerror (rc));
995   return rc;
996 }
997
998
999 static gcry_err_code_t
1000 elg_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1001 {
1002   gcry_err_code_t rc;
1003   struct pk_encoding_ctx ctx;
1004   gcry_sexp_t l1 = NULL;
1005   gcry_mpi_t sig_r = NULL;
1006   gcry_mpi_t sig_s = NULL;
1007   gcry_mpi_t data = NULL;
1008   ELG_public_key pk = { NULL, NULL, NULL };
1009
1010   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1011                                    elg_get_nbits (s_keyparms));
1012
1013   /* Extract the data.  */
1014   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1015   if (rc)
1016     goto leave;
1017   if (DBG_CIPHER)
1018     log_mpidump ("elg_verify data", data);
1019   if (mpi_is_opaque (data))
1020     {
1021       rc = GPG_ERR_INV_DATA;
1022       goto leave;
1023     }
1024
1025   /* Extract the signature value.  */
1026   rc = _gcry_pk_util_preparse_sigval (s_sig, elg_names, &l1, NULL);
1027   if (rc)
1028     goto leave;
1029   rc = sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1030   if (rc)
1031     goto leave;
1032   if (DBG_CIPHER)
1033     {
1034       log_mpidump ("elg_verify  s_r", sig_r);
1035       log_mpidump ("elg_verify  s_s", sig_s);
1036     }
1037
1038   /* Extract the key.  */
1039   rc = sexp_extract_param (s_keyparms, NULL, "pgy",
1040                                  &pk.p, &pk.g, &pk.y, NULL);
1041   if (rc)
1042     goto leave;
1043   if (DBG_CIPHER)
1044     {
1045       log_mpidump ("elg_verify    p", pk.p);
1046       log_mpidump ("elg_verify    g", pk.g);
1047       log_mpidump ("elg_verify    y", pk.y);
1048     }
1049
1050   /* Verify the signature.  */
1051   if (!verify (sig_r, sig_s, data, &pk))
1052     rc = GPG_ERR_BAD_SIGNATURE;
1053
1054  leave:
1055   _gcry_mpi_release (pk.p);
1056   _gcry_mpi_release (pk.g);
1057   _gcry_mpi_release (pk.y);
1058   _gcry_mpi_release (data);
1059   _gcry_mpi_release (sig_r);
1060   _gcry_mpi_release (sig_s);
1061   sexp_release (l1);
1062   _gcry_pk_util_free_encoding_ctx (&ctx);
1063   if (DBG_CIPHER)
1064     log_debug ("elg_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1065   return rc;
1066 }
1067
1068
1069 /* Return the number of bits for the key described by PARMS.  On error
1070  * 0 is returned.  The format of PARMS starts with the algorithm name;
1071  * for example:
1072  *
1073  *   (dsa
1074  *     (p <mpi>)
1075  *     (g <mpi>)
1076  *     (y <mpi>))
1077  *
1078  * More parameters may be given but we only need P here.
1079  */
1080 static unsigned int
1081 elg_get_nbits (gcry_sexp_t parms)
1082 {
1083   gcry_sexp_t l1;
1084   gcry_mpi_t p;
1085   unsigned int nbits;
1086
1087   l1 = sexp_find_token (parms, "p", 1);
1088   if (!l1)
1089     return 0; /* Parameter P not found.  */
1090
1091   p= sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1092   sexp_release (l1);
1093   nbits = p? mpi_get_nbits (p) : 0;
1094   _gcry_mpi_release (p);
1095   return nbits;
1096 }
1097
1098
1099 \f
1100 gcry_pk_spec_t _gcry_pubkey_spec_elg =
1101   {
1102     GCRY_PK_ELG, { 0, 0 },
1103     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1104     "ELG", elg_names,
1105     "pgy", "pgyx", "ab", "rs", "pgy",
1106     elg_generate,
1107     elg_check_secret_key,
1108     elg_encrypt,
1109     elg_decrypt,
1110     elg_sign,
1111     elg_verify,
1112     elg_get_nbits,
1113   };