Improve style
[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             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
300 int 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         if (q == NULL)
380             goto err;
381     }
382
383     if (!BN_lshift(test, BN_value_one(), L - 1))
384         goto err;
385     for (;;) {
386         for (;;) {              /* find q */
387             unsigned char *pmd;
388             /* step 1 */
389             if (!BN_GENCB_call(cb, 0, m++))
390                 goto err;
391
392             if (!seed_in) {
393                 if (RAND_bytes(seed, seed_len) <= 0)
394                     goto err;
395             }
396             /* step 2 */
397             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
398                 goto err;
399             /* Take least significant bits of md */
400             if (mdsize > qsize)
401                 pmd = md + mdsize - qsize;
402             else
403                 pmd = md;
404
405             if (mdsize < qsize)
406                 memset(md + mdsize, 0, qsize - mdsize);
407
408             /* step 3 */
409             pmd[0] |= 0x80;
410             pmd[qsize - 1] |= 0x01;
411             if (!BN_bin2bn(pmd, qsize, q))
412                 goto err;
413
414             /* step 4 */
415             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
416                                         seed_in ? 1 : 0, cb);
417             if (r > 0)
418                 break;
419             if (r != 0)
420                 goto err;
421             /* Provided seed didn't produce a prime: error */
422             if (seed_in) {
423                 ok = 0;
424                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
425                 goto err;
426             }
427
428             /* do a callback call */
429             /* step 5 */
430         }
431         /* Copy seed to seed_out before we mess with it */
432         if (seed_out)
433             memcpy(seed_out, seed, seed_len);
434
435         if (!BN_GENCB_call(cb, 2, 0))
436             goto err;
437         if (!BN_GENCB_call(cb, 3, 0))
438             goto err;
439
440         /* step 6 */
441         counter = 0;
442         /* "offset = 1" */
443
444         n = (L - 1) / (mdsize << 3);
445
446         for (;;) {
447             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
448                 goto err;
449
450             /* step 7 */
451             BN_zero(W);
452             /* now 'buf' contains "SEED + offset - 1" */
453             for (k = 0; k <= n; k++) {
454                 /*
455                  * obtain "SEED + offset + k" by incrementing:
456                  */
457                 for (i = seed_len - 1; i >= 0; i--) {
458                     seed[i]++;
459                     if (seed[i] != 0)
460                         break;
461                 }
462
463                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
464                     goto err;
465
466                 /* step 8 */
467                 if (!BN_bin2bn(md, mdsize, r0))
468                     goto err;
469                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
470                     goto err;
471                 if (!BN_add(W, W, r0))
472                     goto err;
473             }
474
475             /* more of step 8 */
476             if (!BN_mask_bits(W, L - 1))
477                 goto err;
478             if (!BN_copy(X, W))
479                 goto err;
480             if (!BN_add(X, X, test))
481                 goto err;
482
483             /* step 9 */
484             if (!BN_lshift1(r0, q))
485                 goto err;
486             if (!BN_mod(c, X, r0, ctx))
487                 goto err;
488             if (!BN_sub(r0, c, BN_value_one()))
489                 goto err;
490             if (!BN_sub(p, X, r0))
491                 goto err;
492
493             /* step 10 */
494             if (BN_cmp(p, test) >= 0) {
495                 /* step 11 */
496                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
497                 if (r > 0)
498                     goto end;   /* found it */
499                 if (r != 0)
500                     goto err;
501             }
502
503             /* step 13 */
504             counter++;
505             /* "offset = offset + n + 1" */
506
507             /* step 14 */
508             if (counter >= (int)(4 * L))
509                 break;
510         }
511         if (seed_in) {
512             ok = 0;
513             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
514             goto err;
515         }
516     }
517  end:
518     if (!BN_GENCB_call(cb, 2, 1))
519         goto err;
520
521  g_only:
522
523     /* We now need to generate g */
524     /* Set r0=(p-1)/q */
525     if (!BN_sub(test, p, BN_value_one()))
526         goto err;
527     if (!BN_div(r0, NULL, test, q, ctx))
528         goto err;
529
530     if (idx < 0) {
531         if (!BN_set_word(test, h))
532             goto err;
533     } else
534         h = 1;
535     if (!BN_MONT_CTX_set(mont, p, ctx))
536         goto err;
537
538     for (;;) {
539         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
540         if (idx >= 0) {
541             md[0] = idx & 0xff;
542             md[1] = (h >> 8) & 0xff;
543             md[2] = h & 0xff;
544             if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
545                 goto err;
546             if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
547                 goto err;
548             if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
549                 goto err;
550             if (!EVP_DigestUpdate(mctx, md, 3))
551                 goto err;
552             if (!EVP_DigestFinal_ex(mctx, md, NULL))
553                 goto err;
554             if (!BN_bin2bn(md, mdsize, test))
555                 goto err;
556         }
557         /* g=test^r0%p */
558         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
559             goto err;
560         if (!BN_is_one(g))
561             break;
562         if (idx < 0 && !BN_add(test, test, BN_value_one()))
563             goto err;
564         h++;
565         if (idx >= 0 && h > 0xffff)
566             goto err;
567     }
568
569     if (!BN_GENCB_call(cb, 3, 1))
570         goto err;
571
572     ok = 1;
573  err:
574     if (ok == 1) {
575         if (p != ret->p) {
576             BN_free(ret->p);
577             ret->p = BN_dup(p);
578         }
579         if (q != ret->q) {
580             BN_free(ret->q);
581             ret->q = BN_dup(q);
582         }
583         BN_free(ret->g);
584         ret->g = BN_dup(g);
585         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
586             ok = -1;
587             goto err;
588         }
589         if (counter_ret != NULL)
590             *counter_ret = counter;
591         if (h_ret != NULL)
592             *h_ret = h;
593     }
594     OPENSSL_free(seed);
595     if (seed_out != seed_tmp)
596         OPENSSL_free(seed_tmp);
597     if (ctx)
598         BN_CTX_end(ctx);
599     BN_CTX_free(ctx);
600     BN_MONT_CTX_free(mont);
601     EVP_MD_CTX_free(mctx);
602     return ok;
603 }