pqg.c (66873B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5 /* 6 * PQG parameter generation/verification. Based on FIPS 186-3. 7 */ 8 #ifdef FREEBL_NO_DEPEND 9 #include "stubs.h" 10 #endif 11 12 #include "prerr.h" 13 #include "secerr.h" 14 15 #include "prtypes.h" 16 #include "blapi.h" 17 #include "secitem.h" 18 #include "mpi.h" 19 #include "mpprime.h" 20 #include "mplogic.h" 21 #include "secmpi.h" 22 23 #define MAX_ITERATIONS 1000 /* Maximum number of iterations of primegen */ 24 25 typedef enum { 26 FIPS186_1_TYPE, /* Probablistic */ 27 FIPS186_3_TYPE, /* Probablistic */ 28 FIPS186_3_ST_TYPE /* Shawe-Taylor provable */ 29 } pqgGenType; 30 31 /* 32 * These test iterations are quite a bit larger than we previously had. 33 * This is because FIPS 186-3 is worried about the primes in PQG generation. 34 * It may be possible to purposefully construct composites which more 35 * iterations of Miller-Rabin than the for your normal randomly selected 36 * numbers.There are 3 ways to counter this: 1) use one of the cool provably 37 * prime algorithms (which would require a lot more work than DSA-2 deservers. 38 * 2) add a Lucas primality test (which requires coding a Lucas primality test, 39 * or 3) use a larger M-R test count. I chose the latter. It increases the time 40 * that it takes to prove the selected prime, but it shouldn't increase the 41 * overall time to run the algorithm (non-primes should still faile M-R 42 * realively quickly). If you want to get that last bit of performance, 43 * implement Lucas and adjust these two functions. See FIPS 186-3 Appendix C 44 * and F for more information. 45 */ 46 static int 47 prime_testcount_p(int L, int N) 48 { 49 switch (L) { 50 case 1024: 51 return 40; 52 case 2048: 53 return 56; 54 case 3072: 55 return 64; 56 default: 57 break; 58 } 59 return 50; /* L = 512-960 */ 60 } 61 62 /* The q numbers are different if you run M-R followd by Lucas. I created 63 * a separate function so if someone wanted to add the Lucas check, they 64 * could do so fairly easily */ 65 static int 66 prime_testcount_q(int L, int N) 67 { 68 return prime_testcount_p(L, N); 69 } 70 71 /* 72 * generic function to make sure our input matches DSA2 requirements 73 * this gives us one place to go if we need to bump the requirements in the 74 * future. 75 */ 76 static SECStatus 77 pqg_validate_dsa2(unsigned int L, unsigned int N) 78 { 79 80 switch (L) { 81 case 1024: 82 if (N != DSA1_Q_BITS) { 83 PORT_SetError(SEC_ERROR_INVALID_ARGS); 84 return SECFailure; 85 } 86 break; 87 case 2048: 88 if ((N != 224) && (N != 256)) { 89 PORT_SetError(SEC_ERROR_INVALID_ARGS); 90 return SECFailure; 91 } 92 break; 93 case 3072: 94 if (N != 256) { 95 PORT_SetError(SEC_ERROR_INVALID_ARGS); 96 return SECFailure; 97 } 98 break; 99 default: 100 PORT_SetError(SEC_ERROR_INVALID_ARGS); 101 return SECFailure; 102 } 103 return SECSuccess; 104 } 105 106 static unsigned int 107 pqg_get_default_N(unsigned int L) 108 { 109 unsigned int N = 0; 110 switch (L) { 111 case 1024: 112 N = DSA1_Q_BITS; 113 break; 114 case 2048: 115 N = 224; 116 break; 117 case 3072: 118 N = 256; 119 break; 120 default: 121 PORT_SetError(SEC_ERROR_INVALID_ARGS); 122 break; /* N already set to zero */ 123 } 124 return N; 125 } 126 127 /* 128 * Select the lowest hash algorithm usable 129 */ 130 static HASH_HashType 131 getFirstHash(unsigned int L, unsigned int N) 132 { 133 if (N < 224) { 134 return HASH_AlgSHA1; 135 } 136 if (N < 256) { 137 return HASH_AlgSHA224; 138 } 139 if (N < 384) { 140 return HASH_AlgSHA256; 141 } 142 if (N < 512) { 143 return HASH_AlgSHA384; 144 } 145 return HASH_AlgSHA512; 146 } 147 148 /* 149 * find the next usable hash algorthim 150 */ 151 static HASH_HashType 152 getNextHash(HASH_HashType hashtype) 153 { 154 switch (hashtype) { 155 case HASH_AlgSHA1: 156 hashtype = HASH_AlgSHA224; 157 break; 158 case HASH_AlgSHA224: 159 hashtype = HASH_AlgSHA256; 160 break; 161 case HASH_AlgSHA256: 162 hashtype = HASH_AlgSHA384; 163 break; 164 case HASH_AlgSHA384: 165 hashtype = HASH_AlgSHA512; 166 break; 167 case HASH_AlgSHA512: 168 default: 169 hashtype = HASH_AlgTOTAL; 170 break; 171 } 172 return hashtype; 173 } 174 175 static unsigned int 176 HASH_ResultLen(HASH_HashType type) 177 { 178 const SECHashObject *hash_obj = HASH_GetRawHashObject(type); 179 PORT_Assert(hash_obj != NULL); 180 if (hash_obj == NULL) { 181 /* type is always a valid HashType. Thus a null hash_obj must be a bug */ 182 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); 183 return 0; 184 } 185 PORT_Assert(hash_obj->length != 0); 186 return hash_obj->length; 187 } 188 189 SECStatus 190 PQG_HashBuf(HASH_HashType type, unsigned char *dest, 191 const unsigned char *src, PRUint32 src_len) 192 { 193 const SECHashObject *hash_obj = HASH_GetRawHashObject(type); 194 void *hashcx = NULL; 195 unsigned int dummy; 196 197 if (hash_obj == NULL) { 198 return SECFailure; 199 } 200 201 hashcx = hash_obj->create(); 202 if (hashcx == NULL) { 203 return SECFailure; 204 } 205 hash_obj->begin(hashcx); 206 hash_obj->update(hashcx, src, src_len); 207 hash_obj->end(hashcx, dest, &dummy, hash_obj->length); 208 hash_obj->destroy(hashcx, PR_TRUE); 209 return SECSuccess; 210 } 211 212 unsigned int 213 PQG_GetLength(const SECItem *obj) 214 { 215 unsigned int len = obj->len; 216 217 if (obj->data == NULL) { 218 return 0; 219 } 220 if (len > 1 && obj->data[0] == 0) { 221 len--; 222 } 223 return len; 224 } 225 226 SECStatus 227 PQG_Check(const PQGParams *params) 228 { 229 unsigned int L, N; 230 SECStatus rv = SECSuccess; 231 232 if (params == NULL) { 233 PORT_SetError(SEC_ERROR_INVALID_ARGS); 234 return SECFailure; 235 } 236 237 L = PQG_GetLength(¶ms->prime) * PR_BITS_PER_BYTE; 238 N = PQG_GetLength(¶ms->subPrime) * PR_BITS_PER_BYTE; 239 240 if (L < 1024) { 241 int j; 242 243 /* handle DSA1 pqg parameters with less thatn 1024 bits*/ 244 if (N != DSA1_Q_BITS) { 245 PORT_SetError(SEC_ERROR_INVALID_ARGS); 246 return SECFailure; 247 } 248 j = PQG_PBITS_TO_INDEX(L); 249 if (j < 0) { 250 PORT_SetError(SEC_ERROR_INVALID_ARGS); 251 rv = SECFailure; 252 } 253 } else { 254 /* handle DSA2 parameters (includes DSA1, 1024 bits) */ 255 rv = pqg_validate_dsa2(L, N); 256 } 257 return rv; 258 } 259 260 HASH_HashType 261 PQG_GetHashType(const PQGParams *params) 262 { 263 unsigned int L, N; 264 265 if (params == NULL) { 266 PORT_SetError(SEC_ERROR_INVALID_ARGS); 267 return HASH_AlgNULL; 268 } 269 270 L = PQG_GetLength(¶ms->prime) * PR_BITS_PER_BYTE; 271 N = PQG_GetLength(¶ms->subPrime) * PR_BITS_PER_BYTE; 272 return getFirstHash(L, N); 273 } 274 275 /* Get a seed for generating P and Q. If in testing mode, copy in the 276 ** seed from FIPS 186-1 appendix 5. Otherwise, obtain bytes from the 277 ** global random number generator. 278 */ 279 static SECStatus 280 getPQseed(SECItem *seed, PLArenaPool *arena) 281 { 282 SECStatus rv; 283 284 if (!seed->data) { 285 seed->data = (unsigned char *)PORT_ArenaZAlloc(arena, seed->len); 286 } 287 if (!seed->data) { 288 PORT_SetError(SEC_ERROR_NO_MEMORY); 289 return SECFailure; 290 } 291 rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len); 292 /* 293 * NIST CMVP disallows a sequence of 20 bytes with the most 294 * significant byte equal to 0. Perhaps they interpret 295 * "a sequence of at least 160 bits" as "a number >= 2^159". 296 * So we always set the most significant bit to 1. (bug 334533) 297 */ 298 seed->data[0] |= 0x80; 299 return rv; 300 } 301 302 /* Generate a candidate h value. If in testing mode, use the h value 303 ** specified in FIPS 186-1 appendix 5, h = 2. Otherwise, obtain bytes 304 ** from the global random number generator. 305 */ 306 static SECStatus 307 generate_h_candidate(SECItem *hit, mp_int *H) 308 { 309 SECStatus rv = SECSuccess; 310 mp_err err = MP_OKAY; 311 #ifdef FIPS_186_1_A5_TEST 312 memset(hit->data, 0, hit->len); 313 hit->data[hit->len - 1] = 0x02; 314 #else 315 rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len); 316 #endif 317 if (rv) 318 return SECFailure; 319 err = mp_read_unsigned_octets(H, hit->data, hit->len); 320 if (err) { 321 MP_TO_SEC_ERROR(err); 322 return SECFailure; 323 } 324 return SECSuccess; 325 } 326 327 static SECStatus 328 addToSeed(const SECItem *seed, 329 unsigned long addend, 330 int seedlen, /* g in 186-1 */ 331 SECItem *seedout) 332 { 333 mp_int s, sum, modulus, tmp; 334 mp_err err = MP_OKAY; 335 SECStatus rv = SECSuccess; 336 MP_DIGITS(&s) = 0; 337 MP_DIGITS(&sum) = 0; 338 MP_DIGITS(&modulus) = 0; 339 MP_DIGITS(&tmp) = 0; 340 CHECK_MPI_OK(mp_init(&s)); 341 CHECK_MPI_OK(mp_init(&sum)); 342 CHECK_MPI_OK(mp_init(&modulus)); 343 SECITEM_TO_MPINT(*seed, &s); /* s = seed */ 344 /* seed += addend */ 345 if (sizeof(addend) < sizeof(mp_digit) || addend < MP_DIGIT_MAX) { 346 CHECK_MPI_OK(mp_add_d(&s, (mp_digit)addend, &s)); 347 } else { 348 CHECK_MPI_OK(mp_init(&tmp)); 349 CHECK_MPI_OK(mp_set_ulong(&tmp, addend)); 350 CHECK_MPI_OK(mp_add(&s, &tmp, &s)); 351 } 352 /*sum = s mod 2**seedlen */ 353 CHECK_MPI_OK(mp_div_2d(&s, (mp_digit)seedlen, NULL, &sum)); 354 if (seedout->data != NULL) { 355 SECITEM_ZfreeItem(seedout, PR_FALSE); 356 } 357 MPINT_TO_SECITEM(&sum, seedout, NULL); 358 cleanup: 359 mp_clear(&s); 360 mp_clear(&sum); 361 mp_clear(&modulus); 362 mp_clear(&tmp); 363 if (err) { 364 MP_TO_SEC_ERROR(err); 365 return SECFailure; 366 } 367 return rv; 368 } 369 370 /* Compute Hash[(SEED + addend) mod 2**g] 371 ** Result is placed in shaOutBuf. 372 ** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 and 373 ** step 11.2 of FIPS 186-3 Appendix A.1.1.2 . 374 */ 375 static SECStatus 376 addToSeedThenHash(HASH_HashType hashtype, 377 const SECItem *seed, 378 unsigned long addend, 379 int seedlen, /* g in 186-1 */ 380 unsigned char *hashOutBuf) 381 { 382 SECItem str = { 0, 0, 0 }; 383 SECStatus rv; 384 rv = addToSeed(seed, addend, seedlen, &str); 385 if (rv != SECSuccess) { 386 return rv; 387 } 388 rv = PQG_HashBuf(hashtype, hashOutBuf, str.data, str.len); /* hash result */ 389 if (str.data) 390 SECITEM_ZfreeItem(&str, PR_FALSE); 391 return rv; 392 } 393 394 /* 395 ** Perform steps 2 and 3 of FIPS 186-1, appendix 2.2. 396 ** Generate Q from seed. 397 */ 398 static SECStatus 399 makeQfromSeed( 400 unsigned int g, /* input. Length of seed in bits. */ 401 const SECItem *seed, /* input. */ 402 mp_int *Q) /* output. */ 403 { 404 unsigned char sha1[SHA1_LENGTH]; 405 unsigned char sha2[SHA1_LENGTH]; 406 unsigned char U[SHA1_LENGTH]; 407 SECStatus rv = SECSuccess; 408 mp_err err = MP_OKAY; 409 int i; 410 /* ****************************************************************** 411 ** Step 2. 412 ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]." 413 **/ 414 CHECK_SEC_OK(SHA1_HashBuf(sha1, seed->data, seed->len)); 415 CHECK_SEC_OK(addToSeedThenHash(HASH_AlgSHA1, seed, 1, g, sha2)); 416 for (i = 0; i < SHA1_LENGTH; ++i) 417 U[i] = sha1[i] ^ sha2[i]; 418 /* ****************************************************************** 419 ** Step 3. 420 ** "Form Q from U by setting the most signficant bit (the 2**159 bit) 421 ** and the least signficant bit to 1. In terms of boolean operations, 422 ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160." 423 */ 424 U[0] |= 0x80; /* U is MSB first */ 425 U[SHA1_LENGTH - 1] |= 0x01; 426 err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH); 427 cleanup: 428 memset(U, 0, SHA1_LENGTH); 429 memset(sha1, 0, SHA1_LENGTH); 430 memset(sha2, 0, SHA1_LENGTH); 431 if (err) { 432 MP_TO_SEC_ERROR(err); 433 return SECFailure; 434 } 435 return rv; 436 } 437 438 /* 439 ** Perform steps 6 and 7 of FIPS 186-3, appendix A.1.1.2. 440 ** Generate Q from seed. 441 */ 442 static SECStatus 443 makeQ2fromSeed( 444 HASH_HashType hashtype, /* selected Hashing algorithm */ 445 unsigned int N, /* input. Length of q in bits. */ 446 const SECItem *seed, /* input. */ 447 mp_int *Q) /* output. */ 448 { 449 unsigned char U[HASH_LENGTH_MAX]; 450 SECStatus rv = SECSuccess; 451 mp_err err = MP_OKAY; 452 int N_bytes = N / PR_BITS_PER_BYTE; /* length of N in bytes rather than bits */ 453 int hashLen = HASH_ResultLen(hashtype); 454 int offset = 0; 455 456 /* ****************************************************************** 457 ** Step 6. 458 ** "Compute U = hash[SEED] mod 2**N-1]." 459 **/ 460 CHECK_SEC_OK(PQG_HashBuf(hashtype, U, seed->data, seed->len)); 461 /* mod 2**N . Step 7 will explicitly set the top bit to 1, so no need 462 * to handle mod 2**N-1 */ 463 if (hashLen > N_bytes) { 464 offset = hashLen - N_bytes; 465 } 466 /* ****************************************************************** 467 ** Step 7. 468 ** computed_q = 2**(N-1) + U + 1 - (U mod 2) 469 ** 470 ** This is the same as: 471 ** computed_q = 2**(N-1) | U | 1; 472 */ 473 U[offset] |= 0x80; /* U is MSB first */ 474 U[hashLen - 1] |= 0x01; 475 err = mp_read_unsigned_octets(Q, &U[offset], N_bytes); 476 cleanup: 477 memset(U, 0, HASH_LENGTH_MAX); 478 if (err) { 479 MP_TO_SEC_ERROR(err); 480 return SECFailure; 481 } 482 return rv; 483 } 484 485 /* 486 ** Perform steps from FIPS 186-3, Appendix A.1.2.1 and Appendix C.6 487 ** 488 ** This generates a provable prime from two smaller prime. The resulting 489 ** prime p will have q0 as a multiple of p-1. q0 can be 1. 490 ** 491 ** This implments steps 4 thorough 22 of FIPS 186-3 A.1.2.1 and 492 ** steps 16 through 34 of FIPS 186-2 C.6 493 */ 494 static SECStatus 495 makePrimefromPrimesShaweTaylor( 496 HASH_HashType hashtype, /* selected Hashing algorithm */ 497 unsigned int length, /* input. Length of prime in bits. */ 498 unsigned int seedlen, /* input seed length in bits */ 499 mp_int *c0, /* seed prime */ 500 mp_int *q, /* sub prime, can be 1 */ 501 mp_int *prime, /* output. */ 502 SECItem *prime_seed, /* input/output. */ 503 unsigned int *prime_gen_counter) /* input/output. */ 504 { 505 mp_int c; 506 mp_int c0_2; 507 mp_int t; 508 mp_int a; 509 mp_int z; 510 mp_int two_length_minus_1; 511 SECStatus rv = SECFailure; 512 int hashlen = HASH_ResultLen(hashtype); 513 int outlen = hashlen * PR_BITS_PER_BYTE; 514 int offset; 515 unsigned char bit, mask; 516 /* x needs to hold roundup(L/outlen)*outlen. 517 * This can be no larger than L+outlen-1, So we set it's size to 518 * our max L + max outlen and know we are safe */ 519 unsigned char x[DSA_MAX_P_BITS / 8 + HASH_LENGTH_MAX]; 520 mp_err err = MP_OKAY; 521 int i; 522 int iterations; 523 int old_counter; 524 525 MP_DIGITS(&c) = 0; 526 MP_DIGITS(&c0_2) = 0; 527 MP_DIGITS(&t) = 0; 528 MP_DIGITS(&a) = 0; 529 MP_DIGITS(&z) = 0; 530 MP_DIGITS(&two_length_minus_1) = 0; 531 CHECK_MPI_OK(mp_init(&c)); 532 CHECK_MPI_OK(mp_init(&c0_2)); 533 CHECK_MPI_OK(mp_init(&t)); 534 CHECK_MPI_OK(mp_init(&a)); 535 CHECK_MPI_OK(mp_init(&z)); 536 CHECK_MPI_OK(mp_init(&two_length_minus_1)); 537 538 /* 539 ** There is a slight mapping of variable names depending on which 540 ** FIPS 186 steps are being carried out. The mapping is as follows: 541 ** variable A.1.2.1 C.6 542 ** c0 p0 c0 543 ** q q 1 544 ** c p c 545 ** c0_2 2*p0*q 2*c0 546 ** length L length 547 ** prime_seed pseed prime_seed 548 ** prime_gen_counter pgen_counter prime_gen_counter 549 ** 550 ** Also note: or iterations variable is actually iterations+1, since 551 ** iterations+1 works better in C. 552 */ 553 554 /* Step 4/16 iterations = ceiling(length/outlen)-1 */ 555 iterations = (length + outlen - 1) / outlen; /* NOTE: iterations +1 */ 556 /* Step 5/17 old_counter = prime_gen_counter */ 557 old_counter = *prime_gen_counter; 558 /* 559 ** Comment: Generate a pseudorandom integer x in the interval 560 ** [2**(length-1), 2**length]. 561 ** 562 ** Step 6/18 x = 0 563 */ 564 PORT_Memset(x, 0, sizeof(x)); 565 /* 566 ** Step 7/19 for i = 0 to iterations do 567 ** x = x + (HASH(prime_seed + i) * 2^(i*outlen)) 568 */ 569 for (i = 0; i < iterations; i++) { 570 /* is bigger than prime_seed should get to */ 571 CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i, 572 seedlen, &x[(iterations - i - 1) * hashlen])); 573 } 574 /* Step 8/20 prime_seed = prime_seed + iterations + 1 */ 575 CHECK_SEC_OK(addToSeed(prime_seed, iterations, seedlen, prime_seed)); 576 /* 577 ** Step 9/21 x = 2 ** (length-1) + x mod 2 ** (length-1) 578 ** 579 ** This step mathematically sets the high bit and clears out 580 ** all the other bits higher than length. 'x' is stored 581 ** in the x array, MSB first. The above formula gives us an 'x' 582 ** which is length bytes long and has the high bit set. We also know 583 ** that length <= iterations*outlen since 584 ** iterations=ceiling(length/outlen). First we find the offset in 585 ** bytes into the array where the high bit is. 586 */ 587 offset = (outlen * iterations - length) / PR_BITS_PER_BYTE; 588 /* now we want to set the 'high bit', since length may not be a 589 * multiple of 8,*/ 590 bit = 1 << ((length - 1) & 0x7); /* select the proper bit in the byte */ 591 /* we need to zero out the rest of the bits in the byte above */ 592 mask = (bit - 1); 593 /* now we set it */ 594 x[offset] = (mask & x[offset]) | bit; 595 /* 596 ** Comment: Generate a candidate prime c in the interval 597 ** [2**(length-1), 2**length]. 598 ** 599 ** Step 10 t = ceiling(x/(2q(p0))) 600 ** Step 22 t = ceiling(x/(2(c0))) 601 */ 602 CHECK_MPI_OK(mp_read_unsigned_octets(&t, &x[offset], 603 hashlen * iterations - offset)); /* t = x */ 604 CHECK_MPI_OK(mp_mul(c0, q, &c0_2)); /* c0_2 is now c0*q */ 605 CHECK_MPI_OK(mp_add(&c0_2, &c0_2, &c0_2)); /* c0_2 is now 2*q*c0 */ 606 CHECK_MPI_OK(mp_add(&t, &c0_2, &t)); /* t = x+2*q*c0 */ 607 CHECK_MPI_OK(mp_sub_d(&t, (mp_digit)1, &t)); /* t = x+2*q*c0 -1 */ 608 /* t = floor((x+2qc0-1)/2qc0) = ceil(x/2qc0) */ 609 CHECK_MPI_OK(mp_div(&t, &c0_2, &t, NULL)); 610 /* 611 ** step 11: if (2tqp0 +1 > 2**length), then t = ceiling(2**(length-1)/2qp0) 612 ** step 12: t = 2tqp0 +1. 613 ** 614 ** step 23: if (2tc0 +1 > 2**length), then t = ceiling(2**(length-1)/2c0) 615 ** step 24: t = 2tc0 +1. 616 */ 617 CHECK_MPI_OK(mp_2expt(&two_length_minus_1, length - 1)); 618 step_23: 619 CHECK_MPI_OK(mp_mul(&t, &c0_2, &c)); /* c = t*2qc0 */ 620 CHECK_MPI_OK(mp_add_d(&c, (mp_digit)1, &c)); /* c= 2tqc0 + 1*/ 621 if (mpl_significant_bits(&c) > length) { /* if c > 2**length */ 622 CHECK_MPI_OK(mp_sub_d(&c0_2, (mp_digit)1, &t)); /* t = 2qc0-1 */ 623 /* t = 2**(length-1) + 2qc0 -1 */ 624 CHECK_MPI_OK(mp_add(&two_length_minus_1, &t, &t)); 625 /* t = floor((2**(length-1)+2qc0 -1)/2qco) 626 * = ceil(2**(length-2)/2qc0) */ 627 CHECK_MPI_OK(mp_div(&t, &c0_2, &t, NULL)); 628 CHECK_MPI_OK(mp_mul(&t, &c0_2, &c)); 629 CHECK_MPI_OK(mp_add_d(&c, (mp_digit)1, &c)); /* c= 2tqc0 + 1*/ 630 } 631 /* Step 13/25 prime_gen_counter = prime_gen_counter + 1*/ 632 (*prime_gen_counter)++; 633 /* 634 ** Comment: Test the candidate prime c for primality; first pick an 635 ** integer a between 2 and c-2. 636 ** 637 ** Step 14/26 a=0 638 */ 639 PORT_Memset(x, 0, sizeof(x)); /* use x for a */ 640 /* 641 ** Step 15/27 for i = 0 to iterations do 642 ** a = a + (HASH(prime_seed + i) * 2^(i*outlen)) 643 ** 644 ** NOTE: we reuse the x array for 'a' initially. 645 */ 646 for (i = 0; i < iterations; i++) { 647 CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i, 648 seedlen, &x[(iterations - i - 1) * hashlen])); 649 } 650 /* Step 16/28 prime_seed = prime_seed + iterations + 1 */ 651 CHECK_SEC_OK(addToSeed(prime_seed, iterations, seedlen, prime_seed)); 652 /* Step 17/29 a = 2 + (a mod (c-3)). */ 653 CHECK_MPI_OK(mp_read_unsigned_octets(&a, x, iterations * hashlen)); 654 CHECK_MPI_OK(mp_sub_d(&c, (mp_digit)3, &z)); /* z = c -3 */ 655 CHECK_MPI_OK(mp_mod(&a, &z, &a)); /* a = a mod c -3 */ 656 CHECK_MPI_OK(mp_add_d(&a, (mp_digit)2, &a)); /* a = 2 + a mod c -3 */ 657 /* 658 ** Step 18 z = a**(2tq) mod p. 659 ** Step 30 z = a**(2t) mod c. 660 */ 661 CHECK_MPI_OK(mp_mul(&t, q, &z)); /* z = tq */ 662 CHECK_MPI_OK(mp_add(&z, &z, &z)); /* z = 2tq */ 663 CHECK_MPI_OK(mp_exptmod(&a, &z, &c, &z)); /* z = a**(2tq) mod c */ 664 /* 665 ** Step 19 if (( 1 == GCD(z-1,p)) and ( 1 == z**p0 mod p )), then 666 ** Step 31 if (( 1 == GCD(z-1,c)) and ( 1 == z**c0 mod c )), then 667 */ 668 CHECK_MPI_OK(mp_sub_d(&z, (mp_digit)1, &a)); 669 CHECK_MPI_OK(mp_gcd(&a, &c, &a)); 670 if (mp_cmp_d(&a, (mp_digit)1) == 0) { 671 CHECK_MPI_OK(mp_exptmod(&z, c0, &c, &a)); 672 if (mp_cmp_d(&a, (mp_digit)1) == 0) { 673 /* Step 31.1 prime = c */ 674 CHECK_MPI_OK(mp_copy(&c, prime)); 675 /* 676 ** Step 31.2 return Success, prime, prime_seed, 677 ** prime_gen_counter 678 */ 679 rv = SECSuccess; 680 goto cleanup; 681 } 682 } 683 /* 684 ** Step 20/32 If (prime_gen_counter > 4 * length + old_counter then 685 ** return (FAILURE, 0, 0, 0). 686 ** NOTE: the test is reversed, so we fall through on failure to the 687 ** cleanup routine 688 */ 689 if (*prime_gen_counter < (4 * length + old_counter)) { 690 /* Step 21/33 t = t + 1 */ 691 CHECK_MPI_OK(mp_add_d(&t, (mp_digit)1, &t)); 692 /* Step 22/34 Go to step 23/11 */ 693 goto step_23; 694 } 695 696 /* if (prime_gencont > (4*length + old_counter), fall through to failure */ 697 rv = SECFailure; /* really is already set, but paranoia is good */ 698 699 cleanup: 700 mp_clear(&c); 701 mp_clear(&c0_2); 702 mp_clear(&t); 703 mp_clear(&a); 704 mp_clear(&z); 705 mp_clear(&two_length_minus_1); 706 PORT_SafeZero(x, sizeof(x)); 707 if (err) { 708 MP_TO_SEC_ERROR(err); 709 rv = SECFailure; 710 } 711 if (rv == SECFailure) { 712 mp_zero(prime); 713 if (prime_seed->data) { 714 SECITEM_ZfreeItem(prime_seed, PR_FALSE); 715 } 716 *prime_gen_counter = 0; 717 } 718 return rv; 719 } 720 721 /* 722 ** Perform steps from FIPS 186-3, Appendix C.6 723 ** 724 ** This generates a provable prime from a seed 725 */ 726 static SECStatus 727 makePrimefromSeedShaweTaylor( 728 HASH_HashType hashtype, /* selected Hashing algorithm */ 729 unsigned int length, /* input. Length of prime in bits. */ 730 const SECItem *input_seed, /* input. */ 731 mp_int *prime, /* output. */ 732 SECItem *prime_seed, /* output. */ 733 unsigned int *prime_gen_counter) /* output. */ 734 { 735 mp_int c; 736 mp_int c0; 737 mp_int one; 738 SECStatus rv = SECFailure; 739 int hashlen = HASH_ResultLen(hashtype); 740 int outlen = hashlen * PR_BITS_PER_BYTE; 741 int offset; 742 int seedlen = input_seed->len * 8; /*seedlen is in bits */ 743 unsigned char bit, mask; 744 unsigned char x[HASH_LENGTH_MAX * 2]; 745 mp_digit dummy; 746 mp_err err = MP_OKAY; 747 int i; 748 749 MP_DIGITS(&c) = 0; 750 MP_DIGITS(&c0) = 0; 751 MP_DIGITS(&one) = 0; 752 CHECK_MPI_OK(mp_init(&c)); 753 CHECK_MPI_OK(mp_init(&c0)); 754 CHECK_MPI_OK(mp_init(&one)); 755 756 /* Step 1. if length < 2 then return (FAILURE, 0, 0, 0) */ 757 if (length < 2) { 758 rv = SECFailure; 759 goto cleanup; 760 } 761 /* Step 2. if length >= 33 then goto step 14 */ 762 if (length >= 33) { 763 mp_zero(&one); 764 CHECK_MPI_OK(mp_add_d(&one, (mp_digit)1, &one)); 765 766 /* Step 14 (status, c0, prime_seed, prime_gen_counter) = 767 ** (ST_Random_Prime((ceil(length/2)+1, input_seed) 768 */ 769 rv = makePrimefromSeedShaweTaylor(hashtype, (length + 1) / 2 + 1, 770 input_seed, &c0, prime_seed, prime_gen_counter); 771 /* Step 15 if FAILURE is returned, return (FAILURE, 0, 0, 0). */ 772 if (rv != SECSuccess) { 773 goto cleanup; 774 } 775 /* Steps 16-34 */ 776 rv = makePrimefromPrimesShaweTaylor(hashtype, length, seedlen, &c0, &one, 777 prime, prime_seed, prime_gen_counter); 778 goto cleanup; /* we're done, one way or the other */ 779 } 780 /* Step 3 prime_seed = input_seed */ 781 CHECK_SEC_OK(SECITEM_CopyItem(NULL, prime_seed, input_seed)); 782 /* Step 4 prime_gen_count = 0 */ 783 *prime_gen_counter = 0; 784 785 step_5: 786 /* Step 5 c = Hash(prime_seed) xor Hash(prime_seed+1). */ 787 CHECK_SEC_OK(PQG_HashBuf(hashtype, x, prime_seed->data, prime_seed->len)); 788 CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, 1, seedlen, &x[hashlen])); 789 for (i = 0; i < hashlen; i++) { 790 x[i] = x[i] ^ x[i + hashlen]; 791 } 792 /* Step 6 c = 2**length-1 + c mod 2**length-1 */ 793 /* This step mathematically sets the high bit and clears out 794 ** all the other bits higher than length. Right now c is stored 795 ** in the x array, MSB first. The above formula gives us a c which 796 ** is length bytes long and has the high bit set. We also know that 797 ** length < outlen since the smallest outlen is 160 bits and the largest 798 ** length at this point is 32 bits. So first we find the offset in bytes 799 ** into the array where the high bit is. 800 */ 801 offset = (outlen - length) / PR_BITS_PER_BYTE; 802 /* now we want to set the 'high bit'. We have to calculate this since 803 * length may not be a multiple of 8.*/ 804 bit = 1 << ((length - 1) & 0x7); /* select the proper bit in the byte */ 805 /* we need to zero out the rest of the bits in the byte above */ 806 mask = (bit - 1); 807 /* now we set it */ 808 x[offset] = (mask & x[offset]) | bit; 809 /* Step 7 c = c*floor(c/2) + 1 */ 810 /* set the low bit. much easier to find (the end of the array) */ 811 x[hashlen - 1] |= 1; 812 /* now that we've set our bits, we can create our candidate "c" */ 813 CHECK_MPI_OK(mp_read_unsigned_octets(&c, &x[offset], hashlen - offset)); 814 /* Step 8 prime_gen_counter = prime_gen_counter + 1 */ 815 (*prime_gen_counter)++; 816 /* Step 9 prime_seed = prime_seed + 2 */ 817 CHECK_SEC_OK(addToSeed(prime_seed, 2, seedlen, prime_seed)); 818 /* Step 10 Perform deterministic primality test on c. For example, since 819 ** c is small, it's primality can be tested by trial division, See 820 ** See Appendic C.7. 821 ** 822 ** We in fact test with trial division. mpi has a built int trial divider 823 ** that divides all divisors up to 2^16. 824 */ 825 if (prime_tab[prime_tab_size - 1] < 0xFFF1) { 826 /* we aren't testing all the primes between 0 and 2^16, we really 827 * can't use this construction. Just fail. */ 828 rv = SECFailure; 829 goto cleanup; 830 } 831 dummy = prime_tab_size; 832 err = mpp_divis_primes(&c, &dummy); 833 /* Step 11 if c is prime then */ 834 if (err == MP_NO) { 835 /* Step 11.1 prime = c */ 836 CHECK_MPI_OK(mp_copy(&c, prime)); 837 /* Step 11.2 return SUCCESS prime, prime_seed, prime_gen_counter */ 838 err = MP_OKAY; 839 rv = SECSuccess; 840 goto cleanup; 841 } else if (err != MP_YES) { 842 goto cleanup; /* function failed, bail out */ 843 } else { 844 /* reset mp_err */ 845 err = MP_OKAY; 846 } 847 /* 848 ** Step 12 if (prime_gen_counter > (4*len)) 849 ** then return (FAILURE, 0, 0, 0)) 850 ** Step 13 goto step 5 851 */ 852 if (*prime_gen_counter <= (4 * length)) { 853 goto step_5; 854 } 855 /* if (prime_gencont > 4*length), fall through to failure */ 856 rv = SECFailure; /* really is already set, but paranoia is good */ 857 858 cleanup: 859 mp_clear(&c); 860 mp_clear(&c0); 861 mp_clear(&one); 862 PORT_SafeZero(x, sizeof(x)); 863 if (err) { 864 MP_TO_SEC_ERROR(err); 865 rv = SECFailure; 866 } 867 if (rv == SECFailure) { 868 mp_zero(prime); 869 if (prime_seed->data) { 870 SECITEM_ZfreeItem(prime_seed, PR_FALSE); 871 } 872 *prime_gen_counter = 0; 873 } 874 return rv; 875 } 876 877 /* 878 * Find a Q and algorithm from Seed. 879 */ 880 static SECStatus 881 findQfromSeed( 882 unsigned int L, /* input. Length of p in bits. */ 883 unsigned int N, /* input. Length of q in bits. */ 884 unsigned int g, /* input. Length of seed in bits. */ 885 const SECItem *seed, /* input. */ 886 mp_int *Q, /* input. */ 887 mp_int *Q_, /* output. */ 888 unsigned int *qseed_len, /* output */ 889 HASH_HashType *hashtypePtr, /* output. Hash uses */ 890 pqgGenType *typePtr, /* output. Generation Type used */ 891 unsigned int *qgen_counter) /* output. q_counter */ 892 { 893 HASH_HashType hashtype = HASH_AlgNULL; 894 SECItem firstseed = { 0, 0, 0 }; 895 SECItem qseed = { 0, 0, 0 }; 896 SECStatus rv; 897 898 *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */ 899 900 /* handle legacy small DSA first can only be FIPS186_1_TYPE */ 901 if (L < 1024) { 902 rv = makeQfromSeed(g, seed, Q_); 903 if ((rv == SECSuccess) && (mp_cmp(Q, Q_) == 0)) { 904 *hashtypePtr = HASH_AlgSHA1; 905 *typePtr = FIPS186_1_TYPE; 906 return SECSuccess; 907 } 908 mp_zero(Q_); 909 return SECFailure; 910 } 911 /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try 912 * them both */ 913 if (L == 1024) { 914 rv = makeQfromSeed(g, seed, Q_); 915 if (rv == SECSuccess) { 916 if (mp_cmp(Q, Q_) == 0) { 917 *hashtypePtr = HASH_AlgSHA1; 918 *typePtr = FIPS186_1_TYPE; 919 return SECSuccess; 920 } 921 } 922 /* fall through for FIPS186_3 types */ 923 } 924 /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3 925 * with appropriate hash types */ 926 for (hashtype = getFirstHash(L, N); hashtype != HASH_AlgTOTAL; 927 hashtype = getNextHash(hashtype)) { 928 rv = makeQ2fromSeed(hashtype, N, seed, Q_); 929 if (rv != SECSuccess) { 930 continue; 931 } 932 if (mp_cmp(Q, Q_) == 0) { 933 *hashtypePtr = hashtype; 934 *typePtr = FIPS186_3_TYPE; 935 return SECSuccess; 936 } 937 } 938 /* 939 * OK finally try FIPS186_3 Shawe-Taylor 940 */ 941 firstseed = *seed; 942 firstseed.len = seed->len / 3; 943 for (hashtype = getFirstHash(L, N); hashtype != HASH_AlgTOTAL; 944 hashtype = getNextHash(hashtype)) { 945 unsigned int count; 946 947 rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_, 948 &qseed, &count); 949 if (rv != SECSuccess) { 950 continue; 951 } 952 if (mp_cmp(Q, Q_) == 0) { 953 /* check qseed as well... */ 954 int offset = seed->len - qseed.len; 955 if ((offset < 0) || 956 (PORT_Memcmp(&seed->data[offset], qseed.data, qseed.len) != 0)) { 957 /* we found q, but the seeds don't match. This isn't an 958 * accident, someone has been tweeking with the seeds, just 959 * fail a this point. */ 960 SECITEM_FreeItem(&qseed, PR_FALSE); 961 mp_zero(Q_); 962 return SECFailure; 963 } 964 *qseed_len = qseed.len; 965 *hashtypePtr = hashtype; 966 *typePtr = FIPS186_3_ST_TYPE; 967 *qgen_counter = count; 968 SECITEM_ZfreeItem(&qseed, PR_FALSE); 969 return SECSuccess; 970 } 971 SECITEM_ZfreeItem(&qseed, PR_FALSE); 972 } 973 /* no hash algorithms found which match seed to Q, fail */ 974 mp_zero(Q_); 975 return SECFailure; 976 } 977 978 /* 979 ** Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2. 980 ** which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2 981 ** Generate P from Q, seed, L, and offset. 982 */ 983 static SECStatus 984 makePfromQandSeed( 985 HASH_HashType hashtype, /* selected Hashing algorithm */ 986 unsigned int L, /* Length of P in bits. Per FIPS 186. */ 987 unsigned int N, /* Length of Q in bits. Per FIPS 186. */ 988 unsigned int offset, /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */ 989 unsigned int seedlen, /* input. Length of seed in bits. (g in 186-1)*/ 990 const SECItem *seed, /* input. */ 991 const mp_int *Q, /* input. */ 992 mp_int *P) /* output. */ 993 { 994 unsigned int j; /* Per FIPS 186-3 App. A.1.1.2 (k in 186-1)*/ 995 unsigned int n; /* Per FIPS 186, appendix 2.2. */ 996 mp_digit b; /* Per FIPS 186, appendix 2.2. */ 997 unsigned int outlen; /* Per FIPS 186-3 App. A.1.1.2 */ 998 unsigned int hashlen; /* outlen in bytes */ 999 unsigned char V_j[HASH_LENGTH_MAX]; 1000 mp_int W, X, c, twoQ, V_n, tmp; 1001 mp_err err = MP_OKAY; 1002 SECStatus rv = SECSuccess; 1003 /* Initialize bignums */ 1004 MP_DIGITS(&W) = 0; 1005 MP_DIGITS(&X) = 0; 1006 MP_DIGITS(&c) = 0; 1007 MP_DIGITS(&twoQ) = 0; 1008 MP_DIGITS(&V_n) = 0; 1009 MP_DIGITS(&tmp) = 0; 1010 CHECK_MPI_OK(mp_init(&W)); 1011 CHECK_MPI_OK(mp_init(&X)); 1012 CHECK_MPI_OK(mp_init(&c)); 1013 CHECK_MPI_OK(mp_init(&twoQ)); 1014 CHECK_MPI_OK(mp_init(&tmp)); 1015 CHECK_MPI_OK(mp_init(&V_n)); 1016 1017 hashlen = HASH_ResultLen(hashtype); 1018 outlen = hashlen * PR_BITS_PER_BYTE; 1019 1020 PORT_Assert(outlen > 0); 1021 1022 /* L - 1 = n*outlen + b */ 1023 n = (L - 1) / outlen; 1024 b = (L - 1) % outlen; 1025 1026 /* ****************************************************************** 1027 ** Step 11.1 (Step 7 in 186-1) 1028 ** "for j = 0 ... n let 1029 ** V_j = SHA[(SEED + offset + j) mod 2**seedlen]." 1030 ** 1031 ** Step 11.2 (Step 8 in 186-1) 1032 ** "W = V_0 + (V_1 * 2**outlen) + ... + (V_n-1 * 2**((n-1)*outlen)) 1033 ** + ((V_n mod 2**b) * 2**(n*outlen)) 1034 */ 1035 for (j = 0; j < n; ++j) { /* Do the first n terms of V_j */ 1036 /* Do step 11.1 for iteration j. 1037 ** V_j = HASH[(seed + offset + j) mod 2**g] 1038 */ 1039 CHECK_SEC_OK(addToSeedThenHash(hashtype, seed, offset + j, seedlen, V_j)); 1040 /* Do step 11.2 for iteration j. 1041 ** W += V_j * 2**(j*outlen) 1042 */ 1043 OCTETS_TO_MPINT(V_j, &tmp, hashlen); /* get bignum V_j */ 1044 CHECK_MPI_OK(mpl_lsh(&tmp, &tmp, j * outlen)); /* tmp=V_j << j*outlen */ 1045 CHECK_MPI_OK(mp_add(&W, &tmp, &W)); /* W += tmp */ 1046 } 1047 /* Step 11.2, continued. 1048 ** [W += ((V_n mod 2**b) * 2**(n*outlen))] 1049 */ 1050 CHECK_SEC_OK(addToSeedThenHash(hashtype, seed, offset + n, seedlen, V_j)); 1051 OCTETS_TO_MPINT(V_j, &V_n, hashlen); /* get bignum V_n */ 1052 CHECK_MPI_OK(mp_div_2d(&V_n, b, NULL, &tmp)); /* tmp = V_n mod 2**b */ 1053 CHECK_MPI_OK(mpl_lsh(&tmp, &tmp, n * outlen)); /* tmp = tmp << n*outlen */ 1054 CHECK_MPI_OK(mp_add(&W, &tmp, &W)); /* W += tmp */ 1055 /* Step 11.3, (Step 8 in 186-1) 1056 ** "X = W + 2**(L-1). 1057 ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L." 1058 */ 1059 CHECK_MPI_OK(mpl_set_bit(&X, (mp_size)(L - 1), 1)); /* X = 2**(L-1) */ 1060 CHECK_MPI_OK(mp_add(&X, &W, &X)); /* X += W */ 1061 /************************************************************* 1062 ** Step 11.4. (Step 9 in 186-1) 1063 ** "c = X mod 2q" 1064 */ 1065 CHECK_MPI_OK(mp_mul_2(Q, &twoQ)); /* 2q */ 1066 CHECK_MPI_OK(mp_mod(&X, &twoQ, &c)); /* c = X mod 2q */ 1067 /************************************************************* 1068 ** Step 11.5. (Step 9 in 186-1) 1069 ** "p = X - (c - 1). 1070 ** Note that p is congruent to 1 mod 2q." 1071 */ 1072 CHECK_MPI_OK(mp_sub_d(&c, 1, &c)); /* c -= 1 */ 1073 CHECK_MPI_OK(mp_sub(&X, &c, P)); /* P = X - c */ 1074 cleanup: 1075 PORT_SafeZero(V_j, sizeof V_j); 1076 mp_clear(&W); 1077 mp_clear(&X); 1078 mp_clear(&c); 1079 mp_clear(&twoQ); 1080 mp_clear(&V_n); 1081 mp_clear(&tmp); 1082 if (err) { 1083 MP_TO_SEC_ERROR(err); 1084 mp_zero(P); 1085 return SECFailure; 1086 } 1087 if (rv != SECSuccess) { 1088 mp_zero(P); 1089 } 1090 return rv; 1091 } 1092 1093 /* 1094 ** Generate G from h, P, and Q. 1095 */ 1096 static SECStatus 1097 makeGfromH(const mp_int *P, /* input. */ 1098 const mp_int *Q, /* input. */ 1099 mp_int *H, /* input and output. */ 1100 mp_int *G, /* output. */ 1101 PRBool *passed) 1102 { 1103 mp_int exp, pm1; 1104 mp_err err = MP_OKAY; 1105 SECStatus rv = SECSuccess; 1106 *passed = PR_FALSE; 1107 MP_DIGITS(&exp) = 0; 1108 MP_DIGITS(&pm1) = 0; 1109 CHECK_MPI_OK(mp_init(&exp)); 1110 CHECK_MPI_OK(mp_init(&pm1)); 1111 CHECK_MPI_OK(mp_sub_d(P, 1, &pm1)); /* P - 1 */ 1112 if (mp_cmp(H, &pm1) >= 0) /* H >= P-1 */ 1113 CHECK_MPI_OK(mp_sub(H, &pm1, H)); /* H = H mod (P-1) */ 1114 /* Let b = 2**n (smallest power of 2 greater than P). 1115 ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1 1116 ** so the above operation safely computes H mod (P-1) 1117 */ 1118 /* Check for H = to 0 or 1. Regen H if so. (Regen means return error). */ 1119 if (mp_cmp_d(H, 1) <= 0) { 1120 rv = SECFailure; 1121 goto cleanup; 1122 } 1123 /* Compute G, according to the equation G = (H ** ((P-1)/Q)) mod P */ 1124 CHECK_MPI_OK(mp_div(&pm1, Q, &exp, NULL)); /* exp = (P-1)/Q */ 1125 CHECK_MPI_OK(mp_exptmod(H, &exp, P, G)); /* G = H ** exp mod P */ 1126 /* Check for G == 0 or G == 1, return error if so. */ 1127 if (mp_cmp_d(G, 1) <= 0) { 1128 rv = SECFailure; 1129 goto cleanup; 1130 } 1131 *passed = PR_TRUE; 1132 cleanup: 1133 mp_clear(&exp); 1134 mp_clear(&pm1); 1135 if (err) { 1136 MP_TO_SEC_ERROR(err); 1137 rv = SECFailure; 1138 } 1139 if (rv != SECSuccess) { 1140 mp_zero(G); 1141 } 1142 return rv; 1143 } 1144 1145 /* 1146 ** Generate G from seed, index, P, and Q. 1147 */ 1148 static SECStatus 1149 makeGfromIndex(HASH_HashType hashtype, 1150 const mp_int *P, /* input. */ 1151 const mp_int *Q, /* input. */ 1152 const SECItem *seed, /* input. */ 1153 unsigned char index, /* input. */ 1154 mp_int *G) /* input/output */ 1155 { 1156 mp_int e, pm1, W; 1157 unsigned int count; 1158 unsigned char data[HASH_LENGTH_MAX]; 1159 unsigned int len; 1160 mp_err err = MP_OKAY; 1161 SECStatus rv = SECSuccess; 1162 const SECHashObject *hashobj = NULL; 1163 void *hashcx = NULL; 1164 1165 MP_DIGITS(&e) = 0; 1166 MP_DIGITS(&pm1) = 0; 1167 MP_DIGITS(&W) = 0; 1168 CHECK_MPI_OK(mp_init(&e)); 1169 CHECK_MPI_OK(mp_init(&pm1)); 1170 CHECK_MPI_OK(mp_init(&W)); 1171 1172 /* initialize our hash stuff */ 1173 hashobj = HASH_GetRawHashObject(hashtype); 1174 if (hashobj == NULL) { 1175 /* shouldn't happen */ 1176 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); 1177 rv = SECFailure; 1178 goto cleanup; 1179 } 1180 hashcx = hashobj->create(); 1181 if (hashcx == NULL) { 1182 rv = SECFailure; 1183 goto cleanup; 1184 } 1185 1186 CHECK_MPI_OK(mp_sub_d(P, 1, &pm1)); /* P - 1 */ 1187 /* Step 3 e = (p-1)/q */ 1188 CHECK_MPI_OK(mp_div(&pm1, Q, &e, NULL)); /* e = (P-1)/Q */ 1189 /* Steps 4, 5, and 6 */ 1190 /* count is a 16 bit value in the spec. We actually represent count 1191 * as more than 16 bits so we can easily detect the 16 bit overflow */ 1192 #define MAX_COUNT 0x10000 1193 for (count = 1; count < MAX_COUNT; count++) { 1194 /* step 7 1195 * U = domain_param_seed || "ggen" || index || count 1196 * step 8 1197 * W = HASH(U) 1198 */ 1199 hashobj->begin(hashcx); 1200 hashobj->update(hashcx, seed->data, seed->len); 1201 hashobj->update(hashcx, (unsigned char *)"ggen", 4); 1202 hashobj->update(hashcx, &index, 1); 1203 data[0] = (count >> 8) & 0xff; 1204 data[1] = count & 0xff; 1205 hashobj->update(hashcx, data, 2); 1206 hashobj->end(hashcx, data, &len, sizeof(data)); 1207 OCTETS_TO_MPINT(data, &W, len); 1208 /* step 9. g = W**e mod p */ 1209 CHECK_MPI_OK(mp_exptmod(&W, &e, P, G)); 1210 /* step 10. if (g < 2) then goto step 5 */ 1211 /* NOTE: this weird construct is to keep the flow according to the spec. 1212 * the continue puts us back to step 5 of the for loop */ 1213 if (mp_cmp_d(G, 2) < 0) { 1214 continue; 1215 } 1216 break; /* step 11 follows step 10 if the test condition is false */ 1217 } 1218 if (count >= MAX_COUNT) { 1219 rv = SECFailure; /* last part of step 6 */ 1220 } 1221 /* step 11. 1222 * return valid G */ 1223 cleanup: 1224 PORT_SafeZero(data, sizeof(data)); 1225 if (hashcx) { 1226 hashobj->destroy(hashcx, PR_TRUE); 1227 } 1228 mp_clear(&e); 1229 mp_clear(&pm1); 1230 mp_clear(&W); 1231 if (err) { 1232 MP_TO_SEC_ERROR(err); 1233 rv = SECFailure; 1234 } 1235 return rv; 1236 } 1237 1238 /* This code uses labels and gotos, so that it can follow the numbered 1239 ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely, 1240 ** and so that the correctness of this code can be easily verified. 1241 ** So, please forgive the ugly c code. 1242 **/ 1243 static SECStatus 1244 pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type, 1245 unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy) 1246 { 1247 unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ 1248 unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/ 1249 unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ 1250 unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ 1251 unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */ 1252 unsigned int maxCount; 1253 HASH_HashType hashtype = HASH_AlgNULL; 1254 SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ 1255 PLArenaPool *arena = NULL; 1256 PQGParams *params = NULL; 1257 PQGVerify *verify = NULL; 1258 PRBool passed; 1259 SECItem hit = { 0, 0, 0 }; 1260 SECItem firstseed = { 0, 0, 0 }; 1261 SECItem qseed = { 0, 0, 0 }; 1262 SECItem pseed = { 0, 0, 0 }; 1263 mp_int P, Q, G, H, l, p0; 1264 mp_err err = MP_OKAY; 1265 SECStatus rv = SECFailure; 1266 int iterations = 0; 1267 1268 /* Step 1. L and N already checked by caller*/ 1269 /* Step 2. if (seedlen < N) return INVALID; */ 1270 if (seedBytes < N / PR_BITS_PER_BYTE || !pParams || !pVfy) { 1271 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1272 return SECFailure; 1273 } 1274 1275 /* Initialize bignums */ 1276 MP_DIGITS(&P) = 0; 1277 MP_DIGITS(&Q) = 0; 1278 MP_DIGITS(&G) = 0; 1279 MP_DIGITS(&H) = 0; 1280 MP_DIGITS(&l) = 0; 1281 MP_DIGITS(&p0) = 0; 1282 CHECK_MPI_OK(mp_init(&P)); 1283 CHECK_MPI_OK(mp_init(&Q)); 1284 CHECK_MPI_OK(mp_init(&G)); 1285 CHECK_MPI_OK(mp_init(&H)); 1286 CHECK_MPI_OK(mp_init(&l)); 1287 CHECK_MPI_OK(mp_init(&p0)); 1288 1289 /* parameters have been passed in, only generate G */ 1290 if (*pParams != NULL) { 1291 /* we only support G index generation if generating separate from PQ */ 1292 if ((*pVfy == NULL) || (type == FIPS186_1_TYPE) || 1293 ((*pVfy)->h.len != 1) || ((*pVfy)->h.data == NULL) || 1294 ((*pVfy)->seed.data == NULL) || ((*pVfy)->seed.len == 0)) { 1295 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1296 return SECFailure; 1297 } 1298 params = *pParams; 1299 verify = *pVfy; 1300 1301 /* fill in P Q, */ 1302 SECITEM_TO_MPINT((*pParams)->prime, &P); 1303 SECITEM_TO_MPINT((*pParams)->subPrime, &Q); 1304 hashtype = getFirstHash(L, N); 1305 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &(*pVfy)->seed, 1306 (*pVfy)->h.data[0], &G)); 1307 MPINT_TO_SECITEM(&G, &(*pParams)->base, (*pParams)->arena); 1308 goto cleanup; 1309 } 1310 /* Initialize an arena for the params. */ 1311 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); 1312 if (!arena) { 1313 PORT_SetError(SEC_ERROR_NO_MEMORY); 1314 return SECFailure; 1315 } 1316 params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams)); 1317 if (!params) { 1318 PORT_SetError(SEC_ERROR_NO_MEMORY); 1319 PORT_FreeArena(arena, PR_TRUE); 1320 return SECFailure; 1321 } 1322 params->arena = arena; 1323 /* Initialize an arena for the verify. */ 1324 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); 1325 if (!arena) { 1326 PORT_SetError(SEC_ERROR_NO_MEMORY); 1327 PORT_FreeArena(params->arena, PR_TRUE); 1328 return SECFailure; 1329 } 1330 verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify)); 1331 if (!verify) { 1332 PORT_SetError(SEC_ERROR_NO_MEMORY); 1333 PORT_FreeArena(arena, PR_TRUE); 1334 PORT_FreeArena(params->arena, PR_TRUE); 1335 return SECFailure; 1336 } 1337 verify->arena = arena; 1338 seed = &verify->seed; 1339 arena = NULL; 1340 1341 /* Select Hash and Compute lengths. */ 1342 /* getFirstHash gives us the smallest acceptable hash for this key 1343 * strength */ 1344 hashtype = getFirstHash(L, N); 1345 outlen = HASH_ResultLen(hashtype) * PR_BITS_PER_BYTE; 1346 1347 /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */ 1348 n = (L - 1) / outlen; 1349 /* Step 4: (skipped since we don't use b): b = L -1 - (n*outlen); */ 1350 seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */ 1351 step_5: 1352 /* ****************************************************************** 1353 ** Step 5. (Step 1 in 186-1) 1354 ** "Choose an abitrary sequence of at least N bits and call it SEED. 1355 ** Let g be the length of SEED in bits." 1356 */ 1357 if (++iterations > MAX_ITERATIONS) { /* give up after a while */ 1358 PORT_SetError(SEC_ERROR_NEED_RANDOM); 1359 goto cleanup; 1360 } 1361 seed->len = seedBytes; 1362 CHECK_SEC_OK(getPQseed(seed, verify->arena)); 1363 /* ****************************************************************** 1364 ** Step 6. (Step 2 in 186-1) 1365 ** 1366 ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]. (186-1)" 1367 ** "Compute U = HASH[SEED] 2**(N-1). (186-3)" 1368 ** 1369 ** Step 7. (Step 3 in 186-1) 1370 ** "Form Q from U by setting the most signficant bit (the 2**159 bit) 1371 ** and the least signficant bit to 1. In terms of boolean operations, 1372 ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160. (186-1)" 1373 ** 1374 ** "q = 2**(N-1) + U + 1 - (U mod 2) (186-3) 1375 ** 1376 ** Note: Both formulations are the same for U < 2**(N-1) and N=160 1377 ** 1378 ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block 1379 ** FIPS186_3_ST_TYPE. 1380 */ 1381 if (type == FIPS186_1_TYPE) { 1382 CHECK_SEC_OK(makeQfromSeed(seedlen, seed, &Q)); 1383 } else if (type == FIPS186_3_TYPE) { 1384 CHECK_SEC_OK(makeQ2fromSeed(hashtype, N, seed, &Q)); 1385 } else { 1386 /* FIPS186_3_ST_TYPE */ 1387 unsigned int qgen_counter, pgen_counter; 1388 1389 /* Step 1 (L,N) already checked for acceptability */ 1390 1391 firstseed = *seed; 1392 qgen_counter = 0; 1393 /* Step 2. Use N and firstseed to generate random prime q 1394 * using Apendix C.6 */ 1395 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q, 1396 &qseed, &qgen_counter)); 1397 /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0 1398 * using Appendix C.6 */ 1399 pgen_counter = 0; 1400 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, (L + 1) / 2 + 1, 1401 &qseed, &p0, &pseed, &pgen_counter)); 1402 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */ 1403 CHECK_SEC_OK(makePrimefromPrimesShaweTaylor(hashtype, L, seedBytes * 8, 1404 &p0, &Q, &P, &pseed, &pgen_counter)); 1405 1406 /* combine all the seeds */ 1407 if ((qseed.len > firstseed.len) || (pseed.len > firstseed.len)) { 1408 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); /* shouldn't happen */ 1409 goto cleanup; 1410 } 1411 /* If the seed overflows, then pseed and qseed may have leading zeros which the mpl code clamps. 1412 * we want to make sure those are added back in so the individual seed lengths are predictable from 1413 * the overall seed length */ 1414 seed->len = firstseed.len * 3; 1415 seed->data = PORT_ArenaZAlloc(verify->arena, seed->len); 1416 if (seed->data == NULL) { 1417 goto cleanup; 1418 } 1419 PORT_Memcpy(seed->data, firstseed.data, firstseed.len); 1420 PORT_Memcpy(seed->data + 2 * firstseed.len - pseed.len, pseed.data, pseed.len); 1421 PORT_Memcpy(seed->data + 3 * firstseed.len - qseed.len, qseed.data, qseed.len); 1422 counter = (qgen_counter << 16) | pgen_counter; 1423 1424 /* we've generated both P and Q now, skip to generating G */ 1425 goto generate_G; 1426 } 1427 /* ****************************************************************** 1428 ** Step 8. (Step 4 in 186-1) 1429 ** "Use a robust primality testing algorithm to test whether q is prime." 1430 ** 1431 ** Appendix 2.1 states that a Rabin test with at least 50 iterations 1432 ** "will give an acceptable probability of error." 1433 */ 1434 /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/ 1435 err = mpp_pprime_secure(&Q, prime_testcount_q(L, N)); 1436 passed = (err == MP_YES) ? SECSuccess : SECFailure; 1437 /* ****************************************************************** 1438 ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)." 1439 */ 1440 if (passed != SECSuccess) 1441 goto step_5; 1442 /* ****************************************************************** 1443 ** Step 10. 1444 ** offset = 1; 1445 **( Step 6b 186-1)"Let counter = 0 and offset = 2." 1446 */ 1447 offset = (type == FIPS186_1_TYPE) ? 2 : 1; 1448 /* 1449 ** Step 11. (Step 6a,13a,14 in 186-1) 1450 ** For counter - 0 to (4L-1) do 1451 ** 1452 */ 1453 maxCount = L >= 1024 ? (4 * L - 1) : 4095; 1454 for (counter = 0; counter <= maxCount; counter++) { 1455 /* ****************************************************************** 1456 ** Step 11.1 (Step 7 in 186-1) 1457 ** "for j = 0 ... n let 1458 ** V_j = HASH[(SEED + offset + j) mod 2**seedlen]." 1459 ** 1460 ** Step 11.2 (Step 8 in 186-1) 1461 ** "W = V_0 + V_1*2**outlen+...+ V_n-1 * 2**((n-1)*outlen) + 1462 ** ((Vn* mod 2**b)*2**(n*outlen))" 1463 ** Step 11.3 (Step 8 in 186-1) 1464 ** "X = W + 2**(L-1) 1465 ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L." 1466 ** 1467 ** Step 11.4 (Step 9 in 186-1). 1468 ** "c = X mod 2q" 1469 ** 1470 ** Step 11.5 (Step 9 in 186-1). 1471 ** " p = X - (c - 1). 1472 ** Note that p is congruent to 1 mod 2q." 1473 */ 1474 CHECK_SEC_OK(makePfromQandSeed(hashtype, L, N, offset, seedlen, 1475 seed, &Q, &P)); 1476 /************************************************************* 1477 ** Step 11.6. (Step 10 in 186-1) 1478 ** "if p < 2**(L-1), then goto step 11.9. (step 13 in 186-1)" 1479 */ 1480 CHECK_MPI_OK(mpl_set_bit(&l, (mp_size)(L - 1), 1)); /* l = 2**(L-1) */ 1481 if (mp_cmp(&P, &l) < 0) 1482 goto step_11_9; 1483 /************************************************************ 1484 ** Step 11.7 (step 11 in 186-1) 1485 ** "Perform a robust primality test on p." 1486 */ 1487 /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/ 1488 err = mpp_pprime_secure(&P, prime_testcount_p(L, N)); 1489 passed = (err == MP_YES) ? SECSuccess : SECFailure; 1490 /* ****************************************************************** 1491 ** Step 11.8. "If p is determined to be primed return VALID 1492 ** values of p, q, seed and counter." 1493 */ 1494 if (passed == SECSuccess) 1495 break; 1496 step_11_9: 1497 /* ****************************************************************** 1498 ** Step 11.9. "offset = offset + n + 1." 1499 */ 1500 offset += n + 1; 1501 } 1502 /* ****************************************************************** 1503 ** Step 12. "goto step 5." 1504 ** 1505 ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8 1506 ** and now need to return p,q, seed, and counter. 1507 */ 1508 if (counter > maxCount) 1509 goto step_5; 1510 1511 generate_G: 1512 /* ****************************************************************** 1513 ** returning p, q, seed and counter 1514 */ 1515 if (type == FIPS186_1_TYPE) { 1516 /* Generate g, This is called the "Unverifiable Generation of g 1517 * in FIPA186-3 Appedix A.2.1. For compatibility we maintain 1518 * this version of the code */ 1519 SECITEM_AllocItem(NULL, &hit, L / 8); /* h is no longer than p */ 1520 if (!hit.data) 1521 goto cleanup; 1522 do { 1523 /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */ 1524 CHECK_SEC_OK(generate_h_candidate(&hit, &H)); 1525 CHECK_SEC_OK(makeGfromH(&P, &Q, &H, &G, &passed)); 1526 } while (passed != PR_TRUE); 1527 MPINT_TO_SECITEM(&H, &verify->h, verify->arena); 1528 } else { 1529 unsigned char index = 1; /* default to 1 */ 1530 verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1); 1531 if (verify->h.data == NULL) { 1532 goto cleanup; 1533 } 1534 verify->h.len = 1; 1535 verify->h.data[0] = index; 1536 /* Generate g, using the FIPS 186-3 Appendix A.23 */ 1537 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G)); 1538 } 1539 /* All generation is done. Now, save the PQG params. */ 1540 MPINT_TO_SECITEM(&P, ¶ms->prime, params->arena); 1541 MPINT_TO_SECITEM(&Q, ¶ms->subPrime, params->arena); 1542 MPINT_TO_SECITEM(&G, ¶ms->base, params->arena); 1543 verify->counter = counter; 1544 *pParams = params; 1545 *pVfy = verify; 1546 cleanup: 1547 if (pseed.data) { 1548 SECITEM_ZfreeItem(&pseed, PR_FALSE); 1549 } 1550 if (qseed.data) { 1551 SECITEM_ZfreeItem(&qseed, PR_FALSE); 1552 } 1553 mp_clear(&P); 1554 mp_clear(&Q); 1555 mp_clear(&G); 1556 mp_clear(&H); 1557 mp_clear(&l); 1558 mp_clear(&p0); 1559 if (err) { 1560 MP_TO_SEC_ERROR(err); 1561 rv = SECFailure; 1562 } 1563 if (rv) { 1564 if (params) { 1565 PORT_FreeArena(params->arena, PR_TRUE); 1566 } 1567 if (verify) { 1568 PORT_FreeArena(verify->arena, PR_TRUE); 1569 } 1570 } 1571 if (hit.data) { 1572 SECITEM_ZfreeItem(&hit, PR_FALSE); 1573 } 1574 return rv; 1575 } 1576 1577 SECStatus 1578 PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy) 1579 { 1580 unsigned int L; /* Length of P in bits. Per FIPS 186. */ 1581 unsigned int seedBytes; 1582 1583 if (j > 8 || !pParams || !pVfy) { 1584 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1585 return SECFailure; 1586 } 1587 L = 512 + (j * 64); /* bits in P */ 1588 seedBytes = L / 8; 1589 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes, 1590 pParams, pVfy); 1591 } 1592 1593 SECStatus 1594 PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes, 1595 PQGParams **pParams, PQGVerify **pVfy) 1596 { 1597 unsigned int L; /* Length of P in bits. Per FIPS 186. */ 1598 1599 if (j > 8 || !pParams || !pVfy) { 1600 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1601 return SECFailure; 1602 } 1603 L = 512 + (j * 64); /* bits in P */ 1604 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes, 1605 pParams, pVfy); 1606 } 1607 1608 SECStatus 1609 PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes, 1610 PQGParams **pParams, PQGVerify **pVfy) 1611 { 1612 if (N == 0) { 1613 N = pqg_get_default_N(L); 1614 } 1615 if (seedBytes == 0) { 1616 /* seedBytes == L/8 for probable primes, N/8 for Shawe-Taylor Primes */ 1617 seedBytes = N / 8; 1618 } 1619 if (pqg_validate_dsa2(L, N) != SECSuccess) { 1620 /* error code already set */ 1621 return SECFailure; 1622 } 1623 return pqg_ParamGen(L, N, FIPS186_3_ST_TYPE, seedBytes, pParams, pVfy); 1624 } 1625 1626 /* 1627 * verify can use vfy structures returned from either FIPS186-1 or 1628 * FIPS186-2, and can handle differences in selected Hash functions to 1629 * generate the parameters. 1630 */ 1631 SECStatus 1632 PQG_VerifyParams(const PQGParams *params, 1633 const PQGVerify *vfy, SECStatus *result) 1634 { 1635 SECStatus rv = SECSuccess; 1636 unsigned int g, n, L, N, offset, outlen; 1637 mp_int p0, P, Q, G, P_, Q_, G_, r, h; 1638 mp_err err = MP_OKAY; 1639 int j; 1640 unsigned int counter_max = 0; /* handle legacy L < 1024 */ 1641 unsigned int qseed_len; 1642 unsigned int qgen_counter_ = 0; 1643 SECItem pseed_ = { 0, 0, 0 }; 1644 HASH_HashType hashtype = HASH_AlgNULL; 1645 pqgGenType type = FIPS186_1_TYPE; 1646 1647 #define CHECKPARAM(cond) \ 1648 if (!(cond)) { \ 1649 *result = SECFailure; \ 1650 goto cleanup; \ 1651 } 1652 if (!params || !vfy || !result) { 1653 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1654 return SECFailure; 1655 } 1656 /* always need at least p, q, and seed for any meaningful check */ 1657 if ((params->prime.len == 0) || (params->subPrime.len == 0) || 1658 (vfy->seed.len == 0)) { 1659 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1660 return SECFailure; 1661 } 1662 /* we want to either check PQ or G or both. If we don't have G, make 1663 * sure we have count so we can check P. */ 1664 if ((params->base.len == 0) && (vfy->counter == -1)) { 1665 PORT_SetError(SEC_ERROR_INVALID_ARGS); 1666 return SECFailure; 1667 } 1668 1669 MP_DIGITS(&p0) = 0; 1670 MP_DIGITS(&P) = 0; 1671 MP_DIGITS(&Q) = 0; 1672 MP_DIGITS(&G) = 0; 1673 MP_DIGITS(&P_) = 0; 1674 MP_DIGITS(&Q_) = 0; 1675 MP_DIGITS(&G_) = 0; 1676 MP_DIGITS(&r) = 0; 1677 MP_DIGITS(&h) = 0; 1678 CHECK_MPI_OK(mp_init(&p0)); 1679 CHECK_MPI_OK(mp_init(&P)); 1680 CHECK_MPI_OK(mp_init(&Q)); 1681 CHECK_MPI_OK(mp_init(&G)); 1682 CHECK_MPI_OK(mp_init(&P_)); 1683 CHECK_MPI_OK(mp_init(&Q_)); 1684 CHECK_MPI_OK(mp_init(&G_)); 1685 CHECK_MPI_OK(mp_init(&r)); 1686 CHECK_MPI_OK(mp_init(&h)); 1687 *result = SECSuccess; 1688 SECITEM_TO_MPINT(params->prime, &P); 1689 SECITEM_TO_MPINT(params->subPrime, &Q); 1690 /* if G isn't specified, just check P and Q */ 1691 if (params->base.len != 0) { 1692 SECITEM_TO_MPINT(params->base, &G); 1693 } 1694 /* 1. Check (L,N) pair */ 1695 N = mpl_significant_bits(&Q); 1696 L = mpl_significant_bits(&P); 1697 if (L < 1024) { 1698 /* handle DSA1 pqg parameters with less thatn 1024 bits*/ 1699 CHECKPARAM(N == DSA1_Q_BITS); 1700 j = PQG_PBITS_TO_INDEX(L); 1701 CHECKPARAM(j >= 0 && j <= 8); 1702 counter_max = 4096; 1703 } else { 1704 /* handle DSA2 parameters (includes DSA1, 1024 bits) */ 1705 CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess); 1706 counter_max = 4 * L; 1707 } 1708 /* 3. G < P */ 1709 if (params->base.len != 0) { 1710 CHECKPARAM(mp_cmp(&G, &P) < 0); 1711 } 1712 /* 4. P % Q == 1 */ 1713 CHECK_MPI_OK(mp_mod(&P, &Q, &r)); 1714 CHECKPARAM(mp_cmp_d(&r, 1) == 0); 1715 /* 5. Q is prime */ 1716 CHECKPARAM(mpp_pprime_secure(&Q, prime_testcount_q(L, N)) == MP_YES); 1717 /* 6. P is prime */ 1718 CHECKPARAM(mpp_pprime_secure(&P, prime_testcount_p(L, N)) == MP_YES); 1719 /* Steps 7-12 are done only if the optional PQGVerify is supplied. */ 1720 /* continue processing P */ 1721 /* 7. counter < 4*L */ 1722 /* 8. g >= N and g < 2*L (g is length of seed in bits) */ 1723 /* step 7 and 8 are delayed until we determine which type of generation 1724 * was used */ 1725 /* 9. Q generated from SEED matches Q in PQGParams. */ 1726 /* This function checks all possible hash and generation types to 1727 * find a Q_ which matches Q. */ 1728 g = vfy->seed.len * 8; 1729 CHECKPARAM(findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len, 1730 &hashtype, &type, &qgen_counter_) == SECSuccess); 1731 CHECKPARAM(mp_cmp(&Q, &Q_) == 0); 1732 /* now we can do steps 7 & 8*/ 1733 if ((type == FIPS186_1_TYPE) || (type == FIPS186_3_TYPE)) { 1734 CHECKPARAM((vfy->counter == -1) || (vfy->counter < counter_max)); 1735 CHECKPARAM(g >= N && g < counter_max / 2); 1736 } 1737 if (type == FIPS186_3_ST_TYPE) { 1738 SECItem qseed = { 0, 0, 0 }; 1739 SECItem pseed = { 0, 0, 0 }; 1740 unsigned int first_seed_len; 1741 unsigned int pgen_counter_ = 0; 1742 unsigned int qgen_counter = (vfy->counter >> 16) & 0xffff; 1743 unsigned int pgen_counter = (vfy->counter) & 0xffff; 1744 1745 /* extract pseed and qseed from domain_parameter_seed, which is 1746 * first_seed || pseed || qseed. qseed is first_seed + small_integer 1747 * mod the length of first_seed. pseed is qseed + small_integer mod 1748 * the length of first_seed. This means most of the time 1749 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or 1750 * pseed.len will be smaller because mpi clamps them. pqgGen 1751 * automatically adds the zero pad back though, so we can depend 1752 * domain_parameter_seed.len to be a multiple of three. We only have 1753 * to deal with the fact that the returned seeds from our functions 1754 * could be shorter. 1755 * first_seed.len = domain_parameter_seed.len/3 1756 * We can now find the offsets; 1757 * first_seed.data = domain_parameter_seed.data + 0 1758 * pseed.data = domain_parameter_seed.data + first_seed.len 1759 * qseed.data = domain_parameter_seed.data 1760 * + domain_paramter_seed.len - qseed.len 1761 * We deal with pseed possibly having zero pad in the pseed check later. 1762 */ 1763 first_seed_len = vfy->seed.len / 3; 1764 CHECKPARAM(qseed_len < vfy->seed.len); 1765 CHECKPARAM(first_seed_len * 8 > N - 1); 1766 CHECKPARAM(first_seed_len * 8 < counter_max / 2); 1767 CHECKPARAM(first_seed_len >= qseed_len); 1768 qseed.len = qseed_len; 1769 qseed.data = vfy->seed.data + vfy->seed.len - qseed.len; 1770 pseed.len = first_seed_len; 1771 pseed.data = vfy->seed.data + first_seed_len; 1772 1773 /* 1774 * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed 1775 * above in our initial checks, Step 2 was completed by 1776 * findQfromSeed */ 1777 1778 /* Step 3 (status, c0, prime_seed, prime_gen_counter) = 1779 ** (ST_Random_Prime((ceil(length/2)+1, input_seed) 1780 */ 1781 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, (L + 1) / 2 + 1, 1782 &qseed, &p0, &pseed_, &pgen_counter_)); 1783 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */ 1784 CHECK_SEC_OK(makePrimefromPrimesShaweTaylor(hashtype, L, first_seed_len * 8, 1785 &p0, &Q_, &P_, &pseed_, &pgen_counter_)); 1786 CHECKPARAM(mp_cmp(&P, &P_) == 0); 1787 /* make sure pseed wasn't tampered with (since it is part of 1788 * calculating G) */ 1789 if (pseed.len > pseed_.len) { 1790 /* handle the case of zero pad for pseed */ 1791 int extra = pseed.len - pseed_.len; 1792 int i; 1793 for (i = 0; i < extra; i++) { 1794 if (pseed.data[i] != 0) { 1795 *result = SECFailure; 1796 goto cleanup; 1797 } 1798 } 1799 pseed.data += extra; 1800 pseed.len -= extra; 1801 /* the rest is handled in the normal compare below */ 1802 } 1803 CHECKPARAM(SECITEM_CompareItem(&pseed, &pseed_) == SECEqual); 1804 if (vfy->counter != -1) { 1805 CHECKPARAM(pgen_counter < counter_max); 1806 CHECKPARAM(qgen_counter < counter_max); 1807 CHECKPARAM((pgen_counter_ == pgen_counter)); 1808 CHECKPARAM((qgen_counter_ == qgen_counter)); 1809 } 1810 } else if (vfy->counter == -1) { 1811 /* If counter is set to -1, we are really only verifying G, skip 1812 * the remainder of the checks for P */ 1813 CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */ 1814 } else { 1815 /* 10. P generated from (L, counter, g, SEED, Q) matches P 1816 * in PQGParams. */ 1817 outlen = HASH_ResultLen(hashtype) * PR_BITS_PER_BYTE; 1818 PORT_Assert(outlen > 0); 1819 n = (L - 1) / outlen; 1820 offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1); 1821 CHECK_SEC_OK(makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed, 1822 &Q, &P_)); 1823 CHECKPARAM(mp_cmp(&P, &P_) == 0); 1824 } 1825 1826 /* now check G, skip if don't have a g */ 1827 if (params->base.len == 0) 1828 goto cleanup; 1829 1830 /* first Always check that G is OK FIPS186-3 A.2.2 & A.2.4*/ 1831 /* 1. 2 < G < P-1 */ 1832 /* P is prime, p-1 == zero 1st bit */ 1833 CHECK_MPI_OK(mpl_set_bit(&P, 0, 0)); 1834 CHECKPARAM(mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0); 1835 CHECK_MPI_OK(mpl_set_bit(&P, 0, 1)); /* set it back */ 1836 /* 2. verify g**q mod p == 1 */ 1837 CHECK_MPI_OK(mp_exptmod(&G, &Q, &P, &h)); /* h = G ** Q mod P */ 1838 CHECKPARAM(mp_cmp_d(&h, 1) == 0); 1839 1840 /* no h, the above is the best we can do */ 1841 if (vfy->h.len == 0) { 1842 if (type != FIPS186_1_TYPE) { 1843 *result = SECWouldBlock; 1844 } 1845 goto cleanup; 1846 } 1847 1848 /* 1849 * If h is one byte and FIPS186-3 was used to generate Q (we've verified 1850 * Q was generated from seed already, then we assume that FIPS 186-3 1851 * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was 1852 * used to generate G. 1853 */ 1854 if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) { 1855 /* A.2.3 */ 1856 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed, 1857 vfy->h.data[0], &G_)); 1858 CHECKPARAM(mp_cmp(&G, &G_) == 0); 1859 } else { 1860 int passed; 1861 /* A.2.1 */ 1862 SECITEM_TO_MPINT(vfy->h, &h); 1863 /* 11. 1 < h < P-1 */ 1864 /* P is prime, p-1 == zero 1st bit */ 1865 CHECK_MPI_OK(mpl_set_bit(&P, 0, 0)); 1866 CHECKPARAM(mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P)); 1867 CHECK_MPI_OK(mpl_set_bit(&P, 0, 1)); /* set it back */ 1868 /* 12. G generated from h matches G in PQGParams. */ 1869 CHECK_SEC_OK(makeGfromH(&P, &Q, &h, &G_, &passed)); 1870 CHECKPARAM(passed && mp_cmp(&G, &G_) == 0); 1871 } 1872 cleanup: 1873 mp_clear(&p0); 1874 mp_clear(&P); 1875 mp_clear(&Q); 1876 mp_clear(&G); 1877 mp_clear(&P_); 1878 mp_clear(&Q_); 1879 mp_clear(&G_); 1880 mp_clear(&r); 1881 mp_clear(&h); 1882 if (pseed_.data) { 1883 SECITEM_ZfreeItem(&pseed_, PR_FALSE); 1884 } 1885 if (err) { 1886 MP_TO_SEC_ERROR(err); 1887 rv = SECFailure; 1888 } 1889 return rv; 1890 } 1891 1892 /************************************************************************** 1893 * Free the PQGParams struct and the things it points to. * 1894 **************************************************************************/ 1895 void 1896 PQG_DestroyParams(PQGParams *params) 1897 { 1898 if (params == NULL) 1899 return; 1900 if (params->arena != NULL) { 1901 PORT_FreeArena(params->arena, PR_TRUE); 1902 } else { 1903 SECITEM_ZfreeItem(¶ms->prime, PR_FALSE); /* don't free prime */ 1904 SECITEM_ZfreeItem(¶ms->subPrime, PR_FALSE); /* don't free subPrime */ 1905 SECITEM_ZfreeItem(¶ms->base, PR_FALSE); /* don't free base */ 1906 PORT_Free(params); 1907 } 1908 } 1909 1910 /************************************************************************** 1911 * Free the PQGVerify struct and the things it points to. * 1912 **************************************************************************/ 1913 1914 void 1915 PQG_DestroyVerify(PQGVerify *vfy) 1916 { 1917 if (vfy == NULL) 1918 return; 1919 if (vfy->arena != NULL) { 1920 PORT_FreeArena(vfy->arena, PR_TRUE); 1921 } else { 1922 SECITEM_ZfreeItem(&vfy->seed, PR_FALSE); /* don't free seed */ 1923 SECITEM_ZfreeItem(&vfy->h, PR_FALSE); /* don't free h */ 1924 PORT_Free(vfy); 1925 } 1926 }