fips_dsa_gen.c revision 296465 
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#undef GENUINE_DSA
60
61#ifdef GENUINE_DSA
62/*
63 * Parameter generation follows the original release of FIPS PUB 186,
64 * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180)
65 */
66# define HASH    EVP_sha()
67#else
68/*
69 * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
70 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
71 * 180-1)
72 */
73# define HASH    EVP_sha1()
74#endif
75
76#include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
77
78#ifndef OPENSSL_NO_SHA
79
80# include <stdio.h>
81# include <time.h>
82# include <string.h>
83# include <openssl/evp.h>
84# include <openssl/bn.h>
85# include <openssl/dsa.h>
86# include <openssl/rand.h>
87# include <openssl/sha.h>
88# include <openssl/err.h>
89
90# ifdef OPENSSL_FIPS
91
92static int dsa_builtin_paramgen(DSA *ret, int bits,
93                                unsigned char *seed_in, int seed_len,
94                                int *counter_ret, unsigned long *h_ret,
95                                BN_GENCB *cb);
96
97int DSA_generate_parameters_ex(DSA *ret, int bits,
98                               unsigned char *seed_in, int seed_len,
99                               int *counter_ret, unsigned long *h_ret,
100                               BN_GENCB *cb)
101{
102    if (ret->meth->dsa_paramgen)
103        return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
104                                       counter_ret, h_ret, cb);
105    return dsa_builtin_paramgen(ret, bits, seed_in, seed_len,
106                                counter_ret, h_ret, cb);
107}
108
109static int dsa_builtin_paramgen(DSA *ret, int bits,
110                                unsigned char *seed_in, int seed_len,
111                                int *counter_ret, unsigned long *h_ret,
112                                BN_GENCB *cb)
113{
114    int ok = 0;
115    unsigned char seed[SHA_DIGEST_LENGTH];
116    unsigned char md[SHA_DIGEST_LENGTH];
117    unsigned char buf[SHA_DIGEST_LENGTH], buf2[SHA_DIGEST_LENGTH];
118    BIGNUM *r0, *W, *X, *c, *test;
119    BIGNUM *g = NULL, *q = NULL, *p = NULL;
120    BN_MONT_CTX *mont = NULL;
121    int k, n = 0, i, b, m = 0;
122    int counter = 0;
123    int r = 0;
124    BN_CTX *ctx = NULL;
125    unsigned int h = 2;
126
127    if (FIPS_selftest_failed()) {
128        FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN, FIPS_R_FIPS_SELFTEST_FAILED);
129        goto err;
130    }
131
132    if (FIPS_mode() && (bits < OPENSSL_DSA_FIPS_MIN_MODULUS_BITS)) {
133        DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_KEY_SIZE_TOO_SMALL);
134        goto err;
135    }
136
137    if (bits < 512)
138        bits = 512;
139    bits = (bits + 63) / 64 * 64;
140
141    /*
142     * NB: seed_len == 0 is special case: copy generated seed to seed_in if
143     * it is not NULL.
144     */
145    if (seed_len && (seed_len < 20))
146        seed_in = NULL;         /* seed buffer too small -- ignore */
147    if (seed_len > 20)
148        seed_len = 20;          /* App. 2.2 of FIPS PUB 186 allows larger
149                                 * SEED, but our internal buffers are
150                                 * restricted to 160 bits */
151    if ((seed_in != NULL) && (seed_len == 20)) {
152        memcpy(seed, seed_in, seed_len);
153        /* set seed_in to NULL to avoid it being copied back */
154        seed_in = NULL;
155    }
156
157    if ((ctx = BN_CTX_new()) == NULL)
158        goto err;
159
160    if ((mont = BN_MONT_CTX_new()) == NULL)
161        goto err;
162
163    BN_CTX_start(ctx);
164    r0 = BN_CTX_get(ctx);
165    g = BN_CTX_get(ctx);
166    W = BN_CTX_get(ctx);
167    q = BN_CTX_get(ctx);
168    X = BN_CTX_get(ctx);
169    c = BN_CTX_get(ctx);
170    p = BN_CTX_get(ctx);
171    test = BN_CTX_get(ctx);
172
173    if (!BN_lshift(test, BN_value_one(), bits - 1))
174        goto err;
175
176    for (;;) {
177        for (;;) {              /* find q */
178            int seed_is_random;
179
180            /* step 1 */
181            if (!BN_GENCB_call(cb, 0, m++))
182                goto err;
183
184            if (!seed_len) {
185                RAND_pseudo_bytes(seed, SHA_DIGEST_LENGTH);
186                seed_is_random = 1;
187            } else {
188                seed_is_random = 0;
189                seed_len = 0;   /* use random seed if 'seed_in' turns out to
190                                 * be bad */
191            }
192            memcpy(buf, seed, SHA_DIGEST_LENGTH);
193            memcpy(buf2, seed, SHA_DIGEST_LENGTH);
194            /* precompute "SEED + 1" for step 7: */
195            for (i = SHA_DIGEST_LENGTH - 1; i >= 0; i--) {
196                buf[i]++;
197                if (buf[i] != 0)
198                    break;
199            }
200
201            /* step 2 */
202            EVP_Digest(seed, SHA_DIGEST_LENGTH, md, NULL, HASH, NULL);
203            EVP_Digest(buf, SHA_DIGEST_LENGTH, buf2, NULL, HASH, NULL);
204            for (i = 0; i < SHA_DIGEST_LENGTH; i++)
205                md[i] ^= buf2[i];
206
207            /* step 3 */
208            md[0] |= 0x80;
209            md[SHA_DIGEST_LENGTH - 1] |= 0x01;
210            if (!BN_bin2bn(md, SHA_DIGEST_LENGTH, q))
211                goto err;
212
213            /* step 4 */
214            r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
215                                        seed_is_random, cb);
216            if (r > 0)
217                break;
218            if (r != 0)
219                goto err;
220
221            /* do a callback call */
222            /* step 5 */
223        }
224
225        if (!BN_GENCB_call(cb, 2, 0))
226            goto err;
227        if (!BN_GENCB_call(cb, 3, 0))
228            goto err;
229
230        /* step 6 */
231        counter = 0;
232        /* "offset = 2" */
233
234        n = (bits - 1) / 160;
235        b = (bits - 1) - n * 160;
236
237        for (;;) {
238            if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
239                goto err;
240
241            /* step 7 */
242            BN_zero(W);
243            /* now 'buf' contains "SEED + offset - 1" */
244            for (k = 0; k <= n; k++) {
245                /*
246                 * obtain "SEED + offset + k" by incrementing:
247                 */
248                for (i = SHA_DIGEST_LENGTH - 1; i >= 0; i--) {
249                    buf[i]++;
250                    if (buf[i] != 0)
251                        break;
252                }
253
254                EVP_Digest(buf, SHA_DIGEST_LENGTH, md, NULL, HASH, NULL);
255
256                /* step 8 */
257                if (!BN_bin2bn(md, SHA_DIGEST_LENGTH, r0))
258                    goto err;
259                if (!BN_lshift(r0, r0, 160 * k))
260                    goto err;
261                if (!BN_add(W, W, r0))
262                    goto err;
263            }
264
265            /* more of step 8 */
266            if (!BN_mask_bits(W, bits - 1))
267                goto err;
268            if (!BN_copy(X, W))
269                goto err;
270            if (!BN_add(X, X, test))
271                goto err;
272
273            /* step 9 */
274            if (!BN_lshift1(r0, q))
275                goto err;
276            if (!BN_mod(c, X, r0, ctx))
277                goto err;
278            if (!BN_sub(r0, c, BN_value_one()))
279                goto err;
280            if (!BN_sub(p, X, r0))
281                goto err;
282
283            /* step 10 */
284            if (BN_cmp(p, test) >= 0) {
285                /* step 11 */
286                r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
287                if (r > 0)
288                    goto end;   /* found it */
289                if (r != 0)
290                    goto err;
291            }
292
293            /* step 13 */
294            counter++;
295            /* "offset = offset + n + 1" */
296
297            /* step 14 */
298            if (counter >= 4096)
299                break;
300        }
301    }
302 end:
303    if (!BN_GENCB_call(cb, 2, 1))
304        goto err;
305
306    /* We now need to generate g */
307    /* Set r0=(p-1)/q */
308    if (!BN_sub(test, p, BN_value_one()))
309        goto err;
310    if (!BN_div(r0, NULL, test, q, ctx))
311        goto err;
312
313    if (!BN_set_word(test, h))
314        goto err;
315    if (!BN_MONT_CTX_set(mont, p, ctx))
316        goto err;
317
318    for (;;) {
319        /* g=test^r0%p */
320        if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
321            goto err;
322        if (!BN_is_one(g))
323            break;
324        if (!BN_add(test, test, BN_value_one()))
325            goto err;
326        h++;
327    }
328
329    if (!BN_GENCB_call(cb, 3, 1))
330        goto err;
331
332    ok = 1;
333 err:
334    if (ok) {
335        if (ret->p)
336            BN_free(ret->p);
337        if (ret->q)
338            BN_free(ret->q);
339        if (ret->g)
340            BN_free(ret->g);
341        ret->p = BN_dup(p);
342        ret->q = BN_dup(q);
343        ret->g = BN_dup(g);
344        if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
345            ok = 0;
346            goto err;
347        }
348        if (seed_in != NULL)
349            memcpy(seed_in, seed, 20);
350        if (counter_ret != NULL)
351            *counter_ret = counter;
352        if (h_ret != NULL)
353            *h_ret = h;
354    }
355    if (ctx) {
356        BN_CTX_end(ctx);
357        BN_CTX_free(ctx);
358    }
359    if (mont != NULL)
360        BN_MONT_CTX_free(mont);
361    return ok;
362}
363# endif
364#endif
365