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 (int algo, gcry_mpi_t *skey)
 734 {
 735   gcry_err_code_t err = GPG_ERR_NO_ERROR;
 736   ELG_secret_key sk;
 737
 738   (void)algo;
 739
 740   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]))
 741     err = GPG_ERR_BAD_MPI;
 742   else
 743     {
 744       sk.p = skey[0];
 745       sk.g = skey[1];
 746       sk.y = skey[2];
 747       sk.x = skey[3];
 748
 749       if (! check_secret_key (&sk))
 750         err = GPG_ERR_BAD_SECKEY;
 751     }
 752
 753   return err;
 754 }
 755
 756
 757 static gcry_err_code_t
 758 elg_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
 759 {
 760   gcry_err_code_t rc;
 761   struct pk_encoding_ctx ctx;
 762   gcry_mpi_t mpi_a = NULL;
 763   gcry_mpi_t mpi_b = NULL;
 764   gcry_mpi_t data = NULL;
 765   ELG_public_key pk = { NULL, NULL, NULL };
 766
 767   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
 768                                    elg_get_nbits (keyparms));
 769
 770   /* Extract the data.  */
 771   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
 772   if (rc)
 773     goto leave;
 774   if (DBG_CIPHER)
 775     log_mpidump ("elg_encrypt data", data);
 776   if (mpi_is_opaque (data))
 777     {
 778       rc = GPG_ERR_INV_DATA;
 779       goto leave;
 780     }
 781
 782   /* Extract the key.  */
 783   rc = _gcry_pk_util_extract_mpis (keyparms, "pgy", &pk.p, &pk.g, &pk.y, NULL);
 784   if (rc)
 785     return rc;
 786   if (DBG_CIPHER)
 787     {
 788       log_mpidump ("elg_encrypt  p", pk.p);
 789       log_mpidump ("elg_encrypt  g", pk.g);
 790       log_mpidump ("elg_encrypt  y", pk.y);
 791     }
 792
 793   /* Do Elgamal computation and build result.  */
 794   mpi_a = gcry_mpi_new (0);
 795   mpi_b = gcry_mpi_new (0);
 796   do_encrypt (mpi_a, mpi_b, data, &pk);
 797   rc = gcry_sexp_build (r_ciph, NULL, "(enc-val(elg(a%m)(b%m)))", mpi_a, mpi_b);
 798
 799  leave:
 800   gcry_mpi_release (mpi_a);
 801   gcry_mpi_release (mpi_b);
 802   gcry_mpi_release (pk.p);
 803   gcry_mpi_release (pk.g);
 804   gcry_mpi_release (pk.y);
 805   gcry_mpi_release (data);
 806   _gcry_pk_util_free_encoding_ctx (&ctx);
 807   if (DBG_CIPHER)
 808     log_debug ("elg_encrypt   => %s\n", gpg_strerror (rc));
 809   return rc;
 810 }
 811
 812
 813 static gcry_err_code_t
 814 elg_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
 815 {
 816   gpg_err_code_t rc;
 817   struct pk_encoding_ctx ctx;
 818   gcry_sexp_t l1 = NULL;
 819   gcry_mpi_t data_a = NULL;
 820   gcry_mpi_t data_b = NULL;
 821   ELG_secret_key sk = {NULL, NULL, NULL, NULL};
 822   gcry_mpi_t plain = NULL;
 823   unsigned char *unpad = NULL;
 824   size_t unpadlen = 0;
 825
 826   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
 827                                    elg_get_nbits (keyparms));
 828
 829   /* Extract the data.  */
 830   rc = _gcry_pk_util_preparse_encval (s_data, elg_names, &l1, &ctx);
 831   if (rc)
 832     goto leave;
 833   rc = _gcry_pk_util_extract_mpis (l1, "ab", &data_a, &data_b, NULL);
 834   if (rc)
 835     goto leave;
 836   if (DBG_CIPHER)
 837     {
 838       log_printmpi ("elg_decrypt  d_a", data_a);
 839       log_printmpi ("elg_decrypt  d_b", data_b);
 840     }
 841   if (mpi_is_opaque (data_a) || mpi_is_opaque (data_b))
 842     {
 843       rc = GPG_ERR_INV_DATA;
 844       goto leave;
 845     }
 846
 847   /* Extract the key.  */
 848   rc = _gcry_pk_util_extract_mpis (keyparms, "pgyx",
 849                                    &sk.p, &sk.g, &sk.y, &sk.x,
 850                                    NULL);
 851   if (rc)
 852     return rc;
 853   if (DBG_CIPHER)
 854     {
 855       log_printmpi ("elg_decrypt    p", sk.p);
 856       log_printmpi ("elg_decrypt    g", sk.g);
 857       log_printmpi ("elg_decrypt    y", sk.y);
 858       if (!fips_mode ())
 859         log_printmpi ("elg_decrypt    x", sk.x);
 860     }
 861
 862   plain = gcry_mpi_snew (ctx.nbits);
 863   decrypt (plain, data_a, data_b, &sk);
 864   if (DBG_CIPHER)
 865     log_printmpi ("elg_decrypt  res", plain);
 866
 867   /* Reverse the encoding and build the s-expression.  */
 868   switch (ctx.encoding)
 869     {
 870     case PUBKEY_ENC_PKCS1:
 871       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
 872       mpi_free (plain); plain = NULL;
 873       if (!rc)
 874         rc = gcry_sexp_build (r_plain, NULL, "(value %b)",
 875                               (int)unpadlen, unpad);
 876       break;
 877
 878     case PUBKEY_ENC_OAEP:
 879       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
 880                                   ctx.nbits, ctx.hash_algo, plain,
 881                                   ctx.label, ctx.labellen);
 882       mpi_free (plain); plain = NULL;
 883       if (!rc)
 884         rc = gcry_sexp_build (r_plain, NULL, "(value %b)",
 885                               (int)unpadlen, unpad);
 886       break;
 887
 888     default:
 889       /* Raw format.  For backward compatibility we need to assume a
 890          signed mpi by using the sexp format string "%m".  */
 891       rc = gcry_sexp_build (r_plain, NULL,
 892                             (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
 893                             ? "%m" : "(value %m)",
 894                             plain);
 895       break;
 896     }
 897
 898
 899  leave:
 900   gcry_free (unpad);
 901   gcry_mpi_release (plain);
 902   gcry_mpi_release (sk.p);
 903   gcry_mpi_release (sk.g);
 904   gcry_mpi_release (sk.y);
 905   gcry_mpi_release (sk.x);
 906   gcry_mpi_release (data_a);
 907   gcry_mpi_release (data_b);
 908   gcry_sexp_release (l1);
 909   _gcry_pk_util_free_encoding_ctx (&ctx);
 910   if (DBG_CIPHER)
 911     log_debug ("elg_decrypt    => %s\n", gpg_strerror (rc));
 912   return rc;
 913 }
 914
 915
 916 static gcry_err_code_t
 917 elg_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
 918 {
 919   gcry_err_code_t rc;
 920   struct pk_encoding_ctx ctx;
 921   gcry_mpi_t data = NULL;
 922   ELG_secret_key sk = {NULL, NULL, NULL, NULL};
 923   gcry_mpi_t sig_r = NULL;
 924   gcry_mpi_t sig_s = NULL;
 925
 926   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
 927                                    elg_get_nbits (keyparms));
 928
 929   /* Extract the data.  */
 930   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
 931   if (rc)
 932     goto leave;
 933   if (DBG_CIPHER)
 934     log_mpidump ("elg_sign   data", data);
 935   if (mpi_is_opaque (data))
 936     {
 937       rc = GPG_ERR_INV_DATA;
 938       goto leave;
 939     }
 940
 941   /* Extract the key.  */
 942   rc = _gcry_pk_util_extract_mpis (keyparms, "pgyx",
 943                                    &sk.p, &sk.g, &sk.y, &sk.x, NULL);
 944   if (rc)
 945     return rc;
 946   if (DBG_CIPHER)
 947     {
 948       log_mpidump ("elg_sign      p", sk.p);
 949       log_mpidump ("elg_sign      g", sk.g);
 950       log_mpidump ("elg_sign      y", sk.y);
 951       if (!fips_mode ())
 952         log_mpidump ("elg_sign      x", sk.x);
 953     }
 954
 955   sig_r = gcry_mpi_new (0);
 956   sig_s = gcry_mpi_new (0);
 957   sign (sig_r, sig_s, data, &sk);
 958   if (DBG_CIPHER)
 959     {
 960       log_mpidump ("elg_sign  sig_r", sig_r);
 961       log_mpidump ("elg_sign  sig_s", sig_s);
 962     }
 963   rc = gcry_sexp_build (r_sig, NULL, "(sig-val(elg(r%M)(s%M)))", sig_r, sig_s);
 964
 965  leave:
 966   gcry_mpi_release (sig_r);
 967   gcry_mpi_release (sig_s);
 968   gcry_mpi_release (sk.p);
 969   gcry_mpi_release (sk.g);
 970   gcry_mpi_release (sk.y);
 971   gcry_mpi_release (sk.x);
 972   gcry_mpi_release (data);
 973   _gcry_pk_util_free_encoding_ctx (&ctx);
 974   if (DBG_CIPHER)
 975     log_debug ("elg_sign      => %s\n", gpg_strerror (rc));
 976   return rc;
 977 }
 978
 979
 980 static gcry_err_code_t
 981 elg_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
 982 {
 983   gcry_err_code_t rc;
 984   struct pk_encoding_ctx ctx;
 985   gcry_sexp_t l1 = NULL;
 986   gcry_mpi_t sig_r = NULL;
 987   gcry_mpi_t sig_s = NULL;
 988   gcry_mpi_t data = NULL;
 989   ELG_public_key pk = { NULL, NULL, NULL };
 990
 991   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
 992                                    elg_get_nbits (s_keyparms));
 993
 994   /* Extract the data.  */
 995   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
 996   if (rc)
 997     goto leave;
 998   if (DBG_CIPHER)
 999     log_mpidump ("elg_verify data", data);
1000   if (mpi_is_opaque (data))
1001     {
1002       rc = GPG_ERR_INV_DATA;
1003       goto leave;
1004     }
1005
1006   /* Extract the signature value.  */
1007   rc = _gcry_pk_util_preparse_sigval (s_sig, elg_names, &l1, NULL);
1008   if (rc)
1009     goto leave;
1010   rc = _gcry_pk_util_extract_mpis (l1, "rs", &sig_r, &sig_s, NULL);
1011   if (rc)
1012     goto leave;
1013   if (DBG_CIPHER)
1014     {
1015       log_mpidump ("elg_verify  s_r", sig_r);
1016       log_mpidump ("elg_verify  s_s", sig_s);
1017     }
1018
1019   /* Extract the key.  */
1020   rc = _gcry_pk_util_extract_mpis (s_keyparms, "pgy",
1021                                    &pk.p, &pk.g, &pk.y, NULL);
1022   if (rc)
1023     return rc;
1024   if (DBG_CIPHER)
1025     {
1026       log_mpidump ("elg_verify    p", pk.p);
1027       log_mpidump ("elg_verify    g", pk.g);
1028       log_mpidump ("elg_verify    y", pk.y);
1029     }
1030
1031   /* Verify the signature.  */
1032   if (!verify (sig_r, sig_s, data, &pk))
1033     rc = GPG_ERR_BAD_SIGNATURE;
1034
1035  leave:
1036   gcry_mpi_release (pk.p);
1037   gcry_mpi_release (pk.g);
1038   gcry_mpi_release (pk.y);
1039   gcry_mpi_release (data);
1040   gcry_mpi_release (sig_r);
1041   gcry_mpi_release (sig_s);
1042   gcry_sexp_release (l1);
1043   _gcry_pk_util_free_encoding_ctx (&ctx);
1044   if (DBG_CIPHER)
1045     log_debug ("elg_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1046   return rc;
1047 }
1048
1049
1050 /* Return the number of bits for the key described by PARMS.  On error
1051  * 0 is returned.  The format of PARMS starts with the algorithm name;
1052  * for example:
1053  *
1054  *   (dsa
1055  *     (p <mpi>)
1056  *     (g <mpi>)
1057  *     (y <mpi>))
1058  *
1059  * More parameters may be given but we only need P here.
1060  */
1061 static unsigned int
1062 elg_get_nbits (gcry_sexp_t parms)
1063 {
1064   gcry_sexp_t l1;
1065   gcry_mpi_t p;
1066   unsigned int nbits;
1067
1068   l1 = gcry_sexp_find_token (parms, "p", 1);
1069   if (!l1)
1070     return 0; /* Parameter P not found.  */
1071
1072   p= gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1073   gcry_sexp_release (l1);
1074   nbits = p? mpi_get_nbits (p) : 0;
1075   gcry_mpi_release (p);
1076   return nbits;
1077 }
1078
1079
1080 \f
1081 gcry_pk_spec_t _gcry_pubkey_spec_elg =
1082   {
1083     GCRY_PK_ELG, { 0, 0 },
1084     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1085     "ELG", elg_names,
1086     "pgy", "pgyx", "ab", "rs", "pgy",
1087     elg_generate,
1088     elg_check_secret_key,
1089     elg_encrypt,
1090     elg_decrypt,
1091     elg_sign,
1092     elg_verify,
1093     elg_get_nbits,
1094   };