michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: /* michael@0: * PQG parameter generation/verification. Based on FIPS 186-3. michael@0: */ michael@0: #ifdef FREEBL_NO_DEPEND michael@0: #include "stubs.h" michael@0: #endif michael@0: michael@0: #include "prerr.h" michael@0: #include "secerr.h" michael@0: michael@0: #include "prtypes.h" michael@0: #include "blapi.h" michael@0: #include "secitem.h" michael@0: #include "mpi.h" michael@0: #include "mpprime.h" michael@0: #include "mplogic.h" michael@0: #include "secmpi.h" michael@0: michael@0: #define MAX_ITERATIONS 1000 /* Maximum number of iterations of primegen */ michael@0: michael@0: typedef enum { michael@0: FIPS186_1_TYPE, /* Probablistic */ michael@0: FIPS186_3_TYPE, /* Probablistic */ michael@0: FIPS186_3_ST_TYPE /* Shawe-Taylor provable */ michael@0: } pqgGenType; michael@0: michael@0: /* michael@0: * These test iterations are quite a bit larger than we previously had. michael@0: * This is because FIPS 186-3 is worried about the primes in PQG generation. michael@0: * It may be possible to purposefully construct composites which more michael@0: * iterations of Miller-Rabin than the for your normal randomly selected michael@0: * numbers.There are 3 ways to counter this: 1) use one of the cool provably michael@0: * prime algorithms (which would require a lot more work than DSA-2 deservers. michael@0: * 2) add a Lucas primality test (which requires coding a Lucas primality test, michael@0: * or 3) use a larger M-R test count. I chose the latter. It increases the time michael@0: * that it takes to prove the selected prime, but it shouldn't increase the michael@0: * overall time to run the algorithm (non-primes should still faile M-R michael@0: * realively quickly). If you want to get that last bit of performance, michael@0: * implement Lucas and adjust these two functions. See FIPS 186-3 Appendix C michael@0: * and F for more information. michael@0: */ michael@0: int prime_testcount_p(int L, int N) michael@0: { michael@0: switch (L) { michael@0: case 1024: michael@0: return 40; michael@0: case 2048: michael@0: return 56; michael@0: case 3072: michael@0: return 64; michael@0: default: michael@0: break; michael@0: } michael@0: return 50; /* L = 512-960 */ michael@0: } michael@0: michael@0: /* The q numbers are different if you run M-R followd by Lucas. I created michael@0: * a separate function so if someone wanted to add the Lucas check, they michael@0: * could do so fairly easily */ michael@0: int prime_testcount_q(int L, int N) michael@0: { michael@0: return prime_testcount_p(L,N); michael@0: } michael@0: michael@0: /* michael@0: * generic function to make sure our input matches DSA2 requirements michael@0: * this gives us one place to go if we need to bump the requirements in the michael@0: * future. michael@0: */ michael@0: static SECStatus michael@0: pqg_validate_dsa2(unsigned int L, unsigned int N) michael@0: { michael@0: michael@0: switch (L) { michael@0: case 1024: michael@0: if (N != DSA1_Q_BITS) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: break; michael@0: case 2048: michael@0: if ((N != 224) && (N != 256)) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: break; michael@0: case 3072: michael@0: if (N != 256) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: break; michael@0: default: michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: return SECSuccess; michael@0: } michael@0: michael@0: static unsigned int michael@0: pqg_get_default_N(unsigned int L) michael@0: { michael@0: unsigned int N = 0; michael@0: switch (L) { michael@0: case 1024: michael@0: N = DSA1_Q_BITS; michael@0: break; michael@0: case 2048: michael@0: N = 224; michael@0: break; michael@0: case 3072: michael@0: N = 256; michael@0: break; michael@0: default: michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: break; /* N already set to zero */ michael@0: } michael@0: return N; michael@0: } michael@0: michael@0: /* michael@0: * Select the lowest hash algorithm usable michael@0: */ michael@0: static HASH_HashType michael@0: getFirstHash(unsigned int L, unsigned int N) michael@0: { michael@0: if (N < 224) { michael@0: return HASH_AlgSHA1; michael@0: } michael@0: if (N < 256) { michael@0: return HASH_AlgSHA224; michael@0: } michael@0: if (N < 384) { michael@0: return HASH_AlgSHA256; michael@0: } michael@0: if (N < 512) { michael@0: return HASH_AlgSHA384; michael@0: } michael@0: return HASH_AlgSHA512; michael@0: } michael@0: michael@0: /* michael@0: * find the next usable hash algorthim michael@0: */ michael@0: static HASH_HashType michael@0: getNextHash(HASH_HashType hashtype) michael@0: { michael@0: switch (hashtype) { michael@0: case HASH_AlgSHA1: michael@0: hashtype = HASH_AlgSHA224; michael@0: break; michael@0: case HASH_AlgSHA224: michael@0: hashtype = HASH_AlgSHA256; michael@0: break; michael@0: case HASH_AlgSHA256: michael@0: hashtype = HASH_AlgSHA384; michael@0: break; michael@0: case HASH_AlgSHA384: michael@0: hashtype = HASH_AlgSHA512; michael@0: break; michael@0: case HASH_AlgSHA512: michael@0: default: michael@0: hashtype = HASH_AlgTOTAL; michael@0: break; michael@0: } michael@0: return hashtype; michael@0: } michael@0: michael@0: static unsigned int michael@0: HASH_ResultLen(HASH_HashType type) michael@0: { michael@0: const SECHashObject *hash_obj = HASH_GetRawHashObject(type); michael@0: if (hash_obj == NULL) { michael@0: return 0; michael@0: } michael@0: return hash_obj->length; michael@0: } michael@0: michael@0: static SECStatus michael@0: HASH_HashBuf(HASH_HashType type, unsigned char *dest, michael@0: const unsigned char *src, PRUint32 src_len) michael@0: { michael@0: const SECHashObject *hash_obj = HASH_GetRawHashObject(type); michael@0: void *hashcx = NULL; michael@0: unsigned int dummy; michael@0: michael@0: if (hash_obj == NULL) { michael@0: return SECFailure; michael@0: } michael@0: michael@0: hashcx = hash_obj->create(); michael@0: if (hashcx == NULL) { michael@0: return SECFailure; michael@0: } michael@0: hash_obj->begin(hashcx); michael@0: hash_obj->update(hashcx,src,src_len); michael@0: hash_obj->end(hashcx,dest, &dummy, hash_obj->length); michael@0: hash_obj->destroy(hashcx, PR_TRUE); michael@0: return SECSuccess; michael@0: } michael@0: michael@0: unsigned int michael@0: PQG_GetLength(const SECItem *obj) michael@0: { michael@0: unsigned int len = obj->len; michael@0: michael@0: if (obj->data == NULL) { michael@0: return 0; michael@0: } michael@0: if (len > 1 && obj->data[0] == 0) { michael@0: len--; michael@0: } michael@0: return len; michael@0: } michael@0: michael@0: SECStatus michael@0: PQG_Check(const PQGParams *params) michael@0: { michael@0: unsigned int L,N; michael@0: SECStatus rv = SECSuccess; michael@0: michael@0: if (params == NULL) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: michael@0: L = PQG_GetLength(¶ms->prime)*PR_BITS_PER_BYTE; michael@0: N = PQG_GetLength(¶ms->subPrime)*PR_BITS_PER_BYTE; michael@0: michael@0: if (L < 1024) { michael@0: int j; michael@0: michael@0: /* handle DSA1 pqg parameters with less thatn 1024 bits*/ michael@0: if ( N != DSA1_Q_BITS ) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: j = PQG_PBITS_TO_INDEX(L); michael@0: if ( j < 0 ) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: rv = SECFailure; michael@0: } michael@0: } else { michael@0: /* handle DSA2 parameters (includes DSA1, 1024 bits) */ michael@0: rv = pqg_validate_dsa2(L, N); michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: HASH_HashType michael@0: PQG_GetHashType(const PQGParams *params) michael@0: { michael@0: unsigned int L,N; michael@0: michael@0: if (params == NULL) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return HASH_AlgNULL; michael@0: } michael@0: michael@0: L = PQG_GetLength(¶ms->prime)*PR_BITS_PER_BYTE; michael@0: N = PQG_GetLength(¶ms->subPrime)*PR_BITS_PER_BYTE; michael@0: return getFirstHash(L, N); michael@0: } michael@0: michael@0: /* Get a seed for generating P and Q. If in testing mode, copy in the michael@0: ** seed from FIPS 186-1 appendix 5. Otherwise, obtain bytes from the michael@0: ** global random number generator. michael@0: */ michael@0: static SECStatus michael@0: getPQseed(SECItem *seed, PLArenaPool* arena) michael@0: { michael@0: SECStatus rv; michael@0: michael@0: if (!seed->data) { michael@0: seed->data = (unsigned char*)PORT_ArenaZAlloc(arena, seed->len); michael@0: } michael@0: if (!seed->data) { michael@0: PORT_SetError(SEC_ERROR_NO_MEMORY); michael@0: return SECFailure; michael@0: } michael@0: rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len); michael@0: /* michael@0: * NIST CMVP disallows a sequence of 20 bytes with the most michael@0: * significant byte equal to 0. Perhaps they interpret michael@0: * "a sequence of at least 160 bits" as "a number >= 2^159". michael@0: * So we always set the most significant bit to 1. (bug 334533) michael@0: */ michael@0: seed->data[0] |= 0x80; michael@0: return rv; michael@0: } michael@0: michael@0: /* Generate a candidate h value. If in testing mode, use the h value michael@0: ** specified in FIPS 186-1 appendix 5, h = 2. Otherwise, obtain bytes michael@0: ** from the global random number generator. michael@0: */ michael@0: static SECStatus michael@0: generate_h_candidate(SECItem *hit, mp_int *H) michael@0: { michael@0: SECStatus rv = SECSuccess; michael@0: mp_err err = MP_OKAY; michael@0: #ifdef FIPS_186_1_A5_TEST michael@0: memset(hit->data, 0, hit->len); michael@0: hit->data[hit->len-1] = 0x02; michael@0: #else michael@0: rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len); michael@0: #endif michael@0: if (rv) michael@0: return SECFailure; michael@0: err = mp_read_unsigned_octets(H, hit->data, hit->len); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: return SECFailure; michael@0: } michael@0: return SECSuccess; michael@0: } michael@0: michael@0: static SECStatus michael@0: addToSeed(const SECItem * seed, michael@0: unsigned long addend, michael@0: int seedlen, /* g in 186-1 */ michael@0: SECItem * seedout) michael@0: { michael@0: mp_int s, sum, modulus, tmp; michael@0: mp_err err = MP_OKAY; michael@0: SECStatus rv = SECSuccess; michael@0: MP_DIGITS(&s) = 0; michael@0: MP_DIGITS(&sum) = 0; michael@0: MP_DIGITS(&modulus) = 0; michael@0: MP_DIGITS(&tmp) = 0; michael@0: CHECK_MPI_OK( mp_init(&s) ); michael@0: CHECK_MPI_OK( mp_init(&sum) ); michael@0: CHECK_MPI_OK( mp_init(&modulus) ); michael@0: SECITEM_TO_MPINT(*seed, &s); /* s = seed */ michael@0: /* seed += addend */ michael@0: if (addend < MP_DIGIT_MAX) { michael@0: CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) ); michael@0: } else { michael@0: CHECK_MPI_OK( mp_init(&tmp) ); michael@0: CHECK_MPI_OK( mp_set_ulong(&tmp, addend) ); michael@0: CHECK_MPI_OK( mp_add(&s, &tmp, &s) ); michael@0: } michael@0: /*sum = s mod 2**seedlen */ michael@0: CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)seedlen, NULL, &sum) ); michael@0: if (seedout->data != NULL) { michael@0: SECITEM_ZfreeItem(seedout, PR_FALSE); michael@0: } michael@0: MPINT_TO_SECITEM(&sum, seedout, NULL); michael@0: cleanup: michael@0: mp_clear(&s); michael@0: mp_clear(&sum); michael@0: mp_clear(&modulus); michael@0: mp_clear(&tmp); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: return SECFailure; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /* Compute Hash[(SEED + addend) mod 2**g] michael@0: ** Result is placed in shaOutBuf. michael@0: ** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 and michael@0: ** step 11.2 of FIPS 186-3 Appendix A.1.1.2 . michael@0: */ michael@0: static SECStatus michael@0: addToSeedThenHash(HASH_HashType hashtype, michael@0: const SECItem * seed, michael@0: unsigned long addend, michael@0: int seedlen, /* g in 186-1 */ michael@0: unsigned char * hashOutBuf) michael@0: { michael@0: SECItem str = { 0, 0, 0 }; michael@0: SECStatus rv; michael@0: rv = addToSeed(seed, addend, seedlen, &str); michael@0: if (rv != SECSuccess) { michael@0: return rv; michael@0: } michael@0: rv = HASH_HashBuf(hashtype, hashOutBuf, str.data, str.len);/* hash result */ michael@0: if (str.data) michael@0: SECITEM_ZfreeItem(&str, PR_FALSE); michael@0: return rv; michael@0: } michael@0: michael@0: /* michael@0: ** Perform steps 2 and 3 of FIPS 186-1, appendix 2.2. michael@0: ** Generate Q from seed. michael@0: */ michael@0: static SECStatus michael@0: makeQfromSeed( michael@0: unsigned int g, /* input. Length of seed in bits. */ michael@0: const SECItem * seed, /* input. */ michael@0: mp_int * Q) /* output. */ michael@0: { michael@0: unsigned char sha1[SHA1_LENGTH]; michael@0: unsigned char sha2[SHA1_LENGTH]; michael@0: unsigned char U[SHA1_LENGTH]; michael@0: SECStatus rv = SECSuccess; michael@0: mp_err err = MP_OKAY; michael@0: int i; michael@0: /* ****************************************************************** michael@0: ** Step 2. michael@0: ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]." michael@0: **/ michael@0: CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) ); michael@0: CHECK_SEC_OK( addToSeedThenHash(HASH_AlgSHA1, seed, 1, g, sha2) ); michael@0: for (i=0; idata, seed->len) ); michael@0: /* mod 2**N . Step 7 will explicitly set the top bit to 1, so no need michael@0: * to handle mod 2**N-1 */ michael@0: if (hashLen > N_bytes) { michael@0: offset = hashLen - N_bytes; michael@0: } michael@0: /* ****************************************************************** michael@0: ** Step 7. michael@0: ** computed_q = 2**(N-1) + U + 1 - (U mod 2) michael@0: ** michael@0: ** This is the same as: michael@0: ** computed_q = 2**(N-1) | U | 1; michael@0: */ michael@0: U[offset] |= 0x80; /* U is MSB first */ michael@0: U[hashLen-1] |= 0x01; michael@0: err = mp_read_unsigned_octets(Q, &U[offset], N_bytes); michael@0: cleanup: michael@0: memset(U, 0, HASH_LENGTH_MAX); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: return SECFailure; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /* michael@0: ** Perform steps from FIPS 186-3, Appendix A.1.2.1 and Appendix C.6 michael@0: ** michael@0: ** This generates a provable prime from two smaller prime. The resulting michael@0: ** prime p will have q0 as a multiple of p-1. q0 can be 1. michael@0: ** michael@0: ** This implments steps 4 thorough 22 of FIPS 186-3 A.1.2.1 and michael@0: ** steps 16 through 34 of FIPS 186-2 C.6 michael@0: */ michael@0: #define MAX_ST_SEED_BITS (HASH_LENGTH_MAX*PR_BITS_PER_BYTE) michael@0: SECStatus michael@0: makePrimefromPrimesShaweTaylor( michael@0: HASH_HashType hashtype, /* selected Hashing algorithm */ michael@0: unsigned int length, /* input. Length of prime in bits. */ michael@0: mp_int * c0, /* seed prime */ michael@0: mp_int * q, /* sub prime, can be 1 */ michael@0: mp_int * prime, /* output. */ michael@0: SECItem * prime_seed, /* input/output. */ michael@0: int * prime_gen_counter) /* input/output. */ michael@0: { michael@0: mp_int c; michael@0: mp_int c0_2; michael@0: mp_int t; michael@0: mp_int a; michael@0: mp_int z; michael@0: mp_int two_length_minus_1; michael@0: SECStatus rv = SECFailure; michael@0: int hashlen = HASH_ResultLen(hashtype); michael@0: int outlen = hashlen*PR_BITS_PER_BYTE; michael@0: int offset; michael@0: unsigned char bit, mask; michael@0: /* x needs to hold roundup(L/outlen)*outlen. michael@0: * This can be no larger than L+outlen-1, So we set it's size to michael@0: * our max L + max outlen and know we are safe */ michael@0: unsigned char x[DSA_MAX_P_BITS/8+HASH_LENGTH_MAX]; michael@0: mp_err err = MP_OKAY; michael@0: int i; michael@0: int iterations; michael@0: int old_counter; michael@0: michael@0: MP_DIGITS(&c) = 0; michael@0: MP_DIGITS(&c0_2) = 0; michael@0: MP_DIGITS(&t) = 0; michael@0: MP_DIGITS(&a) = 0; michael@0: MP_DIGITS(&z) = 0; michael@0: MP_DIGITS(&two_length_minus_1) = 0; michael@0: CHECK_MPI_OK( mp_init(&c) ); michael@0: CHECK_MPI_OK( mp_init(&c0_2) ); michael@0: CHECK_MPI_OK( mp_init(&t) ); michael@0: CHECK_MPI_OK( mp_init(&a) ); michael@0: CHECK_MPI_OK( mp_init(&z) ); michael@0: CHECK_MPI_OK( mp_init(&two_length_minus_1) ); michael@0: michael@0: michael@0: /* michael@0: ** There is a slight mapping of variable names depending on which michael@0: ** FIPS 186 steps are being carried out. The mapping is as follows: michael@0: ** variable A.1.2.1 C.6 michael@0: ** c0 p0 c0 michael@0: ** q q 1 michael@0: ** c p c michael@0: ** c0_2 2*p0*q 2*c0 michael@0: ** length L length michael@0: ** prime_seed pseed prime_seed michael@0: ** prime_gen_counter pgen_counter prime_gen_counter michael@0: ** michael@0: ** Also note: or iterations variable is actually iterations+1, since michael@0: ** iterations+1 works better in C. michael@0: */ michael@0: michael@0: /* Step 4/16 iterations = ceiling(length/outlen)-1 */ michael@0: iterations = (length+outlen-1)/outlen; /* NOTE: iterations +1 */ michael@0: /* Step 5/17 old_counter = prime_gen_counter */ michael@0: old_counter = *prime_gen_counter; michael@0: /* michael@0: ** Comment: Generate a pseudorandom integer x in the interval michael@0: ** [2**(lenght-1), 2**length]. michael@0: ** michael@0: ** Step 6/18 x = 0 michael@0: */ michael@0: PORT_Memset(x, 0, sizeof(x)); michael@0: /* michael@0: ** Step 7/19 for i = 0 to iterations do michael@0: ** x = x + (HASH(prime_seed + i) * 2^(i*outlen)) michael@0: */ michael@0: for (i=0; i < iterations; i++) { michael@0: /* is bigger than prime_seed should get to */ michael@0: CHECK_SEC_OK( addToSeedThenHash(hashtype, prime_seed, i, michael@0: MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen])); michael@0: } michael@0: /* Step 8/20 prime_seed = prime_seed + iterations + 1 */ michael@0: CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS, michael@0: prime_seed)); michael@0: /* michael@0: ** Step 9/21 x = 2 ** (length-1) + x mod 2 ** (length-1) michael@0: ** michael@0: ** This step mathematically sets the high bit and clears out michael@0: ** all the other bits higher than length. 'x' is stored michael@0: ** in the x array, MSB first. The above formula gives us an 'x' michael@0: ** which is length bytes long and has the high bit set. We also know michael@0: ** that length <= iterations*outlen since michael@0: ** iterations=ceiling(length/outlen). First we find the offset in michael@0: ** bytes into the array where the high bit is. michael@0: */ michael@0: offset = (outlen*iterations - length)/PR_BITS_PER_BYTE; michael@0: /* now we want to set the 'high bit', since length may not be a michael@0: * multiple of 8,*/ michael@0: bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */ michael@0: /* we need to zero out the rest of the bits in the byte above */ michael@0: mask = (bit-1); michael@0: /* now we set it */ michael@0: x[offset] = (mask & x[offset]) | bit; michael@0: /* michael@0: ** Comment: Generate a candidate prime c in the interval michael@0: ** [2**(lenght-1), 2**length]. michael@0: ** michael@0: ** Step 10 t = ceiling(x/(2q(p0))) michael@0: ** Step 22 t = ceiling(x/(2(c0))) michael@0: */ michael@0: CHECK_MPI_OK( mp_read_unsigned_octets(&t, &x[offset], michael@0: hashlen*iterations - offset ) ); /* t = x */ michael@0: CHECK_MPI_OK( mp_mul(c0, q, &c0_2) ); /* c0_2 is now c0*q */ michael@0: CHECK_MPI_OK( mp_add(&c0_2, &c0_2, &c0_2) ); /* c0_2 is now 2*q*c0 */ michael@0: CHECK_MPI_OK( mp_add(&t, &c0_2, &t) ); /* t = x+2*q*c0 */ michael@0: CHECK_MPI_OK( mp_sub_d(&t, (mp_digit) 1, &t) ); /* t = x+2*q*c0 -1 */ michael@0: /* t = floor((x+2qc0-1)/2qc0) = ceil(x/2qc0) */ michael@0: CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) ); michael@0: /* michael@0: ** step 11: if (2tqp0 +1 > 2**length), then t = ceiling(2**(length-1)/2qp0) michael@0: ** step 12: t = 2tqp0 +1. michael@0: ** michael@0: ** step 23: if (2tc0 +1 > 2**length), then t = ceiling(2**(length-1)/2c0) michael@0: ** step 24: t = 2tc0 +1. michael@0: */ michael@0: CHECK_MPI_OK( mp_2expt(&two_length_minus_1, length-1) ); michael@0: step_23: michael@0: CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) ); /* c = t*2qc0 */ michael@0: CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/ michael@0: if (mpl_significant_bits(&c) > length) { /* if c > 2**length */ michael@0: CHECK_MPI_OK( mp_sub_d(&c0_2, (mp_digit) 1, &t) ); /* t = 2qc0-1 */ michael@0: /* t = 2**(length-1) + 2qc0 -1 */ michael@0: CHECK_MPI_OK( mp_add(&two_length_minus_1,&t, &t) ); michael@0: /* t = floor((2**(length-1)+2qc0 -1)/2qco) michael@0: * = ceil(2**(lenght-2)/2qc0) */ michael@0: CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) ); michael@0: CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) ); michael@0: CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/ michael@0: } michael@0: /* Step 13/25 prime_gen_counter = prime_gen_counter + 1*/ michael@0: (*prime_gen_counter)++; michael@0: /* michael@0: ** Comment: Test the candidate prime c for primality; first pick an michael@0: ** integer a between 2 and c-2. michael@0: ** michael@0: ** Step 14/26 a=0 michael@0: */ michael@0: PORT_Memset(x, 0, sizeof(x)); /* use x for a */ michael@0: /* michael@0: ** Step 15/27 for i = 0 to iterations do michael@0: ** a = a + (HASH(prime_seed + i) * 2^(i*outlen)) michael@0: ** michael@0: ** NOTE: we reuse the x array for 'a' initially. michael@0: */ michael@0: for (i=0; i < iterations; i++) { michael@0: /* MAX_ST_SEED_BITS is bigger than prime_seed should get to */ michael@0: CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i, michael@0: MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen])); michael@0: } michael@0: /* Step 16/28 prime_seed = prime_seed + iterations + 1 */ michael@0: CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS, michael@0: prime_seed)); michael@0: /* Step 17/29 a = 2 + (a mod (c-3)). */ michael@0: CHECK_MPI_OK( mp_read_unsigned_octets(&a, x, iterations*hashlen) ); michael@0: CHECK_MPI_OK( mp_sub_d(&c, (mp_digit) 3, &z) ); /* z = c -3 */ michael@0: CHECK_MPI_OK( mp_mod(&a, &z, &a) ); /* a = a mod c -3 */ michael@0: CHECK_MPI_OK( mp_add_d(&a, (mp_digit) 2, &a) ); /* a = 2 + a mod c -3 */ michael@0: /* michael@0: ** Step 18 z = a**(2tq) mod p. michael@0: ** Step 30 z = a**(2t) mod c. michael@0: */ michael@0: CHECK_MPI_OK( mp_mul(&t, q, &z) ); /* z = tq */ michael@0: CHECK_MPI_OK( mp_add(&z, &z, &z) ); /* z = 2tq */ michael@0: CHECK_MPI_OK( mp_exptmod(&a, &z, &c, &z) ); /* z = a**(2tq) mod c */ michael@0: /* michael@0: ** Step 19 if (( 1 == GCD(z-1,p)) and ( 1 == z**p0 mod p )), then michael@0: ** Step 31 if (( 1 == GCD(z-1,c)) and ( 1 == z**c0 mod c )), then michael@0: */ michael@0: CHECK_MPI_OK( mp_sub_d(&z, (mp_digit) 1, &a) ); michael@0: CHECK_MPI_OK( mp_gcd(&a,&c,&a )); michael@0: if (mp_cmp_d(&a, (mp_digit)1) == 0) { michael@0: CHECK_MPI_OK( mp_exptmod(&z, c0, &c, &a) ); michael@0: if (mp_cmp_d(&a, (mp_digit)1) == 0) { michael@0: /* Step 31.1 prime = c */ michael@0: CHECK_MPI_OK( mp_copy(&c, prime) ); michael@0: /* michael@0: ** Step 31.2 return Success, prime, prime_seed, michael@0: ** prime_gen_counter michael@0: */ michael@0: rv = SECSuccess; michael@0: goto cleanup; michael@0: } michael@0: } michael@0: /* michael@0: ** Step 20/32 If (prime_gen_counter > 4 * length + old_counter then michael@0: ** return (FAILURE, 0, 0, 0). michael@0: ** NOTE: the test is reversed, so we fall through on failure to the michael@0: ** cleanup routine michael@0: */ michael@0: if (*prime_gen_counter < (4*length + old_counter)) { michael@0: /* Step 21/33 t = t + 1 */ michael@0: CHECK_MPI_OK( mp_add_d(&t, (mp_digit) 1, &t) ); michael@0: /* Step 22/34 Go to step 23/11 */ michael@0: goto step_23; michael@0: } michael@0: michael@0: /* if (prime_gencont > (4*length + old_counter), fall through to failure */ michael@0: rv = SECFailure; /* really is already set, but paranoia is good */ michael@0: michael@0: cleanup: michael@0: mp_clear(&c); michael@0: mp_clear(&c0_2); michael@0: mp_clear(&t); michael@0: mp_clear(&a); michael@0: mp_clear(&z); michael@0: mp_clear(&two_length_minus_1); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: if (rv == SECFailure) { michael@0: mp_zero(prime); michael@0: if (prime_seed->data) { michael@0: SECITEM_FreeItem(prime_seed, PR_FALSE); michael@0: } michael@0: *prime_gen_counter = 0; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /* michael@0: ** Perform steps from FIPS 186-3, Appendix C.6 michael@0: ** michael@0: ** This generates a provable prime from a seed michael@0: */ michael@0: SECStatus michael@0: makePrimefromSeedShaweTaylor( michael@0: HASH_HashType hashtype, /* selected Hashing algorithm */ michael@0: unsigned int length, /* input. Length of prime in bits. */ michael@0: const SECItem * input_seed, /* input. */ michael@0: mp_int * prime, /* output. */ michael@0: SECItem * prime_seed, /* output. */ michael@0: int * prime_gen_counter) /* output. */ michael@0: { michael@0: mp_int c; michael@0: mp_int c0; michael@0: mp_int one; michael@0: SECStatus rv = SECFailure; michael@0: int hashlen = HASH_ResultLen(hashtype); michael@0: int outlen = hashlen*PR_BITS_PER_BYTE; michael@0: int offset; michael@0: unsigned char bit, mask; michael@0: unsigned char x[HASH_LENGTH_MAX*2]; michael@0: mp_digit dummy; michael@0: mp_err err = MP_OKAY; michael@0: int i; michael@0: michael@0: MP_DIGITS(&c) = 0; michael@0: MP_DIGITS(&c0) = 0; michael@0: MP_DIGITS(&one) = 0; michael@0: CHECK_MPI_OK( mp_init(&c) ); michael@0: CHECK_MPI_OK( mp_init(&c0) ); michael@0: CHECK_MPI_OK( mp_init(&one) ); michael@0: michael@0: /* Step 1. if length < 2 then return (FAILURE, 0, 0, 0) */ michael@0: if (length < 2) { michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: /* Step 2. if length >= 33 then goto step 14 */ michael@0: if (length >= 33) { michael@0: mp_zero(&one); michael@0: CHECK_MPI_OK( mp_add_d(&one, (mp_digit) 1, &one) ); michael@0: michael@0: /* Step 14 (status, c0, prime_seed, prime_gen_counter) = michael@0: ** (ST_Random_Prime((ceil(length/2)+1, input_seed) michael@0: */ michael@0: rv = makePrimefromSeedShaweTaylor(hashtype, (length+1)/2+1, michael@0: input_seed, &c0, prime_seed, prime_gen_counter); michael@0: /* Step 15 if FAILURE is returned, return (FAILURE, 0, 0, 0). */ michael@0: if (rv != SECSuccess) { michael@0: goto cleanup; michael@0: } michael@0: /* Steps 16-34 */ michael@0: rv = makePrimefromPrimesShaweTaylor(hashtype,length, &c0, &one, michael@0: prime, prime_seed, prime_gen_counter); michael@0: goto cleanup; /* we're done, one way or the other */ michael@0: } michael@0: /* Step 3 prime_seed = input_seed */ michael@0: CHECK_SEC_OK(SECITEM_CopyItem(NULL, prime_seed, input_seed)); michael@0: /* Step 4 prime_gen_count = 0 */ michael@0: *prime_gen_counter = 0; michael@0: michael@0: step_5: michael@0: /* Step 5 c = Hash(prime_seed) xor Hash(prime_seed+1). */ michael@0: CHECK_SEC_OK(HASH_HashBuf(hashtype, x, prime_seed->data, prime_seed->len) ); michael@0: CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, 1, michael@0: MAX_ST_SEED_BITS, &x[hashlen]) ); michael@0: for (i=0; i < hashlen; i++) { michael@0: x[i] = x[i] ^ x[i+hashlen]; michael@0: } michael@0: /* Step 6 c = 2**length-1 + c mod 2**length-1 */ michael@0: /* This step mathematically sets the high bit and clears out michael@0: ** all the other bits higher than length. Right now c is stored michael@0: ** in the x array, MSB first. The above formula gives us a c which michael@0: ** is length bytes long and has the high bit set. We also know that michael@0: ** length < outlen since the smallest outlen is 160 bits and the largest michael@0: ** length at this point is 32 bits. So first we find the offset in bytes michael@0: ** into the array where the high bit is. michael@0: */ michael@0: offset = (outlen - length)/PR_BITS_PER_BYTE; michael@0: /* now we want to set the 'high bit'. We have to calculate this since michael@0: * length may not be a multiple of 8.*/ michael@0: bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */ michael@0: /* we need to zero out the rest of the bits in the byte above */ michael@0: mask = (bit-1); michael@0: /* now we set it */ michael@0: x[offset] = (mask & x[offset]) | bit; michael@0: /* Step 7 c = c*floor(c/2) + 1 */ michael@0: /* set the low bit. much easier to find (the end of the array) */ michael@0: x[hashlen-1] |= 1; michael@0: /* now that we've set our bits, we can create our candidate "c" */ michael@0: CHECK_MPI_OK( mp_read_unsigned_octets(&c, &x[offset], hashlen-offset) ); michael@0: /* Step 8 prime_gen_counter = prime_gen_counter + 1 */ michael@0: (*prime_gen_counter)++; michael@0: /* Step 9 prime_seed = prime_seed + 2 */ michael@0: CHECK_SEC_OK(addToSeed(prime_seed, 2, MAX_ST_SEED_BITS, prime_seed)); michael@0: /* Step 10 Perform deterministic primality test on c. For example, since michael@0: ** c is small, it's primality can be tested by trial division, See michael@0: ** See Appendic C.7. michael@0: ** michael@0: ** We in fact test with trial division. mpi has a built int trial divider michael@0: ** that divides all divisors up to 2^16. michael@0: */ michael@0: if (prime_tab[prime_tab_size-1] < 0xFFF1) { michael@0: /* we aren't testing all the primes between 0 and 2^16, we really michael@0: * can't use this construction. Just fail. */ michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: dummy = prime_tab_size; michael@0: err = mpp_divis_primes(&c, &dummy); michael@0: /* Step 11 if c is prime then */ michael@0: if (err == MP_NO) { michael@0: /* Step 11.1 prime = c */ michael@0: CHECK_MPI_OK( mp_copy(&c, prime) ); michael@0: /* Step 11.2 return SUCCESS prime, prime_seed, prime_gen_counter */ michael@0: err = MP_OKAY; michael@0: rv = SECSuccess; michael@0: goto cleanup; michael@0: } else if (err != MP_YES) { michael@0: goto cleanup; /* function failed, bail out */ michael@0: } else { michael@0: /* reset mp_err */ michael@0: err = MP_OKAY; michael@0: } michael@0: /* michael@0: ** Step 12 if (prime_gen_counter > (4*len)) michael@0: ** then return (FAILURE, 0, 0, 0)) michael@0: ** Step 13 goto step 5 michael@0: */ michael@0: if (*prime_gen_counter <= (4*length)) { michael@0: goto step_5; michael@0: } michael@0: /* if (prime_gencont > 4*length), fall through to failure */ michael@0: rv = SECFailure; /* really is already set, but paranoia is good */ michael@0: michael@0: cleanup: michael@0: mp_clear(&c); michael@0: mp_clear(&c0); michael@0: mp_clear(&one); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: if (rv == SECFailure) { michael@0: mp_zero(prime); michael@0: if (prime_seed->data) { michael@0: SECITEM_FreeItem(prime_seed, PR_FALSE); michael@0: } michael@0: *prime_gen_counter = 0; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: michael@0: /* michael@0: * Find a Q and algorithm from Seed. michael@0: */ michael@0: static SECStatus michael@0: findQfromSeed( michael@0: unsigned int L, /* input. Length of p in bits. */ michael@0: unsigned int N, /* input. Length of q in bits. */ michael@0: unsigned int g, /* input. Length of seed in bits. */ michael@0: const SECItem * seed, /* input. */ michael@0: mp_int * Q, /* input. */ michael@0: mp_int * Q_, /* output. */ michael@0: int * qseed_len, /* output */ michael@0: HASH_HashType *hashtypePtr, /* output. Hash uses */ michael@0: pqgGenType *typePtr) /* output. Generation Type used */ michael@0: { michael@0: HASH_HashType hashtype; michael@0: SECItem firstseed = { 0, 0, 0 }; michael@0: SECItem qseed = { 0, 0, 0 }; michael@0: SECStatus rv; michael@0: michael@0: *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */ michael@0: michael@0: /* handle legacy small DSA first can only be FIPS186_1_TYPE */ michael@0: if (L < 1024) { michael@0: rv =makeQfromSeed(g,seed,Q_); michael@0: if ((rv == SECSuccess) && (mp_cmp(Q,Q_) == 0)) { michael@0: *hashtypePtr = HASH_AlgSHA1; michael@0: *typePtr = FIPS186_1_TYPE; michael@0: return SECSuccess; michael@0: } michael@0: return SECFailure; michael@0: } michael@0: /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try michael@0: * them both */ michael@0: if (L == 1024) { michael@0: rv = makeQfromSeed(g,seed,Q_); michael@0: if (rv == SECSuccess) { michael@0: if (mp_cmp(Q,Q_) == 0) { michael@0: *hashtypePtr = HASH_AlgSHA1; michael@0: *typePtr = FIPS186_1_TYPE; michael@0: return SECSuccess; michael@0: } michael@0: } michael@0: /* fall through for FIPS186_3 types */ michael@0: } michael@0: /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3 michael@0: * with appropriate hash types */ michael@0: for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; michael@0: hashtype=getNextHash(hashtype)) { michael@0: rv = makeQ2fromSeed(hashtype, N, seed, Q_); michael@0: if (rv != SECSuccess) { michael@0: continue; michael@0: } michael@0: if (mp_cmp(Q,Q_) == 0) { michael@0: *hashtypePtr = hashtype; michael@0: *typePtr = FIPS186_3_TYPE; michael@0: return SECSuccess; michael@0: } michael@0: } michael@0: /* michael@0: * OK finally try FIPS186_3 Shawe-Taylor michael@0: */ michael@0: firstseed = *seed; michael@0: firstseed.len = seed->len/3; michael@0: for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; michael@0: hashtype=getNextHash(hashtype)) { michael@0: int count; michael@0: michael@0: rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_, michael@0: &qseed, &count); michael@0: if (rv != SECSuccess) { michael@0: continue; michael@0: } michael@0: if (mp_cmp(Q,Q_) == 0) { michael@0: /* check qseed as well... */ michael@0: int offset = seed->len - qseed.len; michael@0: if ((offset < 0) || michael@0: (PORT_Memcmp(&seed->data[offset],qseed.data,qseed.len) != 0)) { michael@0: /* we found q, but the seeds don't match. This isn't an michael@0: * accident, someone has been tweeking with the seeds, just michael@0: * fail a this point. */ michael@0: SECITEM_FreeItem(&qseed,PR_FALSE); michael@0: return SECFailure; michael@0: } michael@0: *qseed_len = qseed.len; michael@0: *hashtypePtr = hashtype; michael@0: *typePtr = FIPS186_3_ST_TYPE; michael@0: SECITEM_FreeItem(&qseed, PR_FALSE); michael@0: return SECSuccess; michael@0: } michael@0: SECITEM_FreeItem(&qseed, PR_FALSE); michael@0: } michael@0: /* no hash algorithms found which match seed to Q, fail */ michael@0: return SECFailure; michael@0: } michael@0: michael@0: michael@0: michael@0: /* michael@0: ** Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2. michael@0: ** which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2 michael@0: ** Generate P from Q, seed, L, and offset. michael@0: */ michael@0: static SECStatus michael@0: makePfromQandSeed( michael@0: HASH_HashType hashtype, /* selected Hashing algorithm */ michael@0: unsigned int L, /* Length of P in bits. Per FIPS 186. */ michael@0: unsigned int N, /* Length of Q in bits. Per FIPS 186. */ michael@0: unsigned int offset, /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */ michael@0: unsigned int seedlen, /* input. Length of seed in bits. (g in 186-1)*/ michael@0: const SECItem * seed, /* input. */ michael@0: const mp_int * Q, /* input. */ michael@0: mp_int * P) /* output. */ michael@0: { michael@0: unsigned int j; /* Per FIPS 186-3 App. A.1.1.2 (k in 186-1)*/ michael@0: unsigned int n; /* Per FIPS 186, appendix 2.2. */ michael@0: mp_digit b; /* Per FIPS 186, appendix 2.2. */ michael@0: unsigned int outlen; /* Per FIPS 186-3 App. A.1.1.2 */ michael@0: unsigned int hashlen; /* outlen in bytes */ michael@0: unsigned char V_j[HASH_LENGTH_MAX]; michael@0: mp_int W, X, c, twoQ, V_n, tmp; michael@0: mp_err err = MP_OKAY; michael@0: SECStatus rv = SECSuccess; michael@0: /* Initialize bignums */ michael@0: MP_DIGITS(&W) = 0; michael@0: MP_DIGITS(&X) = 0; michael@0: MP_DIGITS(&c) = 0; michael@0: MP_DIGITS(&twoQ) = 0; michael@0: MP_DIGITS(&V_n) = 0; michael@0: MP_DIGITS(&tmp) = 0; michael@0: CHECK_MPI_OK( mp_init(&W) ); michael@0: CHECK_MPI_OK( mp_init(&X) ); michael@0: CHECK_MPI_OK( mp_init(&c) ); michael@0: CHECK_MPI_OK( mp_init(&twoQ) ); michael@0: CHECK_MPI_OK( mp_init(&tmp) ); michael@0: CHECK_MPI_OK( mp_init(&V_n) ); michael@0: michael@0: hashlen = HASH_ResultLen(hashtype); michael@0: outlen = hashlen*PR_BITS_PER_BYTE; michael@0: michael@0: /* L - 1 = n*outlen + b */ michael@0: n = (L - 1) / outlen; michael@0: b = (L - 1) % outlen; michael@0: michael@0: /* ****************************************************************** michael@0: ** Step 11.1 (Step 7 in 186-1) michael@0: ** "for j = 0 ... n let michael@0: ** V_j = SHA[(SEED + offset + j) mod 2**seedlen]." michael@0: ** michael@0: ** Step 11.2 (Step 8 in 186-1) michael@0: ** "W = V_0 + (V_1 * 2**outlen) + ... + (V_n-1 * 2**((n-1)*outlen)) michael@0: ** + ((V_n mod 2**b) * 2**(n*outlen)) michael@0: */ michael@0: for (j=0; j= 0) /* H >= P-1 */ michael@0: CHECK_MPI_OK( mp_sub(H, &pm1, H) ); /* H = H mod (P-1) */ michael@0: /* Let b = 2**n (smallest power of 2 greater than P). michael@0: ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1 michael@0: ** so the above operation safely computes H mod (P-1) michael@0: */ michael@0: /* Check for H = to 0 or 1. Regen H if so. (Regen means return error). */ michael@0: if (mp_cmp_d(H, 1) <= 0) { michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: /* Compute G, according to the equation G = (H ** ((P-1)/Q)) mod P */ michael@0: CHECK_MPI_OK( mp_div(&pm1, Q, &exp, NULL) ); /* exp = (P-1)/Q */ michael@0: CHECK_MPI_OK( mp_exptmod(H, &exp, P, G) ); /* G = H ** exp mod P */ michael@0: /* Check for G == 0 or G == 1, return error if so. */ michael@0: if (mp_cmp_d(G, 1) <= 0) { michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: *passed = PR_TRUE; michael@0: cleanup: michael@0: mp_clear(&exp); michael@0: mp_clear(&pm1); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /* michael@0: ** Generate G from seed, index, P, and Q. michael@0: */ michael@0: static SECStatus michael@0: makeGfromIndex(HASH_HashType hashtype, michael@0: const mp_int *P, /* input. */ michael@0: const mp_int *Q, /* input. */ michael@0: const SECItem *seed, /* input. */ michael@0: unsigned char index, /* input. */ michael@0: mp_int *G) /* input/output */ michael@0: { michael@0: mp_int e, pm1, W; michael@0: unsigned int count; michael@0: unsigned char data[HASH_LENGTH_MAX]; michael@0: unsigned int len; michael@0: mp_err err = MP_OKAY; michael@0: SECStatus rv = SECSuccess; michael@0: const SECHashObject *hashobj; michael@0: void *hashcx = NULL; michael@0: michael@0: MP_DIGITS(&e) = 0; michael@0: MP_DIGITS(&pm1) = 0; michael@0: MP_DIGITS(&W) = 0; michael@0: CHECK_MPI_OK( mp_init(&e) ); michael@0: CHECK_MPI_OK( mp_init(&pm1) ); michael@0: CHECK_MPI_OK( mp_init(&W) ); michael@0: michael@0: /* initialize our hash stuff */ michael@0: hashobj = HASH_GetRawHashObject(hashtype); michael@0: if (hashobj == NULL) { michael@0: /* shouldn't happen */ michael@0: PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: hashcx = hashobj->create(); michael@0: if (hashcx == NULL) { michael@0: rv = SECFailure; michael@0: goto cleanup; michael@0: } michael@0: michael@0: CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) ); /* P - 1 */ michael@0: /* Step 3 e = (p-1)/q */ michael@0: CHECK_MPI_OK( mp_div(&pm1, Q, &e, NULL) ); /* e = (P-1)/Q */ michael@0: /* Steps 4, 5, and 6 */ michael@0: /* count is a 16 bit value in the spec. We actually represent count michael@0: * as more than 16 bits so we can easily detect the 16 bit overflow */ michael@0: #define MAX_COUNT 0x10000 michael@0: for (count = 1; count < MAX_COUNT; count++) { michael@0: /* step 7 michael@0: * U = domain_param_seed || "ggen" || index || count michael@0: * step 8 michael@0: * W = HASH(U) michael@0: */ michael@0: hashobj->begin(hashcx); michael@0: hashobj->update(hashcx,seed->data,seed->len); michael@0: hashobj->update(hashcx, (unsigned char *)"ggen", 4); michael@0: hashobj->update(hashcx,&index, 1); michael@0: data[0] = (count >> 8) & 0xff; michael@0: data[1] = count & 0xff; michael@0: hashobj->update(hashcx, data, 2); michael@0: hashobj->end(hashcx, data, &len, sizeof(data)); michael@0: OCTETS_TO_MPINT(data, &W, len); michael@0: /* step 9. g = W**e mod p */ michael@0: CHECK_MPI_OK( mp_exptmod(&W, &e, P, G) ); michael@0: /* step 10. if (g < 2) then goto step 5 */ michael@0: /* NOTE: this weird construct is to keep the flow according to the spec. michael@0: * the continue puts us back to step 5 of the for loop */ michael@0: if (mp_cmp_d(G, 2) < 0) { michael@0: continue; michael@0: } michael@0: break; /* step 11 follows step 10 if the test condition is false */ michael@0: } michael@0: if (count >= MAX_COUNT) { michael@0: rv = SECFailure; /* last part of step 6 */ michael@0: } michael@0: /* step 11. michael@0: * return valid G */ michael@0: cleanup: michael@0: PORT_Memset(data, 0, sizeof(data)); michael@0: if (hashcx) { michael@0: hashobj->destroy(hashcx, PR_TRUE); michael@0: } michael@0: mp_clear(&e); michael@0: mp_clear(&pm1); michael@0: mp_clear(&W); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /* This code uses labels and gotos, so that it can follow the numbered michael@0: ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely, michael@0: ** and so that the correctness of this code can be easily verified. michael@0: ** So, please forgive the ugly c code. michael@0: **/ michael@0: static SECStatus michael@0: pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type, michael@0: unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy) michael@0: { michael@0: unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ michael@0: unsigned int b; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ michael@0: unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/ michael@0: unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ michael@0: unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ michael@0: unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */ michael@0: unsigned int maxCount; michael@0: HASH_HashType hashtype; michael@0: SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ michael@0: PLArenaPool *arena = NULL; michael@0: PQGParams *params = NULL; michael@0: PQGVerify *verify = NULL; michael@0: PRBool passed; michael@0: SECItem hit = { 0, 0, 0 }; michael@0: SECItem firstseed = { 0, 0, 0 }; michael@0: SECItem qseed = { 0, 0, 0 }; michael@0: SECItem pseed = { 0, 0, 0 }; michael@0: mp_int P, Q, G, H, l, p0; michael@0: mp_err err = MP_OKAY; michael@0: SECStatus rv = SECFailure; michael@0: int iterations = 0; michael@0: michael@0: michael@0: /* Step 1. L and N already checked by caller*/ michael@0: /* Step 2. if (seedlen < N) return INVALID; */ michael@0: if (seedBytes < N/PR_BITS_PER_BYTE || !pParams || !pVfy) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: /* Initialize an arena for the params. */ michael@0: arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); michael@0: if (!arena) { michael@0: PORT_SetError(SEC_ERROR_NO_MEMORY); michael@0: return SECFailure; michael@0: } michael@0: params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams)); michael@0: if (!params) { michael@0: PORT_SetError(SEC_ERROR_NO_MEMORY); michael@0: PORT_FreeArena(arena, PR_TRUE); michael@0: return SECFailure; michael@0: } michael@0: params->arena = arena; michael@0: /* Initialize an arena for the verify. */ michael@0: arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); michael@0: if (!arena) { michael@0: PORT_SetError(SEC_ERROR_NO_MEMORY); michael@0: PORT_FreeArena(params->arena, PR_TRUE); michael@0: return SECFailure; michael@0: } michael@0: verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify)); michael@0: if (!verify) { michael@0: PORT_SetError(SEC_ERROR_NO_MEMORY); michael@0: PORT_FreeArena(arena, PR_TRUE); michael@0: PORT_FreeArena(params->arena, PR_TRUE); michael@0: return SECFailure; michael@0: } michael@0: verify->arena = arena; michael@0: seed = &verify->seed; michael@0: arena = NULL; michael@0: /* Initialize bignums */ michael@0: MP_DIGITS(&P) = 0; michael@0: MP_DIGITS(&Q) = 0; michael@0: MP_DIGITS(&G) = 0; michael@0: MP_DIGITS(&H) = 0; michael@0: MP_DIGITS(&l) = 0; michael@0: MP_DIGITS(&p0) = 0; michael@0: CHECK_MPI_OK( mp_init(&P) ); michael@0: CHECK_MPI_OK( mp_init(&Q) ); michael@0: CHECK_MPI_OK( mp_init(&G) ); michael@0: CHECK_MPI_OK( mp_init(&H) ); michael@0: CHECK_MPI_OK( mp_init(&l) ); michael@0: CHECK_MPI_OK( mp_init(&p0) ); michael@0: michael@0: /* Select Hash and Compute lengths. */ michael@0: /* getFirstHash gives us the smallest acceptable hash for this key michael@0: * strength */ michael@0: hashtype = getFirstHash(L,N); michael@0: outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE; michael@0: michael@0: /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */ michael@0: n = (L - 1) / outlen; michael@0: /* Step 4: b = L -1 - (n*outlen); (same as n = (L-1) mod outlen) */ michael@0: b = (L - 1) % outlen; michael@0: seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */ michael@0: step_5: michael@0: /* ****************************************************************** michael@0: ** Step 5. (Step 1 in 186-1) michael@0: ** "Choose an abitrary sequence of at least N bits and call it SEED. michael@0: ** Let g be the length of SEED in bits." michael@0: */ michael@0: if (++iterations > MAX_ITERATIONS) { /* give up after a while */ michael@0: PORT_SetError(SEC_ERROR_NEED_RANDOM); michael@0: goto cleanup; michael@0: } michael@0: seed->len = seedBytes; michael@0: CHECK_SEC_OK( getPQseed(seed, verify->arena) ); michael@0: /* ****************************************************************** michael@0: ** Step 6. (Step 2 in 186-1) michael@0: ** michael@0: ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]. (186-1)" michael@0: ** "Compute U = HASH[SEED] 2**(N-1). (186-3)" michael@0: ** michael@0: ** Step 7. (Step 3 in 186-1) michael@0: ** "Form Q from U by setting the most signficant bit (the 2**159 bit) michael@0: ** and the least signficant bit to 1. In terms of boolean operations, michael@0: ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160. (186-1)" michael@0: ** michael@0: ** "q = 2**(N-1) + U + 1 - (U mod 2) (186-3) michael@0: ** michael@0: ** Note: Both formulations are the same for U < 2**(N-1) and N=160 michael@0: ** michael@0: ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block michael@0: ** FIPS186_3_ST_TYPE. michael@0: */ michael@0: if (type == FIPS186_1_TYPE) { michael@0: CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) ); michael@0: } else if (type == FIPS186_3_TYPE) { michael@0: CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) ); michael@0: } else { michael@0: /* FIPS186_3_ST_TYPE */ michael@0: int qgen_counter, pgen_counter; michael@0: michael@0: /* Step 1 (L,N) already checked for acceptability */ michael@0: michael@0: firstseed = *seed; michael@0: qgen_counter = 0; michael@0: /* Step 2. Use N and firstseed to generate random prime q michael@0: * using Apendix C.6 */ michael@0: CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q, michael@0: &qseed, &qgen_counter) ); michael@0: /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0 michael@0: * using Appendix C.6 */ michael@0: pgen_counter = 0; michael@0: CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1, michael@0: &qseed, &p0, &pseed, &pgen_counter) ); michael@0: /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */ michael@0: CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L, michael@0: &p0, &Q, &P, &pseed, &pgen_counter) ); michael@0: michael@0: /* combine all the seeds */ michael@0: seed->len = firstseed.len +qseed.len + pseed.len; michael@0: seed->data = PORT_ArenaZAlloc(verify->arena, seed->len); michael@0: if (seed->data == NULL) { michael@0: goto cleanup; michael@0: } michael@0: PORT_Memcpy(seed->data, firstseed.data, firstseed.len); michael@0: PORT_Memcpy(seed->data+firstseed.len, pseed.data, pseed.len); michael@0: PORT_Memcpy(seed->data+firstseed.len+pseed.len, qseed.data, qseed.len); michael@0: counter = 0 ; /* (qgen_counter << 16) | pgen_counter; */ michael@0: michael@0: /* we've generated both P and Q now, skip to generating G */ michael@0: goto generate_G; michael@0: } michael@0: /* ****************************************************************** michael@0: ** Step 8. (Step 4 in 186-1) michael@0: ** "Use a robust primality testing algorithm to test whether q is prime." michael@0: ** michael@0: ** Appendix 2.1 states that a Rabin test with at least 50 iterations michael@0: ** "will give an acceptable probability of error." michael@0: */ michael@0: /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/ michael@0: err = mpp_pprime(&Q, prime_testcount_q(L,N)); michael@0: passed = (err == MP_YES) ? SECSuccess : SECFailure; michael@0: /* ****************************************************************** michael@0: ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)." michael@0: */ michael@0: if (passed != SECSuccess) michael@0: goto step_5; michael@0: /* ****************************************************************** michael@0: ** Step 10. michael@0: ** offset = 1; michael@0: **( Step 6b 186-1)"Let counter = 0 and offset = 2." michael@0: */ michael@0: offset = (type == FIPS186_1_TYPE) ? 2 : 1; michael@0: /* michael@0: ** Step 11. (Step 6a,13a,14 in 186-1) michael@0: ** For counter - 0 to (4L-1) do michael@0: ** michael@0: */ michael@0: maxCount = L >= 1024 ? (4*L - 1) : 4095; michael@0: for (counter = 0; counter <= maxCount; counter++) { michael@0: /* ****************************************************************** michael@0: ** Step 11.1 (Step 7 in 186-1) michael@0: ** "for j = 0 ... n let michael@0: ** V_j = HASH[(SEED + offset + j) mod 2**seedlen]." michael@0: ** michael@0: ** Step 11.2 (Step 8 in 186-1) michael@0: ** "W = V_0 + V_1*2**outlen+...+ V_n-1 * 2**((n-1)*outlen) + michael@0: ** ((Vn* mod 2**b)*2**(n*outlen))" michael@0: ** Step 11.3 (Step 8 in 186-1) michael@0: ** "X = W + 2**(L-1) michael@0: ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L." michael@0: ** michael@0: ** Step 11.4 (Step 9 in 186-1). michael@0: ** "c = X mod 2q" michael@0: ** michael@0: ** Step 11.5 (Step 9 in 186-1). michael@0: ** " p = X - (c - 1). michael@0: ** Note that p is congruent to 1 mod 2q." michael@0: */ michael@0: CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, seedlen, michael@0: seed, &Q, &P) ); michael@0: /************************************************************* michael@0: ** Step 11.6. (Step 10 in 186-1) michael@0: ** "if p < 2**(L-1), then goto step 11.9. (step 13 in 186-1)" michael@0: */ michael@0: CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */ michael@0: if (mp_cmp(&P, &l) < 0) michael@0: goto step_11_9; michael@0: /************************************************************ michael@0: ** Step 11.7 (step 11 in 186-1) michael@0: ** "Perform a robust primality test on p." michael@0: */ michael@0: /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/ michael@0: err = mpp_pprime(&P, prime_testcount_p(L, N)); michael@0: passed = (err == MP_YES) ? SECSuccess : SECFailure; michael@0: /* ****************************************************************** michael@0: ** Step 11.8. "If p is determined to be primed return VALID michael@0: ** values of p, q, seed and counter." michael@0: */ michael@0: if (passed == SECSuccess) michael@0: break; michael@0: step_11_9: michael@0: /* ****************************************************************** michael@0: ** Step 11.9. "offset = offset + n + 1." michael@0: */ michael@0: offset += n + 1; michael@0: } michael@0: /* ****************************************************************** michael@0: ** Step 12. "goto step 5." michael@0: ** michael@0: ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8 michael@0: ** and now need to return p,q, seed, and counter. michael@0: */ michael@0: if (counter > maxCount) michael@0: goto step_5; michael@0: michael@0: generate_G: michael@0: /* ****************************************************************** michael@0: ** returning p, q, seed and counter michael@0: */ michael@0: if (type == FIPS186_1_TYPE) { michael@0: /* Generate g, This is called the "Unverifiable Generation of g michael@0: * in FIPA186-3 Appedix A.2.1. For compatibility we maintain michael@0: * this version of the code */ michael@0: SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */ michael@0: if (!hit.data) goto cleanup; michael@0: do { michael@0: /* loop generate h until 1 1 */ michael@0: CHECK_SEC_OK( generate_h_candidate(&hit, &H) ); michael@0: CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) ); michael@0: } while (passed != PR_TRUE); michael@0: MPINT_TO_SECITEM(&H, &verify->h, verify->arena); michael@0: } else { michael@0: unsigned char index = 1; /* default to 1 */ michael@0: verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1); michael@0: if (verify->h.data == NULL) { goto cleanup; } michael@0: verify->h.len = 1; michael@0: verify->h.data[0] = index; michael@0: /* Generate g, using the FIPS 186-3 Appendix A.23 */ michael@0: CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G) ); michael@0: } michael@0: /* All generation is done. Now, save the PQG params. */ michael@0: MPINT_TO_SECITEM(&P, ¶ms->prime, params->arena); michael@0: MPINT_TO_SECITEM(&Q, ¶ms->subPrime, params->arena); michael@0: MPINT_TO_SECITEM(&G, ¶ms->base, params->arena); michael@0: verify->counter = counter; michael@0: *pParams = params; michael@0: *pVfy = verify; michael@0: cleanup: michael@0: if (pseed.data) { michael@0: PORT_Free(pseed.data); michael@0: } michael@0: if (qseed.data) { michael@0: PORT_Free(qseed.data); michael@0: } michael@0: mp_clear(&P); michael@0: mp_clear(&Q); michael@0: mp_clear(&G); michael@0: mp_clear(&H); michael@0: mp_clear(&l); michael@0: mp_clear(&p0); michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: if (rv) { michael@0: PORT_FreeArena(params->arena, PR_TRUE); michael@0: PORT_FreeArena(verify->arena, PR_TRUE); michael@0: } michael@0: if (hit.data) { michael@0: SECITEM_FreeItem(&hit, PR_FALSE); michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: SECStatus michael@0: PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy) michael@0: { michael@0: unsigned int L; /* Length of P in bits. Per FIPS 186. */ michael@0: unsigned int seedBytes; michael@0: michael@0: if (j > 8 || !pParams || !pVfy) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: L = 512 + (j * 64); /* bits in P */ michael@0: seedBytes = L/8; michael@0: return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes, michael@0: pParams, pVfy); michael@0: } michael@0: michael@0: SECStatus michael@0: PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes, michael@0: PQGParams **pParams, PQGVerify **pVfy) michael@0: { michael@0: unsigned int L; /* Length of P in bits. Per FIPS 186. */ michael@0: michael@0: if (j > 8 || !pParams || !pVfy) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: L = 512 + (j * 64); /* bits in P */ michael@0: return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes, michael@0: pParams, pVfy); michael@0: } michael@0: michael@0: SECStatus michael@0: PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes, michael@0: PQGParams **pParams, PQGVerify **pVfy) michael@0: { michael@0: if (N == 0) { michael@0: N = pqg_get_default_N(L); michael@0: } michael@0: if (seedBytes == 0) { michael@0: /* seedBytes == L/8 for probable primes, N/8 for Shawe-Taylor Primes */ michael@0: seedBytes = N/8; michael@0: } michael@0: if (pqg_validate_dsa2(L,N) != SECSuccess) { michael@0: /* error code already set */ michael@0: return SECFailure; michael@0: } michael@0: return pqg_ParamGen(L, N, FIPS186_3_ST_TYPE, seedBytes, pParams, pVfy); michael@0: } michael@0: michael@0: michael@0: /* michael@0: * verify can use vfy structures returned from either FIPS186-1 or michael@0: * FIPS186-2, and can handle differences in selected Hash functions to michael@0: * generate the parameters. michael@0: */ michael@0: SECStatus michael@0: PQG_VerifyParams(const PQGParams *params, michael@0: const PQGVerify *vfy, SECStatus *result) michael@0: { michael@0: SECStatus rv = SECSuccess; michael@0: unsigned int g, n, L, N, offset, outlen; michael@0: mp_int p0, P, Q, G, P_, Q_, G_, r, h; michael@0: mp_err err = MP_OKAY; michael@0: int j; michael@0: unsigned int counter_max = 0; /* handle legacy L < 1024 */ michael@0: int qseed_len; michael@0: SECItem pseed_ = {0, 0, 0}; michael@0: HASH_HashType hashtype; michael@0: pqgGenType type; michael@0: michael@0: #define CHECKPARAM(cond) \ michael@0: if (!(cond)) { \ michael@0: *result = SECFailure; \ michael@0: goto cleanup; \ michael@0: } michael@0: if (!params || !vfy || !result) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: /* always need at least p, q, and seed for any meaningful check */ michael@0: if ((params->prime.len == 0) || (params->subPrime.len == 0) || michael@0: (vfy->seed.len == 0)) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: /* we want to either check PQ or G or both. If we don't have G, make michael@0: * sure we have count so we can check P. */ michael@0: if ((params->base.len == 0) && (vfy->counter == -1)) { michael@0: PORT_SetError(SEC_ERROR_INVALID_ARGS); michael@0: return SECFailure; michael@0: } michael@0: michael@0: MP_DIGITS(&p0) = 0; michael@0: MP_DIGITS(&P) = 0; michael@0: MP_DIGITS(&Q) = 0; michael@0: MP_DIGITS(&G) = 0; michael@0: MP_DIGITS(&P_) = 0; michael@0: MP_DIGITS(&Q_) = 0; michael@0: MP_DIGITS(&G_) = 0; michael@0: MP_DIGITS(&r) = 0; michael@0: MP_DIGITS(&h) = 0; michael@0: CHECK_MPI_OK( mp_init(&p0) ); michael@0: CHECK_MPI_OK( mp_init(&P) ); michael@0: CHECK_MPI_OK( mp_init(&Q) ); michael@0: CHECK_MPI_OK( mp_init(&G) ); michael@0: CHECK_MPI_OK( mp_init(&P_) ); michael@0: CHECK_MPI_OK( mp_init(&Q_) ); michael@0: CHECK_MPI_OK( mp_init(&G_) ); michael@0: CHECK_MPI_OK( mp_init(&r) ); michael@0: CHECK_MPI_OK( mp_init(&h) ); michael@0: *result = SECSuccess; michael@0: SECITEM_TO_MPINT(params->prime, &P); michael@0: SECITEM_TO_MPINT(params->subPrime, &Q); michael@0: /* if G isn't specified, just check P and Q */ michael@0: if (params->base.len != 0) { michael@0: SECITEM_TO_MPINT(params->base, &G); michael@0: } michael@0: /* 1. Check (L,N) pair */ michael@0: N = mpl_significant_bits(&Q); michael@0: L = mpl_significant_bits(&P); michael@0: if (L < 1024) { michael@0: /* handle DSA1 pqg parameters with less thatn 1024 bits*/ michael@0: CHECKPARAM( N == DSA1_Q_BITS ); michael@0: j = PQG_PBITS_TO_INDEX(L); michael@0: CHECKPARAM( j >= 0 && j <= 8 ); michael@0: counter_max = 4096; michael@0: } else { michael@0: /* handle DSA2 parameters (includes DSA1, 1024 bits) */ michael@0: CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess); michael@0: counter_max = 4*L; michael@0: } michael@0: /* 3. G < P */ michael@0: if (params->base.len != 0) { michael@0: CHECKPARAM( mp_cmp(&G, &P) < 0 ); michael@0: } michael@0: /* 4. P % Q == 1 */ michael@0: CHECK_MPI_OK( mp_mod(&P, &Q, &r) ); michael@0: CHECKPARAM( mp_cmp_d(&r, 1) == 0 ); michael@0: /* 5. Q is prime */ michael@0: CHECKPARAM( mpp_pprime(&Q, prime_testcount_q(L,N)) == MP_YES ); michael@0: /* 6. P is prime */ michael@0: CHECKPARAM( mpp_pprime(&P, prime_testcount_p(L,N)) == MP_YES ); michael@0: /* Steps 7-12 are done only if the optional PQGVerify is supplied. */ michael@0: /* continue processing P */ michael@0: /* 7. counter < 4*L */ michael@0: CHECKPARAM( (vfy->counter == -1) || (vfy->counter < counter_max) ); michael@0: /* 8. g >= N and g < 2*L (g is length of seed in bits) */ michael@0: g = vfy->seed.len * 8; michael@0: CHECKPARAM( g >= N && g < counter_max/2 ); michael@0: /* 9. Q generated from SEED matches Q in PQGParams. */ michael@0: /* This function checks all possible hash and generation types to michael@0: * find a Q_ which matches Q. */ michael@0: CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len, michael@0: &hashtype, &type) == SECSuccess ); michael@0: CHECKPARAM( mp_cmp(&Q, &Q_) == 0 ); michael@0: if (type == FIPS186_3_ST_TYPE) { michael@0: SECItem qseed = { 0, 0, 0 }; michael@0: SECItem pseed = { 0, 0, 0 }; michael@0: int first_seed_len; michael@0: int pgen_counter = 0; michael@0: michael@0: /* extract pseed and qseed from domain_parameter_seed, which is michael@0: * first_seed || pseed || qseed. qseed is first_seed + small_integer michael@0: * pseed is qseed + small_integer. This means most of the time michael@0: * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or michael@0: * pseed.len will be one greater than first_seed.len, so we can michael@0: * depend on the fact that michael@0: * first_seed.len = floor(domain_parameter_seed.len/3). michael@0: * findQfromSeed returned qseed.len, so we can calculate pseed.len as michael@0: * pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len michael@0: * this is probably over kill, since 99.999% of the time they will all michael@0: * be equal. michael@0: * michael@0: * With the lengths, we can now find the offsets; michael@0: * first_seed.data = domain_parameter_seed.data + 0 michael@0: * pseed.data = domain_parameter_seed.data + first_seed.len michael@0: * qseed.data = domain_parameter_seed.data michael@0: * + domain_paramter_seed.len - qseed.len michael@0: * michael@0: */ michael@0: first_seed_len = vfy->seed.len/3; michael@0: CHECKPARAM(qseed_len < vfy->seed.len); michael@0: CHECKPARAM(first_seed_len*8 > N-1); michael@0: CHECKPARAM(first_seed_len+qseed_len < vfy->seed.len); michael@0: qseed.len = qseed_len; michael@0: qseed.data = vfy->seed.data + vfy->seed.len - qseed.len; michael@0: pseed.len = vfy->seed.len - (first_seed_len+qseed_len); michael@0: pseed.data = vfy->seed.data + first_seed_len; michael@0: michael@0: /* michael@0: * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed michael@0: * above in our initial checks, Step 2 was completed by michael@0: * findQfromSeed */ michael@0: michael@0: /* Step 3 (status, c0, prime_seed, prime_gen_counter) = michael@0: ** (ST_Random_Prime((ceil(length/2)+1, input_seed) michael@0: */ michael@0: CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1, michael@0: &qseed, &p0, &pseed_, &pgen_counter) ); michael@0: /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */ michael@0: CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L, michael@0: &p0, &Q_, &P_, &pseed_, &pgen_counter) ); michael@0: CHECKPARAM( mp_cmp(&P, &P_) == 0 ); michael@0: /* make sure pseed wasn't tampered with (since it is part of michael@0: * calculating G) */ michael@0: CHECKPARAM( SECITEM_CompareItem(&pseed, &pseed_) == SECEqual ); michael@0: } else if (vfy->counter == -1) { michael@0: /* If counter is set to -1, we are really only verifying G, skip michael@0: * the remainder of the checks for P */ michael@0: CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */ michael@0: } else { michael@0: /* 10. P generated from (L, counter, g, SEED, Q) matches P michael@0: * in PQGParams. */ michael@0: outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE; michael@0: n = (L - 1) / outlen; michael@0: offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1); michael@0: CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed, michael@0: &Q, &P_) ); michael@0: CHECKPARAM( mp_cmp(&P, &P_) == 0 ); michael@0: } michael@0: michael@0: /* now check G, skip if don't have a g */ michael@0: if (params->base.len == 0) goto cleanup; michael@0: michael@0: /* first Always check that G is OK FIPS186-3 A.2.2 & A.2.4*/ michael@0: /* 1. 2 < G < P-1 */ michael@0: /* P is prime, p-1 == zero 1st bit */ michael@0: CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) ); michael@0: CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0 ); michael@0: CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */ michael@0: /* 2. verify g**q mod p == 1 */ michael@0: CHECK_MPI_OK( mp_exptmod(&G, &Q, &P, &h) ); /* h = G ** Q mod P */ michael@0: CHECKPARAM(mp_cmp_d(&h, 1) == 0); michael@0: michael@0: /* no h, the above is the best we can do */ michael@0: if (vfy->h.len == 0) { michael@0: if (type != FIPS186_1_TYPE) { michael@0: *result = SECWouldBlock; michael@0: } michael@0: goto cleanup; michael@0: } michael@0: michael@0: /* michael@0: * If h is one byte and FIPS186-3 was used to generate Q (we've verified michael@0: * Q was generated from seed already, then we assume that FIPS 186-3 michael@0: * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was michael@0: * used to generate G. michael@0: */ michael@0: if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) { michael@0: /* A.2.3 */ michael@0: CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed, michael@0: vfy->h.data[0], &G_) ); michael@0: CHECKPARAM( mp_cmp(&G, &G_) == 0 ); michael@0: } else { michael@0: int passed; michael@0: /* A.2.1 */ michael@0: SECITEM_TO_MPINT(vfy->h, &h); michael@0: /* 11. 1 < h < P-1 */ michael@0: /* P is prime, p-1 == zero 1st bit */ michael@0: CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) ); michael@0: CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) ); michael@0: CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */ michael@0: /* 12. G generated from h matches G in PQGParams. */ michael@0: CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) ); michael@0: CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 ); michael@0: } michael@0: cleanup: michael@0: mp_clear(&p0); michael@0: mp_clear(&P); michael@0: mp_clear(&Q); michael@0: mp_clear(&G); michael@0: mp_clear(&P_); michael@0: mp_clear(&Q_); michael@0: mp_clear(&G_); michael@0: mp_clear(&r); michael@0: mp_clear(&h); michael@0: if (pseed_.data) { michael@0: SECITEM_FreeItem(&pseed_,PR_FALSE); michael@0: } michael@0: if (err) { michael@0: MP_TO_SEC_ERROR(err); michael@0: rv = SECFailure; michael@0: } michael@0: return rv; michael@0: } michael@0: michael@0: /************************************************************************** michael@0: * Free the PQGParams struct and the things it points to. * michael@0: **************************************************************************/ michael@0: void michael@0: PQG_DestroyParams(PQGParams *params) michael@0: { michael@0: if (params == NULL) michael@0: return; michael@0: if (params->arena != NULL) { michael@0: PORT_FreeArena(params->arena, PR_FALSE); /* don't zero it */ michael@0: } else { michael@0: SECITEM_FreeItem(¶ms->prime, PR_FALSE); /* don't free prime */ michael@0: SECITEM_FreeItem(¶ms->subPrime, PR_FALSE); /* don't free subPrime */ michael@0: SECITEM_FreeItem(¶ms->base, PR_FALSE); /* don't free base */ michael@0: PORT_Free(params); michael@0: } michael@0: } michael@0: michael@0: /************************************************************************** michael@0: * Free the PQGVerify struct and the things it points to. * michael@0: **************************************************************************/ michael@0: michael@0: void michael@0: PQG_DestroyVerify(PQGVerify *vfy) michael@0: { michael@0: if (vfy == NULL) michael@0: return; michael@0: if (vfy->arena != NULL) { michael@0: PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */ michael@0: } else { michael@0: SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */ michael@0: SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */ michael@0: PORT_Free(vfy); michael@0: } michael@0: }