1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/pqg.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1847 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +/*
1.9 + * PQG parameter generation/verification. Based on FIPS 186-3.
1.10 + */
1.11 +#ifdef FREEBL_NO_DEPEND
1.12 +#include "stubs.h"
1.13 +#endif
1.14 +
1.15 +#include "prerr.h"
1.16 +#include "secerr.h"
1.17 +
1.18 +#include "prtypes.h"
1.19 +#include "blapi.h"
1.20 +#include "secitem.h"
1.21 +#include "mpi.h"
1.22 +#include "mpprime.h"
1.23 +#include "mplogic.h"
1.24 +#include "secmpi.h"
1.25 +
1.26 +#define MAX_ITERATIONS 1000 /* Maximum number of iterations of primegen */
1.27 +
1.28 +typedef enum {
1.29 + FIPS186_1_TYPE, /* Probablistic */
1.30 + FIPS186_3_TYPE, /* Probablistic */
1.31 + FIPS186_3_ST_TYPE /* Shawe-Taylor provable */
1.32 +} pqgGenType;
1.33 +
1.34 +/*
1.35 + * These test iterations are quite a bit larger than we previously had.
1.36 + * This is because FIPS 186-3 is worried about the primes in PQG generation.
1.37 + * It may be possible to purposefully construct composites which more
1.38 + * iterations of Miller-Rabin than the for your normal randomly selected
1.39 + * numbers.There are 3 ways to counter this: 1) use one of the cool provably
1.40 + * prime algorithms (which would require a lot more work than DSA-2 deservers.
1.41 + * 2) add a Lucas primality test (which requires coding a Lucas primality test,
1.42 + * or 3) use a larger M-R test count. I chose the latter. It increases the time
1.43 + * that it takes to prove the selected prime, but it shouldn't increase the
1.44 + * overall time to run the algorithm (non-primes should still faile M-R
1.45 + * realively quickly). If you want to get that last bit of performance,
1.46 + * implement Lucas and adjust these two functions. See FIPS 186-3 Appendix C
1.47 + * and F for more information.
1.48 + */
1.49 +int prime_testcount_p(int L, int N)
1.50 +{
1.51 + switch (L) {
1.52 + case 1024:
1.53 + return 40;
1.54 + case 2048:
1.55 + return 56;
1.56 + case 3072:
1.57 + return 64;
1.58 + default:
1.59 + break;
1.60 + }
1.61 + return 50; /* L = 512-960 */
1.62 +}
1.63 +
1.64 +/* The q numbers are different if you run M-R followd by Lucas. I created
1.65 + * a separate function so if someone wanted to add the Lucas check, they
1.66 + * could do so fairly easily */
1.67 +int prime_testcount_q(int L, int N)
1.68 +{
1.69 + return prime_testcount_p(L,N);
1.70 +}
1.71 +
1.72 +/*
1.73 + * generic function to make sure our input matches DSA2 requirements
1.74 + * this gives us one place to go if we need to bump the requirements in the
1.75 + * future.
1.76 + */
1.77 +static SECStatus
1.78 +pqg_validate_dsa2(unsigned int L, unsigned int N)
1.79 +{
1.80 +
1.81 + switch (L) {
1.82 + case 1024:
1.83 + if (N != DSA1_Q_BITS) {
1.84 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.85 + return SECFailure;
1.86 + }
1.87 + break;
1.88 + case 2048:
1.89 + if ((N != 224) && (N != 256)) {
1.90 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.91 + return SECFailure;
1.92 + }
1.93 + break;
1.94 + case 3072:
1.95 + if (N != 256) {
1.96 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.97 + return SECFailure;
1.98 + }
1.99 + break;
1.100 + default:
1.101 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.102 + return SECFailure;
1.103 + }
1.104 + return SECSuccess;
1.105 +}
1.106 +
1.107 +static unsigned int
1.108 +pqg_get_default_N(unsigned int L)
1.109 +{
1.110 + unsigned int N = 0;
1.111 + switch (L) {
1.112 + case 1024:
1.113 + N = DSA1_Q_BITS;
1.114 + break;
1.115 + case 2048:
1.116 + N = 224;
1.117 + break;
1.118 + case 3072:
1.119 + N = 256;
1.120 + break;
1.121 + default:
1.122 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.123 + break; /* N already set to zero */
1.124 + }
1.125 + return N;
1.126 +}
1.127 +
1.128 +/*
1.129 + * Select the lowest hash algorithm usable
1.130 + */
1.131 +static HASH_HashType
1.132 +getFirstHash(unsigned int L, unsigned int N)
1.133 +{
1.134 + if (N < 224) {
1.135 + return HASH_AlgSHA1;
1.136 + }
1.137 + if (N < 256) {
1.138 + return HASH_AlgSHA224;
1.139 + }
1.140 + if (N < 384) {
1.141 + return HASH_AlgSHA256;
1.142 + }
1.143 + if (N < 512) {
1.144 + return HASH_AlgSHA384;
1.145 + }
1.146 + return HASH_AlgSHA512;
1.147 +}
1.148 +
1.149 +/*
1.150 + * find the next usable hash algorthim
1.151 + */
1.152 +static HASH_HashType
1.153 +getNextHash(HASH_HashType hashtype)
1.154 +{
1.155 + switch (hashtype) {
1.156 + case HASH_AlgSHA1:
1.157 + hashtype = HASH_AlgSHA224;
1.158 + break;
1.159 + case HASH_AlgSHA224:
1.160 + hashtype = HASH_AlgSHA256;
1.161 + break;
1.162 + case HASH_AlgSHA256:
1.163 + hashtype = HASH_AlgSHA384;
1.164 + break;
1.165 + case HASH_AlgSHA384:
1.166 + hashtype = HASH_AlgSHA512;
1.167 + break;
1.168 + case HASH_AlgSHA512:
1.169 + default:
1.170 + hashtype = HASH_AlgTOTAL;
1.171 + break;
1.172 + }
1.173 + return hashtype;
1.174 +}
1.175 +
1.176 +static unsigned int
1.177 +HASH_ResultLen(HASH_HashType type)
1.178 +{
1.179 + const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
1.180 + if (hash_obj == NULL) {
1.181 + return 0;
1.182 + }
1.183 + return hash_obj->length;
1.184 +}
1.185 +
1.186 +static SECStatus
1.187 +HASH_HashBuf(HASH_HashType type, unsigned char *dest,
1.188 + const unsigned char *src, PRUint32 src_len)
1.189 +{
1.190 + const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
1.191 + void *hashcx = NULL;
1.192 + unsigned int dummy;
1.193 +
1.194 + if (hash_obj == NULL) {
1.195 + return SECFailure;
1.196 + }
1.197 +
1.198 + hashcx = hash_obj->create();
1.199 + if (hashcx == NULL) {
1.200 + return SECFailure;
1.201 + }
1.202 + hash_obj->begin(hashcx);
1.203 + hash_obj->update(hashcx,src,src_len);
1.204 + hash_obj->end(hashcx,dest, &dummy, hash_obj->length);
1.205 + hash_obj->destroy(hashcx, PR_TRUE);
1.206 + return SECSuccess;
1.207 +}
1.208 +
1.209 +unsigned int
1.210 +PQG_GetLength(const SECItem *obj)
1.211 +{
1.212 + unsigned int len = obj->len;
1.213 +
1.214 + if (obj->data == NULL) {
1.215 + return 0;
1.216 + }
1.217 + if (len > 1 && obj->data[0] == 0) {
1.218 + len--;
1.219 + }
1.220 + return len;
1.221 +}
1.222 +
1.223 +SECStatus
1.224 +PQG_Check(const PQGParams *params)
1.225 +{
1.226 + unsigned int L,N;
1.227 + SECStatus rv = SECSuccess;
1.228 +
1.229 + if (params == NULL) {
1.230 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.231 + return SECFailure;
1.232 + }
1.233 +
1.234 + L = PQG_GetLength(¶ms->prime)*PR_BITS_PER_BYTE;
1.235 + N = PQG_GetLength(¶ms->subPrime)*PR_BITS_PER_BYTE;
1.236 +
1.237 + if (L < 1024) {
1.238 + int j;
1.239 +
1.240 + /* handle DSA1 pqg parameters with less thatn 1024 bits*/
1.241 + if ( N != DSA1_Q_BITS ) {
1.242 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.243 + return SECFailure;
1.244 + }
1.245 + j = PQG_PBITS_TO_INDEX(L);
1.246 + if ( j < 0 ) {
1.247 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.248 + rv = SECFailure;
1.249 + }
1.250 + } else {
1.251 + /* handle DSA2 parameters (includes DSA1, 1024 bits) */
1.252 + rv = pqg_validate_dsa2(L, N);
1.253 + }
1.254 + return rv;
1.255 +}
1.256 +
1.257 +HASH_HashType
1.258 +PQG_GetHashType(const PQGParams *params)
1.259 +{
1.260 + unsigned int L,N;
1.261 +
1.262 + if (params == NULL) {
1.263 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.264 + return HASH_AlgNULL;
1.265 + }
1.266 +
1.267 + L = PQG_GetLength(¶ms->prime)*PR_BITS_PER_BYTE;
1.268 + N = PQG_GetLength(¶ms->subPrime)*PR_BITS_PER_BYTE;
1.269 + return getFirstHash(L, N);
1.270 +}
1.271 +
1.272 +/* Get a seed for generating P and Q. If in testing mode, copy in the
1.273 +** seed from FIPS 186-1 appendix 5. Otherwise, obtain bytes from the
1.274 +** global random number generator.
1.275 +*/
1.276 +static SECStatus
1.277 +getPQseed(SECItem *seed, PLArenaPool* arena)
1.278 +{
1.279 + SECStatus rv;
1.280 +
1.281 + if (!seed->data) {
1.282 + seed->data = (unsigned char*)PORT_ArenaZAlloc(arena, seed->len);
1.283 + }
1.284 + if (!seed->data) {
1.285 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.286 + return SECFailure;
1.287 + }
1.288 + rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len);
1.289 + /*
1.290 + * NIST CMVP disallows a sequence of 20 bytes with the most
1.291 + * significant byte equal to 0. Perhaps they interpret
1.292 + * "a sequence of at least 160 bits" as "a number >= 2^159".
1.293 + * So we always set the most significant bit to 1. (bug 334533)
1.294 + */
1.295 + seed->data[0] |= 0x80;
1.296 + return rv;
1.297 +}
1.298 +
1.299 +/* Generate a candidate h value. If in testing mode, use the h value
1.300 +** specified in FIPS 186-1 appendix 5, h = 2. Otherwise, obtain bytes
1.301 +** from the global random number generator.
1.302 +*/
1.303 +static SECStatus
1.304 +generate_h_candidate(SECItem *hit, mp_int *H)
1.305 +{
1.306 + SECStatus rv = SECSuccess;
1.307 + mp_err err = MP_OKAY;
1.308 +#ifdef FIPS_186_1_A5_TEST
1.309 + memset(hit->data, 0, hit->len);
1.310 + hit->data[hit->len-1] = 0x02;
1.311 +#else
1.312 + rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len);
1.313 +#endif
1.314 + if (rv)
1.315 + return SECFailure;
1.316 + err = mp_read_unsigned_octets(H, hit->data, hit->len);
1.317 + if (err) {
1.318 + MP_TO_SEC_ERROR(err);
1.319 + return SECFailure;
1.320 + }
1.321 + return SECSuccess;
1.322 +}
1.323 +
1.324 +static SECStatus
1.325 +addToSeed(const SECItem * seed,
1.326 + unsigned long addend,
1.327 + int seedlen, /* g in 186-1 */
1.328 + SECItem * seedout)
1.329 +{
1.330 + mp_int s, sum, modulus, tmp;
1.331 + mp_err err = MP_OKAY;
1.332 + SECStatus rv = SECSuccess;
1.333 + MP_DIGITS(&s) = 0;
1.334 + MP_DIGITS(&sum) = 0;
1.335 + MP_DIGITS(&modulus) = 0;
1.336 + MP_DIGITS(&tmp) = 0;
1.337 + CHECK_MPI_OK( mp_init(&s) );
1.338 + CHECK_MPI_OK( mp_init(&sum) );
1.339 + CHECK_MPI_OK( mp_init(&modulus) );
1.340 + SECITEM_TO_MPINT(*seed, &s); /* s = seed */
1.341 + /* seed += addend */
1.342 + if (addend < MP_DIGIT_MAX) {
1.343 + CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );
1.344 + } else {
1.345 + CHECK_MPI_OK( mp_init(&tmp) );
1.346 + CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );
1.347 + CHECK_MPI_OK( mp_add(&s, &tmp, &s) );
1.348 + }
1.349 + /*sum = s mod 2**seedlen */
1.350 + CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)seedlen, NULL, &sum) );
1.351 + if (seedout->data != NULL) {
1.352 + SECITEM_ZfreeItem(seedout, PR_FALSE);
1.353 + }
1.354 + MPINT_TO_SECITEM(&sum, seedout, NULL);
1.355 +cleanup:
1.356 + mp_clear(&s);
1.357 + mp_clear(&sum);
1.358 + mp_clear(&modulus);
1.359 + mp_clear(&tmp);
1.360 + if (err) {
1.361 + MP_TO_SEC_ERROR(err);
1.362 + return SECFailure;
1.363 + }
1.364 + return rv;
1.365 +}
1.366 +
1.367 +/* Compute Hash[(SEED + addend) mod 2**g]
1.368 +** Result is placed in shaOutBuf.
1.369 +** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 and
1.370 +** step 11.2 of FIPS 186-3 Appendix A.1.1.2 .
1.371 +*/
1.372 +static SECStatus
1.373 +addToSeedThenHash(HASH_HashType hashtype,
1.374 + const SECItem * seed,
1.375 + unsigned long addend,
1.376 + int seedlen, /* g in 186-1 */
1.377 + unsigned char * hashOutBuf)
1.378 +{
1.379 + SECItem str = { 0, 0, 0 };
1.380 + SECStatus rv;
1.381 + rv = addToSeed(seed, addend, seedlen, &str);
1.382 + if (rv != SECSuccess) {
1.383 + return rv;
1.384 + }
1.385 + rv = HASH_HashBuf(hashtype, hashOutBuf, str.data, str.len);/* hash result */
1.386 + if (str.data)
1.387 + SECITEM_ZfreeItem(&str, PR_FALSE);
1.388 + return rv;
1.389 +}
1.390 +
1.391 +/*
1.392 +** Perform steps 2 and 3 of FIPS 186-1, appendix 2.2.
1.393 +** Generate Q from seed.
1.394 +*/
1.395 +static SECStatus
1.396 +makeQfromSeed(
1.397 + unsigned int g, /* input. Length of seed in bits. */
1.398 +const SECItem * seed, /* input. */
1.399 + mp_int * Q) /* output. */
1.400 +{
1.401 + unsigned char sha1[SHA1_LENGTH];
1.402 + unsigned char sha2[SHA1_LENGTH];
1.403 + unsigned char U[SHA1_LENGTH];
1.404 + SECStatus rv = SECSuccess;
1.405 + mp_err err = MP_OKAY;
1.406 + int i;
1.407 + /* ******************************************************************
1.408 + ** Step 2.
1.409 + ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
1.410 + **/
1.411 + CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );
1.412 + CHECK_SEC_OK( addToSeedThenHash(HASH_AlgSHA1, seed, 1, g, sha2) );
1.413 + for (i=0; i<SHA1_LENGTH; ++i)
1.414 + U[i] = sha1[i] ^ sha2[i];
1.415 + /* ******************************************************************
1.416 + ** Step 3.
1.417 + ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
1.418 + ** and the least signficant bit to 1. In terms of boolean operations,
1.419 + ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160."
1.420 + */
1.421 + U[0] |= 0x80; /* U is MSB first */
1.422 + U[SHA1_LENGTH-1] |= 0x01;
1.423 + err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH);
1.424 +cleanup:
1.425 + memset(U, 0, SHA1_LENGTH);
1.426 + memset(sha1, 0, SHA1_LENGTH);
1.427 + memset(sha2, 0, SHA1_LENGTH);
1.428 + if (err) {
1.429 + MP_TO_SEC_ERROR(err);
1.430 + return SECFailure;
1.431 + }
1.432 + return rv;
1.433 +}
1.434 +
1.435 +/*
1.436 +** Perform steps 6 and 7 of FIPS 186-3, appendix A.1.1.2.
1.437 +** Generate Q from seed.
1.438 +*/
1.439 +static SECStatus
1.440 +makeQ2fromSeed(
1.441 + HASH_HashType hashtype, /* selected Hashing algorithm */
1.442 + unsigned int N, /* input. Length of q in bits. */
1.443 +const SECItem * seed, /* input. */
1.444 + mp_int * Q) /* output. */
1.445 +{
1.446 + unsigned char U[HASH_LENGTH_MAX];
1.447 + SECStatus rv = SECSuccess;
1.448 + mp_err err = MP_OKAY;
1.449 + int N_bytes = N/PR_BITS_PER_BYTE; /* length of N in bytes rather than bits */
1.450 + int hashLen = HASH_ResultLen(hashtype);
1.451 + int offset = 0;
1.452 +
1.453 + /* ******************************************************************
1.454 + ** Step 6.
1.455 + ** "Compute U = hash[SEED] mod 2**N-1]."
1.456 + **/
1.457 + CHECK_SEC_OK( HASH_HashBuf(hashtype, U, seed->data, seed->len) );
1.458 + /* mod 2**N . Step 7 will explicitly set the top bit to 1, so no need
1.459 + * to handle mod 2**N-1 */
1.460 + if (hashLen > N_bytes) {
1.461 + offset = hashLen - N_bytes;
1.462 + }
1.463 + /* ******************************************************************
1.464 + ** Step 7.
1.465 + ** computed_q = 2**(N-1) + U + 1 - (U mod 2)
1.466 + **
1.467 + ** This is the same as:
1.468 + ** computed_q = 2**(N-1) | U | 1;
1.469 + */
1.470 + U[offset] |= 0x80; /* U is MSB first */
1.471 + U[hashLen-1] |= 0x01;
1.472 + err = mp_read_unsigned_octets(Q, &U[offset], N_bytes);
1.473 +cleanup:
1.474 + memset(U, 0, HASH_LENGTH_MAX);
1.475 + if (err) {
1.476 + MP_TO_SEC_ERROR(err);
1.477 + return SECFailure;
1.478 + }
1.479 + return rv;
1.480 +}
1.481 +
1.482 +/*
1.483 +** Perform steps from FIPS 186-3, Appendix A.1.2.1 and Appendix C.6
1.484 +**
1.485 +** This generates a provable prime from two smaller prime. The resulting
1.486 +** prime p will have q0 as a multiple of p-1. q0 can be 1.
1.487 +**
1.488 +** This implments steps 4 thorough 22 of FIPS 186-3 A.1.2.1 and
1.489 +** steps 16 through 34 of FIPS 186-2 C.6
1.490 +*/
1.491 +#define MAX_ST_SEED_BITS (HASH_LENGTH_MAX*PR_BITS_PER_BYTE)
1.492 +SECStatus
1.493 +makePrimefromPrimesShaweTaylor(
1.494 + HASH_HashType hashtype, /* selected Hashing algorithm */
1.495 + unsigned int length, /* input. Length of prime in bits. */
1.496 + mp_int * c0, /* seed prime */
1.497 + mp_int * q, /* sub prime, can be 1 */
1.498 + mp_int * prime, /* output. */
1.499 + SECItem * prime_seed, /* input/output. */
1.500 + int * prime_gen_counter) /* input/output. */
1.501 +{
1.502 + mp_int c;
1.503 + mp_int c0_2;
1.504 + mp_int t;
1.505 + mp_int a;
1.506 + mp_int z;
1.507 + mp_int two_length_minus_1;
1.508 + SECStatus rv = SECFailure;
1.509 + int hashlen = HASH_ResultLen(hashtype);
1.510 + int outlen = hashlen*PR_BITS_PER_BYTE;
1.511 + int offset;
1.512 + unsigned char bit, mask;
1.513 + /* x needs to hold roundup(L/outlen)*outlen.
1.514 + * This can be no larger than L+outlen-1, So we set it's size to
1.515 + * our max L + max outlen and know we are safe */
1.516 + unsigned char x[DSA_MAX_P_BITS/8+HASH_LENGTH_MAX];
1.517 + mp_err err = MP_OKAY;
1.518 + int i;
1.519 + int iterations;
1.520 + int old_counter;
1.521 +
1.522 + MP_DIGITS(&c) = 0;
1.523 + MP_DIGITS(&c0_2) = 0;
1.524 + MP_DIGITS(&t) = 0;
1.525 + MP_DIGITS(&a) = 0;
1.526 + MP_DIGITS(&z) = 0;
1.527 + MP_DIGITS(&two_length_minus_1) = 0;
1.528 + CHECK_MPI_OK( mp_init(&c) );
1.529 + CHECK_MPI_OK( mp_init(&c0_2) );
1.530 + CHECK_MPI_OK( mp_init(&t) );
1.531 + CHECK_MPI_OK( mp_init(&a) );
1.532 + CHECK_MPI_OK( mp_init(&z) );
1.533 + CHECK_MPI_OK( mp_init(&two_length_minus_1) );
1.534 +
1.535 +
1.536 + /*
1.537 + ** There is a slight mapping of variable names depending on which
1.538 + ** FIPS 186 steps are being carried out. The mapping is as follows:
1.539 + ** variable A.1.2.1 C.6
1.540 + ** c0 p0 c0
1.541 + ** q q 1
1.542 + ** c p c
1.543 + ** c0_2 2*p0*q 2*c0
1.544 + ** length L length
1.545 + ** prime_seed pseed prime_seed
1.546 + ** prime_gen_counter pgen_counter prime_gen_counter
1.547 + **
1.548 + ** Also note: or iterations variable is actually iterations+1, since
1.549 + ** iterations+1 works better in C.
1.550 + */
1.551 +
1.552 + /* Step 4/16 iterations = ceiling(length/outlen)-1 */
1.553 + iterations = (length+outlen-1)/outlen; /* NOTE: iterations +1 */
1.554 + /* Step 5/17 old_counter = prime_gen_counter */
1.555 + old_counter = *prime_gen_counter;
1.556 + /*
1.557 + ** Comment: Generate a pseudorandom integer x in the interval
1.558 + ** [2**(lenght-1), 2**length].
1.559 + **
1.560 + ** Step 6/18 x = 0
1.561 + */
1.562 + PORT_Memset(x, 0, sizeof(x));
1.563 + /*
1.564 + ** Step 7/19 for i = 0 to iterations do
1.565 + ** x = x + (HASH(prime_seed + i) * 2^(i*outlen))
1.566 + */
1.567 + for (i=0; i < iterations; i++) {
1.568 + /* is bigger than prime_seed should get to */
1.569 + CHECK_SEC_OK( addToSeedThenHash(hashtype, prime_seed, i,
1.570 + MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));
1.571 + }
1.572 + /* Step 8/20 prime_seed = prime_seed + iterations + 1 */
1.573 + CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS,
1.574 + prime_seed));
1.575 + /*
1.576 + ** Step 9/21 x = 2 ** (length-1) + x mod 2 ** (length-1)
1.577 + **
1.578 + ** This step mathematically sets the high bit and clears out
1.579 + ** all the other bits higher than length. 'x' is stored
1.580 + ** in the x array, MSB first. The above formula gives us an 'x'
1.581 + ** which is length bytes long and has the high bit set. We also know
1.582 + ** that length <= iterations*outlen since
1.583 + ** iterations=ceiling(length/outlen). First we find the offset in
1.584 + ** bytes into the array where the high bit is.
1.585 + */
1.586 + offset = (outlen*iterations - length)/PR_BITS_PER_BYTE;
1.587 + /* now we want to set the 'high bit', since length may not be a
1.588 + * multiple of 8,*/
1.589 + bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */
1.590 + /* we need to zero out the rest of the bits in the byte above */
1.591 + mask = (bit-1);
1.592 + /* now we set it */
1.593 + x[offset] = (mask & x[offset]) | bit;
1.594 + /*
1.595 + ** Comment: Generate a candidate prime c in the interval
1.596 + ** [2**(lenght-1), 2**length].
1.597 + **
1.598 + ** Step 10 t = ceiling(x/(2q(p0)))
1.599 + ** Step 22 t = ceiling(x/(2(c0)))
1.600 + */
1.601 + CHECK_MPI_OK( mp_read_unsigned_octets(&t, &x[offset],
1.602 + hashlen*iterations - offset ) ); /* t = x */
1.603 + CHECK_MPI_OK( mp_mul(c0, q, &c0_2) ); /* c0_2 is now c0*q */
1.604 + CHECK_MPI_OK( mp_add(&c0_2, &c0_2, &c0_2) ); /* c0_2 is now 2*q*c0 */
1.605 + CHECK_MPI_OK( mp_add(&t, &c0_2, &t) ); /* t = x+2*q*c0 */
1.606 + CHECK_MPI_OK( mp_sub_d(&t, (mp_digit) 1, &t) ); /* t = x+2*q*c0 -1 */
1.607 + /* t = floor((x+2qc0-1)/2qc0) = ceil(x/2qc0) */
1.608 + CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );
1.609 + /*
1.610 + ** step 11: if (2tqp0 +1 > 2**length), then t = ceiling(2**(length-1)/2qp0)
1.611 + ** step 12: t = 2tqp0 +1.
1.612 + **
1.613 + ** step 23: if (2tc0 +1 > 2**length), then t = ceiling(2**(length-1)/2c0)
1.614 + ** step 24: t = 2tc0 +1.
1.615 + */
1.616 + CHECK_MPI_OK( mp_2expt(&two_length_minus_1, length-1) );
1.617 +step_23:
1.618 + CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) ); /* c = t*2qc0 */
1.619 + CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/
1.620 + if (mpl_significant_bits(&c) > length) { /* if c > 2**length */
1.621 + CHECK_MPI_OK( mp_sub_d(&c0_2, (mp_digit) 1, &t) ); /* t = 2qc0-1 */
1.622 + /* t = 2**(length-1) + 2qc0 -1 */
1.623 + CHECK_MPI_OK( mp_add(&two_length_minus_1,&t, &t) );
1.624 + /* t = floor((2**(length-1)+2qc0 -1)/2qco)
1.625 + * = ceil(2**(lenght-2)/2qc0) */
1.626 + CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );
1.627 + CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) );
1.628 + CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) ); /* c= 2tqc0 + 1*/
1.629 + }
1.630 + /* Step 13/25 prime_gen_counter = prime_gen_counter + 1*/
1.631 + (*prime_gen_counter)++;
1.632 + /*
1.633 + ** Comment: Test the candidate prime c for primality; first pick an
1.634 + ** integer a between 2 and c-2.
1.635 + **
1.636 + ** Step 14/26 a=0
1.637 + */
1.638 + PORT_Memset(x, 0, sizeof(x)); /* use x for a */
1.639 + /*
1.640 + ** Step 15/27 for i = 0 to iterations do
1.641 + ** a = a + (HASH(prime_seed + i) * 2^(i*outlen))
1.642 + **
1.643 + ** NOTE: we reuse the x array for 'a' initially.
1.644 + */
1.645 + for (i=0; i < iterations; i++) {
1.646 + /* MAX_ST_SEED_BITS is bigger than prime_seed should get to */
1.647 + CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i,
1.648 + MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));
1.649 + }
1.650 + /* Step 16/28 prime_seed = prime_seed + iterations + 1 */
1.651 + CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS,
1.652 + prime_seed));
1.653 + /* Step 17/29 a = 2 + (a mod (c-3)). */
1.654 + CHECK_MPI_OK( mp_read_unsigned_octets(&a, x, iterations*hashlen) );
1.655 + CHECK_MPI_OK( mp_sub_d(&c, (mp_digit) 3, &z) ); /* z = c -3 */
1.656 + CHECK_MPI_OK( mp_mod(&a, &z, &a) ); /* a = a mod c -3 */
1.657 + CHECK_MPI_OK( mp_add_d(&a, (mp_digit) 2, &a) ); /* a = 2 + a mod c -3 */
1.658 + /*
1.659 + ** Step 18 z = a**(2tq) mod p.
1.660 + ** Step 30 z = a**(2t) mod c.
1.661 + */
1.662 + CHECK_MPI_OK( mp_mul(&t, q, &z) ); /* z = tq */
1.663 + CHECK_MPI_OK( mp_add(&z, &z, &z) ); /* z = 2tq */
1.664 + CHECK_MPI_OK( mp_exptmod(&a, &z, &c, &z) ); /* z = a**(2tq) mod c */
1.665 + /*
1.666 + ** Step 19 if (( 1 == GCD(z-1,p)) and ( 1 == z**p0 mod p )), then
1.667 + ** Step 31 if (( 1 == GCD(z-1,c)) and ( 1 == z**c0 mod c )), then
1.668 + */
1.669 + CHECK_MPI_OK( mp_sub_d(&z, (mp_digit) 1, &a) );
1.670 + CHECK_MPI_OK( mp_gcd(&a,&c,&a ));
1.671 + if (mp_cmp_d(&a, (mp_digit)1) == 0) {
1.672 + CHECK_MPI_OK( mp_exptmod(&z, c0, &c, &a) );
1.673 + if (mp_cmp_d(&a, (mp_digit)1) == 0) {
1.674 + /* Step 31.1 prime = c */
1.675 + CHECK_MPI_OK( mp_copy(&c, prime) );
1.676 + /*
1.677 + ** Step 31.2 return Success, prime, prime_seed,
1.678 + ** prime_gen_counter
1.679 + */
1.680 + rv = SECSuccess;
1.681 + goto cleanup;
1.682 + }
1.683 + }
1.684 + /*
1.685 + ** Step 20/32 If (prime_gen_counter > 4 * length + old_counter then
1.686 + ** return (FAILURE, 0, 0, 0).
1.687 + ** NOTE: the test is reversed, so we fall through on failure to the
1.688 + ** cleanup routine
1.689 + */
1.690 + if (*prime_gen_counter < (4*length + old_counter)) {
1.691 + /* Step 21/33 t = t + 1 */
1.692 + CHECK_MPI_OK( mp_add_d(&t, (mp_digit) 1, &t) );
1.693 + /* Step 22/34 Go to step 23/11 */
1.694 + goto step_23;
1.695 + }
1.696 +
1.697 + /* if (prime_gencont > (4*length + old_counter), fall through to failure */
1.698 + rv = SECFailure; /* really is already set, but paranoia is good */
1.699 +
1.700 +cleanup:
1.701 + mp_clear(&c);
1.702 + mp_clear(&c0_2);
1.703 + mp_clear(&t);
1.704 + mp_clear(&a);
1.705 + mp_clear(&z);
1.706 + mp_clear(&two_length_minus_1);
1.707 + if (err) {
1.708 + MP_TO_SEC_ERROR(err);
1.709 + rv = SECFailure;
1.710 + }
1.711 + if (rv == SECFailure) {
1.712 + mp_zero(prime);
1.713 + if (prime_seed->data) {
1.714 + SECITEM_FreeItem(prime_seed, PR_FALSE);
1.715 + }
1.716 + *prime_gen_counter = 0;
1.717 + }
1.718 + return rv;
1.719 +}
1.720 +
1.721 +/*
1.722 +** Perform steps from FIPS 186-3, Appendix C.6
1.723 +**
1.724 +** This generates a provable prime from a seed
1.725 +*/
1.726 +SECStatus
1.727 +makePrimefromSeedShaweTaylor(
1.728 + HASH_HashType hashtype, /* selected Hashing algorithm */
1.729 + unsigned int length, /* input. Length of prime in bits. */
1.730 +const SECItem * input_seed, /* input. */
1.731 + mp_int * prime, /* output. */
1.732 + SECItem * prime_seed, /* output. */
1.733 + int * prime_gen_counter) /* output. */
1.734 +{
1.735 + mp_int c;
1.736 + mp_int c0;
1.737 + mp_int one;
1.738 + SECStatus rv = SECFailure;
1.739 + int hashlen = HASH_ResultLen(hashtype);
1.740 + int outlen = hashlen*PR_BITS_PER_BYTE;
1.741 + int offset;
1.742 + unsigned char bit, mask;
1.743 + unsigned char x[HASH_LENGTH_MAX*2];
1.744 + mp_digit dummy;
1.745 + mp_err err = MP_OKAY;
1.746 + int i;
1.747 +
1.748 + MP_DIGITS(&c) = 0;
1.749 + MP_DIGITS(&c0) = 0;
1.750 + MP_DIGITS(&one) = 0;
1.751 + CHECK_MPI_OK( mp_init(&c) );
1.752 + CHECK_MPI_OK( mp_init(&c0) );
1.753 + CHECK_MPI_OK( mp_init(&one) );
1.754 +
1.755 + /* Step 1. if length < 2 then return (FAILURE, 0, 0, 0) */
1.756 + if (length < 2) {
1.757 + rv = SECFailure;
1.758 + goto cleanup;
1.759 + }
1.760 + /* Step 2. if length >= 33 then goto step 14 */
1.761 + if (length >= 33) {
1.762 + mp_zero(&one);
1.763 + CHECK_MPI_OK( mp_add_d(&one, (mp_digit) 1, &one) );
1.764 +
1.765 + /* Step 14 (status, c0, prime_seed, prime_gen_counter) =
1.766 + ** (ST_Random_Prime((ceil(length/2)+1, input_seed)
1.767 + */
1.768 + rv = makePrimefromSeedShaweTaylor(hashtype, (length+1)/2+1,
1.769 + input_seed, &c0, prime_seed, prime_gen_counter);
1.770 + /* Step 15 if FAILURE is returned, return (FAILURE, 0, 0, 0). */
1.771 + if (rv != SECSuccess) {
1.772 + goto cleanup;
1.773 + }
1.774 + /* Steps 16-34 */
1.775 + rv = makePrimefromPrimesShaweTaylor(hashtype,length, &c0, &one,
1.776 + prime, prime_seed, prime_gen_counter);
1.777 + goto cleanup; /* we're done, one way or the other */
1.778 + }
1.779 + /* Step 3 prime_seed = input_seed */
1.780 + CHECK_SEC_OK(SECITEM_CopyItem(NULL, prime_seed, input_seed));
1.781 + /* Step 4 prime_gen_count = 0 */
1.782 + *prime_gen_counter = 0;
1.783 +
1.784 +step_5:
1.785 + /* Step 5 c = Hash(prime_seed) xor Hash(prime_seed+1). */
1.786 + CHECK_SEC_OK(HASH_HashBuf(hashtype, x, prime_seed->data, prime_seed->len) );
1.787 + CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, 1,
1.788 + MAX_ST_SEED_BITS, &x[hashlen]) );
1.789 + for (i=0; i < hashlen; i++) {
1.790 + x[i] = x[i] ^ x[i+hashlen];
1.791 + }
1.792 + /* Step 6 c = 2**length-1 + c mod 2**length-1 */
1.793 + /* This step mathematically sets the high bit and clears out
1.794 + ** all the other bits higher than length. Right now c is stored
1.795 + ** in the x array, MSB first. The above formula gives us a c which
1.796 + ** is length bytes long and has the high bit set. We also know that
1.797 + ** length < outlen since the smallest outlen is 160 bits and the largest
1.798 + ** length at this point is 32 bits. So first we find the offset in bytes
1.799 + ** into the array where the high bit is.
1.800 + */
1.801 + offset = (outlen - length)/PR_BITS_PER_BYTE;
1.802 + /* now we want to set the 'high bit'. We have to calculate this since
1.803 + * length may not be a multiple of 8.*/
1.804 + bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */
1.805 + /* we need to zero out the rest of the bits in the byte above */
1.806 + mask = (bit-1);
1.807 + /* now we set it */
1.808 + x[offset] = (mask & x[offset]) | bit;
1.809 + /* Step 7 c = c*floor(c/2) + 1 */
1.810 + /* set the low bit. much easier to find (the end of the array) */
1.811 + x[hashlen-1] |= 1;
1.812 + /* now that we've set our bits, we can create our candidate "c" */
1.813 + CHECK_MPI_OK( mp_read_unsigned_octets(&c, &x[offset], hashlen-offset) );
1.814 + /* Step 8 prime_gen_counter = prime_gen_counter + 1 */
1.815 + (*prime_gen_counter)++;
1.816 + /* Step 9 prime_seed = prime_seed + 2 */
1.817 + CHECK_SEC_OK(addToSeed(prime_seed, 2, MAX_ST_SEED_BITS, prime_seed));
1.818 + /* Step 10 Perform deterministic primality test on c. For example, since
1.819 + ** c is small, it's primality can be tested by trial division, See
1.820 + ** See Appendic C.7.
1.821 + **
1.822 + ** We in fact test with trial division. mpi has a built int trial divider
1.823 + ** that divides all divisors up to 2^16.
1.824 + */
1.825 + if (prime_tab[prime_tab_size-1] < 0xFFF1) {
1.826 + /* we aren't testing all the primes between 0 and 2^16, we really
1.827 + * can't use this construction. Just fail. */
1.828 + rv = SECFailure;
1.829 + goto cleanup;
1.830 + }
1.831 + dummy = prime_tab_size;
1.832 + err = mpp_divis_primes(&c, &dummy);
1.833 + /* Step 11 if c is prime then */
1.834 + if (err == MP_NO) {
1.835 + /* Step 11.1 prime = c */
1.836 + CHECK_MPI_OK( mp_copy(&c, prime) );
1.837 + /* Step 11.2 return SUCCESS prime, prime_seed, prime_gen_counter */
1.838 + err = MP_OKAY;
1.839 + rv = SECSuccess;
1.840 + goto cleanup;
1.841 + } else if (err != MP_YES) {
1.842 + goto cleanup; /* function failed, bail out */
1.843 + } else {
1.844 + /* reset mp_err */
1.845 + err = MP_OKAY;
1.846 + }
1.847 + /*
1.848 + ** Step 12 if (prime_gen_counter > (4*len))
1.849 + ** then return (FAILURE, 0, 0, 0))
1.850 + ** Step 13 goto step 5
1.851 + */
1.852 + if (*prime_gen_counter <= (4*length)) {
1.853 + goto step_5;
1.854 + }
1.855 + /* if (prime_gencont > 4*length), fall through to failure */
1.856 + rv = SECFailure; /* really is already set, but paranoia is good */
1.857 +
1.858 +cleanup:
1.859 + mp_clear(&c);
1.860 + mp_clear(&c0);
1.861 + mp_clear(&one);
1.862 + if (err) {
1.863 + MP_TO_SEC_ERROR(err);
1.864 + rv = SECFailure;
1.865 + }
1.866 + if (rv == SECFailure) {
1.867 + mp_zero(prime);
1.868 + if (prime_seed->data) {
1.869 + SECITEM_FreeItem(prime_seed, PR_FALSE);
1.870 + }
1.871 + *prime_gen_counter = 0;
1.872 + }
1.873 + return rv;
1.874 +}
1.875 +
1.876 +
1.877 +/*
1.878 + * Find a Q and algorithm from Seed.
1.879 + */
1.880 +static SECStatus
1.881 +findQfromSeed(
1.882 + unsigned int L, /* input. Length of p in bits. */
1.883 + unsigned int N, /* input. Length of q in bits. */
1.884 + unsigned int g, /* input. Length of seed in bits. */
1.885 +const SECItem * seed, /* input. */
1.886 + mp_int * Q, /* input. */
1.887 + mp_int * Q_, /* output. */
1.888 + int * qseed_len, /* output */
1.889 + HASH_HashType *hashtypePtr, /* output. Hash uses */
1.890 + pqgGenType *typePtr) /* output. Generation Type used */
1.891 +{
1.892 + HASH_HashType hashtype;
1.893 + SECItem firstseed = { 0, 0, 0 };
1.894 + SECItem qseed = { 0, 0, 0 };
1.895 + SECStatus rv;
1.896 +
1.897 + *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */
1.898 +
1.899 + /* handle legacy small DSA first can only be FIPS186_1_TYPE */
1.900 + if (L < 1024) {
1.901 + rv =makeQfromSeed(g,seed,Q_);
1.902 + if ((rv == SECSuccess) && (mp_cmp(Q,Q_) == 0)) {
1.903 + *hashtypePtr = HASH_AlgSHA1;
1.904 + *typePtr = FIPS186_1_TYPE;
1.905 + return SECSuccess;
1.906 + }
1.907 + return SECFailure;
1.908 + }
1.909 + /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try
1.910 + * them both */
1.911 + if (L == 1024) {
1.912 + rv = makeQfromSeed(g,seed,Q_);
1.913 + if (rv == SECSuccess) {
1.914 + if (mp_cmp(Q,Q_) == 0) {
1.915 + *hashtypePtr = HASH_AlgSHA1;
1.916 + *typePtr = FIPS186_1_TYPE;
1.917 + return SECSuccess;
1.918 + }
1.919 + }
1.920 + /* fall through for FIPS186_3 types */
1.921 + }
1.922 + /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3
1.923 + * with appropriate hash types */
1.924 + for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL;
1.925 + hashtype=getNextHash(hashtype)) {
1.926 + rv = makeQ2fromSeed(hashtype, N, seed, Q_);
1.927 + if (rv != SECSuccess) {
1.928 + continue;
1.929 + }
1.930 + if (mp_cmp(Q,Q_) == 0) {
1.931 + *hashtypePtr = hashtype;
1.932 + *typePtr = FIPS186_3_TYPE;
1.933 + return SECSuccess;
1.934 + }
1.935 + }
1.936 + /*
1.937 + * OK finally try FIPS186_3 Shawe-Taylor
1.938 + */
1.939 + firstseed = *seed;
1.940 + firstseed.len = seed->len/3;
1.941 + for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL;
1.942 + hashtype=getNextHash(hashtype)) {
1.943 + int count;
1.944 +
1.945 + rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_,
1.946 + &qseed, &count);
1.947 + if (rv != SECSuccess) {
1.948 + continue;
1.949 + }
1.950 + if (mp_cmp(Q,Q_) == 0) {
1.951 + /* check qseed as well... */
1.952 + int offset = seed->len - qseed.len;
1.953 + if ((offset < 0) ||
1.954 + (PORT_Memcmp(&seed->data[offset],qseed.data,qseed.len) != 0)) {
1.955 + /* we found q, but the seeds don't match. This isn't an
1.956 + * accident, someone has been tweeking with the seeds, just
1.957 + * fail a this point. */
1.958 + SECITEM_FreeItem(&qseed,PR_FALSE);
1.959 + return SECFailure;
1.960 + }
1.961 + *qseed_len = qseed.len;
1.962 + *hashtypePtr = hashtype;
1.963 + *typePtr = FIPS186_3_ST_TYPE;
1.964 + SECITEM_FreeItem(&qseed, PR_FALSE);
1.965 + return SECSuccess;
1.966 + }
1.967 + SECITEM_FreeItem(&qseed, PR_FALSE);
1.968 + }
1.969 + /* no hash algorithms found which match seed to Q, fail */
1.970 + return SECFailure;
1.971 +}
1.972 +
1.973 +
1.974 +
1.975 +/*
1.976 +** Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
1.977 +** which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2
1.978 +** Generate P from Q, seed, L, and offset.
1.979 +*/
1.980 +static SECStatus
1.981 +makePfromQandSeed(
1.982 + HASH_HashType hashtype, /* selected Hashing algorithm */
1.983 + unsigned int L, /* Length of P in bits. Per FIPS 186. */
1.984 + unsigned int N, /* Length of Q in bits. Per FIPS 186. */
1.985 + unsigned int offset, /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */
1.986 + unsigned int seedlen, /* input. Length of seed in bits. (g in 186-1)*/
1.987 +const SECItem * seed, /* input. */
1.988 +const mp_int * Q, /* input. */
1.989 + mp_int * P) /* output. */
1.990 +{
1.991 + unsigned int j; /* Per FIPS 186-3 App. A.1.1.2 (k in 186-1)*/
1.992 + unsigned int n; /* Per FIPS 186, appendix 2.2. */
1.993 + mp_digit b; /* Per FIPS 186, appendix 2.2. */
1.994 + unsigned int outlen; /* Per FIPS 186-3 App. A.1.1.2 */
1.995 + unsigned int hashlen; /* outlen in bytes */
1.996 + unsigned char V_j[HASH_LENGTH_MAX];
1.997 + mp_int W, X, c, twoQ, V_n, tmp;
1.998 + mp_err err = MP_OKAY;
1.999 + SECStatus rv = SECSuccess;
1.1000 + /* Initialize bignums */
1.1001 + MP_DIGITS(&W) = 0;
1.1002 + MP_DIGITS(&X) = 0;
1.1003 + MP_DIGITS(&c) = 0;
1.1004 + MP_DIGITS(&twoQ) = 0;
1.1005 + MP_DIGITS(&V_n) = 0;
1.1006 + MP_DIGITS(&tmp) = 0;
1.1007 + CHECK_MPI_OK( mp_init(&W) );
1.1008 + CHECK_MPI_OK( mp_init(&X) );
1.1009 + CHECK_MPI_OK( mp_init(&c) );
1.1010 + CHECK_MPI_OK( mp_init(&twoQ) );
1.1011 + CHECK_MPI_OK( mp_init(&tmp) );
1.1012 + CHECK_MPI_OK( mp_init(&V_n) );
1.1013 +
1.1014 + hashlen = HASH_ResultLen(hashtype);
1.1015 + outlen = hashlen*PR_BITS_PER_BYTE;
1.1016 +
1.1017 + /* L - 1 = n*outlen + b */
1.1018 + n = (L - 1) / outlen;
1.1019 + b = (L - 1) % outlen;
1.1020 +
1.1021 + /* ******************************************************************
1.1022 + ** Step 11.1 (Step 7 in 186-1)
1.1023 + ** "for j = 0 ... n let
1.1024 + ** V_j = SHA[(SEED + offset + j) mod 2**seedlen]."
1.1025 + **
1.1026 + ** Step 11.2 (Step 8 in 186-1)
1.1027 + ** "W = V_0 + (V_1 * 2**outlen) + ... + (V_n-1 * 2**((n-1)*outlen))
1.1028 + ** + ((V_n mod 2**b) * 2**(n*outlen))
1.1029 + */
1.1030 + for (j=0; j<n; ++j) { /* Do the first n terms of V_j */
1.1031 + /* Do step 11.1 for iteration j.
1.1032 + ** V_j = HASH[(seed + offset + j) mod 2**g]
1.1033 + */
1.1034 + CHECK_SEC_OK( addToSeedThenHash(hashtype,seed,offset+j, seedlen, V_j) );
1.1035 + /* Do step 11.2 for iteration j.
1.1036 + ** W += V_j * 2**(j*outlen)
1.1037 + */
1.1038 + OCTETS_TO_MPINT(V_j, &tmp, hashlen); /* get bignum V_j */
1.1039 + CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, j*outlen) );/* tmp=V_j << j*outlen */
1.1040 + CHECK_MPI_OK( mp_add(&W, &tmp, &W) ); /* W += tmp */
1.1041 + }
1.1042 + /* Step 11.2, continued.
1.1043 + ** [W += ((V_n mod 2**b) * 2**(n*outlen))]
1.1044 + */
1.1045 + CHECK_SEC_OK( addToSeedThenHash(hashtype, seed, offset + n, seedlen, V_j) );
1.1046 + OCTETS_TO_MPINT(V_j, &V_n, hashlen); /* get bignum V_n */
1.1047 + CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) ); /* tmp = V_n mod 2**b */
1.1048 + CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*outlen) ); /* tmp = tmp << n*outlen */
1.1049 + CHECK_MPI_OK( mp_add(&W, &tmp, &W) ); /* W += tmp */
1.1050 + /* Step 11.3, (Step 8 in 186-1)
1.1051 + ** "X = W + 2**(L-1).
1.1052 + ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
1.1053 + */
1.1054 + CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) ); /* X = 2**(L-1) */
1.1055 + CHECK_MPI_OK( mp_add(&X, &W, &X) ); /* X += W */
1.1056 + /*************************************************************
1.1057 + ** Step 11.4. (Step 9 in 186-1)
1.1058 + ** "c = X mod 2q"
1.1059 + */
1.1060 + CHECK_MPI_OK( mp_mul_2(Q, &twoQ) ); /* 2q */
1.1061 + CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) ); /* c = X mod 2q */
1.1062 + /*************************************************************
1.1063 + ** Step 11.5. (Step 9 in 186-1)
1.1064 + ** "p = X - (c - 1).
1.1065 + ** Note that p is congruent to 1 mod 2q."
1.1066 + */
1.1067 + CHECK_MPI_OK( mp_sub_d(&c, 1, &c) ); /* c -= 1 */
1.1068 + CHECK_MPI_OK( mp_sub(&X, &c, P) ); /* P = X - c */
1.1069 +cleanup:
1.1070 + mp_clear(&W);
1.1071 + mp_clear(&X);
1.1072 + mp_clear(&c);
1.1073 + mp_clear(&twoQ);
1.1074 + mp_clear(&V_n);
1.1075 + mp_clear(&tmp);
1.1076 + if (err) {
1.1077 + MP_TO_SEC_ERROR(err);
1.1078 + return SECFailure;
1.1079 + }
1.1080 + return rv;
1.1081 +}
1.1082 +
1.1083 +/*
1.1084 +** Generate G from h, P, and Q.
1.1085 +*/
1.1086 +static SECStatus
1.1087 +makeGfromH(const mp_int *P, /* input. */
1.1088 + const mp_int *Q, /* input. */
1.1089 + mp_int *H, /* input and output. */
1.1090 + mp_int *G, /* output. */
1.1091 + PRBool *passed)
1.1092 +{
1.1093 + mp_int exp, pm1;
1.1094 + mp_err err = MP_OKAY;
1.1095 + SECStatus rv = SECSuccess;
1.1096 + *passed = PR_FALSE;
1.1097 + MP_DIGITS(&exp) = 0;
1.1098 + MP_DIGITS(&pm1) = 0;
1.1099 + CHECK_MPI_OK( mp_init(&exp) );
1.1100 + CHECK_MPI_OK( mp_init(&pm1) );
1.1101 + CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) ); /* P - 1 */
1.1102 + if ( mp_cmp(H, &pm1) >= 0) /* H >= P-1 */
1.1103 + CHECK_MPI_OK( mp_sub(H, &pm1, H) ); /* H = H mod (P-1) */
1.1104 + /* Let b = 2**n (smallest power of 2 greater than P).
1.1105 + ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1
1.1106 + ** so the above operation safely computes H mod (P-1)
1.1107 + */
1.1108 + /* Check for H = to 0 or 1. Regen H if so. (Regen means return error). */
1.1109 + if (mp_cmp_d(H, 1) <= 0) {
1.1110 + rv = SECFailure;
1.1111 + goto cleanup;
1.1112 + }
1.1113 + /* Compute G, according to the equation G = (H ** ((P-1)/Q)) mod P */
1.1114 + CHECK_MPI_OK( mp_div(&pm1, Q, &exp, NULL) ); /* exp = (P-1)/Q */
1.1115 + CHECK_MPI_OK( mp_exptmod(H, &exp, P, G) ); /* G = H ** exp mod P */
1.1116 + /* Check for G == 0 or G == 1, return error if so. */
1.1117 + if (mp_cmp_d(G, 1) <= 0) {
1.1118 + rv = SECFailure;
1.1119 + goto cleanup;
1.1120 + }
1.1121 + *passed = PR_TRUE;
1.1122 +cleanup:
1.1123 + mp_clear(&exp);
1.1124 + mp_clear(&pm1);
1.1125 + if (err) {
1.1126 + MP_TO_SEC_ERROR(err);
1.1127 + rv = SECFailure;
1.1128 + }
1.1129 + return rv;
1.1130 +}
1.1131 +
1.1132 +/*
1.1133 +** Generate G from seed, index, P, and Q.
1.1134 +*/
1.1135 +static SECStatus
1.1136 +makeGfromIndex(HASH_HashType hashtype,
1.1137 + const mp_int *P, /* input. */
1.1138 + const mp_int *Q, /* input. */
1.1139 + const SECItem *seed, /* input. */
1.1140 + unsigned char index, /* input. */
1.1141 + mp_int *G) /* input/output */
1.1142 +{
1.1143 + mp_int e, pm1, W;
1.1144 + unsigned int count;
1.1145 + unsigned char data[HASH_LENGTH_MAX];
1.1146 + unsigned int len;
1.1147 + mp_err err = MP_OKAY;
1.1148 + SECStatus rv = SECSuccess;
1.1149 + const SECHashObject *hashobj;
1.1150 + void *hashcx = NULL;
1.1151 +
1.1152 + MP_DIGITS(&e) = 0;
1.1153 + MP_DIGITS(&pm1) = 0;
1.1154 + MP_DIGITS(&W) = 0;
1.1155 + CHECK_MPI_OK( mp_init(&e) );
1.1156 + CHECK_MPI_OK( mp_init(&pm1) );
1.1157 + CHECK_MPI_OK( mp_init(&W) );
1.1158 +
1.1159 + /* initialize our hash stuff */
1.1160 + hashobj = HASH_GetRawHashObject(hashtype);
1.1161 + if (hashobj == NULL) {
1.1162 + /* shouldn't happen */
1.1163 + PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1.1164 + rv = SECFailure;
1.1165 + goto cleanup;
1.1166 + }
1.1167 + hashcx = hashobj->create();
1.1168 + if (hashcx == NULL) {
1.1169 + rv = SECFailure;
1.1170 + goto cleanup;
1.1171 + }
1.1172 +
1.1173 + CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) ); /* P - 1 */
1.1174 + /* Step 3 e = (p-1)/q */
1.1175 + CHECK_MPI_OK( mp_div(&pm1, Q, &e, NULL) ); /* e = (P-1)/Q */
1.1176 + /* Steps 4, 5, and 6 */
1.1177 + /* count is a 16 bit value in the spec. We actually represent count
1.1178 + * as more than 16 bits so we can easily detect the 16 bit overflow */
1.1179 +#define MAX_COUNT 0x10000
1.1180 + for (count = 1; count < MAX_COUNT; count++) {
1.1181 + /* step 7
1.1182 + * U = domain_param_seed || "ggen" || index || count
1.1183 + * step 8
1.1184 + * W = HASH(U)
1.1185 + */
1.1186 + hashobj->begin(hashcx);
1.1187 + hashobj->update(hashcx,seed->data,seed->len);
1.1188 + hashobj->update(hashcx, (unsigned char *)"ggen", 4);
1.1189 + hashobj->update(hashcx,&index, 1);
1.1190 + data[0] = (count >> 8) & 0xff;
1.1191 + data[1] = count & 0xff;
1.1192 + hashobj->update(hashcx, data, 2);
1.1193 + hashobj->end(hashcx, data, &len, sizeof(data));
1.1194 + OCTETS_TO_MPINT(data, &W, len);
1.1195 + /* step 9. g = W**e mod p */
1.1196 + CHECK_MPI_OK( mp_exptmod(&W, &e, P, G) );
1.1197 + /* step 10. if (g < 2) then goto step 5 */
1.1198 + /* NOTE: this weird construct is to keep the flow according to the spec.
1.1199 + * the continue puts us back to step 5 of the for loop */
1.1200 + if (mp_cmp_d(G, 2) < 0) {
1.1201 + continue;
1.1202 + }
1.1203 + break; /* step 11 follows step 10 if the test condition is false */
1.1204 + }
1.1205 + if (count >= MAX_COUNT) {
1.1206 + rv = SECFailure; /* last part of step 6 */
1.1207 + }
1.1208 + /* step 11.
1.1209 + * return valid G */
1.1210 +cleanup:
1.1211 + PORT_Memset(data, 0, sizeof(data));
1.1212 + if (hashcx) {
1.1213 + hashobj->destroy(hashcx, PR_TRUE);
1.1214 + }
1.1215 + mp_clear(&e);
1.1216 + mp_clear(&pm1);
1.1217 + mp_clear(&W);
1.1218 + if (err) {
1.1219 + MP_TO_SEC_ERROR(err);
1.1220 + rv = SECFailure;
1.1221 + }
1.1222 + return rv;
1.1223 +}
1.1224 +
1.1225 +/* This code uses labels and gotos, so that it can follow the numbered
1.1226 +** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely,
1.1227 +** and so that the correctness of this code can be easily verified.
1.1228 +** So, please forgive the ugly c code.
1.1229 +**/
1.1230 +static SECStatus
1.1231 +pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type,
1.1232 + unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy)
1.1233 +{
1.1234 + unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1.1235 + unsigned int b; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1.1236 + unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/
1.1237 + unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1.1238 + unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1.1239 + unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */
1.1240 + unsigned int maxCount;
1.1241 + HASH_HashType hashtype;
1.1242 + SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
1.1243 + PLArenaPool *arena = NULL;
1.1244 + PQGParams *params = NULL;
1.1245 + PQGVerify *verify = NULL;
1.1246 + PRBool passed;
1.1247 + SECItem hit = { 0, 0, 0 };
1.1248 + SECItem firstseed = { 0, 0, 0 };
1.1249 + SECItem qseed = { 0, 0, 0 };
1.1250 + SECItem pseed = { 0, 0, 0 };
1.1251 + mp_int P, Q, G, H, l, p0;
1.1252 + mp_err err = MP_OKAY;
1.1253 + SECStatus rv = SECFailure;
1.1254 + int iterations = 0;
1.1255 +
1.1256 +
1.1257 + /* Step 1. L and N already checked by caller*/
1.1258 + /* Step 2. if (seedlen < N) return INVALID; */
1.1259 + if (seedBytes < N/PR_BITS_PER_BYTE || !pParams || !pVfy) {
1.1260 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1261 + return SECFailure;
1.1262 + }
1.1263 + /* Initialize an arena for the params. */
1.1264 + arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1.1265 + if (!arena) {
1.1266 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.1267 + return SECFailure;
1.1268 + }
1.1269 + params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams));
1.1270 + if (!params) {
1.1271 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.1272 + PORT_FreeArena(arena, PR_TRUE);
1.1273 + return SECFailure;
1.1274 + }
1.1275 + params->arena = arena;
1.1276 + /* Initialize an arena for the verify. */
1.1277 + arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1.1278 + if (!arena) {
1.1279 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.1280 + PORT_FreeArena(params->arena, PR_TRUE);
1.1281 + return SECFailure;
1.1282 + }
1.1283 + verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify));
1.1284 + if (!verify) {
1.1285 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.1286 + PORT_FreeArena(arena, PR_TRUE);
1.1287 + PORT_FreeArena(params->arena, PR_TRUE);
1.1288 + return SECFailure;
1.1289 + }
1.1290 + verify->arena = arena;
1.1291 + seed = &verify->seed;
1.1292 + arena = NULL;
1.1293 + /* Initialize bignums */
1.1294 + MP_DIGITS(&P) = 0;
1.1295 + MP_DIGITS(&Q) = 0;
1.1296 + MP_DIGITS(&G) = 0;
1.1297 + MP_DIGITS(&H) = 0;
1.1298 + MP_DIGITS(&l) = 0;
1.1299 + MP_DIGITS(&p0) = 0;
1.1300 + CHECK_MPI_OK( mp_init(&P) );
1.1301 + CHECK_MPI_OK( mp_init(&Q) );
1.1302 + CHECK_MPI_OK( mp_init(&G) );
1.1303 + CHECK_MPI_OK( mp_init(&H) );
1.1304 + CHECK_MPI_OK( mp_init(&l) );
1.1305 + CHECK_MPI_OK( mp_init(&p0) );
1.1306 +
1.1307 + /* Select Hash and Compute lengths. */
1.1308 + /* getFirstHash gives us the smallest acceptable hash for this key
1.1309 + * strength */
1.1310 + hashtype = getFirstHash(L,N);
1.1311 + outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE;
1.1312 +
1.1313 + /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */
1.1314 + n = (L - 1) / outlen;
1.1315 + /* Step 4: b = L -1 - (n*outlen); (same as n = (L-1) mod outlen) */
1.1316 + b = (L - 1) % outlen;
1.1317 + seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */
1.1318 +step_5:
1.1319 + /* ******************************************************************
1.1320 + ** Step 5. (Step 1 in 186-1)
1.1321 + ** "Choose an abitrary sequence of at least N bits and call it SEED.
1.1322 + ** Let g be the length of SEED in bits."
1.1323 + */
1.1324 + if (++iterations > MAX_ITERATIONS) { /* give up after a while */
1.1325 + PORT_SetError(SEC_ERROR_NEED_RANDOM);
1.1326 + goto cleanup;
1.1327 + }
1.1328 + seed->len = seedBytes;
1.1329 + CHECK_SEC_OK( getPQseed(seed, verify->arena) );
1.1330 + /* ******************************************************************
1.1331 + ** Step 6. (Step 2 in 186-1)
1.1332 + **
1.1333 + ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]. (186-1)"
1.1334 + ** "Compute U = HASH[SEED] 2**(N-1). (186-3)"
1.1335 + **
1.1336 + ** Step 7. (Step 3 in 186-1)
1.1337 + ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
1.1338 + ** and the least signficant bit to 1. In terms of boolean operations,
1.1339 + ** Q = U OR 2**159 OR 1. Note that 2**159 < Q < 2**160. (186-1)"
1.1340 + **
1.1341 + ** "q = 2**(N-1) + U + 1 - (U mod 2) (186-3)
1.1342 + **
1.1343 + ** Note: Both formulations are the same for U < 2**(N-1) and N=160
1.1344 + **
1.1345 + ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block
1.1346 + ** FIPS186_3_ST_TYPE.
1.1347 + */
1.1348 + if (type == FIPS186_1_TYPE) {
1.1349 + CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) );
1.1350 + } else if (type == FIPS186_3_TYPE) {
1.1351 + CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) );
1.1352 + } else {
1.1353 + /* FIPS186_3_ST_TYPE */
1.1354 + int qgen_counter, pgen_counter;
1.1355 +
1.1356 + /* Step 1 (L,N) already checked for acceptability */
1.1357 +
1.1358 + firstseed = *seed;
1.1359 + qgen_counter = 0;
1.1360 + /* Step 2. Use N and firstseed to generate random prime q
1.1361 + * using Apendix C.6 */
1.1362 + CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q,
1.1363 + &qseed, &qgen_counter) );
1.1364 + /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0
1.1365 + * using Appendix C.6 */
1.1366 + pgen_counter = 0;
1.1367 + CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1,
1.1368 + &qseed, &p0, &pseed, &pgen_counter) );
1.1369 + /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */
1.1370 + CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L,
1.1371 + &p0, &Q, &P, &pseed, &pgen_counter) );
1.1372 +
1.1373 + /* combine all the seeds */
1.1374 + seed->len = firstseed.len +qseed.len + pseed.len;
1.1375 + seed->data = PORT_ArenaZAlloc(verify->arena, seed->len);
1.1376 + if (seed->data == NULL) {
1.1377 + goto cleanup;
1.1378 + }
1.1379 + PORT_Memcpy(seed->data, firstseed.data, firstseed.len);
1.1380 + PORT_Memcpy(seed->data+firstseed.len, pseed.data, pseed.len);
1.1381 + PORT_Memcpy(seed->data+firstseed.len+pseed.len, qseed.data, qseed.len);
1.1382 + counter = 0 ; /* (qgen_counter << 16) | pgen_counter; */
1.1383 +
1.1384 + /* we've generated both P and Q now, skip to generating G */
1.1385 + goto generate_G;
1.1386 + }
1.1387 + /* ******************************************************************
1.1388 + ** Step 8. (Step 4 in 186-1)
1.1389 + ** "Use a robust primality testing algorithm to test whether q is prime."
1.1390 + **
1.1391 + ** Appendix 2.1 states that a Rabin test with at least 50 iterations
1.1392 + ** "will give an acceptable probability of error."
1.1393 + */
1.1394 + /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
1.1395 + err = mpp_pprime(&Q, prime_testcount_q(L,N));
1.1396 + passed = (err == MP_YES) ? SECSuccess : SECFailure;
1.1397 + /* ******************************************************************
1.1398 + ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)."
1.1399 + */
1.1400 + if (passed != SECSuccess)
1.1401 + goto step_5;
1.1402 + /* ******************************************************************
1.1403 + ** Step 10.
1.1404 + ** offset = 1;
1.1405 + **( Step 6b 186-1)"Let counter = 0 and offset = 2."
1.1406 + */
1.1407 + offset = (type == FIPS186_1_TYPE) ? 2 : 1;
1.1408 + /*
1.1409 + ** Step 11. (Step 6a,13a,14 in 186-1)
1.1410 + ** For counter - 0 to (4L-1) do
1.1411 + **
1.1412 + */
1.1413 + maxCount = L >= 1024 ? (4*L - 1) : 4095;
1.1414 + for (counter = 0; counter <= maxCount; counter++) {
1.1415 + /* ******************************************************************
1.1416 + ** Step 11.1 (Step 7 in 186-1)
1.1417 + ** "for j = 0 ... n let
1.1418 + ** V_j = HASH[(SEED + offset + j) mod 2**seedlen]."
1.1419 + **
1.1420 + ** Step 11.2 (Step 8 in 186-1)
1.1421 + ** "W = V_0 + V_1*2**outlen+...+ V_n-1 * 2**((n-1)*outlen) +
1.1422 + ** ((Vn* mod 2**b)*2**(n*outlen))"
1.1423 + ** Step 11.3 (Step 8 in 186-1)
1.1424 + ** "X = W + 2**(L-1)
1.1425 + ** Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
1.1426 + **
1.1427 + ** Step 11.4 (Step 9 in 186-1).
1.1428 + ** "c = X mod 2q"
1.1429 + **
1.1430 + ** Step 11.5 (Step 9 in 186-1).
1.1431 + ** " p = X - (c - 1).
1.1432 + ** Note that p is congruent to 1 mod 2q."
1.1433 + */
1.1434 + CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, seedlen,
1.1435 + seed, &Q, &P) );
1.1436 + /*************************************************************
1.1437 + ** Step 11.6. (Step 10 in 186-1)
1.1438 + ** "if p < 2**(L-1), then goto step 11.9. (step 13 in 186-1)"
1.1439 + */
1.1440 + CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */
1.1441 + if (mp_cmp(&P, &l) < 0)
1.1442 + goto step_11_9;
1.1443 + /************************************************************
1.1444 + ** Step 11.7 (step 11 in 186-1)
1.1445 + ** "Perform a robust primality test on p."
1.1446 + */
1.1447 + /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
1.1448 + err = mpp_pprime(&P, prime_testcount_p(L, N));
1.1449 + passed = (err == MP_YES) ? SECSuccess : SECFailure;
1.1450 + /* ******************************************************************
1.1451 + ** Step 11.8. "If p is determined to be primed return VALID
1.1452 + ** values of p, q, seed and counter."
1.1453 + */
1.1454 + if (passed == SECSuccess)
1.1455 + break;
1.1456 +step_11_9:
1.1457 + /* ******************************************************************
1.1458 + ** Step 11.9. "offset = offset + n + 1."
1.1459 + */
1.1460 + offset += n + 1;
1.1461 + }
1.1462 + /* ******************************************************************
1.1463 + ** Step 12. "goto step 5."
1.1464 + **
1.1465 + ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8
1.1466 + ** and now need to return p,q, seed, and counter.
1.1467 + */
1.1468 + if (counter > maxCount)
1.1469 + goto step_5;
1.1470 +
1.1471 +generate_G:
1.1472 + /* ******************************************************************
1.1473 + ** returning p, q, seed and counter
1.1474 + */
1.1475 + if (type == FIPS186_1_TYPE) {
1.1476 + /* Generate g, This is called the "Unverifiable Generation of g
1.1477 + * in FIPA186-3 Appedix A.2.1. For compatibility we maintain
1.1478 + * this version of the code */
1.1479 + SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */
1.1480 + if (!hit.data) goto cleanup;
1.1481 + do {
1.1482 + /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
1.1483 + CHECK_SEC_OK( generate_h_candidate(&hit, &H) );
1.1484 + CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );
1.1485 + } while (passed != PR_TRUE);
1.1486 + MPINT_TO_SECITEM(&H, &verify->h, verify->arena);
1.1487 + } else {
1.1488 + unsigned char index = 1; /* default to 1 */
1.1489 + verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1);
1.1490 + if (verify->h.data == NULL) { goto cleanup; }
1.1491 + verify->h.len = 1;
1.1492 + verify->h.data[0] = index;
1.1493 + /* Generate g, using the FIPS 186-3 Appendix A.23 */
1.1494 + CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G) );
1.1495 + }
1.1496 + /* All generation is done. Now, save the PQG params. */
1.1497 + MPINT_TO_SECITEM(&P, ¶ms->prime, params->arena);
1.1498 + MPINT_TO_SECITEM(&Q, ¶ms->subPrime, params->arena);
1.1499 + MPINT_TO_SECITEM(&G, ¶ms->base, params->arena);
1.1500 + verify->counter = counter;
1.1501 + *pParams = params;
1.1502 + *pVfy = verify;
1.1503 +cleanup:
1.1504 + if (pseed.data) {
1.1505 + PORT_Free(pseed.data);
1.1506 + }
1.1507 + if (qseed.data) {
1.1508 + PORT_Free(qseed.data);
1.1509 + }
1.1510 + mp_clear(&P);
1.1511 + mp_clear(&Q);
1.1512 + mp_clear(&G);
1.1513 + mp_clear(&H);
1.1514 + mp_clear(&l);
1.1515 + mp_clear(&p0);
1.1516 + if (err) {
1.1517 + MP_TO_SEC_ERROR(err);
1.1518 + rv = SECFailure;
1.1519 + }
1.1520 + if (rv) {
1.1521 + PORT_FreeArena(params->arena, PR_TRUE);
1.1522 + PORT_FreeArena(verify->arena, PR_TRUE);
1.1523 + }
1.1524 + if (hit.data) {
1.1525 + SECITEM_FreeItem(&hit, PR_FALSE);
1.1526 + }
1.1527 + return rv;
1.1528 +}
1.1529 +
1.1530 +SECStatus
1.1531 +PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
1.1532 +{
1.1533 + unsigned int L; /* Length of P in bits. Per FIPS 186. */
1.1534 + unsigned int seedBytes;
1.1535 +
1.1536 + if (j > 8 || !pParams || !pVfy) {
1.1537 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1538 + return SECFailure;
1.1539 + }
1.1540 + L = 512 + (j * 64); /* bits in P */
1.1541 + seedBytes = L/8;
1.1542 + return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,
1.1543 + pParams, pVfy);
1.1544 +}
1.1545 +
1.1546 +SECStatus
1.1547 +PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
1.1548 + PQGParams **pParams, PQGVerify **pVfy)
1.1549 +{
1.1550 + unsigned int L; /* Length of P in bits. Per FIPS 186. */
1.1551 +
1.1552 + if (j > 8 || !pParams || !pVfy) {
1.1553 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1554 + return SECFailure;
1.1555 + }
1.1556 + L = 512 + (j * 64); /* bits in P */
1.1557 + return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,
1.1558 + pParams, pVfy);
1.1559 +}
1.1560 +
1.1561 +SECStatus
1.1562 +PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes,
1.1563 + PQGParams **pParams, PQGVerify **pVfy)
1.1564 +{
1.1565 + if (N == 0) {
1.1566 + N = pqg_get_default_N(L);
1.1567 + }
1.1568 + if (seedBytes == 0) {
1.1569 + /* seedBytes == L/8 for probable primes, N/8 for Shawe-Taylor Primes */
1.1570 + seedBytes = N/8;
1.1571 + }
1.1572 + if (pqg_validate_dsa2(L,N) != SECSuccess) {
1.1573 + /* error code already set */
1.1574 + return SECFailure;
1.1575 + }
1.1576 + return pqg_ParamGen(L, N, FIPS186_3_ST_TYPE, seedBytes, pParams, pVfy);
1.1577 +}
1.1578 +
1.1579 +
1.1580 +/*
1.1581 + * verify can use vfy structures returned from either FIPS186-1 or
1.1582 + * FIPS186-2, and can handle differences in selected Hash functions to
1.1583 + * generate the parameters.
1.1584 + */
1.1585 +SECStatus
1.1586 +PQG_VerifyParams(const PQGParams *params,
1.1587 + const PQGVerify *vfy, SECStatus *result)
1.1588 +{
1.1589 + SECStatus rv = SECSuccess;
1.1590 + unsigned int g, n, L, N, offset, outlen;
1.1591 + mp_int p0, P, Q, G, P_, Q_, G_, r, h;
1.1592 + mp_err err = MP_OKAY;
1.1593 + int j;
1.1594 + unsigned int counter_max = 0; /* handle legacy L < 1024 */
1.1595 + int qseed_len;
1.1596 + SECItem pseed_ = {0, 0, 0};
1.1597 + HASH_HashType hashtype;
1.1598 + pqgGenType type;
1.1599 +
1.1600 +#define CHECKPARAM(cond) \
1.1601 + if (!(cond)) { \
1.1602 + *result = SECFailure; \
1.1603 + goto cleanup; \
1.1604 + }
1.1605 + if (!params || !vfy || !result) {
1.1606 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1607 + return SECFailure;
1.1608 + }
1.1609 + /* always need at least p, q, and seed for any meaningful check */
1.1610 + if ((params->prime.len == 0) || (params->subPrime.len == 0) ||
1.1611 + (vfy->seed.len == 0)) {
1.1612 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1613 + return SECFailure;
1.1614 + }
1.1615 + /* we want to either check PQ or G or both. If we don't have G, make
1.1616 + * sure we have count so we can check P. */
1.1617 + if ((params->base.len == 0) && (vfy->counter == -1)) {
1.1618 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.1619 + return SECFailure;
1.1620 + }
1.1621 +
1.1622 + MP_DIGITS(&p0) = 0;
1.1623 + MP_DIGITS(&P) = 0;
1.1624 + MP_DIGITS(&Q) = 0;
1.1625 + MP_DIGITS(&G) = 0;
1.1626 + MP_DIGITS(&P_) = 0;
1.1627 + MP_DIGITS(&Q_) = 0;
1.1628 + MP_DIGITS(&G_) = 0;
1.1629 + MP_DIGITS(&r) = 0;
1.1630 + MP_DIGITS(&h) = 0;
1.1631 + CHECK_MPI_OK( mp_init(&p0) );
1.1632 + CHECK_MPI_OK( mp_init(&P) );
1.1633 + CHECK_MPI_OK( mp_init(&Q) );
1.1634 + CHECK_MPI_OK( mp_init(&G) );
1.1635 + CHECK_MPI_OK( mp_init(&P_) );
1.1636 + CHECK_MPI_OK( mp_init(&Q_) );
1.1637 + CHECK_MPI_OK( mp_init(&G_) );
1.1638 + CHECK_MPI_OK( mp_init(&r) );
1.1639 + CHECK_MPI_OK( mp_init(&h) );
1.1640 + *result = SECSuccess;
1.1641 + SECITEM_TO_MPINT(params->prime, &P);
1.1642 + SECITEM_TO_MPINT(params->subPrime, &Q);
1.1643 + /* if G isn't specified, just check P and Q */
1.1644 + if (params->base.len != 0) {
1.1645 + SECITEM_TO_MPINT(params->base, &G);
1.1646 + }
1.1647 + /* 1. Check (L,N) pair */
1.1648 + N = mpl_significant_bits(&Q);
1.1649 + L = mpl_significant_bits(&P);
1.1650 + if (L < 1024) {
1.1651 + /* handle DSA1 pqg parameters with less thatn 1024 bits*/
1.1652 + CHECKPARAM( N == DSA1_Q_BITS );
1.1653 + j = PQG_PBITS_TO_INDEX(L);
1.1654 + CHECKPARAM( j >= 0 && j <= 8 );
1.1655 + counter_max = 4096;
1.1656 + } else {
1.1657 + /* handle DSA2 parameters (includes DSA1, 1024 bits) */
1.1658 + CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess);
1.1659 + counter_max = 4*L;
1.1660 + }
1.1661 + /* 3. G < P */
1.1662 + if (params->base.len != 0) {
1.1663 + CHECKPARAM( mp_cmp(&G, &P) < 0 );
1.1664 + }
1.1665 + /* 4. P % Q == 1 */
1.1666 + CHECK_MPI_OK( mp_mod(&P, &Q, &r) );
1.1667 + CHECKPARAM( mp_cmp_d(&r, 1) == 0 );
1.1668 + /* 5. Q is prime */
1.1669 + CHECKPARAM( mpp_pprime(&Q, prime_testcount_q(L,N)) == MP_YES );
1.1670 + /* 6. P is prime */
1.1671 + CHECKPARAM( mpp_pprime(&P, prime_testcount_p(L,N)) == MP_YES );
1.1672 + /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
1.1673 + /* continue processing P */
1.1674 + /* 7. counter < 4*L */
1.1675 + CHECKPARAM( (vfy->counter == -1) || (vfy->counter < counter_max) );
1.1676 + /* 8. g >= N and g < 2*L (g is length of seed in bits) */
1.1677 + g = vfy->seed.len * 8;
1.1678 + CHECKPARAM( g >= N && g < counter_max/2 );
1.1679 + /* 9. Q generated from SEED matches Q in PQGParams. */
1.1680 + /* This function checks all possible hash and generation types to
1.1681 + * find a Q_ which matches Q. */
1.1682 + CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len,
1.1683 + &hashtype, &type) == SECSuccess );
1.1684 + CHECKPARAM( mp_cmp(&Q, &Q_) == 0 );
1.1685 + if (type == FIPS186_3_ST_TYPE) {
1.1686 + SECItem qseed = { 0, 0, 0 };
1.1687 + SECItem pseed = { 0, 0, 0 };
1.1688 + int first_seed_len;
1.1689 + int pgen_counter = 0;
1.1690 +
1.1691 + /* extract pseed and qseed from domain_parameter_seed, which is
1.1692 + * first_seed || pseed || qseed. qseed is first_seed + small_integer
1.1693 + * pseed is qseed + small_integer. This means most of the time
1.1694 + * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or
1.1695 + * pseed.len will be one greater than first_seed.len, so we can
1.1696 + * depend on the fact that
1.1697 + * first_seed.len = floor(domain_parameter_seed.len/3).
1.1698 + * findQfromSeed returned qseed.len, so we can calculate pseed.len as
1.1699 + * pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len
1.1700 + * this is probably over kill, since 99.999% of the time they will all
1.1701 + * be equal.
1.1702 + *
1.1703 + * With the lengths, we can now find the offsets;
1.1704 + * first_seed.data = domain_parameter_seed.data + 0
1.1705 + * pseed.data = domain_parameter_seed.data + first_seed.len
1.1706 + * qseed.data = domain_parameter_seed.data
1.1707 + * + domain_paramter_seed.len - qseed.len
1.1708 + *
1.1709 + */
1.1710 + first_seed_len = vfy->seed.len/3;
1.1711 + CHECKPARAM(qseed_len < vfy->seed.len);
1.1712 + CHECKPARAM(first_seed_len*8 > N-1);
1.1713 + CHECKPARAM(first_seed_len+qseed_len < vfy->seed.len);
1.1714 + qseed.len = qseed_len;
1.1715 + qseed.data = vfy->seed.data + vfy->seed.len - qseed.len;
1.1716 + pseed.len = vfy->seed.len - (first_seed_len+qseed_len);
1.1717 + pseed.data = vfy->seed.data + first_seed_len;
1.1718 +
1.1719 + /*
1.1720 + * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed
1.1721 + * above in our initial checks, Step 2 was completed by
1.1722 + * findQfromSeed */
1.1723 +
1.1724 + /* Step 3 (status, c0, prime_seed, prime_gen_counter) =
1.1725 + ** (ST_Random_Prime((ceil(length/2)+1, input_seed)
1.1726 + */
1.1727 + CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, (L+1)/2+1,
1.1728 + &qseed, &p0, &pseed_, &pgen_counter) );
1.1729 + /* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */
1.1730 + CHECK_SEC_OK( makePrimefromPrimesShaweTaylor(hashtype, L,
1.1731 + &p0, &Q_, &P_, &pseed_, &pgen_counter) );
1.1732 + CHECKPARAM( mp_cmp(&P, &P_) == 0 );
1.1733 + /* make sure pseed wasn't tampered with (since it is part of
1.1734 + * calculating G) */
1.1735 + CHECKPARAM( SECITEM_CompareItem(&pseed, &pseed_) == SECEqual );
1.1736 + } else if (vfy->counter == -1) {
1.1737 + /* If counter is set to -1, we are really only verifying G, skip
1.1738 + * the remainder of the checks for P */
1.1739 + CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */
1.1740 + } else {
1.1741 + /* 10. P generated from (L, counter, g, SEED, Q) matches P
1.1742 + * in PQGParams. */
1.1743 + outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE;
1.1744 + n = (L - 1) / outlen;
1.1745 + offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1);
1.1746 + CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed,
1.1747 + &Q, &P_) );
1.1748 + CHECKPARAM( mp_cmp(&P, &P_) == 0 );
1.1749 + }
1.1750 +
1.1751 + /* now check G, skip if don't have a g */
1.1752 + if (params->base.len == 0) goto cleanup;
1.1753 +
1.1754 + /* first Always check that G is OK FIPS186-3 A.2.2 & A.2.4*/
1.1755 + /* 1. 2 < G < P-1 */
1.1756 + /* P is prime, p-1 == zero 1st bit */
1.1757 + CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );
1.1758 + CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0 );
1.1759 + CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
1.1760 + /* 2. verify g**q mod p == 1 */
1.1761 + CHECK_MPI_OK( mp_exptmod(&G, &Q, &P, &h) ); /* h = G ** Q mod P */
1.1762 + CHECKPARAM(mp_cmp_d(&h, 1) == 0);
1.1763 +
1.1764 + /* no h, the above is the best we can do */
1.1765 + if (vfy->h.len == 0) {
1.1766 + if (type != FIPS186_1_TYPE) {
1.1767 + *result = SECWouldBlock;
1.1768 + }
1.1769 + goto cleanup;
1.1770 + }
1.1771 +
1.1772 + /*
1.1773 + * If h is one byte and FIPS186-3 was used to generate Q (we've verified
1.1774 + * Q was generated from seed already, then we assume that FIPS 186-3
1.1775 + * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was
1.1776 + * used to generate G.
1.1777 + */
1.1778 + if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) {
1.1779 + /* A.2.3 */
1.1780 + CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed,
1.1781 + vfy->h.data[0], &G_) );
1.1782 + CHECKPARAM( mp_cmp(&G, &G_) == 0 );
1.1783 + } else {
1.1784 + int passed;
1.1785 + /* A.2.1 */
1.1786 + SECITEM_TO_MPINT(vfy->h, &h);
1.1787 + /* 11. 1 < h < P-1 */
1.1788 + /* P is prime, p-1 == zero 1st bit */
1.1789 + CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );
1.1790 + CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) );
1.1791 + CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
1.1792 + /* 12. G generated from h matches G in PQGParams. */
1.1793 + CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );
1.1794 + CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );
1.1795 + }
1.1796 +cleanup:
1.1797 + mp_clear(&p0);
1.1798 + mp_clear(&P);
1.1799 + mp_clear(&Q);
1.1800 + mp_clear(&G);
1.1801 + mp_clear(&P_);
1.1802 + mp_clear(&Q_);
1.1803 + mp_clear(&G_);
1.1804 + mp_clear(&r);
1.1805 + mp_clear(&h);
1.1806 + if (pseed_.data) {
1.1807 + SECITEM_FreeItem(&pseed_,PR_FALSE);
1.1808 + }
1.1809 + if (err) {
1.1810 + MP_TO_SEC_ERROR(err);
1.1811 + rv = SECFailure;
1.1812 + }
1.1813 + return rv;
1.1814 +}
1.1815 +
1.1816 +/**************************************************************************
1.1817 + * Free the PQGParams struct and the things it points to. *
1.1818 + **************************************************************************/
1.1819 +void
1.1820 +PQG_DestroyParams(PQGParams *params)
1.1821 +{
1.1822 + if (params == NULL)
1.1823 + return;
1.1824 + if (params->arena != NULL) {
1.1825 + PORT_FreeArena(params->arena, PR_FALSE); /* don't zero it */
1.1826 + } else {
1.1827 + SECITEM_FreeItem(¶ms->prime, PR_FALSE); /* don't free prime */
1.1828 + SECITEM_FreeItem(¶ms->subPrime, PR_FALSE); /* don't free subPrime */
1.1829 + SECITEM_FreeItem(¶ms->base, PR_FALSE); /* don't free base */
1.1830 + PORT_Free(params);
1.1831 + }
1.1832 +}
1.1833 +
1.1834 +/**************************************************************************
1.1835 + * Free the PQGVerify struct and the things it points to. *
1.1836 + **************************************************************************/
1.1837 +
1.1838 +void
1.1839 +PQG_DestroyVerify(PQGVerify *vfy)
1.1840 +{
1.1841 + if (vfy == NULL)
1.1842 + return;
1.1843 + if (vfy->arena != NULL) {
1.1844 + PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */
1.1845 + } else {
1.1846 + SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */
1.1847 + SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */
1.1848 + PORT_Free(vfy);
1.1849 + }
1.1850 +}
