Gitiles
Code Review Sign In
192.168.1.100 / R306 / 2dbc1526a2b84342aa5d5d2a0b7c25c960d13710 / . / ap / lib / libssl / openssl-1.1.1o / crypto / dsa / dsa_gen.c
blob: 5d066a06c546d9d6cf0e56cabd201cc12e24f1e2 [file] [log] [blame]
yuezonghe824eb0c2024-06-27 02:32:26 -0700[diff] [blame]1/*
2 * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10/*
11 * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
12 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
13 * 180-1)
14 */
15#define xxxHASH EVP_sha1()
16
17#include <openssl/opensslconf.h>
18#include <stdio.h>
19#include "internal/cryptlib.h"
20#include <openssl/evp.h>
21#include <openssl/bn.h>
22#include <openssl/rand.h>
23#include <openssl/sha.h>
24#include "dsa_local.h"
25
26int DSA_generate_parameters_ex(DSA *ret, int bits,
27 const unsigned char *seed_in, int seed_len,
28 int *counter_ret, unsigned long *h_ret,
29 BN_GENCB *cb)
30{
31 if (ret->meth->dsa_paramgen)
32 return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
33 counter_ret, h_ret, cb);
34 else {
35 const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1();
36 size_t qbits = EVP_MD_size(evpmd) * 8;
37
38 return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
39 seed_in, seed_len, NULL, counter_ret,
40 h_ret, cb);
41 }
42}
43
44int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
45 const EVP_MD *evpmd, const unsigned char *seed_in,
46 size_t seed_len, unsigned char *seed_out,
47 int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
48{
49 int ok = 0;
50 unsigned char seed[SHA256_DIGEST_LENGTH];
51 unsigned char md[SHA256_DIGEST_LENGTH];
52 unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
53 BIGNUM *r0, *W, *X, *c, *test;
54 BIGNUM *g = NULL, *q = NULL, *p = NULL;
55 BN_MONT_CTX *mont = NULL;
56 int i, k, n = 0, m = 0, qsize = qbits >> 3;
57 int counter = 0;
58 int r = 0;
59 BN_CTX *ctx = NULL;
60 unsigned int h = 2;
61
62 if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
63 qsize != SHA256_DIGEST_LENGTH)
64 /* invalid q size */
65 return 0;
66
67 if (evpmd == NULL) {
68 if (qsize == SHA_DIGEST_LENGTH)
69 evpmd = EVP_sha1();
70 else if (qsize == SHA224_DIGEST_LENGTH)
71 evpmd = EVP_sha224();
72 else
73 evpmd = EVP_sha256();
74 } else {
75 qsize = EVP_MD_size(evpmd);
76 }
77
78 if (bits < 512)
79 bits = 512;
80
81 bits = (bits + 63) / 64 * 64;
82
83 if (seed_in != NULL) {
84 if (seed_len < (size_t)qsize) {
85 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL);
86 return 0;
87 }
88 if (seed_len > (size_t)qsize) {
89 /* Only consume as much seed as is expected. */
90 seed_len = qsize;
91 }
92 memcpy(seed, seed_in, seed_len);
93 }
94
95 if ((mont = BN_MONT_CTX_new()) == NULL)
96 goto err;
97
98 if ((ctx = BN_CTX_new()) == NULL)
99 goto err;
100
101 BN_CTX_start(ctx);
102
103 r0 = BN_CTX_get(ctx);
104 g = BN_CTX_get(ctx);
105 W = BN_CTX_get(ctx);
106 q = BN_CTX_get(ctx);
107 X = BN_CTX_get(ctx);
108 c = BN_CTX_get(ctx);
109 p = BN_CTX_get(ctx);
110 test = BN_CTX_get(ctx);
111
112 if (test == NULL)
113 goto err;
114
115 if (!BN_lshift(test, BN_value_one(), bits - 1))
116 goto err;
117
118 for (;;) {
119 for (;;) { /* find q */
120 int use_random_seed = (seed_in == NULL);
121
122 /* step 1 */
123 if (!BN_GENCB_call(cb, 0, m++))
124 goto err;
125
126 if (use_random_seed) {
127 if (RAND_bytes(seed, qsize) <= 0)
128 goto err;
129 } else {
130 /* If we come back through, use random seed next time. */
131 seed_in = NULL;
132 }
133 memcpy(buf, seed, qsize);
134 memcpy(buf2, seed, qsize);
135 /* precompute "SEED + 1" for step 7: */
136 for (i = qsize - 1; i >= 0; i--) {
137 buf[i]++;
138 if (buf[i] != 0)
139 break;
140 }
141
142 /* step 2 */
143 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
144 goto err;
145 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
146 goto err;
147 for (i = 0; i < qsize; i++)
148 md[i] ^= buf2[i];
149
150 /* step 3 */
151 md[0] |= 0x80;
152 md[qsize - 1] |= 0x01;
153 if (!BN_bin2bn(md, qsize, q))
154 goto err;
155
156 /* step 4 */
157 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
158 use_random_seed, cb);
159 if (r > 0)
160 break;
161 if (r != 0)
162 goto err;
163
164 /* do a callback call */
165 /* step 5 */
166 }
167
168 if (!BN_GENCB_call(cb, 2, 0))
169 goto err;
170 if (!BN_GENCB_call(cb, 3, 0))
171 goto err;
172
173 /* step 6 */
174 counter = 0;
175 /* "offset = 2" */
176
177 n = (bits - 1) / 160;
178
179 for (;;) {
180 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
181 goto err;
182
183 /* step 7 */
184 BN_zero(W);
185 /* now 'buf' contains "SEED + offset - 1" */
186 for (k = 0; k <= n; k++) {
187 /*
188 * obtain "SEED + offset + k" by incrementing:
189 */
190 for (i = qsize - 1; i >= 0; i--) {
191 buf[i]++;
192 if (buf[i] != 0)
193 break;
194 }
195
196 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
197 goto err;
198
199 /* step 8 */
200 if (!BN_bin2bn(md, qsize, r0))
201 goto err;
202 if (!BN_lshift(r0, r0, (qsize << 3) * k))
203 goto err;
204 if (!BN_add(W, W, r0))
205 goto err;
206 }
207
208 /* more of step 8 */
209 if (!BN_mask_bits(W, bits - 1))
210 goto err;
211 if (!BN_copy(X, W))
212 goto err;
213 if (!BN_add(X, X, test))
214 goto err;
215
216 /* step 9 */
217 if (!BN_lshift1(r0, q))
218 goto err;
219 if (!BN_mod(c, X, r0, ctx))
220 goto err;
221 if (!BN_sub(r0, c, BN_value_one()))
222 goto err;
223 if (!BN_sub(p, X, r0))
224 goto err;
225
226 /* step 10 */
227 if (BN_cmp(p, test) >= 0) {
228 /* step 11 */
229 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
230 if (r > 0)
231 goto end; /* found it */
232 if (r != 0)
233 goto err;
234 }
235
236 /* step 13 */
237 counter++;
238 /* "offset = offset + n + 1" */
239
240 /* step 14 */
241 if (counter >= 4096)
242 break;
243 }
244 }
245 end:
246 if (!BN_GENCB_call(cb, 2, 1))
247 goto err;
248
249 /* We now need to generate g */
250 /* Set r0=(p-1)/q */
251 if (!BN_sub(test, p, BN_value_one()))
252 goto err;
253 if (!BN_div(r0, NULL, test, q, ctx))
254 goto err;
255
256 if (!BN_set_word(test, h))
257 goto err;
258 if (!BN_MONT_CTX_set(mont, p, ctx))
259 goto err;
260
261 for (;;) {
262 /* g=test^r0%p */
263 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
264 goto err;
265 if (!BN_is_one(g))
266 break;
267 if (!BN_add(test, test, BN_value_one()))
268 goto err;
269 h++;
270 }
271
272 if (!BN_GENCB_call(cb, 3, 1))
273 goto err;
274
275 ok = 1;
276 err:
277 if (ok) {
278 BN_free(ret->p);
279 BN_free(ret->q);
280 BN_free(ret->g);
281 ret->p = BN_dup(p);
282 ret->q = BN_dup(q);
283 ret->g = BN_dup(g);
284 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
285 ok = 0;
286 goto err;
287 }
288 if (counter_ret != NULL)
289 *counter_ret = counter;
290 if (h_ret != NULL)
291 *h_ret = h;
292 if (seed_out)
293 memcpy(seed_out, seed, qsize);
294 }
295 BN_CTX_end(ctx);
296 BN_CTX_free(ctx);
297 BN_MONT_CTX_free(mont);
298 return ok;
299}
300
301/*
302 * This is a parameter generation algorithm for the DSA2 algorithm as
303 * described in FIPS 186-3.
304 */
305
306int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
307 const EVP_MD *evpmd, const unsigned char *seed_in,
308 size_t seed_len, int idx, unsigned char *seed_out,
309 int *counter_ret, unsigned long *h_ret,
310 BN_GENCB *cb)
311{
312 int ok = -1;
313 unsigned char *seed = NULL, *seed_tmp = NULL;
314 unsigned char md[EVP_MAX_MD_SIZE];
315 int mdsize;
316 BIGNUM *r0, *W, *X, *c, *test;
317 BIGNUM *g = NULL, *q = NULL, *p = NULL;
318 BN_MONT_CTX *mont = NULL;
319 int i, k, n = 0, m = 0, qsize = N >> 3;
320 int counter = 0;
321 int r = 0;
322 BN_CTX *ctx = NULL;
323 EVP_MD_CTX *mctx = EVP_MD_CTX_new();
324 unsigned int h = 2;
325
326 if (mctx == NULL)
327 goto err;
328
329 /* make sure L > N, otherwise we'll get trapped in an infinite loop */
330 if (L <= N) {
331 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
332 goto err;
333 }
334
335 if (evpmd == NULL) {
336 if (N == 160)
337 evpmd = EVP_sha1();
338 else if (N == 224)
339 evpmd = EVP_sha224();
340 else
341 evpmd = EVP_sha256();
342 }
343
344 mdsize = EVP_MD_size(evpmd);
345 /* If unverifiable g generation only don't need seed */
346 if (!ret->p || !ret->q || idx >= 0) {
347 if (seed_len == 0)
348 seed_len = mdsize;
349
350 seed = OPENSSL_malloc(seed_len);
351
352 if (seed_out)
353 seed_tmp = seed_out;
354 else
355 seed_tmp = OPENSSL_malloc(seed_len);
356
357 if (seed == NULL || seed_tmp == NULL)
358 goto err;
359
360 if (seed_in)
361 memcpy(seed, seed_in, seed_len);
362
363 }
364
365 if ((ctx = BN_CTX_new()) == NULL)
366 goto err;
367
368 if ((mont = BN_MONT_CTX_new()) == NULL)
369 goto err;
370
371 BN_CTX_start(ctx);
372 r0 = BN_CTX_get(ctx);
373 g = BN_CTX_get(ctx);
374 W = BN_CTX_get(ctx);
375 X = BN_CTX_get(ctx);
376 c = BN_CTX_get(ctx);
377 test = BN_CTX_get(ctx);
378 if (test == NULL)
379 goto err;
380
381 /* if p, q already supplied generate g only */
382 if (ret->p && ret->q) {
383 p = ret->p;
384 q = ret->q;
385 if (idx >= 0)
386 memcpy(seed_tmp, seed, seed_len);
387 goto g_only;
388 } else {
389 p = BN_CTX_get(ctx);
390 q = BN_CTX_get(ctx);
391 if (q == NULL)
392 goto err;
393 }
394
395 if (!BN_lshift(test, BN_value_one(), L - 1))
396 goto err;
397 for (;;) {
398 for (;;) { /* find q */
399 unsigned char *pmd;
400 /* step 1 */
401 if (!BN_GENCB_call(cb, 0, m++))
402 goto err;
403
404 if (!seed_in) {
405 if (RAND_bytes(seed, seed_len) <= 0)
406 goto err;
407 }
408 /* step 2 */
409 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
410 goto err;
411 /* Take least significant bits of md */
412 if (mdsize > qsize)
413 pmd = md + mdsize - qsize;
414 else
415 pmd = md;
416
417 if (mdsize < qsize)
418 memset(md + mdsize, 0, qsize - mdsize);
419
420 /* step 3 */
421 pmd[0] |= 0x80;
422 pmd[qsize - 1] |= 0x01;
423 if (!BN_bin2bn(pmd, qsize, q))
424 goto err;
425
426 /* step 4 */
427 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
428 seed_in ? 1 : 0, cb);
429 if (r > 0)
430 break;
431 if (r != 0)
432 goto err;
433 /* Provided seed didn't produce a prime: error */
434 if (seed_in) {
435 ok = 0;
436 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
437 goto err;
438 }
439
440 /* do a callback call */
441 /* step 5 */
442 }
443 /* Copy seed to seed_out before we mess with it */
444 if (seed_out)
445 memcpy(seed_out, seed, seed_len);
446
447 if (!BN_GENCB_call(cb, 2, 0))
448 goto err;
449 if (!BN_GENCB_call(cb, 3, 0))
450 goto err;
451
452 /* step 6 */
453 counter = 0;
454 /* "offset = 1" */
455
456 n = (L - 1) / (mdsize << 3);
457
458 for (;;) {
459 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
460 goto err;
461
462 /* step 7 */
463 BN_zero(W);
464 /* now 'buf' contains "SEED + offset - 1" */
465 for (k = 0; k <= n; k++) {
466 /*
467 * obtain "SEED + offset + k" by incrementing:
468 */
469 for (i = seed_len - 1; i >= 0; i--) {
470 seed[i]++;
471 if (seed[i] != 0)
472 break;
473 }
474
475 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
476 goto err;
477
478 /* step 8 */
479 if (!BN_bin2bn(md, mdsize, r0))
480 goto err;
481 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
482 goto err;
483 if (!BN_add(W, W, r0))
484 goto err;
485 }
486
487 /* more of step 8 */
488 if (!BN_mask_bits(W, L - 1))
489 goto err;
490 if (!BN_copy(X, W))
491 goto err;
492 if (!BN_add(X, X, test))
493 goto err;
494
495 /* step 9 */
496 if (!BN_lshift1(r0, q))
497 goto err;
498 if (!BN_mod(c, X, r0, ctx))
499 goto err;
500 if (!BN_sub(r0, c, BN_value_one()))
501 goto err;
502 if (!BN_sub(p, X, r0))
503 goto err;
504
505 /* step 10 */
506 if (BN_cmp(p, test) >= 0) {
507 /* step 11 */
508 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
509 if (r > 0)
510 goto end; /* found it */
511 if (r != 0)
512 goto err;
513 }
514
515 /* step 13 */
516 counter++;
517 /* "offset = offset + n + 1" */
518
519 /* step 14 */
520 if (counter >= (int)(4 * L))
521 break;
522 }
523 if (seed_in) {
524 ok = 0;
525 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
526 goto err;
527 }
528 }
529 end:
530 if (!BN_GENCB_call(cb, 2, 1))
531 goto err;
532
533 g_only:
534
535 /* We now need to generate g */
536 /* Set r0=(p-1)/q */
537 if (!BN_sub(test, p, BN_value_one()))
538 goto err;
539 if (!BN_div(r0, NULL, test, q, ctx))
540 goto err;
541
542 if (idx < 0) {
543 if (!BN_set_word(test, h))
544 goto err;
545 } else
546 h = 1;
547 if (!BN_MONT_CTX_set(mont, p, ctx))
548 goto err;
549
550 for (;;) {
551 static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
552 if (idx >= 0) {
553 md[0] = idx & 0xff;
554 md[1] = (h >> 8) & 0xff;
555 md[2] = h & 0xff;
556 if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
557 goto err;
558 if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
559 goto err;
560 if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
561 goto err;
562 if (!EVP_DigestUpdate(mctx, md, 3))
563 goto err;
564 if (!EVP_DigestFinal_ex(mctx, md, NULL))
565 goto err;
566 if (!BN_bin2bn(md, mdsize, test))
567 goto err;
568 }
569 /* g=test^r0%p */
570 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
571 goto err;
572 if (!BN_is_one(g))
573 break;
574 if (idx < 0 && !BN_add(test, test, BN_value_one()))
575 goto err;
576 h++;
577 if (idx >= 0 && h > 0xffff)
578 goto err;
579 }
580
581 if (!BN_GENCB_call(cb, 3, 1))
582 goto err;
583
584 ok = 1;
585 err:
586 if (ok == 1) {
587 if (p != ret->p) {
588 BN_free(ret->p);
589 ret->p = BN_dup(p);
590 }
591 if (q != ret->q) {
592 BN_free(ret->q);
593 ret->q = BN_dup(q);
594 }
595 BN_free(ret->g);
596 ret->g = BN_dup(g);
597 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
598 ok = -1;
599 goto err;
600 }
601 if (counter_ret != NULL)
602 *counter_ret = counter;
603 if (h_ret != NULL)
604 *h_ret = h;
605 }
606 OPENSSL_free(seed);
607 if (seed_out != seed_tmp)
608 OPENSSL_free(seed_tmp);
609 BN_CTX_end(ctx);
610 BN_CTX_free(ctx);
611 BN_MONT_CTX_free(mont);
612 EVP_MD_CTX_free(mctx);
613 return ok;
614}