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
prime_testcount_p(int L,int N)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
prime_testcount_q(int L,int N)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
pqg_validate_dsa2(unsigned int L,unsigned int N)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
pqg_get_default_N(unsigned int L)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
getFirstHash(unsigned int L,unsigned int N)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
getNextHash(HASH_HashType 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
HASH_ResultLen(HASH_HashType type)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 static SECStatus
HASH_HashBuf(HASH_HashType type,unsigned char * dest,const unsigned char * src,PRUint32 src_len)190 HASH_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
PQG_GetLength(const SECItem * obj)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
PQG_Check(const PQGParams * params)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
PQG_GetHashType(const PQGParams * params)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
getPQseed(SECItem * seed,PLArenaPool * arena)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
generate_h_candidate(SECItem * hit,mp_int * H)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
addToSeed(const SECItem * seed,unsigned long addend,int seedlen,SECItem * seedout)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 (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
addToSeedThenHash(HASH_HashType hashtype,const SECItem * seed,unsigned long addend,int seedlen,unsigned char * hashOutBuf)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 = HASH_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
makeQfromSeed(unsigned int g,const SECItem * seed,mp_int * Q)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
makeQ2fromSeed(HASH_HashType hashtype,unsigned int N,const SECItem * seed,mp_int * Q)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(HASH_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
makePrimefromPrimesShaweTaylor(HASH_HashType hashtype,unsigned int length,unsigned int seedlen,mp_int * c0,mp_int * q,mp_int * prime,SECItem * prime_seed,unsigned int * prime_gen_counter)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_Memset(x, 0, 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_FreeItem(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
makePrimefromSeedShaweTaylor(HASH_HashType hashtype,unsigned int length,const SECItem * input_seed,mp_int * prime,SECItem * prime_seed,unsigned int * prime_gen_counter)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(HASH_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_Memset(x, 0, 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_FreeItem(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
findQfromSeed(unsigned int L,unsigned int N,unsigned int g,const SECItem * seed,mp_int * Q,mp_int * Q_,unsigned int * qseed_len,HASH_HashType * hashtypePtr,pqgGenType * typePtr,unsigned int * qgen_counter)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 return SECFailure;
909 }
910 /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try
911 * them both */
912 if (L == 1024) {
913 rv = makeQfromSeed(g, seed, Q_);
914 if (rv == SECSuccess) {
915 if (mp_cmp(Q, Q_) == 0) {
916 *hashtypePtr = HASH_AlgSHA1;
917 *typePtr = FIPS186_1_TYPE;
918 return SECSuccess;
919 }
920 }
921 /* fall through for FIPS186_3 types */
922 }
923 /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3
924 * with appropriate hash types */
925 for (hashtype = getFirstHash(L, N); hashtype != HASH_AlgTOTAL;
926 hashtype = getNextHash(hashtype)) {
927 rv = makeQ2fromSeed(hashtype, N, seed, Q_);
928 if (rv != SECSuccess) {
929 continue;
930 }
931 if (mp_cmp(Q, Q_) == 0) {
932 *hashtypePtr = hashtype;
933 *typePtr = FIPS186_3_TYPE;
934 return SECSuccess;
935 }
936 }
937 /*
938 * OK finally try FIPS186_3 Shawe-Taylor
939 */
940 firstseed = *seed;
941 firstseed.len = seed->len / 3;
942 for (hashtype = getFirstHash(L, N); hashtype != HASH_AlgTOTAL;
943 hashtype = getNextHash(hashtype)) {
944 unsigned int count;
945
946 rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_,
947 &qseed, &count);
948 if (rv != SECSuccess) {
949 continue;
950 }
951 if (mp_cmp(Q, Q_) == 0) {
952 /* check qseed as well... */
953 int offset = seed->len - qseed.len;
954 if ((offset < 0) ||
955 (PORT_Memcmp(&seed->data[offset], qseed.data, qseed.len) != 0)) {
956 /* we found q, but the seeds don't match. This isn't an
957 * accident, someone has been tweeking with the seeds, just
958 * fail a this point. */
959 SECITEM_FreeItem(&qseed, PR_FALSE);
960 return SECFailure;
961 }
962 *qseed_len = qseed.len;
963 *hashtypePtr = hashtype;
964 *typePtr = FIPS186_3_ST_TYPE;
965 *qgen_counter = count;
966 SECITEM_FreeItem(&qseed, PR_FALSE);
967 return SECSuccess;
968 }
969 SECITEM_FreeItem(&qseed, PR_FALSE);
970 }
971 /* no hash algorithms found which match seed to Q, fail */
972 return SECFailure;
973 }
974
975 /*
976 ** Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
977 ** which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2
978 ** Generate P from Q, seed, L, and offset.
979 */
980 static SECStatus
makePfromQandSeed(HASH_HashType hashtype,unsigned int L,unsigned int N,unsigned int offset,unsigned int seedlen,const SECItem * seed,const mp_int * Q,mp_int * P)981 makePfromQandSeed(
982 HASH_HashType hashtype, /* selected Hashing algorithm */
983 unsigned int L, /* Length of P in bits. Per FIPS 186. */
984 unsigned int N, /* Length of Q in bits. Per FIPS 186. */
985 unsigned int offset, /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */
986 unsigned int seedlen, /* input. Length of seed in bits. (g in 186-1)*/
987 const SECItem *seed, /* input. */
988 const mp_int *Q, /* input. */
989 mp_int *P) /* output. */
990 {
991 unsigned int j; /* Per FIPS 186-3 App. A.1.1.2 (k in 186-1)*/
992 unsigned int n; /* Per FIPS 186, appendix 2.2. */
993 mp_digit b; /* Per FIPS 186, appendix 2.2. */
994 unsigned int outlen; /* Per FIPS 186-3 App. A.1.1.2 */
995 unsigned int hashlen; /* outlen in bytes */
996 unsigned char V_j[HASH_LENGTH_MAX];
997 mp_int W, X, c, twoQ, V_n, tmp;
998 mp_err err = MP_OKAY;
999 SECStatus rv = SECSuccess;
1000 /* Initialize bignums */
1001 MP_DIGITS(&W) = 0;
1002 MP_DIGITS(&X) = 0;
1003 MP_DIGITS(&c) = 0;
1004 MP_DIGITS(&twoQ) = 0;
1005 MP_DIGITS(&V_n) = 0;
1006 MP_DIGITS(&tmp) = 0;
1007 CHECK_MPI_OK(mp_init(&W));
1008 CHECK_MPI_OK(mp_init(&X));
1009 CHECK_MPI_OK(mp_init(&c));
1010 CHECK_MPI_OK(mp_init(&twoQ));
1011 CHECK_MPI_OK(mp_init(&tmp));
1012 CHECK_MPI_OK(mp_init(&V_n));
1013
1014 hashlen = HASH_ResultLen(hashtype);
1015 outlen = hashlen * PR_BITS_PER_BYTE;
1016
1017 PORT_Assert(outlen > 0);
1018
1019 /* L - 1 = n*outlen + b */
1020 n = (L - 1) / outlen;
1021 b = (L - 1) % outlen;
1022
1023 /* ******************************************************************
1024 ** Step 11.1 (Step 7 in 186-1)
1025 ** "for j = 0 ... n let
1026 ** V_j = SHA[(SEED + offset + j) mod 2**seedlen]."
1027 **
1028 ** Step 11.2 (Step 8 in 186-1)
1029 ** "W = V_0 + (V_1 * 2**outlen) + ... + (V_n-1 * 2**((n-1)*outlen))
1030 ** + ((V_n mod 2**b) * 2**(n*outlen))
1031 */
1032 for (j = 0; j < n; ++j) { /* Do the first n terms of V_j */
1033 /* Do step 11.1 for iteration j.
1034 ** V_j = HASH[(seed + offset + j) mod 2**g]
1035 */
1036 CHECK_SEC_OK(addToSeedThenHash(hashtype, seed, offset + j, seedlen, V_j));
1037 /* Do step 11.2 for iteration j.
1038 ** W += V_j * 2**(j*outlen)
1039 */
1040 OCTETS_TO_MPINT(V_j, &tmp, hashlen); /* get bignum V_j */
1041 CHECK_MPI_OK(mpl_lsh(&tmp, &tmp, j * outlen)); /* tmp=V_j << j*outlen */
1042 CHECK_MPI_OK(mp_add(&W, &tmp, &W)); /* W += tmp */
1043 }
1044 /* Step 11.2, continued.
1045 ** [W += ((V_n mod 2**b) * 2**(n*outlen))]
1046 */
1047 CHECK_SEC_OK(addToSeedThenHash(hashtype, seed, offset + n, seedlen, V_j));
1048 OCTETS_TO_MPINT(V_j, &V_n, hashlen); /* get bignum V_n */
1049 CHECK_MPI_OK(mp_div_2d(&V_n, b, NULL, &tmp)); /* tmp = V_n mod 2**b */
1050 CHECK_MPI_OK(mpl_lsh(&tmp, &tmp, n * outlen)); /* tmp = tmp << n*outlen */
1051 CHECK_MPI_OK(mp_add(&W, &tmp, &W)); /* W += tmp */
1052 /* Step 11.3, (Step 8 in 186-1)
1053 ** "X = W + 2**(L-1).
1054 ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
1055 */
1056 CHECK_MPI_OK(mpl_set_bit(&X, (mp_size)(L - 1), 1)); /* X = 2**(L-1) */
1057 CHECK_MPI_OK(mp_add(&X, &W, &X)); /* X += W */
1058 /*************************************************************
1059 ** Step 11.4. (Step 9 in 186-1)
1060 ** "c = X mod 2q"
1061 */
1062 CHECK_MPI_OK(mp_mul_2(Q, &twoQ)); /* 2q */
1063 CHECK_MPI_OK(mp_mod(&X, &twoQ, &c)); /* c = X mod 2q */
1064 /*************************************************************
1065 ** Step 11.5. (Step 9 in 186-1)
1066 ** "p = X - (c - 1).
1067 ** Note that p is congruent to 1 mod 2q."
1068 */
1069 CHECK_MPI_OK(mp_sub_d(&c, 1, &c)); /* c -= 1 */
1070 CHECK_MPI_OK(mp_sub(&X, &c, P)); /* P = X - c */
1071 cleanup:
1072 mp_clear(&W);
1073 mp_clear(&X);
1074 mp_clear(&c);
1075 mp_clear(&twoQ);
1076 mp_clear(&V_n);
1077 mp_clear(&tmp);
1078 if (err) {
1079 MP_TO_SEC_ERROR(err);
1080 return SECFailure;
1081 }
1082 return rv;
1083 }
1084
1085 /*
1086 ** Generate G from h, P, and Q.
1087 */
1088 static SECStatus
makeGfromH(const mp_int * P,const mp_int * Q,mp_int * H,mp_int * G,PRBool * passed)1089 makeGfromH(const mp_int *P, /* input. */
1090 const mp_int *Q, /* input. */
1091 mp_int *H, /* input and output. */
1092 mp_int *G, /* output. */
1093 PRBool *passed)
1094 {
1095 mp_int exp, pm1;
1096 mp_err err = MP_OKAY;
1097 SECStatus rv = SECSuccess;
1098 *passed = PR_FALSE;
1099 MP_DIGITS(&exp) = 0;
1100 MP_DIGITS(&pm1) = 0;
1101 CHECK_MPI_OK(mp_init(&exp));
1102 CHECK_MPI_OK(mp_init(&pm1));
1103 CHECK_MPI_OK(mp_sub_d(P, 1, &pm1)); /* P - 1 */
1104 if (mp_cmp(H, &pm1) >= 0) /* H >= P-1 */
1105 CHECK_MPI_OK(mp_sub(H, &pm1, H)); /* H = H mod (P-1) */
1106 /* Let b = 2**n (smallest power of 2 greater than P).
1107 ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1
1108 ** so the above operation safely computes H mod (P-1)
1109 */
1110 /* Check for H = to 0 or 1. Regen H if so. (Regen means return error). */
1111 if (mp_cmp_d(H, 1) <= 0) {
1112 rv = SECFailure;
1113 goto cleanup;
1114 }
1115 /* Compute G, according to the equation G = (H ** ((P-1)/Q)) mod P */
1116 CHECK_MPI_OK(mp_div(&pm1, Q, &exp, NULL)); /* exp = (P-1)/Q */
1117 CHECK_MPI_OK(mp_exptmod(H, &exp, P, G)); /* G = H ** exp mod P */
1118 /* Check for G == 0 or G == 1, return error if so. */
1119 if (mp_cmp_d(G, 1) <= 0) {
1120 rv = SECFailure;
1121 goto cleanup;
1122 }
1123 *passed = PR_TRUE;
1124 cleanup:
1125 mp_clear(&exp);
1126 mp_clear(&pm1);
1127 if (err) {
1128 MP_TO_SEC_ERROR(err);
1129 rv = SECFailure;
1130 }
1131 return rv;
1132 }
1133
1134 /*
1135 ** Generate G from seed, index, P, and Q.
1136 */
1137 static SECStatus
makeGfromIndex(HASH_HashType hashtype,const mp_int * P,const mp_int * Q,const SECItem * seed,unsigned char index,mp_int * G)1138 makeGfromIndex(HASH_HashType hashtype,
1139 const mp_int *P, /* input. */
1140 const mp_int *Q, /* input. */
1141 const SECItem *seed, /* input. */
1142 unsigned char index, /* input. */
1143 mp_int *G) /* input/output */
1144 {
1145 mp_int e, pm1, W;
1146 unsigned int count;
1147 unsigned char data[HASH_LENGTH_MAX];
1148 unsigned int len;
1149 mp_err err = MP_OKAY;
1150 SECStatus rv = SECSuccess;
1151 const SECHashObject *hashobj = NULL;
1152 void *hashcx = NULL;
1153
1154 MP_DIGITS(&e) = 0;
1155 MP_DIGITS(&pm1) = 0;
1156 MP_DIGITS(&W) = 0;
1157 CHECK_MPI_OK(mp_init(&e));
1158 CHECK_MPI_OK(mp_init(&pm1));
1159 CHECK_MPI_OK(mp_init(&W));
1160
1161 /* initialize our hash stuff */
1162 hashobj = HASH_GetRawHashObject(hashtype);
1163 if (hashobj == NULL) {
1164 /* shouldn't happen */
1165 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1166 rv = SECFailure;
1167 goto cleanup;
1168 }
1169 hashcx = hashobj->create();
1170 if (hashcx == NULL) {
1171 rv = SECFailure;
1172 goto cleanup;
1173 }
1174
1175 CHECK_MPI_OK(mp_sub_d(P, 1, &pm1)); /* P - 1 */
1176 /* Step 3 e = (p-1)/q */
1177 CHECK_MPI_OK(mp_div(&pm1, Q, &e, NULL)); /* e = (P-1)/Q */
1178 /* Steps 4, 5, and 6 */
1179 /* count is a 16 bit value in the spec. We actually represent count
1180 * as more than 16 bits so we can easily detect the 16 bit overflow */
1181 #define MAX_COUNT 0x10000
1182 for (count = 1; count < MAX_COUNT; count++) {
1183 /* step 7
1184 * U = domain_param_seed || "ggen" || index || count
1185 * step 8
1186 * W = HASH(U)
1187 */
1188 hashobj->begin(hashcx);
1189 hashobj->update(hashcx, seed->data, seed->len);
1190 hashobj->update(hashcx, (unsigned char *)"ggen", 4);
1191 hashobj->update(hashcx, &index, 1);
1192 data[0] = (count >> 8) & 0xff;
1193 data[1] = count & 0xff;
1194 hashobj->update(hashcx, data, 2);
1195 hashobj->end(hashcx, data, &len, sizeof(data));
1196 OCTETS_TO_MPINT(data, &W, len);
1197 /* step 9. g = W**e mod p */
1198 CHECK_MPI_OK(mp_exptmod(&W, &e, P, G));
1199 /* step 10. if (g < 2) then goto step 5 */
1200 /* NOTE: this weird construct is to keep the flow according to the spec.
1201 * the continue puts us back to step 5 of the for loop */
1202 if (mp_cmp_d(G, 2) < 0) {
1203 continue;
1204 }
1205 break; /* step 11 follows step 10 if the test condition is false */
1206 }
1207 if (count >= MAX_COUNT) {
1208 rv = SECFailure; /* last part of step 6 */
1209 }
1210 /* step 11.
1211 * return valid G */
1212 cleanup:
1213 PORT_Memset(data, 0, sizeof(data));
1214 if (hashcx) {
1215 hashobj->destroy(hashcx, PR_TRUE);
1216 }
1217 mp_clear(&e);
1218 mp_clear(&pm1);
1219 mp_clear(&W);
1220 if (err) {
1221 MP_TO_SEC_ERROR(err);
1222 rv = SECFailure;
1223 }
1224 return rv;
1225 }
1226
1227 /* This code uses labels and gotos, so that it can follow the numbered
1228 ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely,
1229 ** and so that the correctness of this code can be easily verified.
1230 ** So, please forgive the ugly c code.
1231 **/
1232 static SECStatus
pqg_ParamGen(unsigned int L,unsigned int N,pqgGenType type,unsigned int seedBytes,PQGParams ** pParams,PQGVerify ** pVfy)1233 pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type,
1234 unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy)
1235 {
1236 unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1237 unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/
1238 unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1239 unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1240 unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */
1241 unsigned int maxCount;
1242 HASH_HashType hashtype = HASH_AlgNULL;
1243 SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1244 PLArenaPool *arena = NULL;
1245 PQGParams *params = NULL;
1246 PQGVerify *verify = NULL;
1247 PRBool passed;
1248 SECItem hit = { 0, 0, 0 };
1249 SECItem firstseed = { 0, 0, 0 };
1250 SECItem qseed = { 0, 0, 0 };
1251 SECItem pseed = { 0, 0, 0 };
1252 mp_int P, Q, G, H, l, p0;
1253 mp_err err = MP_OKAY;
1254 SECStatus rv = SECFailure;
1255 int iterations = 0;
1256
1257 /* Step 1. L and N already checked by caller*/
1258 /* Step 2. if (seedlen < N) return INVALID; */
1259 if (seedBytes < N / PR_BITS_PER_BYTE || !pParams || !pVfy) {
1260 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1261 return SECFailure;
1262 }
1263
1264 /* Initialize bignums */
1265 MP_DIGITS(&P) = 0;
1266 MP_DIGITS(&Q) = 0;
1267 MP_DIGITS(&G) = 0;
1268 MP_DIGITS(&H) = 0;
1269 MP_DIGITS(&l) = 0;
1270 MP_DIGITS(&p0) = 0;
1271 CHECK_MPI_OK(mp_init(&P));
1272 CHECK_MPI_OK(mp_init(&Q));
1273 CHECK_MPI_OK(mp_init(&G));
1274 CHECK_MPI_OK(mp_init(&H));
1275 CHECK_MPI_OK(mp_init(&l));
1276 CHECK_MPI_OK(mp_init(&p0));
1277
1278 /* parameters have been passed in, only generate G */
1279 if (*pParams != NULL) {
1280 /* we only support G index generation if generating separate from PQ */
1281 if ((*pVfy == NULL) || (type == FIPS186_1_TYPE) ||
1282 ((*pVfy)->h.len != 1) || ((*pVfy)->h.data == NULL) ||
1283 ((*pVfy)->seed.data == NULL) || ((*pVfy)->seed.len == 0)) {
1284 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1285 return SECFailure;
1286 }
1287 params = *pParams;
1288 verify = *pVfy;
1289
1290 /* fill in P Q, */
1291 SECITEM_TO_MPINT((*pParams)->prime, &P);
1292 SECITEM_TO_MPINT((*pParams)->subPrime, &Q);
1293 hashtype = getFirstHash(L, N);
1294 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &(*pVfy)->seed,
1295 (*pVfy)->h.data[0], &G));
1296 MPINT_TO_SECITEM(&G, &(*pParams)->base, (*pParams)->arena);
1297 goto cleanup;
1298 }
1299 /* Initialize an arena for the params. */
1300 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1301 if (!arena) {
1302 PORT_SetError(SEC_ERROR_NO_MEMORY);
1303 return SECFailure;
1304 }
1305 params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams));
1306 if (!params) {
1307 PORT_SetError(SEC_ERROR_NO_MEMORY);
1308 PORT_FreeArena(arena, PR_TRUE);
1309 return SECFailure;
1310 }
1311 params->arena = arena;
1312 /* Initialize an arena for the verify. */
1313 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1314 if (!arena) {
1315 PORT_SetError(SEC_ERROR_NO_MEMORY);
1316 PORT_FreeArena(params->arena, PR_TRUE);
1317 return SECFailure;
1318 }
1319 verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify));
1320 if (!verify) {
1321 PORT_SetError(SEC_ERROR_NO_MEMORY);
1322 PORT_FreeArena(arena, PR_TRUE);
1323 PORT_FreeArena(params->arena, PR_TRUE);
1324 return SECFailure;
1325 }
1326 verify->arena = arena;
1327 seed = &verify->seed;
1328 arena = NULL;
1329
1330 /* Select Hash and Compute lengths. */
1331 /* getFirstHash gives us the smallest acceptable hash for this key
1332 * strength */
1333 hashtype = getFirstHash(L, N);
1334 outlen = HASH_ResultLen(hashtype) * PR_BITS_PER_BYTE;
1335
1336 /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */
1337 n = (L - 1) / outlen;
1338 /* Step 4: (skipped since we don't use b): b = L -1 - (n*outlen); */
1339 seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */
1340 step_5:
1341 /* ******************************************************************
1342 ** Step 5. (Step 1 in 186-1)
1343 ** "Choose an abitrary sequence of at least N bits and call it SEED.
1344 ** Let g be the length of SEED in bits."
1345 */
1346 if (++iterations > MAX_ITERATIONS) { /* give up after a while */
1347 PORT_SetError(SEC_ERROR_NEED_RANDOM);
1348 goto cleanup;
1349 }
1350 seed->len = seedBytes;
1351 CHECK_SEC_OK(getPQseed(seed, verify->arena));
1352 /* ******************************************************************
1353 ** Step 6. (Step 2 in 186-1)
1354 **
1355 ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]. (186-1)"
1356 ** "Compute U = HASH[SEED] 2**(N-1). (186-3)"
1357 **
1358 ** Step 7. (Step 3 in 186-1)
1359 ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
1360 ** and the least signficant bit to 1. In terms of boolean operations,
1361 ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160. (186-1)"
1362 **
1363 ** "q = 2**(N-1) + U + 1 - (U mod 2) (186-3)
1364 **
1365 ** Note: Both formulations are the same for U < 2**(N-1) and N=160
1366 **
1367 ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block
1368 ** FIPS186_3_ST_TYPE.
1369 */
1370 if (type == FIPS186_1_TYPE) {
1371 CHECK_SEC_OK(makeQfromSeed(seedlen, seed, &Q));
1372 } else if (type == FIPS186_3_TYPE) {
1373 CHECK_SEC_OK(makeQ2fromSeed(hashtype, N, seed, &Q));
1374 } else {
1375 /* FIPS186_3_ST_TYPE */
1376 unsigned int qgen_counter, pgen_counter;
1377
1378 /* Step 1 (L,N) already checked for acceptability */
1379
1380 firstseed = *seed;
1381 qgen_counter = 0;
1382 /* Step 2. Use N and firstseed to generate random prime q
1383 * using Apendix C.6 */
1384 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q,
1385 &qseed, &qgen_counter));
1386 /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0
1387 * using Appendix C.6 */
1388 pgen_counter = 0;
1389 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, (L + 1) / 2 + 1,
1390 &qseed, &p0, &pseed, &pgen_counter));
1391 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */
1392 CHECK_SEC_OK(makePrimefromPrimesShaweTaylor(hashtype, L, seedBytes * 8,
1393 &p0, &Q, &P, &pseed, &pgen_counter));
1394
1395 /* combine all the seeds */
1396 if ((qseed.len > firstseed.len) || (pseed.len > firstseed.len)) {
1397 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); /* shouldn't happen */
1398 goto cleanup;
1399 }
1400 /* If the seed overflows, then pseed and qseed may have leading zeros which the mpl code clamps.
1401 * we want to make sure those are added back in so the individual seed lengths are predictable from
1402 * the overall seed length */
1403 seed->len = firstseed.len * 3;
1404 seed->data = PORT_ArenaZAlloc(verify->arena, seed->len);
1405 if (seed->data == NULL) {
1406 goto cleanup;
1407 }
1408 PORT_Memcpy(seed->data, firstseed.data, firstseed.len);
1409 PORT_Memcpy(seed->data + 2 * firstseed.len - pseed.len, pseed.data, pseed.len);
1410 PORT_Memcpy(seed->data + 3 * firstseed.len - qseed.len, qseed.data, qseed.len);
1411 counter = (qgen_counter << 16) | pgen_counter;
1412
1413 /* we've generated both P and Q now, skip to generating G */
1414 goto generate_G;
1415 }
1416 /* ******************************************************************
1417 ** Step 8. (Step 4 in 186-1)
1418 ** "Use a robust primality testing algorithm to test whether q is prime."
1419 **
1420 ** Appendix 2.1 states that a Rabin test with at least 50 iterations
1421 ** "will give an acceptable probability of error."
1422 */
1423 /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
1424 err = mpp_pprime(&Q, prime_testcount_q(L, N));
1425 passed = (err == MP_YES) ? SECSuccess : SECFailure;
1426 /* ******************************************************************
1427 ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)."
1428 */
1429 if (passed != SECSuccess)
1430 goto step_5;
1431 /* ******************************************************************
1432 ** Step 10.
1433 ** offset = 1;
1434 **( Step 6b 186-1)"Let counter = 0 and offset = 2."
1435 */
1436 offset = (type == FIPS186_1_TYPE) ? 2 : 1;
1437 /*
1438 ** Step 11. (Step 6a,13a,14 in 186-1)
1439 ** For counter - 0 to (4L-1) do
1440 **
1441 */
1442 maxCount = L >= 1024 ? (4 * L - 1) : 4095;
1443 for (counter = 0; counter <= maxCount; counter++) {
1444 /* ******************************************************************
1445 ** Step 11.1 (Step 7 in 186-1)
1446 ** "for j = 0 ... n let
1447 ** V_j = HASH[(SEED + offset + j) mod 2**seedlen]."
1448 **
1449 ** Step 11.2 (Step 8 in 186-1)
1450 ** "W = V_0 + V_1*2**outlen+...+ V_n-1 * 2**((n-1)*outlen) +
1451 ** ((Vn* mod 2**b)*2**(n*outlen))"
1452 ** Step 11.3 (Step 8 in 186-1)
1453 ** "X = W + 2**(L-1)
1454 ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
1455 **
1456 ** Step 11.4 (Step 9 in 186-1).
1457 ** "c = X mod 2q"
1458 **
1459 ** Step 11.5 (Step 9 in 186-1).
1460 ** " p = X - (c - 1).
1461 ** Note that p is congruent to 1 mod 2q."
1462 */
1463 CHECK_SEC_OK(makePfromQandSeed(hashtype, L, N, offset, seedlen,
1464 seed, &Q, &P));
1465 /*************************************************************
1466 ** Step 11.6. (Step 10 in 186-1)
1467 ** "if p < 2**(L-1), then goto step 11.9. (step 13 in 186-1)"
1468 */
1469 CHECK_MPI_OK(mpl_set_bit(&l, (mp_size)(L - 1), 1)); /* l = 2**(L-1) */
1470 if (mp_cmp(&P, &l) < 0)
1471 goto step_11_9;
1472 /************************************************************
1473 ** Step 11.7 (step 11 in 186-1)
1474 ** "Perform a robust primality test on p."
1475 */
1476 /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
1477 err = mpp_pprime(&P, prime_testcount_p(L, N));
1478 passed = (err == MP_YES) ? SECSuccess : SECFailure;
1479 /* ******************************************************************
1480 ** Step 11.8. "If p is determined to be primed return VALID
1481 ** values of p, q, seed and counter."
1482 */
1483 if (passed == SECSuccess)
1484 break;
1485 step_11_9:
1486 /* ******************************************************************
1487 ** Step 11.9. "offset = offset + n + 1."
1488 */
1489 offset += n + 1;
1490 }
1491 /* ******************************************************************
1492 ** Step 12. "goto step 5."
1493 **
1494 ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8
1495 ** and now need to return p,q, seed, and counter.
1496 */
1497 if (counter > maxCount)
1498 goto step_5;
1499
1500 generate_G:
1501 /* ******************************************************************
1502 ** returning p, q, seed and counter
1503 */
1504 if (type == FIPS186_1_TYPE) {
1505 /* Generate g, This is called the "Unverifiable Generation of g
1506 * in FIPA186-3 Appedix A.2.1. For compatibility we maintain
1507 * this version of the code */
1508 SECITEM_AllocItem(NULL, &hit, L / 8); /* h is no longer than p */
1509 if (!hit.data)
1510 goto cleanup;
1511 do {
1512 /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
1513 CHECK_SEC_OK(generate_h_candidate(&hit, &H));
1514 CHECK_SEC_OK(makeGfromH(&P, &Q, &H, &G, &passed));
1515 } while (passed != PR_TRUE);
1516 MPINT_TO_SECITEM(&H, &verify->h, verify->arena);
1517 } else {
1518 unsigned char index = 1; /* default to 1 */
1519 verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1);
1520 if (verify->h.data == NULL) {
1521 goto cleanup;
1522 }
1523 verify->h.len = 1;
1524 verify->h.data[0] = index;
1525 /* Generate g, using the FIPS 186-3 Appendix A.23 */
1526 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G));
1527 }
1528 /* All generation is done. Now, save the PQG params. */
1529 MPINT_TO_SECITEM(&P, ¶ms->prime, params->arena);
1530 MPINT_TO_SECITEM(&Q, ¶ms->subPrime, params->arena);
1531 MPINT_TO_SECITEM(&G, ¶ms->base, params->arena);
1532 verify->counter = counter;
1533 *pParams = params;
1534 *pVfy = verify;
1535 cleanup:
1536 if (pseed.data) {
1537 PORT_Free(pseed.data);
1538 }
1539 if (qseed.data) {
1540 PORT_Free(qseed.data);
1541 }
1542 mp_clear(&P);
1543 mp_clear(&Q);
1544 mp_clear(&G);
1545 mp_clear(&H);
1546 mp_clear(&l);
1547 mp_clear(&p0);
1548 if (err) {
1549 MP_TO_SEC_ERROR(err);
1550 rv = SECFailure;
1551 }
1552 if (rv) {
1553 if (params) {
1554 PORT_FreeArena(params->arena, PR_TRUE);
1555 }
1556 if (verify) {
1557 PORT_FreeArena(verify->arena, PR_TRUE);
1558 }
1559 }
1560 if (hit.data) {
1561 SECITEM_FreeItem(&hit, PR_FALSE);
1562 }
1563 return rv;
1564 }
1565
1566 SECStatus
PQG_ParamGen(unsigned int j,PQGParams ** pParams,PQGVerify ** pVfy)1567 PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
1568 {
1569 unsigned int L; /* Length of P in bits. Per FIPS 186. */
1570 unsigned int seedBytes;
1571
1572 if (j > 8 || !pParams || !pVfy) {
1573 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1574 return SECFailure;
1575 }
1576 L = 512 + (j * 64); /* bits in P */
1577 seedBytes = L / 8;
1578 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,
1579 pParams, pVfy);
1580 }
1581
1582 SECStatus
PQG_ParamGenSeedLen(unsigned int j,unsigned int seedBytes,PQGParams ** pParams,PQGVerify ** pVfy)1583 PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
1584 PQGParams **pParams, PQGVerify **pVfy)
1585 {
1586 unsigned int L; /* Length of P in bits. Per FIPS 186. */
1587
1588 if (j > 8 || !pParams || !pVfy) {
1589 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1590 return SECFailure;
1591 }
1592 L = 512 + (j * 64); /* bits in P */
1593 return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,
1594 pParams, pVfy);
1595 }
1596
1597 SECStatus
PQG_ParamGenV2(unsigned int L,unsigned int N,unsigned int seedBytes,PQGParams ** pParams,PQGVerify ** pVfy)1598 PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes,
1599 PQGParams **pParams, PQGVerify **pVfy)
1600 {
1601 if (N == 0) {
1602 N = pqg_get_default_N(L);
1603 }
1604 if (seedBytes == 0) {
1605 /* seedBytes == L/8 for probable primes, N/8 for Shawe-Taylor Primes */
1606 seedBytes = N / 8;
1607 }
1608 if (pqg_validate_dsa2(L, N) != SECSuccess) {
1609 /* error code already set */
1610 return SECFailure;
1611 }
1612 return pqg_ParamGen(L, N, FIPS186_3_ST_TYPE, seedBytes, pParams, pVfy);
1613 }
1614
1615 /*
1616 * verify can use vfy structures returned from either FIPS186-1 or
1617 * FIPS186-2, and can handle differences in selected Hash functions to
1618 * generate the parameters.
1619 */
1620 SECStatus
PQG_VerifyParams(const PQGParams * params,const PQGVerify * vfy,SECStatus * result)1621 PQG_VerifyParams(const PQGParams *params,
1622 const PQGVerify *vfy, SECStatus *result)
1623 {
1624 SECStatus rv = SECSuccess;
1625 unsigned int g, n, L, N, offset, outlen;
1626 mp_int p0, P, Q, G, P_, Q_, G_, r, h;
1627 mp_err err = MP_OKAY;
1628 int j;
1629 unsigned int counter_max = 0; /* handle legacy L < 1024 */
1630 unsigned int qseed_len;
1631 unsigned int qgen_counter_ = 0;
1632 SECItem pseed_ = { 0, 0, 0 };
1633 HASH_HashType hashtype = HASH_AlgNULL;
1634 pqgGenType type = FIPS186_1_TYPE;
1635
1636 #define CHECKPARAM(cond) \
1637 if (!(cond)) { \
1638 *result = SECFailure; \
1639 goto cleanup; \
1640 }
1641 if (!params || !vfy || !result) {
1642 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1643 return SECFailure;
1644 }
1645 /* always need at least p, q, and seed for any meaningful check */
1646 if ((params->prime.len == 0) || (params->subPrime.len == 0) ||
1647 (vfy->seed.len == 0)) {
1648 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1649 return SECFailure;
1650 }
1651 /* we want to either check PQ or G or both. If we don't have G, make
1652 * sure we have count so we can check P. */
1653 if ((params->base.len == 0) && (vfy->counter == -1)) {
1654 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1655 return SECFailure;
1656 }
1657
1658 MP_DIGITS(&p0) = 0;
1659 MP_DIGITS(&P) = 0;
1660 MP_DIGITS(&Q) = 0;
1661 MP_DIGITS(&G) = 0;
1662 MP_DIGITS(&P_) = 0;
1663 MP_DIGITS(&Q_) = 0;
1664 MP_DIGITS(&G_) = 0;
1665 MP_DIGITS(&r) = 0;
1666 MP_DIGITS(&h) = 0;
1667 CHECK_MPI_OK(mp_init(&p0));
1668 CHECK_MPI_OK(mp_init(&P));
1669 CHECK_MPI_OK(mp_init(&Q));
1670 CHECK_MPI_OK(mp_init(&G));
1671 CHECK_MPI_OK(mp_init(&P_));
1672 CHECK_MPI_OK(mp_init(&Q_));
1673 CHECK_MPI_OK(mp_init(&G_));
1674 CHECK_MPI_OK(mp_init(&r));
1675 CHECK_MPI_OK(mp_init(&h));
1676 *result = SECSuccess;
1677 SECITEM_TO_MPINT(params->prime, &P);
1678 SECITEM_TO_MPINT(params->subPrime, &Q);
1679 /* if G isn't specified, just check P and Q */
1680 if (params->base.len != 0) {
1681 SECITEM_TO_MPINT(params->base, &G);
1682 }
1683 /* 1. Check (L,N) pair */
1684 N = mpl_significant_bits(&Q);
1685 L = mpl_significant_bits(&P);
1686 if (L < 1024) {
1687 /* handle DSA1 pqg parameters with less thatn 1024 bits*/
1688 CHECKPARAM(N == DSA1_Q_BITS);
1689 j = PQG_PBITS_TO_INDEX(L);
1690 CHECKPARAM(j >= 0 && j <= 8);
1691 counter_max = 4096;
1692 } else {
1693 /* handle DSA2 parameters (includes DSA1, 1024 bits) */
1694 CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess);
1695 counter_max = 4 * L;
1696 }
1697 /* 3. G < P */
1698 if (params->base.len != 0) {
1699 CHECKPARAM(mp_cmp(&G, &P) < 0);
1700 }
1701 /* 4. P % Q == 1 */
1702 CHECK_MPI_OK(mp_mod(&P, &Q, &r));
1703 CHECKPARAM(mp_cmp_d(&r, 1) == 0);
1704 /* 5. Q is prime */
1705 CHECKPARAM(mpp_pprime(&Q, prime_testcount_q(L, N)) == MP_YES);
1706 /* 6. P is prime */
1707 CHECKPARAM(mpp_pprime(&P, prime_testcount_p(L, N)) == MP_YES);
1708 /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
1709 /* continue processing P */
1710 /* 7. counter < 4*L */
1711 /* 8. g >= N and g < 2*L (g is length of seed in bits) */
1712 /* step 7 and 8 are delayed until we determine which type of generation
1713 * was used */
1714 /* 9. Q generated from SEED matches Q in PQGParams. */
1715 /* This function checks all possible hash and generation types to
1716 * find a Q_ which matches Q. */
1717 g = vfy->seed.len * 8;
1718 CHECKPARAM(findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len,
1719 &hashtype, &type, &qgen_counter_) == SECSuccess);
1720 CHECKPARAM(mp_cmp(&Q, &Q_) == 0);
1721 /* now we can do steps 7 & 8*/
1722 if ((type == FIPS186_1_TYPE) || (type == FIPS186_3_TYPE)) {
1723 CHECKPARAM((vfy->counter == -1) || (vfy->counter < counter_max));
1724 CHECKPARAM(g >= N && g < counter_max / 2);
1725 }
1726 if (type == FIPS186_3_ST_TYPE) {
1727 SECItem qseed = { 0, 0, 0 };
1728 SECItem pseed = { 0, 0, 0 };
1729 unsigned int first_seed_len;
1730 unsigned int pgen_counter_ = 0;
1731 unsigned int qgen_counter = (vfy->counter >> 16) & 0xffff;
1732 unsigned int pgen_counter = (vfy->counter) & 0xffff;
1733
1734 /* extract pseed and qseed from domain_parameter_seed, which is
1735 * first_seed || pseed || qseed. qseed is first_seed + small_integer
1736 * mod the length of first_seed. pseed is qseed + small_integer mod
1737 * the length of first_seed. This means most of the time
1738 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or
1739 * pseed.len will be smaller because mpi clamps them. pqgGen
1740 * automatically adds the zero pad back though, so we can depend
1741 * domain_parameter_seed.len to be a multiple of three. We only have
1742 * to deal with the fact that the returned seeds from our functions
1743 * could be shorter.
1744 * first_seed.len = domain_parameter_seed.len/3
1745 * We can now find the offsets;
1746 * first_seed.data = domain_parameter_seed.data + 0
1747 * pseed.data = domain_parameter_seed.data + first_seed.len
1748 * qseed.data = domain_parameter_seed.data
1749 * + domain_paramter_seed.len - qseed.len
1750 * We deal with pseed possibly having zero pad in the pseed check later.
1751 */
1752 first_seed_len = vfy->seed.len / 3;
1753 CHECKPARAM(qseed_len < vfy->seed.len);
1754 CHECKPARAM(first_seed_len * 8 > N - 1);
1755 CHECKPARAM(first_seed_len * 8 < counter_max / 2);
1756 CHECKPARAM(first_seed_len >= qseed_len);
1757 qseed.len = qseed_len;
1758 qseed.data = vfy->seed.data + vfy->seed.len - qseed.len;
1759 pseed.len = first_seed_len;
1760 pseed.data = vfy->seed.data + first_seed_len;
1761
1762 /*
1763 * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed
1764 * above in our initial checks, Step 2 was completed by
1765 * findQfromSeed */
1766
1767 /* Step 3 (status, c0, prime_seed, prime_gen_counter) =
1768 ** (ST_Random_Prime((ceil(length/2)+1, input_seed)
1769 */
1770 CHECK_SEC_OK(makePrimefromSeedShaweTaylor(hashtype, (L + 1) / 2 + 1,
1771 &qseed, &p0, &pseed_, &pgen_counter_));
1772 /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */
1773 CHECK_SEC_OK(makePrimefromPrimesShaweTaylor(hashtype, L, first_seed_len * 8,
1774 &p0, &Q_, &P_, &pseed_, &pgen_counter_));
1775 CHECKPARAM(mp_cmp(&P, &P_) == 0);
1776 /* make sure pseed wasn't tampered with (since it is part of
1777 * calculating G) */
1778 if (pseed.len > pseed_.len) {
1779 /* handle the case of zero pad for pseed */
1780 int extra = pseed.len - pseed_.len;
1781 int i;
1782 for (i = 0; i < extra; i++) {
1783 if (pseed.data[i] != 0) {
1784 *result = SECFailure;
1785 goto cleanup;
1786 }
1787 }
1788 pseed.data += extra;
1789 pseed.len -= extra;
1790 /* the rest is handled in the normal compare below */
1791 }
1792 CHECKPARAM(SECITEM_CompareItem(&pseed, &pseed_) == SECEqual);
1793 if (vfy->counter != -1) {
1794 CHECKPARAM(pgen_counter < counter_max);
1795 CHECKPARAM(qgen_counter < counter_max);
1796 CHECKPARAM((pgen_counter_ == pgen_counter));
1797 CHECKPARAM((qgen_counter_ == qgen_counter));
1798 }
1799 } else if (vfy->counter == -1) {
1800 /* If counter is set to -1, we are really only verifying G, skip
1801 * the remainder of the checks for P */
1802 CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */
1803 } else {
1804 /* 10. P generated from (L, counter, g, SEED, Q) matches P
1805 * in PQGParams. */
1806 outlen = HASH_ResultLen(hashtype) * PR_BITS_PER_BYTE;
1807 PORT_Assert(outlen > 0);
1808 n = (L - 1) / outlen;
1809 offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1);
1810 CHECK_SEC_OK(makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed,
1811 &Q, &P_));
1812 CHECKPARAM(mp_cmp(&P, &P_) == 0);
1813 }
1814
1815 /* now check G, skip if don't have a g */
1816 if (params->base.len == 0)
1817 goto cleanup;
1818
1819 /* first Always check that G is OK FIPS186-3 A.2.2 & A.2.4*/
1820 /* 1. 2 < G < P-1 */
1821 /* P is prime, p-1 == zero 1st bit */
1822 CHECK_MPI_OK(mpl_set_bit(&P, 0, 0));
1823 CHECKPARAM(mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0);
1824 CHECK_MPI_OK(mpl_set_bit(&P, 0, 1)); /* set it back */
1825 /* 2. verify g**q mod p == 1 */
1826 CHECK_MPI_OK(mp_exptmod(&G, &Q, &P, &h)); /* h = G ** Q mod P */
1827 CHECKPARAM(mp_cmp_d(&h, 1) == 0);
1828
1829 /* no h, the above is the best we can do */
1830 if (vfy->h.len == 0) {
1831 if (type != FIPS186_1_TYPE) {
1832 *result = SECWouldBlock;
1833 }
1834 goto cleanup;
1835 }
1836
1837 /*
1838 * If h is one byte and FIPS186-3 was used to generate Q (we've verified
1839 * Q was generated from seed already, then we assume that FIPS 186-3
1840 * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was
1841 * used to generate G.
1842 */
1843 if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) {
1844 /* A.2.3 */
1845 CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed,
1846 vfy->h.data[0], &G_));
1847 CHECKPARAM(mp_cmp(&G, &G_) == 0);
1848 } else {
1849 int passed;
1850 /* A.2.1 */
1851 SECITEM_TO_MPINT(vfy->h, &h);
1852 /* 11. 1 < h < P-1 */
1853 /* P is prime, p-1 == zero 1st bit */
1854 CHECK_MPI_OK(mpl_set_bit(&P, 0, 0));
1855 CHECKPARAM(mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P));
1856 CHECK_MPI_OK(mpl_set_bit(&P, 0, 1)); /* set it back */
1857 /* 12. G generated from h matches G in PQGParams. */
1858 CHECK_SEC_OK(makeGfromH(&P, &Q, &h, &G_, &passed));
1859 CHECKPARAM(passed && mp_cmp(&G, &G_) == 0);
1860 }
1861 cleanup:
1862 mp_clear(&p0);
1863 mp_clear(&P);
1864 mp_clear(&Q);
1865 mp_clear(&G);
1866 mp_clear(&P_);
1867 mp_clear(&Q_);
1868 mp_clear(&G_);
1869 mp_clear(&r);
1870 mp_clear(&h);
1871 if (pseed_.data) {
1872 SECITEM_FreeItem(&pseed_, PR_FALSE);
1873 }
1874 if (err) {
1875 MP_TO_SEC_ERROR(err);
1876 rv = SECFailure;
1877 }
1878 return rv;
1879 }
1880
1881 /**************************************************************************
1882 * Free the PQGParams struct and the things it points to. *
1883 **************************************************************************/
1884 void
PQG_DestroyParams(PQGParams * params)1885 PQG_DestroyParams(PQGParams *params)
1886 {
1887 if (params == NULL)
1888 return;
1889 if (params->arena != NULL) {
1890 PORT_FreeArena(params->arena, PR_FALSE); /* don't zero it */
1891 } else {
1892 SECITEM_FreeItem(¶ms->prime, PR_FALSE); /* don't free prime */
1893 SECITEM_FreeItem(¶ms->subPrime, PR_FALSE); /* don't free subPrime */
1894 SECITEM_FreeItem(¶ms->base, PR_FALSE); /* don't free base */
1895 PORT_Free(params);
1896 }
1897 }
1898
1899 /**************************************************************************
1900 * Free the PQGVerify struct and the things it points to. *
1901 **************************************************************************/
1902
1903 void
PQG_DestroyVerify(PQGVerify * vfy)1904 PQG_DestroyVerify(PQGVerify *vfy)
1905 {
1906 if (vfy == NULL)
1907 return;
1908 if (vfy->arena != NULL) {
1909 PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */
1910 } else {
1911 SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */
1912 SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */
1913 PORT_Free(vfy);
1914 }
1915 }
1916