Coverage Report

Created: 2024-11-21 07:03

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