nss/lib/freebl/pqg.c - Issue 2078763002: Delete bundled copy of NSS and replace with README.

Side by Side Diff: nss/lib/freebl/pqg.c

Issue 2078763002: Delete bundled copy of NSS and replace with README. (Closed) Base URL: https://chromium.googlesource.com/chromium/deps/nss@master

Patch Set: Delete bundled copy of NSS and replace with README. Created 4 years, 6 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch

OLD	NEW
	(Empty)
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 int prime_testcount_p(int L, int N)

47 {

48 switch (L) {

49 case 1024:

50 return 40;

51 case 2048:

52 return 56;

53 case 3072:

54 return 64;

55 default:

56 break;

57 }

58 return 50; /* L = 512-960 */

59 }

60

61 /* The q numbers are different if you run M-R followd by Lucas. I created

62 * a separate function so if someone wanted to add the Lucas check, they

63 * could do so fairly easily */

64 int prime_testcount_q(int L, int N)

65 {

66 return prime_testcount_p(L,N);

67 }

68

69 /*

70 * generic function to make sure our input matches DSA2 requirements

71 * this gives us one place to go if we need to bump the requirements in the

72 * future.

73 */

74 static SECStatus

75 pqg_validate_dsa2(unsigned int L, unsigned int N)

76 {

77

78 switch (L) {

79 case 1024:

80 if (N != DSA1_Q_BITS) {

81 PORT_SetError(SEC_ERROR_INVALID_ARGS);

82 return SECFailure;

83 }

84 break;

85 case 2048:

86 if ((N != 224) && (N != 256)) {

87 PORT_SetError(SEC_ERROR_INVALID_ARGS);

88 return SECFailure;

89 }

90 break;

91 case 3072:

92 if (N != 256) {

93 PORT_SetError(SEC_ERROR_INVALID_ARGS);

94 return SECFailure;

95 }

96 break;

97 default:

98 PORT_SetError(SEC_ERROR_INVALID_ARGS);

99 return SECFailure;

100 }

101 return SECSuccess;

102 }

103

104 static unsigned int

105 pqg_get_default_N(unsigned int L)

106 {

107 unsigned int N = 0;

108 switch (L) {

109 case 1024:

110 N = DSA1_Q_BITS;

111 break;

112 case 2048:

113 N = 224;

114 break;

115 case 3072:

116 N = 256;

117 break;

118 default:

119 PORT_SetError(SEC_ERROR_INVALID_ARGS);

120 break; /* N already set to zero */

121 }

122 return N;

123 }

124

125 /*

126 * Select the lowest hash algorithm usable

127 */

128 static HASH_HashType

129 getFirstHash(unsigned int L, unsigned int N)

130 {

131 if (N < 224) {

132 return HASH_AlgSHA1;

133 }

134 if (N < 256) {

135 return HASH_AlgSHA224;

136 }

137 if (N < 384) {

138 return HASH_AlgSHA256;

139 }

140 if (N < 512) {

141 return HASH_AlgSHA384;

142 }

143 return HASH_AlgSHA512;

144 }

145

146 /*

147 * find the next usable hash algorthim

148 */

149 static HASH_HashType

150 getNextHash(HASH_HashType hashtype)

151 {

152 switch (hashtype) {

153 case HASH_AlgSHA1:

154 hashtype = HASH_AlgSHA224;

155 break;

156 case HASH_AlgSHA224:

157 hashtype = HASH_AlgSHA256;

158 break;

159 case HASH_AlgSHA256:

160 hashtype = HASH_AlgSHA384;

161 break;

162 case HASH_AlgSHA384:

163 hashtype = HASH_AlgSHA512;

164 break;

165 case HASH_AlgSHA512:

166 default:

167 hashtype = HASH_AlgTOTAL;

168 break;

169 }

170 return hashtype;

171 }

172

173 static unsigned int

174 HASH_ResultLen(HASH_HashType type)

175 {

176 const SECHashObject *hash_obj = HASH_GetRawHashObject(type);

177 if (hash_obj == NULL) {

178 return 0;

179 }

180 return hash_obj->length;

181 }

182

183 static SECStatus

184 HASH_HashBuf(HASH_HashType type, unsigned char *dest,

185 const unsigned char *src, PRUint32 src_len)

186 {

187 const SECHashObject *hash_obj = HASH_GetRawHashObject(type);

188 void *hashcx = NULL;

189 unsigned int dummy;

190

191 if (hash_obj == NULL) {

192 return SECFailure;

193 }

194

195 hashcx = hash_obj->create();

196 if (hashcx == NULL) {

197 return SECFailure;

198 }

199 hash_obj->begin(hashcx);

200 hash_obj->update(hashcx,src,src_len);

201 hash_obj->end(hashcx,dest, &dummy, hash_obj->length);

202 hash_obj->destroy(hashcx, PR_TRUE);

203 return SECSuccess;

204 }

205

206 unsigned int

207 PQG_GetLength(const SECItem *obj)

208 {

209 unsigned int len = obj->len;

210

211 if (obj->data == NULL) {

212 return 0;

213 }

214 if (len > 1 && obj->data[0] == 0) {

215 len--;

216 }

217 return len;

218 }

219

220 SECStatus

221 PQG_Check(const PQGParams *params)

222 {

223 unsigned int L,N;

224 SECStatus rv = SECSuccess;

225

226 if (params == NULL) {

227 PORT_SetError(SEC_ERROR_INVALID_ARGS);

228 return SECFailure;

229 }

230

231 L = PQG_GetLength(&params->prime)*PR_BITS_PER_BYTE;

232 N = PQG_GetLength(&params->subPrime)*PR_BITS_PER_BYTE;

233

234 if (L < 1024) {

235 int j;

236

237 /* handle DSA1 pqg parameters with less thatn 1024 bits*/

238 if ( N != DSA1_Q_BITS ) {

239 PORT_SetError(SEC_ERROR_INVALID_ARGS);

240 return SECFailure;

241 }

242 j = PQG_PBITS_TO_INDEX(L);

243 if ( j < 0 ) {

244 PORT_SetError(SEC_ERROR_INVALID_ARGS);

245 rv = SECFailure;

246 }

247 } else {

248 /* handle DSA2 parameters (includes DSA1, 1024 bits) */

249 rv = pqg_validate_dsa2(L, N);

250 }

251 return rv;

252 }

253

254 HASH_HashType

255 PQG_GetHashType(const PQGParams *params)

256 {

257 unsigned int L,N;

258

259 if (params == NULL) {

260 PORT_SetError(SEC_ERROR_INVALID_ARGS);

261 return HASH_AlgNULL;

262 }

263

264 L = PQG_GetLength(&params->prime)*PR_BITS_PER_BYTE;

265 N = PQG_GetLength(&params->subPrime)*PR_BITS_PER_BYTE;

266 return getFirstHash(L, N);

267 }

268

269 /* Get a seed for generating P and Q. If in testing mode, copy in the

270 ** seed from FIPS 186-1 appendix 5. Otherwise, obtain bytes from the

271 ** global random number generator.

272 */

273 static SECStatus

274 getPQseed(SECItem seed, PLArenaPool arena)

275 {

276 SECStatus rv;

277

278 if (!seed->data) {

279 seed->data = (unsigned char*)PORT_ArenaZAlloc(arena, seed->len);

280 }

281 if (!seed->data) {

282 PORT_SetError(SEC_ERROR_NO_MEMORY);

283 return SECFailure;

284 }

285 rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len);

286 /*

287 * NIST CMVP disallows a sequence of 20 bytes with the most

288 * significant byte equal to 0. Perhaps they interpret

289 * "a sequence of at least 160 bits" as "a number >= 2^159".

290 * So we always set the most significant bit to 1. (bug 334533)

291 */

292 seed->data[0] \|= 0x80;

293 return rv;

294 }

295

296 /* Generate a candidate h value. If in testing mode, use the h value

297 ** specified in FIPS 186-1 appendix 5, h = 2. Otherwise, obtain bytes

298 ** from the global random number generator.

299 */

300 static SECStatus

301 generate_h_candidate(SECItem hit, mp_int H)

302 {

303 SECStatus rv = SECSuccess;

304 mp_err err = MP_OKAY;

305 #ifdef FIPS_186_1_A5_TEST

306 memset(hit->data, 0, hit->len);

307 hit->data[hit->len-1] = 0x02;

308 #else

309 rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len);

310 #endif

311 if (rv)

312 return SECFailure;

313 err = mp_read_unsigned_octets(H, hit->data, hit->len);

314 if (err) {

315 MP_TO_SEC_ERROR(err);

316 return SECFailure;

317 }

318 return SECSuccess;

319 }

320

321 static SECStatus

322 addToSeed(const SECItem * seed,

323 unsigned long addend,

324 int seedlen, /* g in 186-1 */

325 SECItem * seedout)

326 {

327 mp_int s, sum, modulus, tmp;

328 mp_err err = MP_OKAY;

329 SECStatus rv = SECSuccess;

330 MP_DIGITS(&s) = 0;

331 MP_DIGITS(&sum) = 0;

332 MP_DIGITS(&modulus) = 0;

333 MP_DIGITS(&tmp) = 0;

334 CHECK_MPI_OK( mp_init(&s) );

335 CHECK_MPI_OK( mp_init(&sum) );

336 CHECK_MPI_OK( mp_init(&modulus) );

337 SECITEM_TO_MPINT(seed, &s); / s = seed */

338 /* seed += addend */

339 if (addend < MP_DIGIT_MAX) {

340 CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );

341 } else {

342 CHECK_MPI_OK( mp_init(&tmp) );

343 CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );

344 CHECK_MPI_OK( mp_add(&s, &tmp, &s) );

345 }

346 /sum = s mod 2seedlen /

347 CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)seedlen, NULL, &sum) );

348 if (seedout->data != NULL) {

349 SECITEM_ZfreeItem(seedout, PR_FALSE);

350 }

351 MPINT_TO_SECITEM(&sum, seedout, NULL);

352 cleanup:

353 mp_clear(&s);

354 mp_clear(&sum);

355 mp_clear(&modulus);

356 mp_clear(&tmp);

357 if (err) {

358 MP_TO_SEC_ERROR(err);

359 return SECFailure;

360 }

361 return rv;

362 }

363

364 /* Compute Hash[(SEED + addend) mod 2**g]

365 ** Result is placed in shaOutBuf.

366 ** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 and

367 ** step 11.2 of FIPS 186-3 Appendix A.1.1.2 .

368 */

369 static SECStatus

370 addToSeedThenHash(HASH_HashType hashtype,

371 const SECItem * seed,

372 unsigned long addend,

373 int seedlen, /* g in 186-1 */

374 unsigned char * hashOutBuf)

375 {

376 SECItem str = { 0, 0, 0 };

377 SECStatus rv;

378 rv = addToSeed(seed, addend, seedlen, &str);

379 if (rv != SECSuccess) {

380 return rv;

381 }

382 rv = HASH_HashBuf(hashtype, hashOutBuf, str.data, str.len);/* hash result */

383 if (str.data)

384 SECITEM_ZfreeItem(&str, PR_FALSE);

385 return rv;

386 }

387

388 /*

389 ** Perform steps 2 and 3 of FIPS 186-1, appendix 2.2.

390 ** Generate Q from seed.

391 */

392 static SECStatus

393 makeQfromSeed(

394 unsigned int g, /* input. Length of seed in bits. */

395 const SECItem * seed, /* input. */

396 mp_int * Q) /* output. */

397 {

398 unsigned char sha1[SHA1_LENGTH];

399 unsigned char sha2[SHA1_LENGTH];

400 unsigned char U[SHA1_LENGTH];

401 SECStatus rv = SECSuccess;

402 mp_err err = MP_OKAY;

403 int i;

404 /* ******************************************************************

405 ** Step 2.

406 "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2g]."

407 **/

408 CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );

409 CHECK_SEC_OK( addToSeedThenHash(HASH_AlgSHA1, seed, 1, g, sha2) );

410 for (i=0; i<SHA1_LENGTH; ++i)

411 U[i] = sha1[i] ^ sha2[i];

412 /* ******************************************************************

413 ** Step 3.

414 "Form Q from U by setting the most signficant bit (the 2159 bit)

415 ** and the least signficant bit to 1. In terms of boolean operations,

416 Q = U OR 2159 OR 1. Note that 2159 < Q < 2160."

417 */

418 U[0] \|= 0x80; /* U is MSB first */

419 U[SHA1_LENGTH-1] \|= 0x01;

420 err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH);

421 cleanup:

422 memset(U, 0, SHA1_LENGTH);

423 memset(sha1, 0, SHA1_LENGTH);

424 memset(sha2, 0, SHA1_LENGTH);

425 if (err) {

426 MP_TO_SEC_ERROR(err);

427 return SECFailure;

428 }

429 return rv;

430 }

431

432 /*

433 ** Perform steps 6 and 7 of FIPS 186-3, appendix A.1.1.2.

434 ** Generate Q from seed.

435 */

436 static SECStatus

437 makeQ2fromSeed(

438 HASH_HashType hashtype, /* selected Hashing algorithm */

439 unsigned int N, /* input. Length of q in bits. */

440 const SECItem * seed, /* input. */

441 mp_int * Q) /* output. */

442 {

443 unsigned char U[HASH_LENGTH_MAX];

444 SECStatus rv = SECSuccess;

445 mp_err err = MP_OKAY;

446 int N_bytes = N/PR_BITS_PER_BYTE; /* length of N in bytes rather than bits * /

447 int hashLen = HASH_ResultLen(hashtype);

448 int offset = 0;

449

450 /* ******************************************************************

451 ** Step 6.

452 "Compute U = hash[SEED] mod 2N-1]."

453 **/

454 CHECK_SEC_OK( HASH_HashBuf(hashtype, U, seed->data, seed->len) );

455 /* mod 2**N . Step 7 will explicitly set the top bit to 1, so no need

456 * to handle mod 2*N-1 /

457 if (hashLen > N_bytes) {

458 offset = hashLen - N_bytes;

459 }

460 /* ******************************************************************

461 ** Step 7.

462 computed_q = 2(N-1) + U + 1 - (U mod 2)

463 **

464 ** This is the same as:

465 computed_q = 2(N-1) \| U \| 1;

466 */

467 U[offset] \|= 0x80; /* U is MSB first */

468 U[hashLen-1] \|= 0x01;

469 err = mp_read_unsigned_octets(Q, &U[offset], N_bytes);

470 cleanup:

471 memset(U, 0, HASH_LENGTH_MAX);

472 if (err) {

473 MP_TO_SEC_ERROR(err);

474 return SECFailure;

475 }

476 return rv;

477 }

478

479 /*

480 ** Perform steps from FIPS 186-3, Appendix A.1.2.1 and Appendix C.6

481 **

482 ** This generates a provable prime from two smaller prime. The resulting

483 ** prime p will have q0 as a multiple of p-1. q0 can be 1.

484 **

485 ** This implments steps 4 thorough 22 of FIPS 186-3 A.1.2.1 and

486 ** steps 16 through 34 of FIPS 186-2 C.6

487 */

488 #define MAX_ST_SEED_BITS (HASH_LENGTH_MAX*PR_BITS_PER_BYTE)

489 SECStatus

490 makePrimefromPrimesShaweTaylor(

491 HASH_HashType hashtype, /* selected Hashing algorithm */

492 unsigned int length, /* input. Length of prime in bits. */

493 mp_int * c0, /* seed prime */

494 mp_int * q, /* sub prime, can be 1 */

495 mp_int * prime, /* output. */

496 SECItem * prime_seed, /* input/output. */

497 unsigned int prime_gen_counter) / input/output. */

498 {

499 mp_int c;

500 mp_int c0_2;

501 mp_int t;

502 mp_int a;

503 mp_int z;

504 mp_int two_length_minus_1;

505 SECStatus rv = SECFailure;

506 int hashlen = HASH_ResultLen(hashtype);

507 int outlen = hashlen*PR_BITS_PER_BYTE;

508 int offset;

509 unsigned char bit, mask;

510 /* x needs to hold roundup(L/outlen)*outlen.

511 * This can be no larger than L+outlen-1, So we set it's size to

512 * our max L + max outlen and know we are safe */

513 unsigned char x[DSA_MAX_P_BITS/8+HASH_LENGTH_MAX];

514 mp_err err = MP_OKAY;

515 int i;

516 int iterations;

517 int old_counter;

518

519 MP_DIGITS(&c) = 0;

520 MP_DIGITS(&c0_2) = 0;

521 MP_DIGITS(&t) = 0;

522 MP_DIGITS(&a) = 0;

523 MP_DIGITS(&z) = 0;

524 MP_DIGITS(&two_length_minus_1) = 0;

525 CHECK_MPI_OK( mp_init(&c) );

526 CHECK_MPI_OK( mp_init(&c0_2) );

527 CHECK_MPI_OK( mp_init(&t) );

528 CHECK_MPI_OK( mp_init(&a) );

529 CHECK_MPI_OK( mp_init(&z) );

530 CHECK_MPI_OK( mp_init(&two_length_minus_1) );

531

532

533 /*

534 ** There is a slight mapping of variable names depending on which

535 ** FIPS 186 steps are being carried out. The mapping is as follows:

536 ** variable A.1.2.1 C.6

537 ** c0 p0 c0

538 ** q q 1

539 ** c p c

540 ** c0_2 2p0q 2*c0

541 ** length L length

542 ** prime_seed pseed prime_seed

543 ** prime_gen_counter pgen_counter prime_gen_counter

544 **

545 ** Also note: or iterations variable is actually iterations+1, since

546 ** iterations+1 works better in C.

547 */

548

549 /* Step 4/16 iterations = ceiling(length/outlen)-1 */

550 iterations = (length+outlen-1)/outlen; /* NOTE: iterations +1 */

551 /* Step 5/17 old_counter = prime_gen_counter */

552 old_counter = *prime_gen_counter;

553 /*

554 ** Comment: Generate a pseudorandom integer x in the interval

555 [2(lenght-1), 2**length].

556 **

557 ** Step 6/18 x = 0

558 */

559 PORT_Memset(x, 0, sizeof(x));

560 /*

561 ** Step 7/19 for i = 0 to iterations do

562 ** x = x + (HASH(prime_seed + i) * 2^(i*outlen))

563 */

564 for (i=0; i < iterations; i++) {

565 /* is bigger than prime_seed should get to */

566 CHECK_SEC_OK( addToSeedThenHash(hashtype, prime_seed, i,

567 MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));

568 }

569 /* Step 8/20 prime_seed = prime_seed + iterations + 1 */

570 CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS,

571 prime_seed));

572 /*

573 Step 9/21 x = 2 (length-1) + x mod 2 ** (length-1)

574 **

575 ** This step mathematically sets the high bit and clears out

576 ** all the other bits higher than length. 'x' is stored

577 ** in the x array, MSB first. The above formula gives us an 'x'

578 ** which is length bytes long and has the high bit set. We also know

579 ** that length <= iterations*outlen since

580 ** iterations=ceiling(length/outlen). First we find the offset in

581 ** bytes into the array where the high bit is.

582 */

583 offset = (outlen*iterations - length)/PR_BITS_PER_BYTE;

584 /* now we want to set the 'high bit', since length may not be a

585 * multiple of 8,*/

586 bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */

587 /* we need to zero out the rest of the bits in the byte above */

588 mask = (bit-1);

589 /* now we set it */

590 x[offset] = (mask & x[offset]) \| bit;

591 /*

592 ** Comment: Generate a candidate prime c in the interval

593 [2(lenght-1), 2**length].

594 **

595 ** Step 10 t = ceiling(x/(2q(p0)))

596 ** Step 22 t = ceiling(x/(2(c0)))

597 */

598 CHECK_MPI_OK( mp_read_unsigned_octets(&t, &x[offset],

599 hashleniterations - offset ) ); / t = x */

600 CHECK_MPI_OK( mp_mul(c0, q, &c0_2) ); /* c0_2 is now c0q /

601 CHECK_MPI_OK( mp_add(&c0_2, &c0_2, &c0_2) ); /* c0_2 is now 2qc0 */

602 CHECK_MPI_OK( mp_add(&t, &c0_2, &t) ); /* t = x+2qc0 */

603 CHECK_MPI_OK( mp_sub_d(&t, (mp_digit) 1, &t) ); /* t = x+2qc0 -1 */

604 /* t = floor((x+2qc0-1)/2qc0) = ceil(x/2qc0) */

605 CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );

606 /*

607 step 11: if (2tqp0 +1 > 2length), then t = ceiling(2**(length-1)/2qp0)

608 ** step 12: t = 2tqp0 +1.

609 **

610 step 23: if (2tc0 +1 > 2length), then t = ceiling(2**(length-1)/2c0)

611 ** step 24: t = 2tc0 +1.

612 */

613 CHECK_MPI_OK( mp_2expt(&two_length_minus_1, length-1) );

614 step_23:

615 CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) ); /* c = t2qc0 /

616 CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/

617 if (mpl_significant_bits(&c) > length) { /* if c > 2*length /

618 CHECK_MPI_OK( mp_sub_d(&c0_2, (mp_digit) 1, &t) ); /* t = 2qc0-1 */

619 /* t = 2*(length-1) + 2qc0 -1 /

620 CHECK_MPI_OK( mp_add(&two_length_minus_1,&t, &t) );

621 /* t = floor((2**(length-1)+2qc0 -1)/2qco)

622 * = ceil(2*(lenght-2)/2qc0) /

623 CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );

624 CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) );

625 CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/

626 }

627 /* Step 13/25 prime_gen_counter = prime_gen_counter + 1*/

628 (*prime_gen_counter)++;

629 /*

630 ** Comment: Test the candidate prime c for primality; first pick an

631 ** integer a between 2 and c-2.

632 **

633 ** Step 14/26 a=0

634 */

635 PORT_Memset(x, 0, sizeof(x)); /* use x for a */

636 /*

637 ** Step 15/27 for i = 0 to iterations do

638 ** a = a + (HASH(prime_seed + i) * 2^(i*outlen))

639 **

640 ** NOTE: we reuse the x array for 'a' initially.

641 */

642 for (i=0; i < iterations; i++) {

643 /* MAX_ST_SEED_BITS is bigger than prime_seed should get to */

644 CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i,

645 MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));

646 }

647 /* Step 16/28 prime_seed = prime_seed + iterations + 1 */

648 CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS,

649 prime_seed));

650 /* Step 17/29 a = 2 + (a mod (c-3)). */

651 CHECK_MPI_OK( mp_read_unsigned_octets(&a, x, iterations*hashlen) );

652 CHECK_MPI_OK( mp_sub_d(&c, (mp_digit) 3, &z) ); /* z = c -3 */

653 CHECK_MPI_OK( mp_mod(&a, &z, &a) ); /* a = a mod c -3 */

654 CHECK_MPI_OK( mp_add_d(&a, (mp_digit) 2, &a) ); /* a = 2 + a mod c -3 */

655 /*

656 Step 18 z = a(2tq) mod p.

657 Step 30 z = a(2t) mod c.

658 */

659 CHECK_MPI_OK( mp_mul(&t, q, &z) ); /* z = tq */

660 CHECK_MPI_OK( mp_add(&z, &z, &z) ); /* z = 2tq */

661 CHECK_MPI_OK( mp_exptmod(&a, &z, &c, &z) ); /* z = a*(2tq) mod c /

662 /*

663 Step 19 if (( 1 == GCD(z-1,p)) and ( 1 == zp0 mod p )), then

664 Step 31 if (( 1 == GCD(z-1,c)) and ( 1 == zc0 mod c )), then

665 */

666 CHECK_MPI_OK( mp_sub_d(&z, (mp_digit) 1, &a) );

667 CHECK_MPI_OK( mp_gcd(&a,&c,&a ));

668 if (mp_cmp_d(&a, (mp_digit)1) == 0) {

669 CHECK_MPI_OK( mp_exptmod(&z, c0, &c, &a) );

670 if (mp_cmp_d(&a, (mp_digit)1) == 0) {

671 /* Step 31.1 prime = c */

672 CHECK_MPI_OK( mp_copy(&c, prime) );

673 /*

674 ** Step 31.2 return Success, prime, prime_seed,

675 ** prime_gen_counter

676 */

677 rv = SECSuccess;

678 goto cleanup;

679 }

680 }

681 /*

682 ** Step 20/32 If (prime_gen_counter > 4 * length + old_counter then

683 ** return (FAILURE, 0, 0, 0).

684 ** NOTE: the test is reversed, so we fall through on failure to the

685 ** cleanup routine

686 */

687 if (prime_gen_counter < (4length + old_counter)) {

688 /* Step 21/33 t = t + 1 */

689 CHECK_MPI_OK( mp_add_d(&t, (mp_digit) 1, &t) );

690 /* Step 22/34 Go to step 23/11 */

691 goto step_23;

692 }

693

694 /* if (prime_gencont > (4length + old_counter), fall through to failure /

695 rv = SECFailure; /* really is already set, but paranoia is good */

696

697 cleanup:

698 mp_clear(&c);

699 mp_clear(&c0_2);

700 mp_clear(&t);

701 mp_clear(&a);

702 mp_clear(&z);

703 mp_clear(&two_length_minus_1);

704 if (err) {

705 MP_TO_SEC_ERROR(err);

706 rv = SECFailure;

707 }

708 if (rv == SECFailure) {

709 mp_zero(prime);

710 if (prime_seed->data) {

711 SECITEM_FreeItem(prime_seed, PR_FALSE);

712 }

713 *prime_gen_counter = 0;

714 }

715 return rv;

716 }

717

718 /*

719 ** Perform steps from FIPS 186-3, Appendix C.6

720 **

721 ** This generates a provable prime from a seed

722 */

723 SECStatus

724 makePrimefromSeedShaweTaylor(

725 HASH_HashType hashtype, /* selected Hashing algorithm */

726 unsigned int length, /* input. Length of prime in bits. */

727 const SECItem * input_seed, /* input. */

728 mp_int * prime, /* output. */

729 SECItem * prime_seed, /* output. */

730 unsigned int prime_gen_counter) / output. */

731 {

732 mp_int c;

733 mp_int c0;

734 mp_int one;

735 SECStatus rv = SECFailure;

736 int hashlen = HASH_ResultLen(hashtype);

737 int outlen = hashlen*PR_BITS_PER_BYTE;

738 int offset;

739 unsigned char bit, mask;

740 unsigned char x[HASH_LENGTH_MAX*2];

741 mp_digit dummy;

742 mp_err err = MP_OKAY;

743 int i;

744

745 MP_DIGITS(&c) = 0;

746 MP_DIGITS(&c0) = 0;

747 MP_DIGITS(&one) = 0;

748 CHECK_MPI_OK( mp_init(&c) );

749 CHECK_MPI_OK( mp_init(&c0) );

750 CHECK_MPI_OK( mp_init(&one) );

751

752 /* Step 1. if length < 2 then return (FAILURE, 0, 0, 0) */

753 if (length < 2) {

754 rv = SECFailure;

755 goto cleanup;

756 }

757 /* Step 2. if length >= 33 then goto step 14 */

758 if (length >= 33) {

759 mp_zero(&one);

760 CHECK_MPI_OK( mp_add_d(&one, (mp_digit) 1, &one) );

761

762 /* Step 14 (status, c0, prime_seed, prime_gen_counter) =

763 ** (ST_Random_Prime((ceil(length/2)+1, input_seed)

764 */

765 rv = makePrimefromSeedShaweTaylor(hashtype, (length+1)/2+1,

766 input_seed, &c0, prime_seed, prime_gen_counter);

767 /* Step 15 if FAILURE is returned, return (FAILURE, 0, 0, 0). */

768 if (rv != SECSuccess) {

769 goto cleanup;

770 }

771 /* Steps 16-34 */

772 rv = makePrimefromPrimesShaweTaylor(hashtype,length, &c0, &one,

773 prime, prime_seed, prime_gen_counter);

774 goto cleanup; /* we're done, one way or the other */

775 }

776 /* Step 3 prime_seed = input_seed */

777 CHECK_SEC_OK(SECITEM_CopyItem(NULL, prime_seed, input_seed));

778 /* Step 4 prime_gen_count = 0 */

779 *prime_gen_counter = 0;

780

781 step_5:

782 /* Step 5 c = Hash(prime_seed) xor Hash(prime_seed+1). */

783 CHECK_SEC_OK(HASH_HashBuf(hashtype, x, prime_seed->data, prime_seed->len) );

784 CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, 1,

785 MAX_ST_SEED_BITS, &x[hashlen]) );

786 for (i=0; i < hashlen; i++) {

787 x[i] = x[i] ^ x[i+hashlen];

788 }

789 /* Step 6 c = 2length-1 + c mod 2length-1 */

790 /* This step mathematically sets the high bit and clears out

791 ** all the other bits higher than length. Right now c is stored

792 ** in the x array, MSB first. The above formula gives us a c which

793 ** is length bytes long and has the high bit set. We also know that

794 ** length < outlen since the smallest outlen is 160 bits and the largest

795 ** length at this point is 32 bits. So first we find the offset in bytes

796 ** into the array where the high bit is.

797 */

798 offset = (outlen - length)/PR_BITS_PER_BYTE;

799 /* now we want to set the 'high bit'. We have to calculate this since

800 * length may not be a multiple of 8.*/

801 bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */

802 /* we need to zero out the rest of the bits in the byte above */

803 mask = (bit-1);

804 /* now we set it */

805 x[offset] = (mask & x[offset]) \| bit;

806 /* Step 7 c = cfloor(c/2) + 1 /

807 /* set the low bit. much easier to find (the end of the array) */

808 x[hashlen-1] \|= 1;

809 /* now that we've set our bits, we can create our candidate "c" */

810 CHECK_MPI_OK( mp_read_unsigned_octets(&c, &x[offset], hashlen-offset) );

811 /* Step 8 prime_gen_counter = prime_gen_counter + 1 */

812 (*prime_gen_counter)++;

813 /* Step 9 prime_seed = prime_seed + 2 */

814 CHECK_SEC_OK(addToSeed(prime_seed, 2, MAX_ST_SEED_BITS, prime_seed));

815 /* Step 10 Perform deterministic primality test on c. For example, since

816 ** c is small, it's primality can be tested by trial division, See

817 ** See Appendic C.7.

818 **

819 ** We in fact test with trial division. mpi has a built int trial divider

820 ** that divides all divisors up to 2^16.

821 */

822 if (prime_tab[prime_tab_size-1] < 0xFFF1) {

823 /* we aren't testing all the primes between 0 and 2^16, we really

824 * can't use this construction. Just fail. */

825 rv = SECFailure;

826 goto cleanup;

827 }

828 dummy = prime_tab_size;

829 err = mpp_divis_primes(&c, &dummy);

830 /* Step 11 if c is prime then */

831 if (err == MP_NO) {

832 /* Step 11.1 prime = c */

833 CHECK_MPI_OK( mp_copy(&c, prime) );

834 /* Step 11.2 return SUCCESS prime, prime_seed, prime_gen_counter */

835 err = MP_OKAY;

836 rv = SECSuccess;

837 goto cleanup;

838 } else if (err != MP_YES) {

839 goto cleanup; /* function failed, bail out */

840 } else {

841 /* reset mp_err */

842 err = MP_OKAY;

843 }

844 /*

845 ** Step 12 if (prime_gen_counter > (4*len))

846 ** then return (FAILURE, 0, 0, 0))

847 ** Step 13 goto step 5

848 */

849 if (prime_gen_counter <= (4length)) {

850 goto step_5;

851 }

852 /* if (prime_gencont > 4length), fall through to failure /

853 rv = SECFailure; /* really is already set, but paranoia is good */

854

855 cleanup:

856 mp_clear(&c);

857 mp_clear(&c0);

858 mp_clear(&one);

859 if (err) {

860 MP_TO_SEC_ERROR(err);

861 rv = SECFailure;

862 }

863 if (rv == SECFailure) {

864 mp_zero(prime);

865 if (prime_seed->data) {

866 SECITEM_FreeItem(prime_seed, PR_FALSE);

867 }

868 *prime_gen_counter = 0;

869 }

870 return rv;

871 }

872

873

874 /*

875 * Find a Q and algorithm from Seed.

876 */

877 static SECStatus

878 findQfromSeed(

879 unsigned int L, /* input. Length of p in bits. */

880 unsigned int N, /* input. Length of q in bits. */

881 unsigned int g, /* input. Length of seed in bits. */

882 const SECItem * seed, /* input. */

883 mp_int * Q, /* input. */

884 mp_int * Q_, /* output. */

885 unsigned int qseed_len, / output */

886 HASH_HashType hashtypePtr, / output. Hash uses */

887 pqgGenType typePtr) / output. Generation Type used */

888 {

889 HASH_HashType hashtype;

890 SECItem firstseed = { 0, 0, 0 };

891 SECItem qseed = { 0, 0, 0 };

892 SECStatus rv;

893

894 qseed_len = 0; / only set if FIPS186_3_ST_TYPE */

895

896 /* handle legacy small DSA first can only be FIPS186_1_TYPE */

897 if (L < 1024) {

898 rv =makeQfromSeed(g,seed,Q_);

899 if ((rv == SECSuccess) && (mp_cmp(Q,Q_) == 0)) {

900 *hashtypePtr = HASH_AlgSHA1;

901 *typePtr = FIPS186_1_TYPE;

902 return SECSuccess;

903 }

904 return SECFailure;

905 }

906 /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try

907 * them both */

908 if (L == 1024) {

909 rv = makeQfromSeed(g,seed,Q_);

910 if (rv == SECSuccess) {

911 if (mp_cmp(Q,Q_) == 0) {

912 *hashtypePtr = HASH_AlgSHA1;

913 *typePtr = FIPS186_1_TYPE;

914 return SECSuccess;

915 }

916 }

917 /* fall through for FIPS186_3 types */

918 }

919 /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3

920 * with appropriate hash types */

921 for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL;

922 hashtype=getNextHash(hashtype)) {

923 rv = makeQ2fromSeed(hashtype, N, seed, Q_);

924 if (rv != SECSuccess) {

925 continue;

926 }

927 if (mp_cmp(Q,Q_) == 0) {

928 *hashtypePtr = hashtype;

929 *typePtr = FIPS186_3_TYPE;

930 return SECSuccess;

931 }

932 }

933 /*

934 * OK finally try FIPS186_3 Shawe-Taylor

935 */

936 firstseed = *seed;

937 firstseed.len = seed->len/3;

938 for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL;

939 hashtype=getNextHash(hashtype)) {

940 unsigned int count;

941

942 rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_,

943 &qseed, &count);

944 if (rv != SECSuccess) {

945 continue;

946 }

947 if (mp_cmp(Q,Q_) == 0) {

948 /* check qseed as well... */

949 int offset = seed->len - qseed.len;

950 if ((offset < 0) \|\|

951 (PORT_Memcmp(&seed->data[offset],qseed.data,qseed.len) != 0)) {

952 /* we found q, but the seeds don't match. This isn't an

953 * accident, someone has been tweeking with the seeds, just

954 * fail a this point. */

955 SECITEM_FreeItem(&qseed,PR_FALSE);

956 return SECFailure;

957 }

958 *qseed_len = qseed.len;

959 *hashtypePtr = hashtype;

960 *typePtr = FIPS186_3_ST_TYPE;

961 SECITEM_FreeItem(&qseed, PR_FALSE);

962 return SECSuccess;

963 }

964 SECITEM_FreeItem(&qseed, PR_FALSE);

965 }

966 /* no hash algorithms found which match seed to Q, fail */

967 return SECFailure;

968 }

969

970

971

972 /*

973 ** Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.

974 ** which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2

975 ** Generate P from Q, seed, L, and offset.

976 */

977 static SECStatus

978 makePfromQandSeed(

979 HASH_HashType hashtype, /* selected Hashing algorithm */

980 unsigned int L, /* Length of P in bits. Per FIPS 186. */

981 unsigned int N, /* Length of Q in bits. Per FIPS 186. */

982 unsigned int offset, /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */

983 unsigned int seedlen, /* input. Length of seed in bits. (g in 186-1)*/

984 const SECItem * seed, /* input. */

985 const mp_int * Q, /* input. */

986 mp_int * P) /* output. */

987 {

988 unsigned int j; /* Per FIPS 186-3 App. A.1.1.2 (k in 186-1)*/

989 unsigned int n; /* Per FIPS 186, appendix 2.2. */

990 mp_digit b; /* Per FIPS 186, appendix 2.2. */

991 unsigned int outlen; /* Per FIPS 186-3 App. A.1.1.2 */

992 unsigned int hashlen; /* outlen in bytes */

993 unsigned char V_j[HASH_LENGTH_MAX];

994 mp_int W, X, c, twoQ, V_n, tmp;

995 mp_err err = MP_OKAY;

996 SECStatus rv = SECSuccess;

997 /* Initialize bignums */

998 MP_DIGITS(&W) = 0;

999 MP_DIGITS(&X) = 0;

1000 MP_DIGITS(&c) = 0;

1001 MP_DIGITS(&twoQ) = 0;

1002 MP_DIGITS(&V_n) = 0;

1003 MP_DIGITS(&tmp) = 0;

1004 CHECK_MPI_OK( mp_init(&W) );

1005 CHECK_MPI_OK( mp_init(&X) );

1006 CHECK_MPI_OK( mp_init(&c) );

1007 CHECK_MPI_OK( mp_init(&twoQ) );

1008 CHECK_MPI_OK( mp_init(&tmp) );

1009 CHECK_MPI_OK( mp_init(&V_n) );

1010

1011 hashlen = HASH_ResultLen(hashtype);

1012 outlen = hashlen*PR_BITS_PER_BYTE;

1013

1014 /* L - 1 = noutlen + b /

1015 n = (L - 1) / outlen;

1016 b = (L - 1) % outlen;

1017

1018 /* ******************************************************************

1019 ** Step 11.1 (Step 7 in 186-1)

1020 ** "for j = 0 ... n let

1021 V_j = SHA[(SEED + offset + j) mod 2seedlen]."

1022 **

1023 ** Step 11.2 (Step 8 in 186-1)

1024 ** "W = V_0 + (V_1 * 2*outlen) + ... + (V_n-1 2*((n-1)outlen))

1025 + ((V_n mod 2b) * 2*(noutlen))

1026 */

1027 for (j=0; j<n; ++j) { /* Do the first n terms of V_j */

1028 /* Do step 11.1 for iteration j.

1029 V_j = HASH[(seed + offset + j) mod 2g]

1030 */

1031 CHECK_SEC_OK( addToSeedThenHash(hashtype,seed,offset+j, seedlen, V_j) );

1032 /* Do step 11.2 for iteration j.

1033 ** W += V_j * 2*(joutlen)

1034 */

1035 OCTETS_TO_MPINT(V_j, &tmp, hashlen); /* get bignum V_j */

1036 CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, joutlen) );/ tmp=V_j << joutlen /

1037 CHECK_MPI_OK( mp_add(&W, &tmp, &W) ); /* W += tmp */

1038 }

1039 /* Step 11.2, continued.

1040 [W += ((V_n mod 2b) * 2*(noutlen))]

1041 */

1042 CHECK_SEC_OK( addToSeedThenHash(hashtype, seed, offset + n, seedlen, V_j) );

1043 OCTETS_TO_MPINT(V_j, &V_n, hashlen); /* get bignum V_n */

1044 CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) ); /* tmp = V_n mod 2*b /

1045 CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, noutlen) ); / tmp = tmp << noutlen /

1046 CHECK_MPI_OK( mp_add(&W, &tmp, &W) ); /* W += tmp */

1047 /* Step 11.3, (Step 8 in 186-1)

1048 "X = W + 2(L-1).

1049 Note that 0 <= W < 2(L-1) and hence 2(L-1) <= X < 2L."

1050 */

1051 CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) ); /* X = 2*(L-1) /

1052 CHECK_MPI_OK( mp_add(&X, &W, &X) ); /* X += W */

1053 /*************************************************************

1054 ** Step 11.4. (Step 9 in 186-1)

1055 ** "c = X mod 2q"

1056 */

1057 CHECK_MPI_OK( mp_mul_2(Q, &twoQ) ); /* 2q */

1058 CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) ); /* c = X mod 2q */

1059 /*************************************************************

1060 ** Step 11.5. (Step 9 in 186-1)

1061 ** "p = X - (c - 1).

1062 ** Note that p is congruent to 1 mod 2q."

1063 */

1064 CHECK_MPI_OK( mp_sub_d(&c, 1, &c) ); /* c -= 1 */

1065 CHECK_MPI_OK( mp_sub(&X, &c, P) ); /* P = X - c */

1066 cleanup:

1067 mp_clear(&W);

1068 mp_clear(&X);

1069 mp_clear(&c);

1070 mp_clear(&twoQ);

1071 mp_clear(&V_n);

1072 mp_clear(&tmp);

1073 if (err) {

1074 MP_TO_SEC_ERROR(err);

1075 return SECFailure;

1076 }

1077 return rv;

1078 }

1079

1080 /*

1081 ** Generate G from h, P, and Q.

1082 */

1083 static SECStatus

1084 makeGfromH(const mp_int P, / input. */

1085 const mp_int Q, / input. */

1086 mp_int H, / input and output. */

1087 mp_int G, / output. */

1088 PRBool *passed)

1089 {

1090 mp_int exp, pm1;

1091 mp_err err = MP_OKAY;

1092 SECStatus rv = SECSuccess;

1093 *passed = PR_FALSE;

1094 MP_DIGITS(&exp) = 0;

1095 MP_DIGITS(&pm1) = 0;

1096 CHECK_MPI_OK( mp_init(&exp) );

1097 CHECK_MPI_OK( mp_init(&pm1) );

1098 CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) ); /* P - 1 */

1099 if ( mp_cmp(H, &pm1) >= 0) /* H >= P-1 */

1100 CHECK_MPI_OK( mp_sub(H, &pm1, H) ); /* H = H mod (P-1) */

1101 /* Let b = 2**n (smallest power of 2 greater than P).

1102 ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1

1103 ** so the above operation safely computes H mod (P-1)

1104 */

1105 /* Check for H = to 0 or 1. Regen H if so. (Regen means return error). */

1106 if (mp_cmp_d(H, 1) <= 0) {

1107 rv = SECFailure;

1108 goto cleanup;

1109 }

1110 /* Compute G, according to the equation G = (H ** ((P-1)/Q)) mod P */

1111 CHECK_MPI_OK( mp_div(&pm1, Q, &exp, NULL) ); /* exp = (P-1)/Q */

1112 CHECK_MPI_OK( mp_exptmod(H, &exp, P, G) ); /* G = H ** exp mod P */

1113 /* Check for G == 0 or G == 1, return error if so. */

1114 if (mp_cmp_d(G, 1) <= 0) {

1115 rv = SECFailure;

1116 goto cleanup;

1117 }

1118 *passed = PR_TRUE;

1119 cleanup:

1120 mp_clear(&exp);

1121 mp_clear(&pm1);

1122 if (err) {

1123 MP_TO_SEC_ERROR(err);

1124 rv = SECFailure;

1125 }

1126 return rv;

1127 }

1128

1129 /*

1130 ** Generate G from seed, index, P, and Q.

1131 */

1132 static SECStatus

1133 makeGfromIndex(HASH_HashType hashtype,

1134 const mp_int P, / input. */

1135 const mp_int Q, / input. */

1136 const SECItem seed, / input. */

1137 unsigned char index, /* input. */

1138 mp_int G) / input/output */

1139 {

1140 mp_int e, pm1, W;

1141 unsigned int count;

1142 unsigned char data[HASH_LENGTH_MAX];

1143 unsigned int len;

1144 mp_err err = MP_OKAY;

1145 SECStatus rv = SECSuccess;

1146 const SECHashObject *hashobj = NULL;

1147 void *hashcx = NULL;

1148

1149 MP_DIGITS(&e) = 0;

1150 MP_DIGITS(&pm1) = 0;

1151 MP_DIGITS(&W) = 0;

1152 CHECK_MPI_OK( mp_init(&e) );

1153 CHECK_MPI_OK( mp_init(&pm1) );

1154 CHECK_MPI_OK( mp_init(&W) );

1155

1156 /* initialize our hash stuff */

1157 hashobj = HASH_GetRawHashObject(hashtype);

1158 if (hashobj == NULL) {

1159 /* shouldn't happen */

1160 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);

1161 rv = SECFailure;

1162 goto cleanup;

1163 }

1164 hashcx = hashobj->create();

1165 if (hashcx == NULL) {

1166 rv = SECFailure;

1167 goto cleanup;

1168 }

1169

1170 CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) ); /* P - 1 */

1171 /* Step 3 e = (p-1)/q */

1172 CHECK_MPI_OK( mp_div(&pm1, Q, &e, NULL) ); /* e = (P-1)/Q */

1173 /* Steps 4, 5, and 6 */

1174 /* count is a 16 bit value in the spec. We actually represent count

1175 * as more than 16 bits so we can easily detect the 16 bit overflow */

1176 #define MAX_COUNT 0x10000

1177 for (count = 1; count < MAX_COUNT; count++) {

1178 /* step 7

1179 * U = domain_param_seed \|\| "ggen" \|\| index \|\| count

1180 * step 8

1181 * W = HASH(U)

1182 */

1183 hashobj->begin(hashcx);

1184 hashobj->update(hashcx,seed->data,seed->len);

1185 hashobj->update(hashcx, (unsigned char *)"ggen", 4);

1186 hashobj->update(hashcx,&index, 1);

1187 data[0] = (count >> 8) & 0xff;

1188 data[1] = count & 0xff;

1189 hashobj->update(hashcx, data, 2);

1190 hashobj->end(hashcx, data, &len, sizeof(data));

1191 OCTETS_TO_MPINT(data, &W, len);

1192 /* step 9. g = W*e mod p /

1193 CHECK_MPI_OK( mp_exptmod(&W, &e, P, G) );

1194 /* step 10. if (g < 2) then goto step 5 */

1195 /* NOTE: this weird construct is to keep the flow according to the spec.

1196 * the continue puts us back to step 5 of the for loop */

1197 if (mp_cmp_d(G, 2) < 0) {

1198 continue;

1199 }

1200 break; /* step 11 follows step 10 if the test condition is false */

1201 }

1202 if (count >= MAX_COUNT) {

1203 rv = SECFailure; /* last part of step 6 */

1204 }

1205 /* step 11.

1206 * return valid G */

1207 cleanup:

1208 PORT_Memset(data, 0, sizeof(data));

1209 if (hashcx) {

1210 hashobj->destroy(hashcx, PR_TRUE);

1211 }

1212 mp_clear(&e);

1213 mp_clear(&pm1);

1214 mp_clear(&W);

1215 if (err) {

1216 MP_TO_SEC_ERROR(err);

1217 rv = SECFailure;

1218 }

1219 return rv;

1220 }

1221

1222 /* This code uses labels and gotos, so that it can follow the numbered

1223 ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely,

1224 ** and so that the correctness of this code can be easily verified.

1225 ** So, please forgive the ugly c code.

1226 **/

1227 static SECStatus

1228 pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type,

1229 unsigned int seedBytes, PQGParams pParams, PQGVerify pVfy)

1230 {

1231 unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */

1232 unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/

1233 unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */

1234 unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */

1235 unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */

1236 unsigned int maxCount;

1237 HASH_HashType hashtype;

1238 SECItem seed; / Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */

1239 PLArenaPool *arena = NULL;

1240 PQGParams *params = NULL;

1241 PQGVerify *verify = NULL;

1242 PRBool passed;

1243 SECItem hit = { 0, 0, 0 };

1244 SECItem firstseed = { 0, 0, 0 };

1245 SECItem qseed = { 0, 0, 0 };

1246 SECItem pseed = { 0, 0, 0 };

1247 mp_int P, Q, G, H, l, p0;

1248 mp_err err = MP_OKAY;

1249 SECStatus rv = SECFailure;

1250 int iterations = 0;

1251

1252

1253 /* Step 1. L and N already checked by caller*/

1254 /* Step 2. if (seedlen < N) return INVALID; */

1255 if (seedBytes < N/PR_BITS_PER_BYTE \|\| !pParams \|\| !pVfy) {

1256 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1257 return SECFailure;

1258 }

1259 /* Initialize an arena for the params. */

1260 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);

1261 if (!arena) {

1262 PORT_SetError(SEC_ERROR_NO_MEMORY);

1263 return SECFailure;

1264 }

1265 params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams));

1266 if (!params) {

1267 PORT_SetError(SEC_ERROR_NO_MEMORY);

1268 PORT_FreeArena(arena, PR_TRUE);

1269 return SECFailure;

1270 }

1271 params->arena = arena;

1272 /* Initialize an arena for the verify. */

1273 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);

1274 if (!arena) {

1275 PORT_SetError(SEC_ERROR_NO_MEMORY);

1276 PORT_FreeArena(params->arena, PR_TRUE);

1277 return SECFailure;

1278 }

1279 verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify));

1280 if (!verify) {

1281 PORT_SetError(SEC_ERROR_NO_MEMORY);

1282 PORT_FreeArena(arena, PR_TRUE);

1283 PORT_FreeArena(params->arena, PR_TRUE);

1284 return SECFailure;

1285 }

1286 verify->arena = arena;

1287 seed = &verify->seed;

1288 arena = NULL;

1289 /* Initialize bignums */

1290 MP_DIGITS(&P) = 0;

1291 MP_DIGITS(&Q) = 0;

1292 MP_DIGITS(&G) = 0;

1293 MP_DIGITS(&H) = 0;

1294 MP_DIGITS(&l) = 0;

1295 MP_DIGITS(&p0) = 0;

1296 CHECK_MPI_OK( mp_init(&P) );

1297 CHECK_MPI_OK( mp_init(&Q) );

1298 CHECK_MPI_OK( mp_init(&G) );

1299 CHECK_MPI_OK( mp_init(&H) );

1300 CHECK_MPI_OK( mp_init(&l) );

1301 CHECK_MPI_OK( mp_init(&p0) );

1302

1303 /* Select Hash and Compute lengths. */

1304 /* getFirstHash gives us the smallest acceptable hash for this key

1305 * strength */

1306 hashtype = getFirstHash(L,N);

1307 outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE;

1308

1309 /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */

1310 n = (L - 1) / outlen;

1311 /* Step 4: (skipped since we don't use b): b = L -1 - (noutlen); /

1312 seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */

1313 step_5:

1314 /* ******************************************************************

1315 ** Step 5. (Step 1 in 186-1)

1316 ** "Choose an abitrary sequence of at least N bits and call it SEED.

1317 ** Let g be the length of SEED in bits."

1318 */

1319 if (++iterations > MAX_ITERATIONS) { /* give up after a while */

1320 PORT_SetError(SEC_ERROR_NEED_RANDOM);

1321 goto cleanup;

1322 }

1323 seed->len = seedBytes;

1324 CHECK_SEC_OK( getPQseed(seed, verify->arena) );

1325 /* ******************************************************************

1326 ** Step 6. (Step 2 in 186-1)

1327 **

1328 "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2g]. (186-1)"

1329 "Compute U = HASH[SEED] 2(N-1). (186-3)"

1330 **

1331 ** Step 7. (Step 3 in 186-1)

1332 "Form Q from U by setting the most signficant bit (the 2159 bit)

1333 ** and the least signficant bit to 1. In terms of boolean operations,

1334 Q = U OR 2159 OR 1. Note that 2159 < Q < 2160. (186-1)"

1335 **

1336 "q = 2(N-1) + U + 1 - (U mod 2) (186-3)

1337 **

1338 Note: Both formulations are the same for U < 2(N-1) and N=160

1339 **

1340 ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block

1341 ** FIPS186_3_ST_TYPE.

1342 */

1343 if (type == FIPS186_1_TYPE) {

1344 CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) );

1345 } else if (type == FIPS186_3_TYPE) {

1346 CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) );

1347 } else {

1348 /* FIPS186_3_ST_TYPE */

1349 unsigned int qgen_counter, pgen_counter;

1350

1351 /* Step 1 (L,N) already checked for acceptability */

1352

1353 firstseed = *seed;

1354 qgen_counter = 0;

1355 /* Step 2. Use N and firstseed to generate random prime q

1356 * using Apendix C.6 */

1357 CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q,

1358 &qseed, &qgen_counter) );

1359 /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0

1360 * using Appendix C.6 */

1361 pgen_counter = 0;

1362 CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1,

1363 &qseed, &p0, &pseed, &pgen_counter) );

1364 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */

1365 CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L,

1366 &p0, &Q, &P, &pseed, &pgen_counter) );

1367

1368 /* combine all the seeds */

1369 seed->len = firstseed.len +qseed.len + pseed.len;

1370 seed->data = PORT_ArenaZAlloc(verify->arena, seed->len);

1371 if (seed->data == NULL) {

1372 goto cleanup;

1373 }

1374 PORT_Memcpy(seed->data, firstseed.data, firstseed.len);

1375 PORT_Memcpy(seed->data+firstseed.len, pseed.data, pseed.len);

1376 PORT_Memcpy(seed->data+firstseed.len+pseed.len, qseed.data, qseed.len);

1377 counter = 0 ; /* (qgen_counter << 16) \| pgen_counter; */

1378

1379 /* we've generated both P and Q now, skip to generating G */

1380 goto generate_G;

1381 }

1382 /* ******************************************************************

1383 ** Step 8. (Step 4 in 186-1)

1384 ** "Use a robust primality testing algorithm to test whether q is prime."

1385 **

1386 ** Appendix 2.1 states that a Rabin test with at least 50 iterations

1387 ** "will give an acceptable probability of error."

1388 */

1389 /CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );/

1390 err = mpp_pprime(&Q, prime_testcount_q(L,N));

1391 passed = (err == MP_YES) ? SECSuccess : SECFailure;

1392 /* ******************************************************************

1393 ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)."

1394 */

1395 if (passed != SECSuccess)

1396 goto step_5;

1397 /* ******************************************************************

1398 ** Step 10.

1399 ** offset = 1;

1400 **( Step 6b 186-1)"Let counter = 0 and offset = 2."

1401 */

1402 offset = (type == FIPS186_1_TYPE) ? 2 : 1;

1403 /*

1404 ** Step 11. (Step 6a,13a,14 in 186-1)

1405 ** For counter - 0 to (4L-1) do

1406 **

1407 */

1408 maxCount = L >= 1024 ? (4*L - 1) : 4095;

1409 for (counter = 0; counter <= maxCount; counter++) {

1410 /* ******************************************************************

1411 ** Step 11.1 (Step 7 in 186-1)

1412 ** "for j = 0 ... n let

1413 V_j = HASH[(SEED + offset + j) mod 2seedlen]."

1414 **

1415 ** Step 11.2 (Step 8 in 186-1)

1416 ** "W = V_0 + V_12outlen+...+ V_n-1 2*((n-1)outlen) +

1417 ** ((Vn* mod 2*b)2*(noutlen))"

1418 ** Step 11.3 (Step 8 in 186-1)

1419 "X = W + 2(L-1)

1420 Note that 0 <= W < 2(L-1) and hence 2(L-1) <= X < 2L."

1421 **

1422 ** Step 11.4 (Step 9 in 186-1).

1423 ** "c = X mod 2q"

1424 **

1425 ** Step 11.5 (Step 9 in 186-1).

1426 ** " p = X - (c - 1).

1427 ** Note that p is congruent to 1 mod 2q."

1428 */

1429 CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, seedlen,

1430 seed, &Q, &P) );

1431 /*************************************************************

1432 ** Step 11.6. (Step 10 in 186-1)

1433 "if p < 2(L-1), then goto step 11.9. (step 13 in 186-1)"

1434 */

1435 CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2*(L-1) /

1436 if (mp_cmp(&P, &l) < 0)

1437 goto step_11_9;

1438 /************************************************************

1439 ** Step 11.7 (step 11 in 186-1)

1440 ** "Perform a robust primality test on p."

1441 */

1442 /CHECK_SEC_OK( prm_RabinTest(&P, &passed) );/

1443 err = mpp_pprime(&P, prime_testcount_p(L, N));

1444 passed = (err == MP_YES) ? SECSuccess : SECFailure;

1445 /* ******************************************************************

1446 ** Step 11.8. "If p is determined to be primed return VALID

1447 ** values of p, q, seed and counter."

1448 */

1449 if (passed == SECSuccess)

1450 break;

1451 step_11_9:

1452 /* ******************************************************************

1453 ** Step 11.9. "offset = offset + n + 1."

1454 */

1455 offset += n + 1;

1456 }

1457 /* ******************************************************************

1458 ** Step 12. "goto step 5."

1459 **

1460 ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8

1461 ** and now need to return p,q, seed, and counter.

1462 */

1463 if (counter > maxCount)

1464 goto step_5;

1465

1466 generate_G:

1467 /* ******************************************************************

1468 ** returning p, q, seed and counter

1469 */

1470 if (type == FIPS186_1_TYPE) {

1471 /* Generate g, This is called the "Unverifiable Generation of g

1472 * in FIPA186-3 Appedix A.2.1. For compatibility we maintain

1473 * this version of the code */

1474 SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */

1475 if (!hit.data) goto cleanup;

1476 do {

1477 /* loop generate h until 1<h<p-1 and (h*[(p-1)/q])mod p > 1 /

1478 CHECK_SEC_OK( generate_h_candidate(&hit, &H) );

1479 CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );

1480 } while (passed != PR_TRUE);

1481 MPINT_TO_SECITEM(&H, &verify->h, verify->arena);

1482 } else {

1483 unsigned char index = 1; /* default to 1 */

1484 verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1);

1485 if (verify->h.data == NULL) { goto cleanup; }

1486 verify->h.len = 1;

1487 verify->h.data[0] = index;

1488 /* Generate g, using the FIPS 186-3 Appendix A.23 */

1489 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G) );

1490 }

1491 /* All generation is done. Now, save the PQG params. */

1492 MPINT_TO_SECITEM(&P, &params->prime, params->arena);

1493 MPINT_TO_SECITEM(&Q, &params->subPrime, params->arena);

1494 MPINT_TO_SECITEM(&G, &params->base, params->arena);

1495 verify->counter = counter;

1496 *pParams = params;

1497 *pVfy = verify;

1498 cleanup:

1499 if (pseed.data) {

1500 PORT_Free(pseed.data);

1501 }

1502 if (qseed.data) {

1503 PORT_Free(qseed.data);

1504 }

1505 mp_clear(&P);

1506 mp_clear(&Q);

1507 mp_clear(&G);

1508 mp_clear(&H);

1509 mp_clear(&l);

1510 mp_clear(&p0);

1511 if (err) {

1512 MP_TO_SEC_ERROR(err);

1513 rv = SECFailure;

1514 }

1515 if (rv) {

1516 PORT_FreeArena(params->arena, PR_TRUE);

1517 PORT_FreeArena(verify->arena, PR_TRUE);

1518 }

1519 if (hit.data) {

1520 SECITEM_FreeItem(&hit, PR_FALSE);

1521 }

1522 return rv;

1523 }

1524

1525 SECStatus

1526 PQG_ParamGen(unsigned int j, PQGParams pParams, PQGVerify pVfy)

1527 {

1528 unsigned int L; /* Length of P in bits. Per FIPS 186. */

1529 unsigned int seedBytes;

1530

1531 if (j > 8 \|\| !pParams \|\| !pVfy) {

1532 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1533 return SECFailure;

1534 }

1535 L = 512 + (j * 64); /* bits in P */

1536 seedBytes = L/8;

1537 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,

1538 pParams, pVfy);

1539 }

1540

1541 SECStatus

1542 PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,

1543 PQGParams pParams, PQGVerify pVfy)

1544 {

1545 unsigned int L; /* Length of P in bits. Per FIPS 186. */

1546

1547 if (j > 8 \|\| !pParams \|\| !pVfy) {

1548 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1549 return SECFailure;

1550 }

1551 L = 512 + (j * 64); /* bits in P */

1552 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,

1553 pParams, pVfy);

1554 }

1555

1556 SECStatus

1557 PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes,

1558 PQGParams pParams, PQGVerify pVfy)

1559 {

1560 if (N == 0) {

1561 N = pqg_get_default_N(L);

1562 }

1563 if (seedBytes == 0) {

1564 /* seedBytes == L/8 for probable primes, N/8 for Shawe-Taylor Primes */

1565 seedBytes = N/8;

1566 }

1567 if (pqg_validate_dsa2(L,N) != SECSuccess) {

1568 /* error code already set */

1569 return SECFailure;

1570 }

1571 return pqg_ParamGen(L, N, FIPS186_3_ST_TYPE, seedBytes, pParams, pVfy);

1572 }

1573

1574

1575 /*

1576 * verify can use vfy structures returned from either FIPS186-1 or

1577 * FIPS186-2, and can handle differences in selected Hash functions to

1578 * generate the parameters.

1579 */

1580 SECStatus

1581 PQG_VerifyParams(const PQGParams *params,

1582 const PQGVerify vfy, SECStatus result)

1583 {

1584 SECStatus rv = SECSuccess;

1585 unsigned int g, n, L, N, offset, outlen;

1586 mp_int p0, P, Q, G, P_, Q_, G_, r, h;

1587 mp_err err = MP_OKAY;

1588 int j;

1589 unsigned int counter_max = 0; /* handle legacy L < 1024 */

1590 unsigned int qseed_len;

1591 SECItem pseed_ = {0, 0, 0};

1592 HASH_HashType hashtype;

1593 pqgGenType type;

1594

1595 #define CHECKPARAM(cond) \

1596 if (!(cond)) { \

1597 *result = SECFailure; \

1598 goto cleanup; \

1599 }

1600 if (!params \|\| !vfy \|\| !result) {

1601 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1602 return SECFailure;

1603 }

1604 /* always need at least p, q, and seed for any meaningful check */

1605 if ((params->prime.len == 0) \|\| (params->subPrime.len == 0) \|\|

1606 (vfy->seed.len == 0)) {

1607 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1608 return SECFailure;

1609 }

1610 /* we want to either check PQ or G or both. If we don't have G, make

1611 * sure we have count so we can check P. */

1612 if ((params->base.len == 0) && (vfy->counter == -1)) {

1613 PORT_SetError(SEC_ERROR_INVALID_ARGS);

1614 return SECFailure;

1615 }

1616

1617 MP_DIGITS(&p0) = 0;

1618 MP_DIGITS(&P) = 0;

1619 MP_DIGITS(&Q) = 0;

1620 MP_DIGITS(&G) = 0;

1621 MP_DIGITS(&P_) = 0;

1622 MP_DIGITS(&Q_) = 0;

1623 MP_DIGITS(&G_) = 0;

1624 MP_DIGITS(&r) = 0;

1625 MP_DIGITS(&h) = 0;

1626 CHECK_MPI_OK( mp_init(&p0) );

1627 CHECK_MPI_OK( mp_init(&P) );

1628 CHECK_MPI_OK( mp_init(&Q) );

1629 CHECK_MPI_OK( mp_init(&G) );

1630 CHECK_MPI_OK( mp_init(&P_) );

1631 CHECK_MPI_OK( mp_init(&Q_) );

1632 CHECK_MPI_OK( mp_init(&G_) );

1633 CHECK_MPI_OK( mp_init(&r) );

1634 CHECK_MPI_OK( mp_init(&h) );

1635 *result = SECSuccess;

1636 SECITEM_TO_MPINT(params->prime, &P);

1637 SECITEM_TO_MPINT(params->subPrime, &Q);

1638 /* if G isn't specified, just check P and Q */

1639 if (params->base.len != 0) {

1640 SECITEM_TO_MPINT(params->base, &G);

1641 }

1642 /* 1. Check (L,N) pair */

1643 N = mpl_significant_bits(&Q);

1644 L = mpl_significant_bits(&P);

1645 if (L < 1024) {

1646 /* handle DSA1 pqg parameters with less thatn 1024 bits*/

1647 CHECKPARAM( N == DSA1_Q_BITS );

1648 j = PQG_PBITS_TO_INDEX(L);

1649 CHECKPARAM( j >= 0 && j <= 8 );

1650 counter_max = 4096;

1651 } else {

1652 /* handle DSA2 parameters (includes DSA1, 1024 bits) */

1653 CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess);

1654 counter_max = 4*L;

1655 }

1656 /* 3. G < P */

1657 if (params->base.len != 0) {

1658 CHECKPARAM( mp_cmp(&G, &P) < 0 );

1659 }

1660 /* 4. P % Q == 1 */

1661 CHECK_MPI_OK( mp_mod(&P, &Q, &r) );

1662 CHECKPARAM( mp_cmp_d(&r, 1) == 0 );

1663 /* 5. Q is prime */

1664 CHECKPARAM( mpp_pprime(&Q, prime_testcount_q(L,N)) == MP_YES );

1665 /* 6. P is prime */

1666 CHECKPARAM( mpp_pprime(&P, prime_testcount_p(L,N)) == MP_YES );

1667 /* Steps 7-12 are done only if the optional PQGVerify is supplied. */

1668 /* continue processing P */

1669 /* 7. counter < 4L /

1670 CHECKPARAM( (vfy->counter == -1) \|\| (vfy->counter < counter_max) );

1671 /* 8. g >= N and g < 2L (g is length of seed in bits) /

1672 g = vfy->seed.len * 8;

1673 CHECKPARAM( g >= N && g < counter_max/2 );

1674 /* 9. Q generated from SEED matches Q in PQGParams. */

1675 /* This function checks all possible hash and generation types to

1676 * find a Q_ which matches Q. */

1677 CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len,

1678 &hashtype, &type) == SECSuccess );

1679 CHECKPARAM( mp_cmp(&Q, &Q_) == 0 );

1680 if (type == FIPS186_3_ST_TYPE) {

1681 SECItem qseed = { 0, 0, 0 };

1682 SECItem pseed = { 0, 0, 0 };

1683 unsigned int first_seed_len;

1684 unsigned int pgen_counter = 0;

1685

1686 /* extract pseed and qseed from domain_parameter_seed, which is

1687 * first_seed \|\| pseed \|\| qseed. qseed is first_seed + small_integer

1688 * pseed is qseed + small_integer. This means most of the time

1689 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or

1690 * pseed.len will be one greater than first_seed.len, so we can

1691 * depend on the fact that

1692 * first_seed.len = floor(domain_parameter_seed.len/3).

1693 * findQfromSeed returned qseed.len, so we can calculate pseed.len as

1694 * pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len

1695 * this is probably over kill, since 99.999% of the time they will all

1696 * be equal.

1697 *

1698 * With the lengths, we can now find the offsets;

1699 * first_seed.data = domain_parameter_seed.data + 0

1700 * pseed.data = domain_parameter_seed.data + first_seed.len

1701 * qseed.data = domain_parameter_seed.data

1702 * + domain_paramter_seed.len - qseed.len

1703 *

1704 */

1705 first_seed_len = vfy->seed.len/3;

1706 CHECKPARAM(qseed_len < vfy->seed.len);

1707 CHECKPARAM(first_seed_len*8 > N-1);

1708 CHECKPARAM(first_seed_len+qseed_len < vfy->seed.len);

1709 qseed.len = qseed_len;

1710 qseed.data = vfy->seed.data + vfy->seed.len - qseed.len;

1711 pseed.len = vfy->seed.len - (first_seed_len+qseed_len);

1712 pseed.data = vfy->seed.data + first_seed_len;

1713

1714 /*

1715 * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed

1716 * above in our initial checks, Step 2 was completed by

1717 * findQfromSeed */

1718

1719 /* Step 3 (status, c0, prime_seed, prime_gen_counter) =

1720 ** (ST_Random_Prime((ceil(length/2)+1, input_seed)

1721 */

1722 CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1,

1723 &qseed, &p0, &pseed_, &pgen_counter) );

1724 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */

1725 CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L,

1726 &p0, &Q_, &P_, &pseed_, &pgen_counter) );

1727 CHECKPARAM( mp_cmp(&P, &P_) == 0 );

1728 /* make sure pseed wasn't tampered with (since it is part of

1729 * calculating G) */

1730 CHECKPARAM( SECITEM_CompareItem(&pseed, &pseed_) == SECEqual );

1731 } else if (vfy->counter == -1) {

1732 /* If counter is set to -1, we are really only verifying G, skip

1733 * the remainder of the checks for P */

1734 CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */

1735 } else {

1736 /* 10. P generated from (L, counter, g, SEED, Q) matches P

1737 * in PQGParams. */

1738 outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE;

1739 n = (L - 1) / outlen;

1740 offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1);

1741 CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed,

1742 &Q, &P_) );

1743 CHECKPARAM( mp_cmp(&P, &P_) == 0 );

1744 }

1745

1746 /* now check G, skip if don't have a g */

1747 if (params->base.len == 0) goto cleanup;

1748

1749 /* first Always check that G is OK FIPS186-3 A.2.2 & A.2.4*/

1750 /* 1. 2 < G < P-1 */

1751 /* P is prime, p-1 == zero 1st bit */

1752 CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );

1753 CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0 );

1754 CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */

1755 /* 2. verify g*q mod p == 1 /

1756 CHECK_MPI_OK( mp_exptmod(&G, &Q, &P, &h) ); /* h = G ** Q mod P */

1757 CHECKPARAM(mp_cmp_d(&h, 1) == 0);

1758

1759 /* no h, the above is the best we can do */

1760 if (vfy->h.len == 0) {

1761 if (type != FIPS186_1_TYPE) {

1762 *result = SECWouldBlock;

1763 }

1764 goto cleanup;

1765 }

1766

1767 /*

1768 * If h is one byte and FIPS186-3 was used to generate Q (we've verified

1769 * Q was generated from seed already, then we assume that FIPS 186-3

1770 * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was

1771 * used to generate G.

1772 */

1773 if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) {

1774 /* A.2.3 */

1775 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed,

1776 vfy->h.data[0], &G_) );

1777 CHECKPARAM( mp_cmp(&G, &G_) == 0 );

1778 } else {

1779 int passed;

1780 /* A.2.1 */

1781 SECITEM_TO_MPINT(vfy->h, &h);

1782 /* 11. 1 < h < P-1 */

1783 /* P is prime, p-1 == zero 1st bit */

1784 CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );

1785 CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) );

1786 CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */

1787 /* 12. G generated from h matches G in PQGParams. */

1788 CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );

1789 CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );

1790 }

1791 cleanup:

1792 mp_clear(&p0);

1793 mp_clear(&P);

1794 mp_clear(&Q);

1795 mp_clear(&G);

1796 mp_clear(&P_);

1797 mp_clear(&Q_);

1798 mp_clear(&G_);

1799 mp_clear(&r);

1800 mp_clear(&h);

1801 if (pseed_.data) {

1802 SECITEM_FreeItem(&pseed_,PR_FALSE);

1803 }

1804 if (err) {

1805 MP_TO_SEC_ERROR(err);

1806 rv = SECFailure;

1807 }

1808 return rv;

1809 }

1810

1811 /**************************************************************************

1812 * Free the PQGParams struct and the things it points to. *

1813 **************************************************************************/

1814 void

1815 PQG_DestroyParams(PQGParams *params)

1816 {

1817 if (params == NULL)

1818 return;

1819 if (params->arena != NULL) {

1820 PORT_FreeArena(params->arena, PR_FALSE); /* don't zero it */

1821 } else {

1822 SECITEM_FreeItem(&params->prime, PR_FALSE); /* don't free prime */

1823 SECITEM_FreeItem(&params->subPrime, PR_FALSE); /* don't free subPrime */

1824 SECITEM_FreeItem(&params->base, PR_FALSE); /* don't free base */

1825 PORT_Free(params);

1826 }

1827 }

1828

1829 /**************************************************************************

1830 * Free the PQGVerify struct and the things it points to. *

1831 **************************************************************************/

1832

1833 void

1834 PQG_DestroyVerify(PQGVerify *vfy)

1835 {

1836 if (vfy == NULL)

1837 return;

1838 if (vfy->arena != NULL) {

1839 PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */

1840 } else {

1841 SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */

1842 SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */

1843 PORT_Free(vfy);

1844 }

1845 }

OLD	NEW

« no previous file with comments | « nss/lib/freebl/pqg.h ('k') | nss/lib/freebl/rawhash.c » ('j') | no next file with comments »