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