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