lib/libgcrypt-grub/cipher/dsa.c

   1 /* This file was automatically imported with
   2    import_gcry.py. Please don't modify it */
   3 /* dsa.c - DSA signature algorithm
   4  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
   5  *               2006, 2008  Free Software Foundation, Inc.
   6  *
   7  * This file is part of Libgcrypt.
   8  *
   9  * Libgcrypt is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU Lesser General Public License as
  11  * published by the Free Software Foundation; either version 2.1 of
  12  * the License, or (at your option) any later version.
  13  *
  14  * Libgcrypt is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
  21  */
  22
  23
  24 #include "g10lib.h"
  25 #include "mpi.h"
  26 #include "cipher.h"
  27
  28 typedef struct
  29 {
  30   gcry_mpi_t p;     /* prime */
  31   gcry_mpi_t q;     /* group order */
  32   gcry_mpi_t g;     /* group generator */
  33   gcry_mpi_t y;     /* g^x mod p */
  34 } DSA_public_key;
  35
  36
  37 typedef struct
  38 {
  39   gcry_mpi_t p;     /* prime */
  40   gcry_mpi_t q;     /* group order */
  41   gcry_mpi_t g;     /* group generator */
  42   gcry_mpi_t y;     /* g^x mod p */
  43   gcry_mpi_t x;     /* secret exponent */
  44 } DSA_secret_key;
  45
  46
  47 /* A structure used to hold domain parameters.  */
  48 typedef struct
  49 {
  50   gcry_mpi_t p;     /* prime */
  51   gcry_mpi_t q;     /* group order */
  52   gcry_mpi_t g;     /* group generator */
  53 } dsa_domain_t;
  54
  55
  56 /* A sample 1024 bit DSA key used for the selftests.  */
  57 static const char sample_secret_key[] =
  58 "(private-key"
  59 " (dsa"
  60 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
  61 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
  62 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
  63 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
  64 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
  65 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
  66 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
  67 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
  68 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
  69 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
  70 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
  71 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
  72 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)"
  73 "  (x #11D54E4ADBD3034160F2CED4B7CD292A4EBF3EC0#)))";
  74 /* A sample 1024 bit DSA key used for the selftests (public only).  */
  75 static const char sample_public_key[] =
  76 "(public-key"
  77 " (dsa"
  78 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
  79 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
  80 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
  81 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
  82 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
  83 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
  84 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
  85 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
  86 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
  87 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
  88 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
  89 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
  90 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)))";
  91
  92
  93
  94 \f
  95 static gcry_mpi_t gen_k (gcry_mpi_t q);
  96 static int test_keys (DSA_secret_key *sk, unsigned int qbits);
  97 static int check_secret_key (DSA_secret_key *sk);
  98 static gpg_err_code_t generate (DSA_secret_key *sk,
  99                                 unsigned int nbits,
 100                                 unsigned int qbits,
 101                                 int transient_key,
 102                                 dsa_domain_t *domain,
 103                                 gcry_mpi_t **ret_factors);
 104 static void sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
 105                   DSA_secret_key *skey);
 106 static int verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
 107                    DSA_public_key *pkey);
 108
 109 static void (*progress_cb) (void *,const char *, int, int, int );
 110 static void *progress_cb_data;
 111
 112
 113 void
 114 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
 115                                             int, int, int),
 116                                 void *cb_data)
 117 {
 118   progress_cb = cb;
 119   progress_cb_data = cb_data;
 120 }
 121
 122
 123 static void
 124 progress (int c)
 125 {
 126   if (progress_cb)
 127     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
 128 }
 129
 130
 131 /*
 132  * Generate a random secret exponent k less than q.
 133  */
 134 static gcry_mpi_t
 135 gen_k( gcry_mpi_t q )
 136 {
 137   gcry_mpi_t k = mpi_alloc_secure( mpi_get_nlimbs(q) );
 138   unsigned int nbits = mpi_get_nbits(q);
 139   unsigned int nbytes = (nbits+7)/8;
 140   char *rndbuf = NULL;
 141
 142   if ( DBG_CIPHER )
 143     log_debug("choosing a random k ");
 144   for (;;)
 145     {
 146       if( DBG_CIPHER )
 147         progress('.');
 148
 149       if ( !rndbuf || nbits < 32 )
 150         {
 151           gcry_free(rndbuf);
 152           rndbuf = gcry_random_bytes_secure( (nbits+7)/8, GCRY_STRONG_RANDOM );
 153         }
 154       else
 155         { /* Change only some of the higher bits.  We could improve
 156              this by directly requesting more memory at the first call
 157              to get_random_bytes() and use this the here maybe it is
 158              easier to do this directly in random.c. */
 159           char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
 160           memcpy( rndbuf,pp, 4 );
 161           gcry_free(pp);
 162         }
 163       _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
 164       if ( mpi_test_bit( k, nbits-1 ) )
 165         mpi_set_highbit( k, nbits-1 );
 166       else
 167         {
 168           mpi_set_highbit( k, nbits-1 );
 169           mpi_clear_bit( k, nbits-1 );
 170         }
 171
 172       if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */
 173         {
 174           if( DBG_CIPHER )
 175             progress('+');
 176           continue; /* no  */
 177         }
 178       if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
 179         {
 180           if( DBG_CIPHER )
 181             progress('-');
 182           continue; /* no */
 183         }
 184       break;    /* okay */
 185     }
 186   gcry_free(rndbuf);
 187   if( DBG_CIPHER )
 188     progress('\n');
 189
 190   return k;
 191 }
 192
 193
 194 /* Check that a freshly generated key actually works.  Returns 0 on success. */
 195 static int
 196 test_keys (DSA_secret_key *sk, unsigned int qbits)
 197 {
 198   int result = -1;  /* Default to failure.  */
 199   DSA_public_key pk;
 200   gcry_mpi_t data  = gcry_mpi_new (qbits);
 201   gcry_mpi_t sig_a = gcry_mpi_new (qbits);
 202   gcry_mpi_t sig_b = gcry_mpi_new (qbits);
 203
 204   /* Put the relevant parameters into a public key structure.  */
 205   pk.p = sk->p;
 206   pk.q = sk->q;
 207   pk.g = sk->g;
 208   pk.y = sk->y;
 209
 210   /* Create a random plaintext.  */
 211   gcry_mpi_randomize (data, qbits, GCRY_WEAK_RANDOM);
 212
 213   /* Sign DATA using the secret key.  */
 214   sign (sig_a, sig_b, data, sk);
 215
 216   /* Verify the signature using the public key.  */
 217   if ( !verify (sig_a, sig_b, data, &pk) )
 218     goto leave; /* Signature does not match.  */
 219
 220   /* Modify the data and check that the signing fails.  */
 221   gcry_mpi_add_ui (data, data, 1);
 222   if ( verify (sig_a, sig_b, data, &pk) )
 223     goto leave; /* Signature matches but should not.  */
 224
 225   result = 0; /* The test succeeded.  */
 226
 227  leave:
 228   gcry_mpi_release (sig_b);
 229   gcry_mpi_release (sig_a);
 230   gcry_mpi_release (data);
 231   return result;
 232 }
 233
 234
 235
 236 /*
 237    Generate a DSA key pair with a key of size NBITS.  If transient_key
 238    is true the key is generated using the standard RNG and not the
 239    very secure one.
 240
 241    Returns: 2 structures filled with all needed values
 242             and an array with the n-1 factors of (p-1)
 243  */
 244 static gpg_err_code_t
 245 generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
 246           int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
 247 {
 248   gcry_mpi_t p;    /* the prime */
 249   gcry_mpi_t q;    /* the 160 bit prime factor */
 250   gcry_mpi_t g;    /* the generator */
 251   gcry_mpi_t y;    /* g^x mod p */
 252   gcry_mpi_t x;    /* the secret exponent */
 253   gcry_mpi_t h, e;  /* helper */
 254   unsigned char *rndbuf;
 255   gcry_random_level_t random_level;
 256
 257   if (qbits)
 258     ; /* Caller supplied qbits.  Use this value.  */
 259   else if ( nbits >= 512 && nbits <= 1024 )
 260     qbits = 160;
 261   else if ( nbits == 2048 )
 262     qbits = 224;
 263   else if ( nbits == 3072 )
 264     qbits = 256;
 265   else if ( nbits == 7680 )
 266     qbits = 384;
 267   else if ( nbits == 15360 )
 268     qbits = 512;
 269   else
 270     return GPG_ERR_INV_VALUE;
 271
 272   if (qbits < 160 || qbits > 512 || (qbits%8) )
 273     return GPG_ERR_INV_VALUE;
 274   if (nbits < 2*qbits || nbits > 15360)
 275     return GPG_ERR_INV_VALUE;
 276
 277   if (fips_mode ())
 278     {
 279       if (nbits < 1024)
 280         return GPG_ERR_INV_VALUE;
 281       if (transient_key)
 282         return GPG_ERR_INV_VALUE;
 283     }
 284
 285   if (domain->p && domain->q && domain->g)
 286     {
 287       /* Domain parameters are given; use them.  */
 288       p = mpi_copy (domain->p);
 289       q = mpi_copy (domain->q);
 290       g = mpi_copy (domain->g);
 291       gcry_assert (mpi_get_nbits (p) == nbits);
 292       gcry_assert (mpi_get_nbits (q) == qbits);
 293       h = mpi_alloc (0);
 294       e = NULL;
 295     }
 296   else
 297     {
 298       /* Generate new domain parameters.  */
 299       p = _gcry_generate_elg_prime (1, nbits, qbits, NULL, ret_factors);
 300       /* Get q out of factors.  */
 301       q = mpi_copy ((*ret_factors)[0]);
 302       gcry_assert (mpi_get_nbits (q) == qbits);
 303
 304       /* Find a generator g (h and e are helpers).
 305          e = (p-1)/q */
 306       e = mpi_alloc (mpi_get_nlimbs (p));
 307       mpi_sub_ui (e, p, 1);
 308       mpi_fdiv_q (e, e, q);
 309       g = mpi_alloc (mpi_get_nlimbs (p));
 310       h = mpi_alloc_set_ui (1); /* (We start with 2.) */
 311       do
 312         {
 313           mpi_add_ui (h, h, 1);
 314           /* g = h^e mod p */
 315           gcry_mpi_powm (g, h, e, p);
 316         }
 317       while (!mpi_cmp_ui (g, 1));  /* Continue until g != 1. */
 318     }
 319
 320   /* Select a random number X with the property:
 321    *     0 < x < q-1
 322    * This must be a very good random number because this is the secret
 323    * part.  The random quality depends on the transient_key flag.  */
 324   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
 325   if (DBG_CIPHER)
 326     log_debug("choosing a random x%s", transient_key? " (transient-key)":"");
 327   gcry_assert( qbits >= 160 );
 328   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
 329   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
 330   rndbuf = NULL;
 331   do
 332     {
 333       if( DBG_CIPHER )
 334         progress('.');
 335       if( !rndbuf )
 336         rndbuf = gcry_random_bytes_secure ((qbits+7)/8, random_level);
 337       else
 338         { /* Change only some of the higher bits (= 2 bytes)*/
 339           char *r = gcry_random_bytes_secure (2, random_level);
 340           memcpy(rndbuf, r, 2 );
 341           gcry_free(r);
 342         }
 343
 344       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
 345       mpi_clear_highbit( x, qbits+1 );
 346     }
 347   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
 348   gcry_free(rndbuf);
 349   mpi_free( e );
 350   mpi_free( h );
 351
 352   /* y = g^x mod p */
 353   y = mpi_alloc( mpi_get_nlimbs(p) );
 354   gcry_mpi_powm( y, g, x, p );
 355
 356   if( DBG_CIPHER )
 357     {
 358       progress('\n');
 359       log_mpidump("dsa  p", p );
 360       log_mpidump("dsa  q", q );
 361       log_mpidump("dsa  g", g );
 362       log_mpidump("dsa  y", y );
 363       log_mpidump("dsa  x", x );
 364     }
 365
 366   /* Copy the stuff to the key structures. */
 367   sk->p = p;
 368   sk->q = q;
 369   sk->g = g;
 370   sk->y = y;
 371   sk->x = x;
 372
 373   /* Now we can test our keys (this should never fail!). */
 374   if ( test_keys (sk, qbits) )
 375     {
 376       gcry_mpi_release (sk->p); sk->p = NULL;
 377       gcry_mpi_release (sk->q); sk->q = NULL;
 378       gcry_mpi_release (sk->g); sk->g = NULL;
 379       gcry_mpi_release (sk->y); sk->y = NULL;
 380       gcry_mpi_release (sk->x); sk->x = NULL;
 381       fips_signal_error ("self-test after key generation failed");
 382       return GPG_ERR_SELFTEST_FAILED;
 383     }
 384   return 0;
 385 }
 386
 387
 388 /* Generate a DSA key pair with a key of size NBITS using the
 389    algorithm given in FIPS-186-3.  If USE_FIPS186_2 is true,
 390    FIPS-186-2 is used and thus the length is restricted to 1024/160.
 391    If DERIVEPARMS is not NULL it may contain a seed value.  If domain
 392    parameters are specified in DOMAIN, DERIVEPARMS may not be given
 393    and NBITS and QBITS must match the specified domain parameters.  */
 394 static gpg_err_code_t
 395 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
 396                   gcry_sexp_t deriveparms, int use_fips186_2,
 397                   dsa_domain_t *domain,
 398                   int *r_counter, void **r_seed, size_t *r_seedlen,
 399                   gcry_mpi_t *r_h)
 400 {
 401   gpg_err_code_t ec;
 402   struct {
 403     gcry_sexp_t sexp;
 404     const void *seed;
 405     size_t seedlen;
 406   } initial_seed = { NULL, NULL, 0 };
 407   gcry_mpi_t prime_q = NULL;
 408   gcry_mpi_t prime_p = NULL;
 409   gcry_mpi_t value_g = NULL; /* The generator. */
 410   gcry_mpi_t value_y = NULL; /* g^x mod p */
 411   gcry_mpi_t value_x = NULL; /* The secret exponent. */
 412   gcry_mpi_t value_h = NULL; /* Helper.  */
 413   gcry_mpi_t value_e = NULL; /* Helper.  */
 414
 415   /* Preset return values.  */
 416   *r_counter = 0;
 417   *r_seed = NULL;
 418   *r_seedlen = 0;
 419   *r_h = NULL;
 420
 421   /* Derive QBITS from NBITS if requested  */
 422   if (!qbits)
 423     {
 424       if (nbits == 1024)
 425         qbits = 160;
 426       else if (nbits == 2048)
 427         qbits = 224;
 428       else if (nbits == 3072)
 429         qbits = 256;
 430     }
 431
 432   /* Check that QBITS and NBITS match the standard.  Note that FIPS
 433      186-3 uses N for QBITS and L for NBITS.  */
 434   if (nbits == 1024 && qbits == 160)
 435     ;
 436   else if (nbits == 2048 && qbits == 224)
 437     ;
 438   else if (nbits == 2048 && qbits == 256)
 439     ;
 440   else if (nbits == 3072 && qbits == 256)
 441     ;
 442   else
 443     return GPG_ERR_INV_VALUE;
 444
 445   if (domain->p && domain->q && domain->g)
 446     {
 447       /* Domain parameters are given; use them.  */
 448       prime_p = mpi_copy (domain->p);
 449       prime_q = mpi_copy (domain->q);
 450       value_g = mpi_copy (domain->g);
 451       gcry_assert (mpi_get_nbits (prime_p) == nbits);
 452       gcry_assert (mpi_get_nbits (prime_q) == qbits);
 453       gcry_assert (!deriveparms);
 454       ec = 0;
 455     }
 456   else
 457     {
 458       /* Generate new domain parameters.  */
 459
 460       /* Get an initial seed value.  */
 461       if (deriveparms)
 462         {
 463           initial_seed.sexp = gcry_sexp_find_token (deriveparms, "seed", 0);
 464           if (initial_seed.sexp)
 465             initial_seed.seed = gcry_sexp_nth_data (initial_seed.sexp, 1,
 466                                                     &initial_seed.seedlen);
 467         }
 468
 469       /* Fixme: Enable 186-3 after it has been approved and after fixing
 470          the generation function.  */
 471       /*   if (use_fips186_2) */
 472       (void)use_fips186_2;
 473       ec = _gcry_generate_fips186_2_prime (nbits, qbits,
 474                                            initial_seed.seed,
 475                                            initial_seed.seedlen,
 476                                            &prime_q, &prime_p,
 477                                            r_counter,
 478                                            r_seed, r_seedlen);
 479       /*   else */
 480       /*     ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0, */
 481       /*                                          &prime_q, &prime_p, */
 482       /*                                          r_counter, */
 483       /*                                          r_seed, r_seedlen, NULL); */
 484       gcry_sexp_release (initial_seed.sexp);
 485       if (ec)
 486         goto leave;
 487
 488       /* Find a generator g (h and e are helpers).
 489          e = (p-1)/q */
 490       value_e = mpi_alloc_like (prime_p);
 491       mpi_sub_ui (value_e, prime_p, 1);
 492       mpi_fdiv_q (value_e, value_e, prime_q );
 493       value_g = mpi_alloc_like (prime_p);
 494       value_h = mpi_alloc_set_ui (1);
 495       do
 496         {
 497           mpi_add_ui (value_h, value_h, 1);
 498           /* g = h^e mod p */
 499           mpi_powm (value_g, value_h, value_e, prime_p);
 500         }
 501       while (!mpi_cmp_ui (value_g, 1));  /* Continue until g != 1.  */
 502     }
 503
 504
 505   /* Select a random number x with:  0 < x < q  */
 506   value_x = gcry_mpi_snew (qbits);
 507   do
 508     {
 509       if( DBG_CIPHER )
 510         progress('.');
 511       gcry_mpi_randomize (value_x, qbits, GCRY_VERY_STRONG_RANDOM);
 512       mpi_clear_highbit (value_x, qbits+1);
 513     }
 514   while (!(mpi_cmp_ui (value_x, 0) > 0 && mpi_cmp (value_x, prime_q) < 0));
 515
 516   /* y = g^x mod p */
 517   value_y = mpi_alloc_like (prime_p);
 518   gcry_mpi_powm (value_y, value_g, value_x, prime_p);
 519
 520   if (DBG_CIPHER)
 521     {
 522       progress('\n');
 523       log_mpidump("dsa  p", prime_p );
 524       log_mpidump("dsa  q", prime_q );
 525       log_mpidump("dsa  g", value_g );
 526       log_mpidump("dsa  y", value_y );
 527       log_mpidump("dsa  x", value_x );
 528       log_mpidump("dsa  h", value_h );
 529     }
 530
 531   /* Copy the stuff to the key structures. */
 532   sk->p = prime_p; prime_p = NULL;
 533   sk->q = prime_q; prime_q = NULL;
 534   sk->g = value_g; value_g = NULL;
 535   sk->y = value_y; value_y = NULL;
 536   sk->x = value_x; value_x = NULL;
 537   *r_h = value_h; value_h = NULL;
 538
 539  leave:
 540   gcry_mpi_release (prime_p);
 541   gcry_mpi_release (prime_q);
 542   gcry_mpi_release (value_g);
 543   gcry_mpi_release (value_y);
 544   gcry_mpi_release (value_x);
 545   gcry_mpi_release (value_h);
 546   gcry_mpi_release (value_e);
 547
 548   /* As a last step test this keys (this should never fail of course). */
 549   if (!ec && test_keys (sk, qbits) )
 550     {
 551       gcry_mpi_release (sk->p); sk->p = NULL;
 552       gcry_mpi_release (sk->q); sk->q = NULL;
 553       gcry_mpi_release (sk->g); sk->g = NULL;
 554       gcry_mpi_release (sk->y); sk->y = NULL;
 555       gcry_mpi_release (sk->x); sk->x = NULL;
 556       fips_signal_error ("self-test after key generation failed");
 557       ec = GPG_ERR_SELFTEST_FAILED;
 558     }
 559
 560   if (ec)
 561     {
 562       *r_counter = 0;
 563       gcry_free (*r_seed); *r_seed = NULL;
 564       *r_seedlen = 0;
 565       gcry_mpi_release (*r_h); *r_h = NULL;
 566     }
 567
 568   return ec;
 569 }
 570
 571
 572
 573 /*
 574    Test whether the secret key is valid.
 575    Returns: if this is a valid key.
 576  */
 577 static int
 578 check_secret_key( DSA_secret_key *sk )
 579 {
 580   int rc;
 581   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
 582
 583   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
 584   rc = !mpi_cmp( y, sk->y );
 585   mpi_free( y );
 586   return rc;
 587 }
 588
 589
 590
 591 /*
 592    Make a DSA signature from HASH and put it into r and s.
 593  */
 594 static void
 595 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
 596 {
 597   gcry_mpi_t k;
 598   gcry_mpi_t kinv;
 599   gcry_mpi_t tmp;
 600
 601   /* Select a random k with 0 < k < q */
 602   k = gen_k( skey->q );
 603
 604   /* r = (a^k mod p) mod q */
 605   gcry_mpi_powm( r, skey->g, k, skey->p );
 606   mpi_fdiv_r( r, r, skey->q );
 607
 608   /* kinv = k^(-1) mod q */
 609   kinv = mpi_alloc( mpi_get_nlimbs(k) );
 610   mpi_invm(kinv, k, skey->q );
 611
 612   /* s = (kinv * ( hash + x * r)) mod q */
 613   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
 614   mpi_mul( tmp, skey->x, r );
 615   mpi_add( tmp, tmp, hash );
 616   mpi_mulm( s , kinv, tmp, skey->q );
 617
 618   mpi_free(k);
 619   mpi_free(kinv);
 620   mpi_free(tmp);
 621 }
 622
 623
 624 /*
 625    Returns true if the signature composed from R and S is valid.
 626  */
 627 static int
 628 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
 629 {
 630   int rc;
 631   gcry_mpi_t w, u1, u2, v;
 632   gcry_mpi_t base[3];
 633   gcry_mpi_t ex[3];
 634
 635   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
 636     return 0; /* assertion      0 < r < q  failed */
 637   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
 638     return 0; /* assertion      0 < s < q  failed */
 639
 640   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
 641   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
 642   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
 643   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
 644
 645   /* w = s^(-1) mod q */
 646   mpi_invm( w, s, pkey->q );
 647
 648   /* u1 = (hash * w) mod q */
 649   mpi_mulm( u1, hash, w, pkey->q );
 650
 651   /* u2 = r * w mod q  */
 652   mpi_mulm( u2, r, w, pkey->q );
 653
 654   /* v =  g^u1 * y^u2 mod p mod q */
 655   base[0] = pkey->g; ex[0] = u1;
 656   base[1] = pkey->y; ex[1] = u2;
 657   base[2] = NULL;    ex[2] = NULL;
 658   mpi_mulpowm( v, base, ex, pkey->p );
 659   mpi_fdiv_r( v, v, pkey->q );
 660
 661   rc = !mpi_cmp( v, r );
 662
 663   mpi_free(w);
 664   mpi_free(u1);
 665   mpi_free(u2);
 666   mpi_free(v);
 667
 668   return rc;
 669 }
 670
 671
 672 /*********************************************
 673  **************  interface  ******************
 674  *********************************************/
 675
 676 static gcry_err_code_t
 677 dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
 678                   const gcry_sexp_t genparms,
 679                   gcry_mpi_t *skey, gcry_mpi_t **retfactors,
 680                   gcry_sexp_t *r_extrainfo)
 681 {
 682   gpg_err_code_t ec;
 683   DSA_secret_key sk;
 684   gcry_sexp_t l1;
 685   unsigned int qbits = 0;
 686   gcry_sexp_t deriveparms = NULL;
 687   gcry_sexp_t seedinfo = NULL;
 688   int transient_key = 0;
 689   int use_fips186_2 = 0;
 690   int use_fips186 = 0;
 691   dsa_domain_t domain;
 692
 693   (void)algo;    /* No need to check it.  */
 694   (void)evalue;  /* Not required for DSA. */
 695
 696   memset (&domain, 0, sizeof domain);
 697
 698   if (genparms)
 699     {
 700       gcry_sexp_t domainsexp;
 701
 702       /* Parse the optional qbits element.  */
 703       l1 = gcry_sexp_find_token (genparms, "qbits", 0);
 704       if (l1)
 705         {
 706           char buf[50];
 707           const char *s;
 708           size_t n;
 709
 710           s = gcry_sexp_nth_data (l1, 1, &n);
 711           if (!s || n >= DIM (buf) - 1 )
 712             {
 713               gcry_sexp_release (l1);
 714               return GPG_ERR_INV_OBJ; /* No value or value too large.  */
 715             }
 716           memcpy (buf, s, n);
 717           buf[n] = 0;
 718           qbits = (unsigned int)strtoul (buf, NULL, 0);
 719           gcry_sexp_release (l1);
 720         }
 721
 722       /* Parse the optional transient-key flag.  */
 723       l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
 724       if (l1)
 725         {
 726           transient_key = 1;
 727           gcry_sexp_release (l1);
 728         }
 729
 730       /* Get the optional derive parameters.  */
 731       deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
 732
 733       /* Parse the optional "use-fips186" flags.  */
 734       l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
 735       if (l1)
 736         {
 737           use_fips186 = 1;
 738           gcry_sexp_release (l1);
 739         }
 740       l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
 741       if (l1)
 742         {
 743           use_fips186_2 = 1;
 744           gcry_sexp_release (l1);
 745         }
 746
 747       /* Check whether domain parameters are given.  */
 748       domainsexp = gcry_sexp_find_token (genparms, "domain", 0);
 749       if (domainsexp)
 750         {
 751           /* DERIVEPARMS can't be used together with domain
 752              parameters.  NBITS abnd QBITS may not be specified
 753              because there values are derived from the domain
 754              parameters.  */
 755           if (deriveparms || qbits || nbits)
 756             {
 757               gcry_sexp_release (domainsexp);
 758               gcry_sexp_release (deriveparms);
 759               return GPG_ERR_INV_VALUE;
 760             }
 761
 762           /* Put all domain parameters into the domain object.  */
 763           l1 = gcry_sexp_find_token (domainsexp, "p", 0);
 764           domain.p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
 765           gcry_sexp_release (l1);
 766           l1 = gcry_sexp_find_token (domainsexp, "q", 0);
 767           domain.q = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
 768           gcry_sexp_release (l1);
 769           l1 = gcry_sexp_find_token (domainsexp, "g", 0);
 770           domain.g = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
 771           gcry_sexp_release (l1);
 772           gcry_sexp_release (domainsexp);
 773
 774           /* Check that all domain parameters are available.  */
 775           if (!domain.p || !domain.q || !domain.g)
 776             {
 777               gcry_mpi_release (domain.p);
 778               gcry_mpi_release (domain.q);
 779               gcry_mpi_release (domain.g);
 780               gcry_sexp_release (deriveparms);
 781               return GPG_ERR_MISSING_VALUE;
 782             }
 783
 784           /* Get NBITS and QBITS from the domain parameters.  */
 785           nbits = mpi_get_nbits (domain.p);
 786           qbits = mpi_get_nbits (domain.q);
 787         }
 788     }
 789
 790   if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
 791     {
 792       int counter;
 793       void *seed;
 794       size_t seedlen;
 795       gcry_mpi_t h_value;
 796
 797       ec = generate_fips186 (&sk, nbits, qbits, deriveparms, use_fips186_2,
 798                              &domain,
 799                              &counter, &seed, &seedlen, &h_value);
 800       gcry_sexp_release (deriveparms);
 801       if (!ec && h_value)
 802         {
 803           /* Format the seed-values unless domain parameters are used
 804              for which a H_VALUE of NULL is an indication.  */
 805           ec = gpg_err_code (gcry_sexp_build
 806                              (&seedinfo, NULL,
 807                               "(seed-values(counter %d)(seed %b)(h %m))",
 808                               counter, (int)seedlen, seed, h_value));
 809           if (ec)
 810             {
 811               gcry_mpi_release (sk.p); sk.p = NULL;
 812               gcry_mpi_release (sk.q); sk.q = NULL;
 813               gcry_mpi_release (sk.g); sk.g = NULL;
 814               gcry_mpi_release (sk.y); sk.y = NULL;
 815               gcry_mpi_release (sk.x); sk.x = NULL;
 816             }
 817           gcry_free (seed);
 818           gcry_mpi_release (h_value);
 819         }
 820     }
 821   else
 822     {
 823       ec = generate (&sk, nbits, qbits, transient_key, &domain, retfactors);
 824     }
 825
 826   gcry_mpi_release (domain.p);
 827   gcry_mpi_release (domain.q);
 828   gcry_mpi_release (domain.g);
 829
 830   if (!ec)
 831     {
 832       skey[0] = sk.p;
 833       skey[1] = sk.q;
 834       skey[2] = sk.g;
 835       skey[3] = sk.y;
 836       skey[4] = sk.x;
 837
 838       if (!r_extrainfo)
 839         {
 840           /* Old style interface - return the factors - if any - at
 841              retfactors.  */
 842         }
 843       else if (!*retfactors && !seedinfo)
 844         {
 845           /* No factors and no seedinfo, thus there is nothing to return.  */
 846           *r_extrainfo = NULL;
 847         }
 848       else
 849         {
 850           /* Put the factors into extrainfo and set retfactors to NULL
 851              to make use of the new interface.  Note that the factors
 852              are not confidential thus we can store them in standard
 853              memory.  */
 854           int nfactors, i, j;
 855           char *p;
 856           char *format = NULL;
 857           void **arg_list = NULL;
 858
 859           for (nfactors=0; *retfactors && (*retfactors)[nfactors]; nfactors++)
 860             ;
 861           /* Allocate space for the format string:
 862                "(misc-key-info%S(pm1-factors%m))"
 863              with one "%m" for each factor and construct it.  */
 864           format = gcry_malloc (50 + 2*nfactors);
 865           if (!format)
 866             ec = gpg_err_code_from_syserror ();
 867           else
 868             {
 869               p = stpcpy (format, "(misc-key-info");
 870               if (seedinfo)
 871                 p = stpcpy (p, "%S");
 872               if (nfactors)
 873                 {
 874                   p = stpcpy (p, "(pm1-factors");
 875                   for (i=0; i < nfactors; i++)
 876                     p = stpcpy (p, "%m");
 877                   p = stpcpy (p, ")");
 878                 }
 879               p = stpcpy (p, ")");
 880
 881               /* Allocate space for the list of factors plus one for
 882                  an S-expression plus an extra NULL entry for safety
 883                  and fill it with the factors.  */
 884               arg_list = gcry_calloc (nfactors+1+1, sizeof *arg_list);
 885               if (!arg_list)
 886                 ec = gpg_err_code_from_syserror ();
 887               else
 888                 {
 889                   i = 0;
 890                   if (seedinfo)
 891                     arg_list[i++] = &seedinfo;
 892                   for (j=0; j < nfactors; j++)
 893                     arg_list[i++] = (*retfactors) + j;
 894                   arg_list[i] = NULL;
 895
 896                   ec = gpg_err_code (gcry_sexp_build_array
 897                                      (r_extrainfo, NULL, format, arg_list));
 898                 }
 899             }
 900
 901           gcry_free (arg_list);
 902           gcry_free (format);
 903           for (i=0; i < nfactors; i++)
 904             {
 905               gcry_mpi_release ((*retfactors)[i]);
 906               (*retfactors)[i] = NULL;
 907             }
 908           *retfactors = NULL;
 909           if (ec)
 910             {
 911               for (i=0; i < 5; i++)
 912                 {
 913                   gcry_mpi_release (skey[i]);
 914                   skey[i] = NULL;
 915                 }
 916             }
 917         }
 918     }
 919
 920   gcry_sexp_release (seedinfo);
 921   return ec;
 922 }
 923
 924
 925 static gcry_err_code_t
 926 dsa_generate (int algo, unsigned int nbits, unsigned long evalue,
 927               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
 928 {
 929   (void)evalue;
 930   return dsa_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
 931 }
 932
 933
 934
 935 static gcry_err_code_t
 936 dsa_check_secret_key (int algo, gcry_mpi_t *skey)
 937 {
 938   gcry_err_code_t err = GPG_ERR_NO_ERROR;
 939   DSA_secret_key sk;
 940
 941   (void)algo;
 942
 943   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
 944     err = GPG_ERR_BAD_MPI;
 945   else
 946     {
 947       sk.p = skey[0];
 948       sk.q = skey[1];
 949       sk.g = skey[2];
 950       sk.y = skey[3];
 951       sk.x = skey[4];
 952       if (! check_secret_key (&sk))
 953         err = GPG_ERR_BAD_SECKEY;
 954     }
 955
 956   return err;
 957 }
 958
 959
 960 static gcry_err_code_t
 961 dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
 962 {
 963   gcry_err_code_t err = GPG_ERR_NO_ERROR;
 964   DSA_secret_key sk;
 965
 966   (void)algo;
 967
 968   if ((! data)
 969       || (! skey[0]) || (! skey[1]) || (! skey[2])
 970       || (! skey[3]) || (! skey[4]))
 971     err = GPG_ERR_BAD_MPI;
 972   else
 973     {
 974       sk.p = skey[0];
 975       sk.q = skey[1];
 976       sk.g = skey[2];
 977       sk.y = skey[3];
 978       sk.x = skey[4];
 979       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
 980       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
 981       sign (resarr[0], resarr[1], data, &sk);
 982     }
 983   return err;
 984 }
 985
 986 static gcry_err_code_t
 987 dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
 988             int (*cmp) (void *, gcry_mpi_t), void *opaquev)
 989 {
 990   gcry_err_code_t err = GPG_ERR_NO_ERROR;
 991   DSA_public_key pk;
 992
 993   (void)algo;
 994   (void)cmp;
 995   (void)opaquev;
 996
 997   if ((! data[0]) || (! data[1]) || (! hash)
 998       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
 999     err = GPG_ERR_BAD_MPI;
1000   else
1001     {
1002       pk.p = pkey[0];
1003       pk.q = pkey[1];
1004       pk.g = pkey[2];
1005       pk.y = pkey[3];
1006       if (! verify (data[0], data[1], hash, &pk))
1007         err = GPG_ERR_BAD_SIGNATURE;
1008     }
1009   return err;
1010 }
1011
1012
1013 static unsigned int
1014 dsa_get_nbits (int algo, gcry_mpi_t *pkey)
1015 {
1016   (void)algo;
1017
1018   return mpi_get_nbits (pkey[0]);
1019 }
1020
1021
1022 \f
1023 /*
1024      Self-test section.
1025  */
1026
1027
1028
1029
1030
1031 /* Run a full self-test for ALGO and return 0 on success.  */
1032
1033
1034
1035 \f
1036 static const char *dsa_names[] =
1037   {
1038     "dsa",
1039     "openpgp-dsa",
1040     NULL,
1041   };
1042
1043 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1044   {
1045     "DSA", dsa_names,
1046     "pqgy", "pqgyx", "", "rs", "pqgy",
1047     GCRY_PK_USAGE_SIGN,
1048     dsa_generate,
1049     dsa_check_secret_key,
1050     NULL,
1051     NULL,
1052     dsa_sign,
1053     dsa_verify,
1054     dsa_get_nbits
1055   };
1056 pk_extra_spec_t _gcry_pubkey_extraspec_dsa =
1057   {
1058     run_selftests,
1059     dsa_generate_ext
1060   };
1061