source: EcnlProtoTool/trunk/openssl-1.1.0e/crypto/dsa/dsa_gen.c@ 331

Last change on this file since 331 was 331, checked in by coas-nagasima, 6 years ago

prototoolに関連するプロジェクトをnewlibからmuslを使うよう変更・更新
ntshellをnewlibの下位の実装から、muslのsyscallの実装に変更・更新
以下のOSSをアップデート
・mruby-1.3.0
・musl-1.1.18
・onigmo-6.1.3
・tcc-0.9.27
以下のOSSを追加
・openssl-1.1.0e
・curl-7.57.0
・zlib-1.2.11
以下のmrbgemsを追加
・iij/mruby-digest
・iij/mruby-env
・iij/mruby-errno
・iij/mruby-iijson
・iij/mruby-ipaddr
・iij/mruby-mock
・iij/mruby-require
・iij/mruby-tls-openssl
  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-csrc
File size: 16.2 KB
Line 
1/*
2 * Copyright 1995-2016 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_locl.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 /* use SHA1 as default */
69 evpmd = EVP_sha1();
70
71 if (bits < 512)
72 bits = 512;
73
74 bits = (bits + 63) / 64 * 64;
75
76 if (seed_in != NULL) {
77 if (seed_len < (size_t)qsize) {
78 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL);
79 return 0;
80 }
81 if (seed_len > (size_t)qsize) {
82 /* Only consume as much seed as is expected. */
83 seed_len = qsize;
84 }
85 memcpy(seed, seed_in, seed_len);
86 }
87
88 if ((mont = BN_MONT_CTX_new()) == NULL)
89 goto err;
90
91 if ((ctx = BN_CTX_new()) == NULL)
92 goto err;
93
94 BN_CTX_start(ctx);
95
96 r0 = BN_CTX_get(ctx);
97 g = BN_CTX_get(ctx);
98 W = BN_CTX_get(ctx);
99 q = BN_CTX_get(ctx);
100 X = BN_CTX_get(ctx);
101 c = BN_CTX_get(ctx);
102 p = BN_CTX_get(ctx);
103 test = BN_CTX_get(ctx);
104
105 if (test == NULL)
106 goto err;
107
108 if (!BN_lshift(test, BN_value_one(), bits - 1))
109 goto err;
110
111 for (;;) {
112 for (;;) { /* find q */
113 int use_random_seed = (seed_in == NULL);
114
115 /* step 1 */
116 if (!BN_GENCB_call(cb, 0, m++))
117 goto err;
118
119 if (use_random_seed) {
120 if (RAND_bytes(seed, qsize) <= 0)
121 goto err;
122 } else {
123 /* If we come back through, use random seed next time. */
124 seed_in = NULL;
125 }
126 memcpy(buf, seed, qsize);
127 memcpy(buf2, seed, qsize);
128 /* precompute "SEED + 1" for step 7: */
129 for (i = qsize - 1; i >= 0; i--) {
130 buf[i]++;
131 if (buf[i] != 0)
132 break;
133 }
134
135 /* step 2 */
136 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
137 goto err;
138 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
139 goto err;
140 for (i = 0; i < qsize; i++)
141 md[i] ^= buf2[i];
142
143 /* step 3 */
144 md[0] |= 0x80;
145 md[qsize - 1] |= 0x01;
146 if (!BN_bin2bn(md, qsize, q))
147 goto err;
148
149 /* step 4 */
150 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
151 use_random_seed, cb);
152 if (r > 0)
153 break;
154 if (r != 0)
155 goto err;
156
157 /* do a callback call */
158 /* step 5 */
159 }
160
161 if (!BN_GENCB_call(cb, 2, 0))
162 goto err;
163 if (!BN_GENCB_call(cb, 3, 0))
164 goto err;
165
166 /* step 6 */
167 counter = 0;
168 /* "offset = 2" */
169
170 n = (bits - 1) / 160;
171
172 for (;;) {
173 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
174 goto err;
175
176 /* step 7 */
177 BN_zero(W);
178 /* now 'buf' contains "SEED + offset - 1" */
179 for (k = 0; k <= n; k++) {
180 /*
181 * obtain "SEED + offset + k" by incrementing:
182 */
183 for (i = qsize - 1; i >= 0; i--) {
184 buf[i]++;
185 if (buf[i] != 0)
186 break;
187 }
188
189 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
190 goto err;
191
192 /* step 8 */
193 if (!BN_bin2bn(md, qsize, r0))
194 goto err;
195 if (!BN_lshift(r0, r0, (qsize << 3) * k))
196 goto err;
197 if (!BN_add(W, W, r0))
198 goto err;
199 }
200
201 /* more of step 8 */
202 if (!BN_mask_bits(W, bits - 1))
203 goto err;
204 if (!BN_copy(X, W))
205 goto err;
206 if (!BN_add(X, X, test))
207 goto err;
208
209 /* step 9 */
210 if (!BN_lshift1(r0, q))
211 goto err;
212 if (!BN_mod(c, X, r0, ctx))
213 goto err;
214 if (!BN_sub(r0, c, BN_value_one()))
215 goto err;
216 if (!BN_sub(p, X, r0))
217 goto err;
218
219 /* step 10 */
220 if (BN_cmp(p, test) >= 0) {
221 /* step 11 */
222 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
223 if (r > 0)
224 goto end; /* found it */
225 if (r != 0)
226 goto err;
227 }
228
229 /* step 13 */
230 counter++;
231 /* "offset = offset + n + 1" */
232
233 /* step 14 */
234 if (counter >= 4096)
235 break;
236 }
237 }
238 end:
239 if (!BN_GENCB_call(cb, 2, 1))
240 goto err;
241
242 /* We now need to generate g */
243 /* Set r0=(p-1)/q */
244 if (!BN_sub(test, p, BN_value_one()))
245 goto err;
246 if (!BN_div(r0, NULL, test, q, ctx))
247 goto err;
248
249 if (!BN_set_word(test, h))
250 goto err;
251 if (!BN_MONT_CTX_set(mont, p, ctx))
252 goto err;
253
254 for (;;) {
255 /* g=test^r0%p */
256 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
257 goto err;
258 if (!BN_is_one(g))
259 break;
260 if (!BN_add(test, test, BN_value_one()))
261 goto err;
262 h++;
263 }
264
265 if (!BN_GENCB_call(cb, 3, 1))
266 goto err;
267
268 ok = 1;
269 err:
270 if (ok) {
271 BN_free(ret->p);
272 BN_free(ret->q);
273 BN_free(ret->g);
274 ret->p = BN_dup(p);
275 ret->q = BN_dup(q);
276 ret->g = BN_dup(g);
277 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
278 ok = 0;
279 goto err;
280 }
281 if (counter_ret != NULL)
282 *counter_ret = counter;
283 if (h_ret != NULL)
284 *h_ret = h;
285 if (seed_out)
286 memcpy(seed_out, seed, qsize);
287 }
288 if (ctx)
289 BN_CTX_end(ctx);
290 BN_CTX_free(ctx);
291 BN_MONT_CTX_free(mont);
292 return ok;
293}
294
295/*
296 * This is a parameter generation algorithm for the DSA2 algorithm as
297 * described in FIPS 186-3.
298 */
299
300int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
301 const EVP_MD *evpmd, const unsigned char *seed_in,
302 size_t seed_len, int idx, unsigned char *seed_out,
303 int *counter_ret, unsigned long *h_ret,
304 BN_GENCB *cb)
305{
306 int ok = -1;
307 unsigned char *seed = NULL, *seed_tmp = NULL;
308 unsigned char md[EVP_MAX_MD_SIZE];
309 int mdsize;
310 BIGNUM *r0, *W, *X, *c, *test;
311 BIGNUM *g = NULL, *q = NULL, *p = NULL;
312 BN_MONT_CTX *mont = NULL;
313 int i, k, n = 0, m = 0, qsize = N >> 3;
314 int counter = 0;
315 int r = 0;
316 BN_CTX *ctx = NULL;
317 EVP_MD_CTX *mctx = EVP_MD_CTX_new();
318 unsigned int h = 2;
319
320 if (mctx == NULL)
321 goto err;
322
323 if (evpmd == NULL) {
324 if (N == 160)
325 evpmd = EVP_sha1();
326 else if (N == 224)
327 evpmd = EVP_sha224();
328 else
329 evpmd = EVP_sha256();
330 }
331
332 mdsize = EVP_MD_size(evpmd);
333 /* If unverifiable g generation only don't need seed */
334 if (!ret->p || !ret->q || idx >= 0) {
335 if (seed_len == 0)
336 seed_len = mdsize;
337
338 seed = OPENSSL_malloc(seed_len);
339
340 if (seed_out)
341 seed_tmp = seed_out;
342 else
343 seed_tmp = OPENSSL_malloc(seed_len);
344
345 if (seed == NULL || seed_tmp == NULL)
346 goto err;
347
348 if (seed_in)
349 memcpy(seed, seed_in, seed_len);
350
351 }
352
353 if ((ctx = BN_CTX_new()) == NULL)
354 goto err;
355
356 if ((mont = BN_MONT_CTX_new()) == NULL)
357 goto err;
358
359 BN_CTX_start(ctx);
360 r0 = BN_CTX_get(ctx);
361 g = BN_CTX_get(ctx);
362 W = BN_CTX_get(ctx);
363 X = BN_CTX_get(ctx);
364 c = BN_CTX_get(ctx);
365 test = BN_CTX_get(ctx);
366 if (test == NULL)
367 goto err;
368
369 /* if p, q already supplied generate g only */
370 if (ret->p && ret->q) {
371 p = ret->p;
372 q = ret->q;
373 if (idx >= 0)
374 memcpy(seed_tmp, seed, seed_len);
375 goto g_only;
376 } else {
377 p = BN_CTX_get(ctx);
378 q = BN_CTX_get(ctx);
379 }
380
381 if (!BN_lshift(test, BN_value_one(), L - 1))
382 goto err;
383 for (;;) {
384 for (;;) { /* find q */
385 unsigned char *pmd;
386 /* step 1 */
387 if (!BN_GENCB_call(cb, 0, m++))
388 goto err;
389
390 if (!seed_in) {
391 if (RAND_bytes(seed, seed_len) <= 0)
392 goto err;
393 }
394 /* step 2 */
395 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
396 goto err;
397 /* Take least significant bits of md */
398 if (mdsize > qsize)
399 pmd = md + mdsize - qsize;
400 else
401 pmd = md;
402
403 if (mdsize < qsize)
404 memset(md + mdsize, 0, qsize - mdsize);
405
406 /* step 3 */
407 pmd[0] |= 0x80;
408 pmd[qsize - 1] |= 0x01;
409 if (!BN_bin2bn(pmd, qsize, q))
410 goto err;
411
412 /* step 4 */
413 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
414 seed_in ? 1 : 0, cb);
415 if (r > 0)
416 break;
417 if (r != 0)
418 goto err;
419 /* Provided seed didn't produce a prime: error */
420 if (seed_in) {
421 ok = 0;
422 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
423 goto err;
424 }
425
426 /* do a callback call */
427 /* step 5 */
428 }
429 /* Copy seed to seed_out before we mess with it */
430 if (seed_out)
431 memcpy(seed_out, seed, seed_len);
432
433 if (!BN_GENCB_call(cb, 2, 0))
434 goto err;
435 if (!BN_GENCB_call(cb, 3, 0))
436 goto err;
437
438 /* step 6 */
439 counter = 0;
440 /* "offset = 1" */
441
442 n = (L - 1) / (mdsize << 3);
443
444 for (;;) {
445 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
446 goto err;
447
448 /* step 7 */
449 BN_zero(W);
450 /* now 'buf' contains "SEED + offset - 1" */
451 for (k = 0; k <= n; k++) {
452 /*
453 * obtain "SEED + offset + k" by incrementing:
454 */
455 for (i = seed_len - 1; i >= 0; i--) {
456 seed[i]++;
457 if (seed[i] != 0)
458 break;
459 }
460
461 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
462 goto err;
463
464 /* step 8 */
465 if (!BN_bin2bn(md, mdsize, r0))
466 goto err;
467 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
468 goto err;
469 if (!BN_add(W, W, r0))
470 goto err;
471 }
472
473 /* more of step 8 */
474 if (!BN_mask_bits(W, L - 1))
475 goto err;
476 if (!BN_copy(X, W))
477 goto err;
478 if (!BN_add(X, X, test))
479 goto err;
480
481 /* step 9 */
482 if (!BN_lshift1(r0, q))
483 goto err;
484 if (!BN_mod(c, X, r0, ctx))
485 goto err;
486 if (!BN_sub(r0, c, BN_value_one()))
487 goto err;
488 if (!BN_sub(p, X, r0))
489 goto err;
490
491 /* step 10 */
492 if (BN_cmp(p, test) >= 0) {
493 /* step 11 */
494 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
495 if (r > 0)
496 goto end; /* found it */
497 if (r != 0)
498 goto err;
499 }
500
501 /* step 13 */
502 counter++;
503 /* "offset = offset + n + 1" */
504
505 /* step 14 */
506 if (counter >= (int)(4 * L))
507 break;
508 }
509 if (seed_in) {
510 ok = 0;
511 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
512 goto err;
513 }
514 }
515 end:
516 if (!BN_GENCB_call(cb, 2, 1))
517 goto err;
518
519 g_only:
520
521 /* We now need to generate g */
522 /* Set r0=(p-1)/q */
523 if (!BN_sub(test, p, BN_value_one()))
524 goto err;
525 if (!BN_div(r0, NULL, test, q, ctx))
526 goto err;
527
528 if (idx < 0) {
529 if (!BN_set_word(test, h))
530 goto err;
531 } else
532 h = 1;
533 if (!BN_MONT_CTX_set(mont, p, ctx))
534 goto err;
535
536 for (;;) {
537 static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
538 if (idx >= 0) {
539 md[0] = idx & 0xff;
540 md[1] = (h >> 8) & 0xff;
541 md[2] = h & 0xff;
542 if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
543 goto err;
544 if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
545 goto err;
546 if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
547 goto err;
548 if (!EVP_DigestUpdate(mctx, md, 3))
549 goto err;
550 if (!EVP_DigestFinal_ex(mctx, md, NULL))
551 goto err;
552 if (!BN_bin2bn(md, mdsize, test))
553 goto err;
554 }
555 /* g=test^r0%p */
556 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
557 goto err;
558 if (!BN_is_one(g))
559 break;
560 if (idx < 0 && !BN_add(test, test, BN_value_one()))
561 goto err;
562 h++;
563 if (idx >= 0 && h > 0xffff)
564 goto err;
565 }
566
567 if (!BN_GENCB_call(cb, 3, 1))
568 goto err;
569
570 ok = 1;
571 err:
572 if (ok == 1) {
573 if (p != ret->p) {
574 BN_free(ret->p);
575 ret->p = BN_dup(p);
576 }
577 if (q != ret->q) {
578 BN_free(ret->q);
579 ret->q = BN_dup(q);
580 }
581 BN_free(ret->g);
582 ret->g = BN_dup(g);
583 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
584 ok = -1;
585 goto err;
586 }
587 if (counter_ret != NULL)
588 *counter_ret = counter;
589 if (h_ret != NULL)
590 *h_ret = h;
591 }
592 OPENSSL_free(seed);
593 if (seed_out != seed_tmp)
594 OPENSSL_free(seed_tmp);
595 if (ctx)
596 BN_CTX_end(ctx);
597 BN_CTX_free(ctx);
598 BN_MONT_CTX_free(mont);
599 EVP_MD_CTX_free(mctx);
600 return ok;
601}
Note: See TracBrowser for help on using the repository browser.