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