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