e030cfa1e9dc68ccbce2375fecf47c4e358cf822
[openssl.git] / crypto / dsa / dsa_gen.c
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 /*
60  * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
61  * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
62  * 180-1)
63  */
64 #define xxxHASH    EVP_sha1()
65
66 #include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
67
68 #include <stdio.h>
69 #include "internal/cryptlib.h"
70 #include <openssl/evp.h>
71 #include <openssl/bn.h>
72 #include <openssl/rand.h>
73 #include <openssl/sha.h>
74
75 #include "dsa_locl.h"
76
77 int DSA_generate_parameters_ex(DSA *ret, int bits,
78                                const unsigned char *seed_in, int seed_len,
79                                int *counter_ret, unsigned long *h_ret,
80                                BN_GENCB *cb)
81 {
82     if (ret->meth->dsa_paramgen)
83         return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
84                                        counter_ret, h_ret, cb);
85     else {
86         const EVP_MD *evpmd;
87         size_t qbits = bits >= 2048 ? 256 : 160;
88
89         if (bits >= 2048) {
90             qbits = 256;
91             evpmd = EVP_sha256();
92         } else {
93             qbits = 160;
94             evpmd = EVP_sha1();
95         }
96
97         return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
98                                     seed_in, seed_len, NULL, counter_ret,
99                                     h_ret, cb);
100     }
101 }
102
103 int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
104                          const EVP_MD *evpmd, const unsigned char *seed_in,
105                          size_t seed_len, unsigned char *seed_out,
106                          int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
107 {
108     int ok = 0;
109     unsigned char seed[SHA256_DIGEST_LENGTH];
110     unsigned char md[SHA256_DIGEST_LENGTH];
111     unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
112     BIGNUM *r0, *W, *X, *c, *test;
113     BIGNUM *g = NULL, *q = NULL, *p = NULL;
114     BN_MONT_CTX *mont = NULL;
115     int i, k, n = 0, m = 0, qsize = qbits >> 3;
116     int counter = 0;
117     int r = 0;
118     BN_CTX *ctx = NULL;
119     unsigned int h = 2;
120
121     if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
122         qsize != SHA256_DIGEST_LENGTH)
123         /* invalid q size */
124         return 0;
125
126     if (evpmd == NULL)
127         /* use SHA1 as default */
128         evpmd = EVP_sha1();
129
130     if (bits < 512)
131         bits = 512;
132
133     bits = (bits + 63) / 64 * 64;
134
135     /*
136      * NB: seed_len == 0 is special case: copy generated seed to seed_in if
137      * it is not NULL.
138      */
139     if (seed_len && (seed_len < (size_t)qsize))
140         seed_in = NULL;         /* seed buffer too small -- ignore */
141     if (seed_len > (size_t)qsize)
142         seed_len = qsize;       /* App. 2.2 of FIPS PUB 186 allows larger
143                                  * SEED, but our internal buffers are
144                                  * restricted to 160 bits */
145     if (seed_in != NULL)
146         memcpy(seed, seed_in, seed_len);
147
148     if ((ctx = BN_CTX_new()) == NULL)
149         goto err;
150
151     if ((mont = BN_MONT_CTX_new()) == NULL)
152         goto err;
153
154     BN_CTX_start(ctx);
155     r0 = BN_CTX_get(ctx);
156     g = BN_CTX_get(ctx);
157     W = BN_CTX_get(ctx);
158     q = BN_CTX_get(ctx);
159     X = BN_CTX_get(ctx);
160     c = BN_CTX_get(ctx);
161     p = BN_CTX_get(ctx);
162     test = BN_CTX_get(ctx);
163
164     if (!BN_lshift(test, BN_value_one(), bits - 1))
165         goto err;
166
167     for (;;) {
168         for (;;) {              /* find q */
169             int seed_is_random;
170
171             /* step 1 */
172             if (!BN_GENCB_call(cb, 0, m++))
173                 goto err;
174
175             if (!seed_len) {
176                 if (RAND_bytes(seed, qsize) <= 0)
177                     goto err;
178                 seed_is_random = 1;
179             } else {
180                 seed_is_random = 0;
181                 seed_len = 0;   /* use random seed if 'seed_in' turns out to
182                                  * be bad */
183             }
184             memcpy(buf, seed, qsize);
185             memcpy(buf2, seed, qsize);
186             /* precompute "SEED + 1" for step 7: */
187             for (i = qsize - 1; i >= 0; i--) {
188                 buf[i]++;
189                 if (buf[i] != 0)
190                     break;
191             }
192
193             /* step 2 */
194             if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
195                 goto err;
196             if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
197                 goto err;
198             for (i = 0; i < qsize; i++)
199                 md[i] ^= buf2[i];
200
201             /* step 3 */
202             md[0] |= 0x80;
203             md[qsize - 1] |= 0x01;
204             if (!BN_bin2bn(md, qsize, q))
205                 goto err;
206
207             /* step 4 */
208             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
209                                         seed_is_random, cb);
210             if (r > 0)
211                 break;
212             if (r != 0)
213                 goto err;
214
215             /* do a callback call */
216             /* step 5 */
217         }
218
219         if (!BN_GENCB_call(cb, 2, 0))
220             goto err;
221         if (!BN_GENCB_call(cb, 3, 0))
222             goto err;
223
224         /* step 6 */
225         counter = 0;
226         /* "offset = 2" */
227
228         n = (bits - 1) / 160;
229
230         for (;;) {
231             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
232                 goto err;
233
234             /* step 7 */
235             BN_zero(W);
236             /* now 'buf' contains "SEED + offset - 1" */
237             for (k = 0; k <= n; k++) {
238                 /*
239                  * obtain "SEED + offset + k" by incrementing:
240                  */
241                 for (i = qsize - 1; i >= 0; i--) {
242                     buf[i]++;
243                     if (buf[i] != 0)
244                         break;
245                 }
246
247                 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
248                     goto err;
249
250                 /* step 8 */
251                 if (!BN_bin2bn(md, qsize, r0))
252                     goto err;
253                 if (!BN_lshift(r0, r0, (qsize << 3) * k))
254                     goto err;
255                 if (!BN_add(W, W, r0))
256                     goto err;
257             }
258
259             /* more of step 8 */
260             if (!BN_mask_bits(W, bits - 1))
261                 goto err;
262             if (!BN_copy(X, W))
263                 goto err;
264             if (!BN_add(X, X, test))
265                 goto err;
266
267             /* step 9 */
268             if (!BN_lshift1(r0, q))
269                 goto err;
270             if (!BN_mod(c, X, r0, ctx))
271                 goto err;
272             if (!BN_sub(r0, c, BN_value_one()))
273                 goto err;
274             if (!BN_sub(p, X, r0))
275                 goto err;
276
277             /* step 10 */
278             if (BN_cmp(p, test) >= 0) {
279                 /* step 11 */
280                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
281                 if (r > 0)
282                     goto end;   /* found it */
283                 if (r != 0)
284                     goto err;
285             }
286
287             /* step 13 */
288             counter++;
289             /* "offset = offset + n + 1" */
290
291             /* step 14 */
292             if (counter >= 4096)
293                 break;
294         }
295     }
296  end:
297     if (!BN_GENCB_call(cb, 2, 1))
298         goto err;
299
300     /* We now need to generate g */
301     /* Set r0=(p-1)/q */
302     if (!BN_sub(test, p, BN_value_one()))
303         goto err;
304     if (!BN_div(r0, NULL, test, q, ctx))
305         goto err;
306
307     if (!BN_set_word(test, h))
308         goto err;
309     if (!BN_MONT_CTX_set(mont, p, ctx))
310         goto err;
311
312     for (;;) {
313         /* g=test^r0%p */
314         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
315             goto err;
316         if (!BN_is_one(g))
317             break;
318         if (!BN_add(test, test, BN_value_one()))
319             goto err;
320         h++;
321     }
322
323     if (!BN_GENCB_call(cb, 3, 1))
324         goto err;
325
326     ok = 1;
327  err:
328     if (ok) {
329         BN_free(ret->p);
330         BN_free(ret->q);
331         BN_free(ret->g);
332         ret->p = BN_dup(p);
333         ret->q = BN_dup(q);
334         ret->g = BN_dup(g);
335         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
336             ok = 0;
337             goto err;
338         }
339         if (counter_ret != NULL)
340             *counter_ret = counter;
341         if (h_ret != NULL)
342             *h_ret = h;
343         if (seed_out)
344             memcpy(seed_out, seed, qsize);
345     }
346     if (ctx)
347         BN_CTX_end(ctx);
348     BN_CTX_free(ctx);
349     BN_MONT_CTX_free(mont);
350     return ok;
351 }
352
353 /*
354  * This is a parameter generation algorithm for the DSA2 algorithm as
355  * described in FIPS 186-3.
356  */
357
358 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
359                           const EVP_MD *evpmd, const unsigned char *seed_in,
360                           size_t seed_len, int idx, unsigned char *seed_out,
361                           int *counter_ret, unsigned long *h_ret,
362                           BN_GENCB *cb)
363 {
364     int ok = -1;
365     unsigned char *seed = NULL, *seed_tmp = NULL;
366     unsigned char md[EVP_MAX_MD_SIZE];
367     int mdsize;
368     BIGNUM *r0, *W, *X, *c, *test;
369     BIGNUM *g = NULL, *q = NULL, *p = NULL;
370     BN_MONT_CTX *mont = NULL;
371     int i, k, n = 0, m = 0, qsize = N >> 3;
372     int counter = 0;
373     int r = 0;
374     BN_CTX *ctx = NULL;
375     EVP_MD_CTX mctx;
376     unsigned int h = 2;
377
378     EVP_MD_CTX_init(&mctx);
379
380     if (evpmd == NULL) {
381         if (N == 160)
382             evpmd = EVP_sha1();
383         else if (N == 224)
384             evpmd = EVP_sha224();
385         else
386             evpmd = EVP_sha256();
387     }
388
389     mdsize = M_EVP_MD_size(evpmd);
390     /* If unverificable g generation only don't need seed */
391     if (!ret->p || !ret->q || idx >= 0) {
392         if (seed_len == 0)
393             seed_len = mdsize;
394
395         seed = OPENSSL_malloc(seed_len);
396
397         if (seed_out)
398             seed_tmp = seed_out;
399         else
400             seed_tmp = OPENSSL_malloc(seed_len);
401
402         if (!seed || !seed_tmp)
403             goto err;
404
405         if (seed_in)
406             memcpy(seed, seed_in, seed_len);
407
408     }
409
410     if ((ctx = BN_CTX_new()) == NULL)
411         goto err;
412
413     if ((mont = BN_MONT_CTX_new()) == NULL)
414         goto err;
415
416     BN_CTX_start(ctx);
417     r0 = BN_CTX_get(ctx);
418     g = BN_CTX_get(ctx);
419     W = BN_CTX_get(ctx);
420     X = BN_CTX_get(ctx);
421     c = BN_CTX_get(ctx);
422     test = BN_CTX_get(ctx);
423
424     /* if p, q already supplied generate g only */
425     if (ret->p && ret->q) {
426         p = ret->p;
427         q = ret->q;
428         if (idx >= 0)
429             memcpy(seed_tmp, seed, seed_len);
430         goto g_only;
431     } else {
432         p = BN_CTX_get(ctx);
433         q = BN_CTX_get(ctx);
434     }
435
436     if (!BN_lshift(test, BN_value_one(), L - 1))
437         goto err;
438     for (;;) {
439         for (;;) {              /* find q */
440             unsigned char *pmd;
441             /* step 1 */
442             if (!BN_GENCB_call(cb, 0, m++))
443                 goto err;
444
445             if (!seed_in) {
446                 if (RAND_bytes(seed, seed_len) <= 0)
447                     goto err;
448             }
449             /* step 2 */
450             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
451                 goto err;
452             /* Take least significant bits of md */
453             if (mdsize > qsize)
454                 pmd = md + mdsize - qsize;
455             else
456                 pmd = md;
457
458             if (mdsize < qsize)
459                 memset(md + mdsize, 0, qsize - mdsize);
460
461             /* step 3 */
462             pmd[0] |= 0x80;
463             pmd[qsize - 1] |= 0x01;
464             if (!BN_bin2bn(pmd, qsize, q))
465                 goto err;
466
467             /* step 4 */
468             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
469                                         seed_in ? 1 : 0, cb);
470             if (r > 0)
471                 break;
472             if (r != 0)
473                 goto err;
474             /* Provided seed didn't produce a prime: error */
475             if (seed_in) {
476                 ok = 0;
477                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
478                 goto err;
479             }
480
481             /* do a callback call */
482             /* step 5 */
483         }
484         /* Copy seed to seed_out before we mess with it */
485         if (seed_out)
486             memcpy(seed_out, seed, seed_len);
487
488         if (!BN_GENCB_call(cb, 2, 0))
489             goto err;
490         if (!BN_GENCB_call(cb, 3, 0))
491             goto err;
492
493         /* step 6 */
494         counter = 0;
495         /* "offset = 1" */
496
497         n = (L - 1) / (mdsize << 3);
498
499         for (;;) {
500             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
501                 goto err;
502
503             /* step 7 */
504             BN_zero(W);
505             /* now 'buf' contains "SEED + offset - 1" */
506             for (k = 0; k <= n; k++) {
507                 /*
508                  * obtain "SEED + offset + k" by incrementing:
509                  */
510                 for (i = seed_len - 1; i >= 0; i--) {
511                     seed[i]++;
512                     if (seed[i] != 0)
513                         break;
514                 }
515
516                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
517                     goto err;
518
519                 /* step 8 */
520                 if (!BN_bin2bn(md, mdsize, r0))
521                     goto err;
522                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
523                     goto err;
524                 if (!BN_add(W, W, r0))
525                     goto err;
526             }
527
528             /* more of step 8 */
529             if (!BN_mask_bits(W, L - 1))
530                 goto err;
531             if (!BN_copy(X, W))
532                 goto err;
533             if (!BN_add(X, X, test))
534                 goto err;
535
536             /* step 9 */
537             if (!BN_lshift1(r0, q))
538                 goto err;
539             if (!BN_mod(c, X, r0, ctx))
540                 goto err;
541             if (!BN_sub(r0, c, BN_value_one()))
542                 goto err;
543             if (!BN_sub(p, X, r0))
544                 goto err;
545
546             /* step 10 */
547             if (BN_cmp(p, test) >= 0) {
548                 /* step 11 */
549                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
550                 if (r > 0)
551                     goto end;   /* found it */
552                 if (r != 0)
553                     goto err;
554             }
555
556             /* step 13 */
557             counter++;
558             /* "offset = offset + n + 1" */
559
560             /* step 14 */
561             if (counter >= (int)(4 * L))
562                 break;
563         }
564         if (seed_in) {
565             ok = 0;
566             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
567             goto err;
568         }
569     }
570  end:
571     if (!BN_GENCB_call(cb, 2, 1))
572         goto err;
573
574  g_only:
575
576     /* We now need to generate g */
577     /* Set r0=(p-1)/q */
578     if (!BN_sub(test, p, BN_value_one()))
579         goto err;
580     if (!BN_div(r0, NULL, test, q, ctx))
581         goto err;
582
583     if (idx < 0) {
584         if (!BN_set_word(test, h))
585             goto err;
586     } else
587         h = 1;
588     if (!BN_MONT_CTX_set(mont, p, ctx))
589         goto err;
590
591     for (;;) {
592         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
593         if (idx >= 0) {
594             md[0] = idx & 0xff;
595             md[1] = (h >> 8) & 0xff;
596             md[2] = h & 0xff;
597             if (!EVP_DigestInit_ex(&mctx, evpmd, NULL))
598                 goto err;
599             if (!EVP_DigestUpdate(&mctx, seed_tmp, seed_len))
600                 goto err;
601             if (!EVP_DigestUpdate(&mctx, ggen, sizeof(ggen)))
602                 goto err;
603             if (!EVP_DigestUpdate(&mctx, md, 3))
604                 goto err;
605             if (!EVP_DigestFinal_ex(&mctx, md, NULL))
606                 goto err;
607             if (!BN_bin2bn(md, mdsize, test))
608                 goto err;
609         }
610         /* g=test^r0%p */
611         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
612             goto err;
613         if (!BN_is_one(g))
614             break;
615         if (idx < 0 && !BN_add(test, test, BN_value_one()))
616             goto err;
617         h++;
618         if (idx >= 0 && h > 0xffff)
619             goto err;
620     }
621
622     if (!BN_GENCB_call(cb, 3, 1))
623         goto err;
624
625     ok = 1;
626  err:
627     if (ok == 1) {
628         if (p != ret->p) {
629             BN_free(ret->p);
630             ret->p = BN_dup(p);
631         }
632         if (q != ret->q) {
633             BN_free(ret->q);
634             ret->q = BN_dup(q);
635         }
636         BN_free(ret->g);
637         ret->g = BN_dup(g);
638         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
639             ok = -1;
640             goto err;
641         }
642         if (counter_ret != NULL)
643             *counter_ret = counter;
644         if (h_ret != NULL)
645             *h_ret = h;
646     }
647     OPENSSL_free(seed);
648     if (seed_out != seed_tmp)
649         OPENSSL_free(seed_tmp);
650     if (ctx)
651         BN_CTX_end(ctx);
652     BN_CTX_free(ctx);
653     BN_MONT_CTX_free(mont);
654     EVP_MD_CTX_cleanup(&mctx);
655     return ok;
656 }
657
658 int dsa_paramgen_check_g(DSA *dsa)
659 {
660     BN_CTX *ctx;
661     BIGNUM *tmp;
662     BN_MONT_CTX *mont = NULL;
663     int rv = -1;
664     ctx = BN_CTX_new();
665     if (!ctx)
666         return -1;
667     BN_CTX_start(ctx);
668     if (BN_cmp(dsa->g, BN_value_one()) <= 0)
669         return 0;
670     if (BN_cmp(dsa->g, dsa->p) >= 0)
671         return 0;
672     tmp = BN_CTX_get(ctx);
673     if (!tmp)
674         goto err;
675     if ((mont = BN_MONT_CTX_new()) == NULL)
676         goto err;
677     if (!BN_MONT_CTX_set(mont, dsa->p, ctx))
678         goto err;
679     /* Work out g^q mod p */
680     if (!BN_mod_exp_mont(tmp, dsa->g, dsa->q, dsa->p, ctx, mont))
681         goto err;
682     if (!BN_cmp(tmp, BN_value_one()))
683         rv = 1;
684     else
685         rv = 0;
686  err:
687     BN_CTX_end(ctx);
688     BN_MONT_CTX_free(mont);
689     BN_CTX_free(ctx);
690     return rv;
691
692 }