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