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