383d853b6d37307be26a3dd5d15277cff79d0db4
[openssl.git] / crypto / dsa / dsa_gen.c
1 /*
2  * Copyright 1995-2018 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
26 int 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
44 int 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     if (ctx)
296         BN_CTX_end(ctx);
297     BN_CTX_free(ctx);
298     BN_MONT_CTX_free(mont);
299     return ok;
300 }
301
302 /*
303  * This is a parameter generation algorithm for the DSA2 algorithm as
304  * described in FIPS 186-3.
305  */
306
307 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
308                           const EVP_MD *evpmd, const unsigned char *seed_in,
309                           size_t seed_len, int idx, unsigned char *seed_out,
310                           int *counter_ret, unsigned long *h_ret,
311                           BN_GENCB *cb)
312 {
313     int ok = -1;
314     unsigned char *seed = NULL, *seed_tmp = NULL;
315     unsigned char md[EVP_MAX_MD_SIZE];
316     int mdsize;
317     BIGNUM *r0, *W, *X, *c, *test;
318     BIGNUM *g = NULL, *q = NULL, *p = NULL;
319     BN_MONT_CTX *mont = NULL;
320     int i, k, n = 0, m = 0, qsize = N >> 3;
321     int counter = 0;
322     int r = 0;
323     BN_CTX *ctx = NULL;
324     EVP_MD_CTX *mctx = EVP_MD_CTX_new();
325     unsigned int h = 2;
326
327     if (mctx == NULL)
328         goto err;
329
330     /* make sure L > N, otherwise we'll get trapped in an infinite loop */
331     if (L <= N) {
332         DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
333         goto err;
334     }
335
336     if (evpmd == NULL) {
337         if (N == 160)
338             evpmd = EVP_sha1();
339         else if (N == 224)
340             evpmd = EVP_sha224();
341         else
342             evpmd = EVP_sha256();
343     }
344
345     mdsize = EVP_MD_size(evpmd);
346     /* If unverifiable g generation only don't need seed */
347     if (!ret->p || !ret->q || idx >= 0) {
348         if (seed_len == 0)
349             seed_len = mdsize;
350
351         seed = OPENSSL_malloc(seed_len);
352
353         if (seed_out)
354             seed_tmp = seed_out;
355         else
356             seed_tmp = OPENSSL_malloc(seed_len);
357
358         if (seed == NULL || seed_tmp == NULL)
359             goto err;
360
361         if (seed_in)
362             memcpy(seed, seed_in, seed_len);
363
364     }
365
366     if ((ctx = BN_CTX_new()) == NULL)
367         goto err;
368
369     if ((mont = BN_MONT_CTX_new()) == NULL)
370         goto err;
371
372     BN_CTX_start(ctx);
373     r0 = BN_CTX_get(ctx);
374     g = BN_CTX_get(ctx);
375     W = BN_CTX_get(ctx);
376     X = BN_CTX_get(ctx);
377     c = BN_CTX_get(ctx);
378     test = BN_CTX_get(ctx);
379     if (test == NULL)
380         goto err;
381
382     /* if p, q already supplied generate g only */
383     if (ret->p && ret->q) {
384         p = ret->p;
385         q = ret->q;
386         if (idx >= 0)
387             memcpy(seed_tmp, seed, seed_len);
388         goto g_only;
389     } else {
390         p = BN_CTX_get(ctx);
391         q = BN_CTX_get(ctx);
392         if (q == NULL)
393             goto err;
394     }
395
396     if (!BN_lshift(test, BN_value_one(), L - 1))
397         goto err;
398     for (;;) {
399         for (;;) {              /* find q */
400             unsigned char *pmd;
401             /* step 1 */
402             if (!BN_GENCB_call(cb, 0, m++))
403                 goto err;
404
405             if (!seed_in) {
406                 if (RAND_bytes(seed, seed_len) <= 0)
407                     goto err;
408             }
409             /* step 2 */
410             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
411                 goto err;
412             /* Take least significant bits of md */
413             if (mdsize > qsize)
414                 pmd = md + mdsize - qsize;
415             else
416                 pmd = md;
417
418             if (mdsize < qsize)
419                 memset(md + mdsize, 0, qsize - mdsize);
420
421             /* step 3 */
422             pmd[0] |= 0x80;
423             pmd[qsize - 1] |= 0x01;
424             if (!BN_bin2bn(pmd, qsize, q))
425                 goto err;
426
427             /* step 4 */
428             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
429                                         seed_in ? 1 : 0, cb);
430             if (r > 0)
431                 break;
432             if (r != 0)
433                 goto err;
434             /* Provided seed didn't produce a prime: error */
435             if (seed_in) {
436                 ok = 0;
437                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
438                 goto err;
439             }
440
441             /* do a callback call */
442             /* step 5 */
443         }
444         /* Copy seed to seed_out before we mess with it */
445         if (seed_out)
446             memcpy(seed_out, seed, seed_len);
447
448         if (!BN_GENCB_call(cb, 2, 0))
449             goto err;
450         if (!BN_GENCB_call(cb, 3, 0))
451             goto err;
452
453         /* step 6 */
454         counter = 0;
455         /* "offset = 1" */
456
457         n = (L - 1) / (mdsize << 3);
458
459         for (;;) {
460             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
461                 goto err;
462
463             /* step 7 */
464             BN_zero(W);
465             /* now 'buf' contains "SEED + offset - 1" */
466             for (k = 0; k <= n; k++) {
467                 /*
468                  * obtain "SEED + offset + k" by incrementing:
469                  */
470                 for (i = seed_len - 1; i >= 0; i--) {
471                     seed[i]++;
472                     if (seed[i] != 0)
473                         break;
474                 }
475
476                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
477                     goto err;
478
479                 /* step 8 */
480                 if (!BN_bin2bn(md, mdsize, r0))
481                     goto err;
482                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
483                     goto err;
484                 if (!BN_add(W, W, r0))
485                     goto err;
486             }
487
488             /* more of step 8 */
489             if (!BN_mask_bits(W, L - 1))
490                 goto err;
491             if (!BN_copy(X, W))
492                 goto err;
493             if (!BN_add(X, X, test))
494                 goto err;
495
496             /* step 9 */
497             if (!BN_lshift1(r0, q))
498                 goto err;
499             if (!BN_mod(c, X, r0, ctx))
500                 goto err;
501             if (!BN_sub(r0, c, BN_value_one()))
502                 goto err;
503             if (!BN_sub(p, X, r0))
504                 goto err;
505
506             /* step 10 */
507             if (BN_cmp(p, test) >= 0) {
508                 /* step 11 */
509                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
510                 if (r > 0)
511                     goto end;   /* found it */
512                 if (r != 0)
513                     goto err;
514             }
515
516             /* step 13 */
517             counter++;
518             /* "offset = offset + n + 1" */
519
520             /* step 14 */
521             if (counter >= (int)(4 * L))
522                 break;
523         }
524         if (seed_in) {
525             ok = 0;
526             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
527             goto err;
528         }
529     }
530  end:
531     if (!BN_GENCB_call(cb, 2, 1))
532         goto err;
533
534  g_only:
535
536     /* We now need to generate g */
537     /* Set r0=(p-1)/q */
538     if (!BN_sub(test, p, BN_value_one()))
539         goto err;
540     if (!BN_div(r0, NULL, test, q, ctx))
541         goto err;
542
543     if (idx < 0) {
544         if (!BN_set_word(test, h))
545             goto err;
546     } else
547         h = 1;
548     if (!BN_MONT_CTX_set(mont, p, ctx))
549         goto err;
550
551     for (;;) {
552         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
553         if (idx >= 0) {
554             md[0] = idx & 0xff;
555             md[1] = (h >> 8) & 0xff;
556             md[2] = h & 0xff;
557             if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
558                 goto err;
559             if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
560                 goto err;
561             if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
562                 goto err;
563             if (!EVP_DigestUpdate(mctx, md, 3))
564                 goto err;
565             if (!EVP_DigestFinal_ex(mctx, md, NULL))
566                 goto err;
567             if (!BN_bin2bn(md, mdsize, test))
568                 goto err;
569         }
570         /* g=test^r0%p */
571         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
572             goto err;
573         if (!BN_is_one(g))
574             break;
575         if (idx < 0 && !BN_add(test, test, BN_value_one()))
576             goto err;
577         h++;
578         if (idx >= 0 && h > 0xffff)
579             goto err;
580     }
581
582     if (!BN_GENCB_call(cb, 3, 1))
583         goto err;
584
585     ok = 1;
586  err:
587     if (ok == 1) {
588         if (p != ret->p) {
589             BN_free(ret->p);
590             ret->p = BN_dup(p);
591         }
592         if (q != ret->q) {
593             BN_free(ret->q);
594             ret->q = BN_dup(q);
595         }
596         BN_free(ret->g);
597         ret->g = BN_dup(g);
598         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
599             ok = -1;
600             goto err;
601         }
602         if (counter_ret != NULL)
603             *counter_ret = counter;
604         if (h_ret != NULL)
605             *h_ret = h;
606     }
607     OPENSSL_free(seed);
608     if (seed_out != seed_tmp)
609         OPENSSL_free(seed_tmp);
610     if (ctx)
611         BN_CTX_end(ctx);
612     BN_CTX_free(ctx);
613     BN_MONT_CTX_free(mont);
614     EVP_MD_CTX_free(mctx);
615     return ok;
616 }