Line data Source code
1 : /* crypto/dsa/dsa_gen.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : * All rights reserved.
4 : *
5 : * This package is an SSL implementation written
6 : * by Eric Young (eay@cryptsoft.com).
7 : * The implementation was written so as to conform with Netscapes SSL.
8 : *
9 : * This library is free for commercial and non-commercial use as long as
10 : * the following conditions are aheared to. The following conditions
11 : * apply to all code found in this distribution, be it the RC4, RSA,
12 : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : * included with this distribution is covered by the same copyright terms
14 : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : *
16 : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : * the code are not to be removed.
18 : * If this package is used in a product, Eric Young should be given attribution
19 : * as the author of the parts of the library used.
20 : * This can be in the form of a textual message at program startup or
21 : * in documentation (online or textual) provided with the package.
22 : *
23 : * Redistribution and use in source and binary forms, with or without
24 : * modification, are permitted provided that the following conditions
25 : * are met:
26 : * 1. Redistributions of source code must retain the copyright
27 : * notice, this list of conditions and the following disclaimer.
28 : * 2. Redistributions in binary form must reproduce the above copyright
29 : * notice, this list of conditions and the following disclaimer in the
30 : * documentation and/or other materials provided with the distribution.
31 : * 3. All advertising materials mentioning features or use of this software
32 : * must display the following acknowledgement:
33 : * "This product includes cryptographic software written by
34 : * Eric Young (eay@cryptsoft.com)"
35 : * The word 'cryptographic' can be left out if the rouines from the library
36 : * being used are not cryptographic related :-).
37 : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : * the apps directory (application code) you must include an acknowledgement:
39 : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : * SUCH DAMAGE.
52 : *
53 : * The licence and distribution terms for any publically available version or
54 : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : * copied and put under another distribution licence
56 : * [including the GNU Public Licence.]
57 : */
58 :
59 : #undef GENUINE_DSA
60 :
61 : #ifdef GENUINE_DSA
62 : /*
63 : * Parameter generation follows the original release of FIPS PUB 186,
64 : * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180)
65 : */
66 : # define HASH EVP_sha()
67 : #else
68 : /*
69 : * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
70 : * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
71 : * 180-1)
72 : */
73 : # define HASH EVP_sha1()
74 : #endif
75 :
76 : #include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
77 :
78 : #ifndef OPENSSL_NO_SHA
79 :
80 : # include <stdio.h>
81 : # include "cryptlib.h"
82 : # include <openssl/evp.h>
83 : # include <openssl/bn.h>
84 : # include <openssl/rand.h>
85 : # include <openssl/sha.h>
86 : # include "dsa_locl.h"
87 :
88 : # ifdef OPENSSL_FIPS
89 : /* Workaround bug in prototype */
90 : # define fips_dsa_builtin_paramgen2 fips_dsa_paramgen_bad
91 : # include <openssl/fips.h>
92 : # endif
93 :
94 0 : int DSA_generate_parameters_ex(DSA *ret, int bits,
95 : const unsigned char *seed_in, int seed_len,
96 : int *counter_ret, unsigned long *h_ret,
97 : BN_GENCB *cb)
98 : {
99 : # ifdef OPENSSL_FIPS
100 : if (FIPS_mode() && !(ret->meth->flags & DSA_FLAG_FIPS_METHOD)
101 : && !(ret->flags & DSA_FLAG_NON_FIPS_ALLOW)) {
102 : DSAerr(DSA_F_DSA_GENERATE_PARAMETERS_EX, DSA_R_NON_FIPS_DSA_METHOD);
103 : return 0;
104 : }
105 : # endif
106 0 : if (ret->meth->dsa_paramgen)
107 0 : return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
108 : counter_ret, h_ret, cb);
109 : # ifdef OPENSSL_FIPS
110 : else if (FIPS_mode()) {
111 : return FIPS_dsa_generate_parameters_ex(ret, bits,
112 : seed_in, seed_len,
113 : counter_ret, h_ret, cb);
114 : }
115 : # endif
116 : else {
117 : const EVP_MD *evpmd;
118 : size_t qbits = bits >= 2048 ? 256 : 160;
119 :
120 0 : if (bits >= 2048) {
121 : qbits = 256;
122 0 : evpmd = EVP_sha256();
123 : } else {
124 : qbits = 160;
125 0 : evpmd = EVP_sha1();
126 : }
127 :
128 0 : return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
129 : seed_in, seed_len, NULL, counter_ret,
130 : h_ret, cb);
131 : }
132 : }
133 :
134 0 : int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
135 : const EVP_MD *evpmd, const unsigned char *seed_in,
136 : size_t seed_len, unsigned char *seed_out,
137 : int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
138 : {
139 : int ok = 0;
140 : unsigned char seed[SHA256_DIGEST_LENGTH];
141 : unsigned char md[SHA256_DIGEST_LENGTH];
142 : unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
143 : BIGNUM *r0, *W, *X, *c, *test;
144 : BIGNUM *g = NULL, *q = NULL, *p = NULL;
145 : BN_MONT_CTX *mont = NULL;
146 0 : int i, k, n = 0, m = 0, qsize = qbits >> 3;
147 : int counter = 0;
148 : int r = 0;
149 : BN_CTX *ctx = NULL;
150 : unsigned int h = 2;
151 :
152 0 : if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
153 : qsize != SHA256_DIGEST_LENGTH)
154 : /* invalid q size */
155 : return 0;
156 :
157 0 : if (evpmd == NULL)
158 : /* use SHA1 as default */
159 0 : evpmd = EVP_sha1();
160 :
161 0 : if (bits < 512)
162 : bits = 512;
163 :
164 0 : bits = (bits + 63) / 64 * 64;
165 :
166 : /*
167 : * NB: seed_len == 0 is special case: copy generated seed to seed_in if
168 : * it is not NULL.
169 : */
170 0 : if (seed_len && (seed_len < (size_t)qsize))
171 : seed_in = NULL; /* seed buffer too small -- ignore */
172 0 : if (seed_len > (size_t)qsize)
173 : seed_len = qsize; /* App. 2.2 of FIPS PUB 186 allows larger
174 : * SEED, but our internal buffers are
175 : * restricted to 160 bits */
176 0 : if (seed_in != NULL)
177 : memcpy(seed, seed_in, seed_len);
178 :
179 0 : if ((ctx = BN_CTX_new()) == NULL)
180 : goto err;
181 :
182 0 : if ((mont = BN_MONT_CTX_new()) == NULL)
183 : goto err;
184 :
185 0 : BN_CTX_start(ctx);
186 0 : r0 = BN_CTX_get(ctx);
187 0 : g = BN_CTX_get(ctx);
188 0 : W = BN_CTX_get(ctx);
189 0 : q = BN_CTX_get(ctx);
190 0 : X = BN_CTX_get(ctx);
191 0 : c = BN_CTX_get(ctx);
192 0 : p = BN_CTX_get(ctx);
193 0 : test = BN_CTX_get(ctx);
194 :
195 0 : if (!BN_lshift(test, BN_value_one(), bits - 1))
196 : goto err;
197 :
198 : for (;;) {
199 : for (;;) { /* find q */
200 : int seed_is_random;
201 :
202 : /* step 1 */
203 0 : if (!BN_GENCB_call(cb, 0, m++))
204 : goto err;
205 :
206 0 : if (!seed_len) {
207 0 : if (RAND_pseudo_bytes(seed, qsize) < 0)
208 : goto err;
209 : seed_is_random = 1;
210 : } else {
211 : seed_is_random = 0;
212 : seed_len = 0; /* use random seed if 'seed_in' turns out to
213 : * be bad */
214 : }
215 : memcpy(buf, seed, qsize);
216 : memcpy(buf2, seed, qsize);
217 : /* precompute "SEED + 1" for step 7: */
218 0 : for (i = qsize - 1; i >= 0; i--) {
219 0 : buf[i]++;
220 0 : if (buf[i] != 0)
221 : break;
222 : }
223 :
224 : /* step 2 */
225 0 : if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
226 : goto err;
227 0 : if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
228 : goto err;
229 0 : for (i = 0; i < qsize; i++)
230 0 : md[i] ^= buf2[i];
231 :
232 : /* step 3 */
233 0 : md[0] |= 0x80;
234 0 : md[qsize - 1] |= 0x01;
235 0 : if (!BN_bin2bn(md, qsize, q))
236 : goto err;
237 :
238 : /* step 4 */
239 0 : r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
240 : seed_is_random, cb);
241 0 : if (r > 0)
242 : break;
243 0 : if (r != 0)
244 : goto err;
245 :
246 : /* do a callback call */
247 : /* step 5 */
248 : }
249 :
250 0 : if (!BN_GENCB_call(cb, 2, 0))
251 : goto err;
252 0 : if (!BN_GENCB_call(cb, 3, 0))
253 : goto err;
254 :
255 : /* step 6 */
256 : counter = 0;
257 : /* "offset = 2" */
258 :
259 0 : n = (bits - 1) / 160;
260 :
261 : for (;;) {
262 0 : if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
263 : goto err;
264 :
265 : /* step 7 */
266 0 : BN_zero(W);
267 : /* now 'buf' contains "SEED + offset - 1" */
268 0 : for (k = 0; k <= n; k++) {
269 : /*
270 : * obtain "SEED + offset + k" by incrementing:
271 : */
272 0 : for (i = qsize - 1; i >= 0; i--) {
273 0 : buf[i]++;
274 0 : if (buf[i] != 0)
275 : break;
276 : }
277 :
278 0 : if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
279 : goto err;
280 :
281 : /* step 8 */
282 0 : if (!BN_bin2bn(md, qsize, r0))
283 : goto err;
284 0 : if (!BN_lshift(r0, r0, (qsize << 3) * k))
285 : goto err;
286 0 : if (!BN_add(W, W, r0))
287 : goto err;
288 : }
289 :
290 : /* more of step 8 */
291 0 : if (!BN_mask_bits(W, bits - 1))
292 : goto err;
293 0 : if (!BN_copy(X, W))
294 : goto err;
295 0 : if (!BN_add(X, X, test))
296 : goto err;
297 :
298 : /* step 9 */
299 0 : if (!BN_lshift1(r0, q))
300 : goto err;
301 0 : if (!BN_mod(c, X, r0, ctx))
302 : goto err;
303 0 : if (!BN_sub(r0, c, BN_value_one()))
304 : goto err;
305 0 : if (!BN_sub(p, X, r0))
306 : goto err;
307 :
308 : /* step 10 */
309 0 : if (BN_cmp(p, test) >= 0) {
310 : /* step 11 */
311 0 : r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
312 0 : if (r > 0)
313 : goto end; /* found it */
314 0 : if (r != 0)
315 : goto err;
316 : }
317 :
318 : /* step 13 */
319 0 : counter++;
320 : /* "offset = offset + n + 1" */
321 :
322 : /* step 14 */
323 0 : if (counter >= 4096)
324 : break;
325 : }
326 : }
327 : end:
328 0 : if (!BN_GENCB_call(cb, 2, 1))
329 : goto err;
330 :
331 : /* We now need to generate g */
332 : /* Set r0=(p-1)/q */
333 0 : if (!BN_sub(test, p, BN_value_one()))
334 : goto err;
335 0 : if (!BN_div(r0, NULL, test, q, ctx))
336 : goto err;
337 :
338 0 : if (!BN_set_word(test, h))
339 : goto err;
340 0 : if (!BN_MONT_CTX_set(mont, p, ctx))
341 : goto err;
342 :
343 : for (;;) {
344 : /* g=test^r0%p */
345 0 : if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
346 : goto err;
347 0 : if (!BN_is_one(g))
348 : break;
349 0 : if (!BN_add(test, test, BN_value_one()))
350 : goto err;
351 0 : h++;
352 0 : }
353 :
354 0 : if (!BN_GENCB_call(cb, 3, 1))
355 : goto err;
356 :
357 : ok = 1;
358 : err:
359 0 : if (ok) {
360 0 : if (ret->p)
361 0 : BN_free(ret->p);
362 0 : if (ret->q)
363 0 : BN_free(ret->q);
364 0 : if (ret->g)
365 0 : BN_free(ret->g);
366 0 : ret->p = BN_dup(p);
367 0 : ret->q = BN_dup(q);
368 0 : ret->g = BN_dup(g);
369 0 : if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
370 : ok = 0;
371 : goto err;
372 : }
373 0 : if (counter_ret != NULL)
374 0 : *counter_ret = counter;
375 0 : if (h_ret != NULL)
376 0 : *h_ret = h;
377 0 : if (seed_out)
378 : memcpy(seed_out, seed, qsize);
379 : }
380 0 : if (ctx) {
381 0 : BN_CTX_end(ctx);
382 0 : BN_CTX_free(ctx);
383 : }
384 0 : if (mont != NULL)
385 0 : BN_MONT_CTX_free(mont);
386 0 : return ok;
387 : }
388 :
389 : # ifdef OPENSSL_FIPS
390 : # undef fips_dsa_builtin_paramgen2
391 : extern int fips_dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
392 : const EVP_MD *evpmd,
393 : const unsigned char *seed_in,
394 : size_t seed_len, int idx,
395 : unsigned char *seed_out,
396 : int *counter_ret, unsigned long *h_ret,
397 : BN_GENCB *cb);
398 : # endif
399 :
400 : /*
401 : * This is a parameter generation algorithm for the DSA2 algorithm as
402 : * described in FIPS 186-3.
403 : */
404 :
405 0 : int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
406 : const EVP_MD *evpmd, const unsigned char *seed_in,
407 : size_t seed_len, int idx, unsigned char *seed_out,
408 : int *counter_ret, unsigned long *h_ret,
409 : BN_GENCB *cb)
410 : {
411 : int ok = -1;
412 : unsigned char *seed = NULL, *seed_tmp = NULL;
413 : unsigned char md[EVP_MAX_MD_SIZE];
414 : int mdsize;
415 : BIGNUM *r0, *W, *X, *c, *test;
416 : BIGNUM *g = NULL, *q = NULL, *p = NULL;
417 : BN_MONT_CTX *mont = NULL;
418 0 : int i, k, n = 0, m = 0, qsize = N >> 3;
419 : int counter = 0;
420 : int r = 0;
421 : BN_CTX *ctx = NULL;
422 : EVP_MD_CTX mctx;
423 : unsigned int h = 2;
424 :
425 : # ifdef OPENSSL_FIPS
426 :
427 : if (FIPS_mode())
428 : return fips_dsa_builtin_paramgen2(ret, L, N, evpmd,
429 : seed_in, seed_len, idx,
430 : seed_out, counter_ret, h_ret, cb);
431 : # endif
432 :
433 0 : EVP_MD_CTX_init(&mctx);
434 :
435 0 : if (evpmd == NULL) {
436 0 : if (N == 160)
437 0 : evpmd = EVP_sha1();
438 0 : else if (N == 224)
439 0 : evpmd = EVP_sha224();
440 : else
441 0 : evpmd = EVP_sha256();
442 : }
443 :
444 0 : mdsize = EVP_MD_size(evpmd);
445 : /* If unverificable g generation only don't need seed */
446 0 : if (!ret->p || !ret->q || idx >= 0) {
447 0 : if (seed_len == 0)
448 0 : seed_len = mdsize;
449 :
450 0 : seed = OPENSSL_malloc(seed_len);
451 :
452 0 : if (seed_out)
453 : seed_tmp = seed_out;
454 : else
455 0 : seed_tmp = OPENSSL_malloc(seed_len);
456 :
457 0 : if (!seed || !seed_tmp)
458 : goto err;
459 :
460 0 : if (seed_in)
461 : memcpy(seed, seed_in, seed_len);
462 :
463 : }
464 :
465 0 : if ((ctx = BN_CTX_new()) == NULL)
466 : goto err;
467 :
468 0 : if ((mont = BN_MONT_CTX_new()) == NULL)
469 : goto err;
470 :
471 0 : BN_CTX_start(ctx);
472 0 : r0 = BN_CTX_get(ctx);
473 0 : g = BN_CTX_get(ctx);
474 0 : W = BN_CTX_get(ctx);
475 0 : X = BN_CTX_get(ctx);
476 0 : c = BN_CTX_get(ctx);
477 0 : test = BN_CTX_get(ctx);
478 :
479 : /* if p, q already supplied generate g only */
480 0 : if (ret->p && ret->q) {
481 : p = ret->p;
482 : q = ret->q;
483 0 : if (idx >= 0)
484 : memcpy(seed_tmp, seed, seed_len);
485 : goto g_only;
486 : } else {
487 0 : p = BN_CTX_get(ctx);
488 0 : q = BN_CTX_get(ctx);
489 : }
490 :
491 0 : if (!BN_lshift(test, BN_value_one(), L - 1))
492 : goto err;
493 : for (;;) {
494 : for (;;) { /* find q */
495 : unsigned char *pmd;
496 : /* step 1 */
497 0 : if (!BN_GENCB_call(cb, 0, m++))
498 : goto err;
499 :
500 0 : if (!seed_in) {
501 0 : if (RAND_pseudo_bytes(seed, seed_len) < 0)
502 : goto err;
503 : }
504 : /* step 2 */
505 0 : if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
506 : goto err;
507 : /* Take least significant bits of md */
508 0 : if (mdsize > qsize)
509 0 : pmd = md + mdsize - qsize;
510 : else
511 : pmd = md;
512 :
513 0 : if (mdsize < qsize)
514 0 : memset(md + mdsize, 0, qsize - mdsize);
515 :
516 : /* step 3 */
517 0 : pmd[0] |= 0x80;
518 0 : pmd[qsize - 1] |= 0x01;
519 0 : if (!BN_bin2bn(pmd, qsize, q))
520 : goto err;
521 :
522 : /* step 4 */
523 0 : r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
524 : seed_in ? 1 : 0, cb);
525 0 : if (r > 0)
526 : break;
527 0 : if (r != 0)
528 : goto err;
529 : /* Provided seed didn't produce a prime: error */
530 0 : if (seed_in) {
531 : ok = 0;
532 0 : DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
533 0 : goto err;
534 : }
535 :
536 : /* do a callback call */
537 : /* step 5 */
538 : }
539 : /* Copy seed to seed_out before we mess with it */
540 0 : if (seed_out)
541 : memcpy(seed_out, seed, seed_len);
542 :
543 0 : if (!BN_GENCB_call(cb, 2, 0))
544 : goto err;
545 0 : if (!BN_GENCB_call(cb, 3, 0))
546 : goto err;
547 :
548 : /* step 6 */
549 : counter = 0;
550 : /* "offset = 1" */
551 :
552 0 : n = (L - 1) / (mdsize << 3);
553 :
554 : for (;;) {
555 0 : if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
556 : goto err;
557 :
558 : /* step 7 */
559 0 : BN_zero(W);
560 : /* now 'buf' contains "SEED + offset - 1" */
561 0 : for (k = 0; k <= n; k++) {
562 : /*
563 : * obtain "SEED + offset + k" by incrementing:
564 : */
565 0 : for (i = seed_len - 1; i >= 0; i--) {
566 0 : seed[i]++;
567 0 : if (seed[i] != 0)
568 : break;
569 : }
570 :
571 0 : if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
572 : goto err;
573 :
574 : /* step 8 */
575 0 : if (!BN_bin2bn(md, mdsize, r0))
576 : goto err;
577 0 : if (!BN_lshift(r0, r0, (mdsize << 3) * k))
578 : goto err;
579 0 : if (!BN_add(W, W, r0))
580 : goto err;
581 : }
582 :
583 : /* more of step 8 */
584 0 : if (!BN_mask_bits(W, L - 1))
585 : goto err;
586 0 : if (!BN_copy(X, W))
587 : goto err;
588 0 : if (!BN_add(X, X, test))
589 : goto err;
590 :
591 : /* step 9 */
592 0 : if (!BN_lshift1(r0, q))
593 : goto err;
594 0 : if (!BN_mod(c, X, r0, ctx))
595 : goto err;
596 0 : if (!BN_sub(r0, c, BN_value_one()))
597 : goto err;
598 0 : if (!BN_sub(p, X, r0))
599 : goto err;
600 :
601 : /* step 10 */
602 0 : if (BN_cmp(p, test) >= 0) {
603 : /* step 11 */
604 0 : r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
605 0 : if (r > 0)
606 : goto end; /* found it */
607 0 : if (r != 0)
608 : goto err;
609 : }
610 :
611 : /* step 13 */
612 0 : counter++;
613 : /* "offset = offset + n + 1" */
614 :
615 : /* step 14 */
616 0 : if (counter >= (int)(4 * L))
617 : break;
618 : }
619 0 : if (seed_in) {
620 : ok = 0;
621 0 : DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
622 0 : goto err;
623 : }
624 : }
625 : end:
626 0 : if (!BN_GENCB_call(cb, 2, 1))
627 : goto err;
628 :
629 : g_only:
630 :
631 : /* We now need to generate g */
632 : /* Set r0=(p-1)/q */
633 0 : if (!BN_sub(test, p, BN_value_one()))
634 : goto err;
635 0 : if (!BN_div(r0, NULL, test, q, ctx))
636 : goto err;
637 :
638 0 : if (idx < 0) {
639 0 : if (!BN_set_word(test, h))
640 : goto err;
641 : } else
642 : h = 1;
643 0 : if (!BN_MONT_CTX_set(mont, p, ctx))
644 : goto err;
645 :
646 : for (;;) {
647 : static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
648 0 : if (idx >= 0) {
649 0 : md[0] = idx & 0xff;
650 0 : md[1] = (h >> 8) & 0xff;
651 0 : md[2] = h & 0xff;
652 0 : if (!EVP_DigestInit_ex(&mctx, evpmd, NULL))
653 : goto err;
654 0 : if (!EVP_DigestUpdate(&mctx, seed_tmp, seed_len))
655 : goto err;
656 0 : if (!EVP_DigestUpdate(&mctx, ggen, sizeof(ggen)))
657 : goto err;
658 0 : if (!EVP_DigestUpdate(&mctx, md, 3))
659 : goto err;
660 0 : if (!EVP_DigestFinal_ex(&mctx, md, NULL))
661 : goto err;
662 0 : if (!BN_bin2bn(md, mdsize, test))
663 : goto err;
664 : }
665 : /* g=test^r0%p */
666 0 : if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
667 : goto err;
668 0 : if (!BN_is_one(g))
669 : break;
670 0 : if (idx < 0 && !BN_add(test, test, BN_value_one()))
671 : goto err;
672 0 : h++;
673 0 : if (idx >= 0 && h > 0xffff)
674 : goto err;
675 : }
676 :
677 0 : if (!BN_GENCB_call(cb, 3, 1))
678 : goto err;
679 :
680 : ok = 1;
681 : err:
682 0 : if (ok == 1) {
683 0 : if (p != ret->p) {
684 0 : if (ret->p)
685 0 : BN_free(ret->p);
686 0 : ret->p = BN_dup(p);
687 : }
688 0 : if (q != ret->q) {
689 0 : if (ret->q)
690 0 : BN_free(ret->q);
691 0 : ret->q = BN_dup(q);
692 : }
693 0 : if (ret->g)
694 0 : BN_free(ret->g);
695 0 : ret->g = BN_dup(g);
696 0 : if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
697 : ok = -1;
698 : goto err;
699 : }
700 0 : if (counter_ret != NULL)
701 0 : *counter_ret = counter;
702 0 : if (h_ret != NULL)
703 0 : *h_ret = h;
704 : }
705 0 : if (seed)
706 0 : OPENSSL_free(seed);
707 0 : if (seed_out != seed_tmp)
708 0 : OPENSSL_free(seed_tmp);
709 0 : if (ctx) {
710 0 : BN_CTX_end(ctx);
711 0 : BN_CTX_free(ctx);
712 : }
713 0 : if (mont != NULL)
714 0 : BN_MONT_CTX_free(mont);
715 0 : EVP_MD_CTX_cleanup(&mctx);
716 0 : return ok;
717 : }
718 :
719 0 : int dsa_paramgen_check_g(DSA *dsa)
720 : {
721 : BN_CTX *ctx;
722 : BIGNUM *tmp;
723 : BN_MONT_CTX *mont = NULL;
724 : int rv = -1;
725 0 : ctx = BN_CTX_new();
726 0 : if (!ctx)
727 : return -1;
728 0 : BN_CTX_start(ctx);
729 0 : if (BN_cmp(dsa->g, BN_value_one()) <= 0)
730 : return 0;
731 0 : if (BN_cmp(dsa->g, dsa->p) >= 0)
732 : return 0;
733 0 : tmp = BN_CTX_get(ctx);
734 0 : if (!tmp)
735 : goto err;
736 0 : if ((mont = BN_MONT_CTX_new()) == NULL)
737 : goto err;
738 0 : if (!BN_MONT_CTX_set(mont, dsa->p, ctx))
739 : goto err;
740 : /* Work out g^q mod p */
741 0 : if (!BN_mod_exp_mont(tmp, dsa->g, dsa->q, dsa->p, ctx, mont))
742 : goto err;
743 0 : if (!BN_cmp(tmp, BN_value_one()))
744 : rv = 1;
745 : else
746 : rv = 0;
747 : err:
748 0 : BN_CTX_end(ctx);
749 0 : if (mont)
750 0 : BN_MONT_CTX_free(mont);
751 0 : BN_CTX_free(ctx);
752 0 : return rv;
753 :
754 : }
755 : #endif
|
