/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(¶ms->prime) * PR_BITS_PER_BYTE; |
238 | 0 | N = PQG_GetLength(¶ms->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(¶ms->prime) * PR_BITS_PER_BYTE; |
271 | 0 | N = PQG_GetLength(¶ms->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, ¶ms->prime, params->arena); |
1541 | 0 | MPINT_TO_SECITEM(&Q, ¶ms->subPrime, params->arena); |
1542 | 0 | MPINT_TO_SECITEM(&G, ¶ms->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(¶ms->prime, PR_FALSE); /* don't free prime */ |
1904 | 0 | SECITEM_ZfreeItem(¶ms->subPrime, PR_FALSE); /* don't free subPrime */ |
1905 | 0 | SECITEM_ZfreeItem(¶ms->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 | } |