[thirdparty/openssl.git] / crypto / dsa / dsa_gen.c

/*
 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

/*
 * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
 * 180-1)
 */
#define xxxHASH    EVP_sha1()

#include <openssl/opensslconf.h>
#include <stdio.h>
#include "internal/cryptlib.h"
#include <openssl/evp.h>
#include <openssl/bn.h>
#include <openssl/rand.h>
#include <openssl/sha.h>
#include "dsa_local.h"

int DSA_generate_parameters_ex(DSA *ret, int bits,
                               const unsigned char *seed_in, int seed_len,
                               int *counter_ret, unsigned long *h_ret,
                               BN_GENCB *cb)
{
    if (ret->meth->dsa_paramgen)
        return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
                                       counter_ret, h_ret, cb);
    else {
        const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1();
        size_t qbits = EVP_MD_size(evpmd) * 8;

        return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
                                    seed_in, seed_len, NULL, counter_ret,
                                    h_ret, cb);
    }
}

int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
                         const EVP_MD *evpmd, const unsigned char *seed_in,
                         size_t seed_len, unsigned char *seed_out,
                         int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
{
    int ok = 0;
    unsigned char seed[SHA256_DIGEST_LENGTH];
    unsigned char md[SHA256_DIGEST_LENGTH];
    unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
    BIGNUM *r0, *W, *X, *c, *test;
    BIGNUM *g = NULL, *q = NULL, *p = NULL;
    BN_MONT_CTX *mont = NULL;
    int i, k, n = 0, m = 0, qsize = qbits >> 3;
    int counter = 0;
    int r = 0;
    BN_CTX *ctx = NULL;
    unsigned int h = 2;

    if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
        qsize != SHA256_DIGEST_LENGTH)
        /* invalid q size */
        return 0;

    if (evpmd == NULL) {
        if (qsize == SHA_DIGEST_LENGTH)
            evpmd = EVP_sha1();
        else if (qsize == SHA224_DIGEST_LENGTH)
            evpmd = EVP_sha224();
        else
            evpmd = EVP_sha256();
    } else {
        qsize = EVP_MD_size(evpmd);
    }

    if (bits < 512)
        bits = 512;

    bits = (bits + 63) / 64 * 64;

    if (seed_in != NULL) {
        if (seed_len < (size_t)qsize) {
            DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL);
            return 0;
        }
        if (seed_len > (size_t)qsize) {
            /* Only consume as much seed as is expected. */
            seed_len = qsize;
        }
        memcpy(seed, seed_in, seed_len);
    }

    if ((mont = BN_MONT_CTX_new()) == NULL)
        goto err;

    if ((ctx = BN_CTX_new()) == NULL)
        goto err;

    BN_CTX_start(ctx);

    r0 = BN_CTX_get(ctx);
    g = BN_CTX_get(ctx);
    W = BN_CTX_get(ctx);
    q = BN_CTX_get(ctx);
    X = BN_CTX_get(ctx);
    c = BN_CTX_get(ctx);
    p = BN_CTX_get(ctx);
    test = BN_CTX_get(ctx);

    if (test == NULL)
        goto err;

    if (!BN_lshift(test, BN_value_one(), bits - 1))
        goto err;

    for (;;) {
        for (;;) {              /* find q */
            int use_random_seed = (seed_in == NULL);

            /* step 1 */
            if (!BN_GENCB_call(cb, 0, m++))
                goto err;

            if (use_random_seed) {
                if (RAND_bytes(seed, qsize) <= 0)
                    goto err;
            } else {
                /* If we come back through, use random seed next time. */
                seed_in = NULL;
            }
            memcpy(buf, seed, qsize);
            memcpy(buf2, seed, qsize);
            /* precompute "SEED + 1" for step 7: */
            for (i = qsize - 1; i >= 0; i--) {
                buf[i]++;
                if (buf[i] != 0)
                    break;
            }

            /* step 2 */
            if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
                goto err;
            if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
                goto err;
            for (i = 0; i < qsize; i++)
                md[i] ^= buf2[i];

            /* step 3 */
            md[0] |= 0x80;
            md[qsize - 1] |= 0x01;
            if (!BN_bin2bn(md, qsize, q))
                goto err;

            /* step 4 */
            r = BN_check_prime(q, ctx, cb);
            if (r > 0)
                break;
            if (r != 0)
                goto err;

            /* do a callback call */
            /* step 5 */
        }

        if (!BN_GENCB_call(cb, 2, 0))
            goto err;
        if (!BN_GENCB_call(cb, 3, 0))
            goto err;

        /* step 6 */
        counter = 0;
        /* "offset = 2" */

        n = (bits - 1) / 160;

        for (;;) {
            if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
                goto err;

            /* step 7 */
            BN_zero(W);
            /* now 'buf' contains "SEED + offset - 1" */
            for (k = 0; k <= n; k++) {
                /*
                 * obtain "SEED + offset + k" by incrementing:
                 */
                for (i = qsize - 1; i >= 0; i--) {
                    buf[i]++;
                    if (buf[i] != 0)
                        break;
                }

                if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
                    goto err;

                /* step 8 */
                if (!BN_bin2bn(md, qsize, r0))
                    goto err;
                if (!BN_lshift(r0, r0, (qsize << 3) * k))
                    goto err;
                if (!BN_add(W, W, r0))
                    goto err;
            }

            /* more of step 8 */
            if (!BN_mask_bits(W, bits - 1))
                goto err;
            if (!BN_copy(X, W))
                goto err;
            if (!BN_add(X, X, test))
                goto err;

            /* step 9 */
            if (!BN_lshift1(r0, q))
                goto err;
            if (!BN_mod(c, X, r0, ctx))
                goto err;
            if (!BN_sub(r0, c, BN_value_one()))
                goto err;
            if (!BN_sub(p, X, r0))
                goto err;

            /* step 10 */
            if (BN_cmp(p, test) >= 0) {
                /* step 11 */
                r = BN_check_prime(p, ctx, cb);
                if (r > 0)
                    goto end;   /* found it */
                if (r != 0)
                    goto err;
            }

            /* step 13 */
            counter++;
            /* "offset = offset + n + 1" */

            /* step 14 */
            if (counter >= 4096)
                break;
        }
    }
 end:
    if (!BN_GENCB_call(cb, 2, 1))
        goto err;

    /* We now need to generate g */
    /* Set r0=(p-1)/q */
    if (!BN_sub(test, p, BN_value_one()))
        goto err;
    if (!BN_div(r0, NULL, test, q, ctx))
        goto err;

    if (!BN_set_word(test, h))
        goto err;
    if (!BN_MONT_CTX_set(mont, p, ctx))
        goto err;

    for (;;) {
        /* g=test^r0%p */
        if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
            goto err;
        if (!BN_is_one(g))
            break;
        if (!BN_add(test, test, BN_value_one()))
            goto err;
        h++;
    }

    if (!BN_GENCB_call(cb, 3, 1))
        goto err;

    ok = 1;
 err:
    if (ok) {
        BN_free(ret->p);
        BN_free(ret->q);
        BN_free(ret->g);
        ret->p = BN_dup(p);
        ret->q = BN_dup(q);
        ret->g = BN_dup(g);
        ret->dirty_cnt++;
        if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
            ok = 0;
            goto err;
        }
        if (counter_ret != NULL)
            *counter_ret = counter;
        if (h_ret != NULL)
            *h_ret = h;
        if (seed_out)
            memcpy(seed_out, seed, qsize);
    }
    BN_CTX_end(ctx);
    BN_CTX_free(ctx);
    BN_MONT_CTX_free(mont);
    return ok;
}

/*
 * This is a parameter generation algorithm for the DSA2 algorithm as
 * described in FIPS 186-3.
 */

int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
                          const EVP_MD *evpmd, const unsigned char *seed_in,
                          size_t seed_len, int idx, unsigned char *seed_out,
                          int *counter_ret, unsigned long *h_ret,
                          BN_GENCB *cb)
{
    int ok = -1;
    unsigned char *seed = NULL, *seed_tmp = NULL;
    unsigned char md[EVP_MAX_MD_SIZE];
    int mdsize;
    BIGNUM *r0, *W, *X, *c, *test;
    BIGNUM *g = NULL, *q = NULL, *p = NULL;
    BN_MONT_CTX *mont = NULL;
    int i, k, n = 0, m = 0, qsize = N >> 3;
    int counter = 0;
    int r = 0;
    BN_CTX *ctx = NULL;
    EVP_MD_CTX *mctx = EVP_MD_CTX_new();
    unsigned int h = 2;

    if (mctx == NULL)
        goto err;

    /* make sure L > N, otherwise we'll get trapped in an infinite loop */
    if (L <= N) {
        DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
        goto err;
    }

    if (evpmd == NULL) {
        if (N == 160)
            evpmd = EVP_sha1();
        else if (N == 224)
            evpmd = EVP_sha224();
        else
            evpmd = EVP_sha256();
    }

    mdsize = EVP_MD_size(evpmd);
    /* If unverifiable g generation only don't need seed */
    if (!ret->p || !ret->q || idx >= 0) {
        if (seed_len == 0)
            seed_len = mdsize;

        seed = OPENSSL_malloc(seed_len);

        if (seed_out)
            seed_tmp = seed_out;
        else
            seed_tmp = OPENSSL_malloc(seed_len);

        if (seed == NULL || seed_tmp == NULL)
            goto err;

        if (seed_in)
            memcpy(seed, seed_in, seed_len);

    }

    if ((ctx = BN_CTX_new()) == NULL)
        goto err;

    if ((mont = BN_MONT_CTX_new()) == NULL)
        goto err;

    BN_CTX_start(ctx);
    r0 = BN_CTX_get(ctx);
    g = BN_CTX_get(ctx);
    W = BN_CTX_get(ctx);
    X = BN_CTX_get(ctx);
    c = BN_CTX_get(ctx);
    test = BN_CTX_get(ctx);
    if (test == NULL)
        goto err;

    /* if p, q already supplied generate g only */
    if (ret->p && ret->q) {
        p = ret->p;
        q = ret->q;
        if (idx >= 0)
            memcpy(seed_tmp, seed, seed_len);
        goto g_only;
    } else {
        p = BN_CTX_get(ctx);
        q = BN_CTX_get(ctx);
        if (q == NULL)
            goto err;
    }

    if (!BN_lshift(test, BN_value_one(), L - 1))
        goto err;
    for (;;) {
        for (;;) {              /* find q */
            unsigned char *pmd;
            /* step 1 */
            if (!BN_GENCB_call(cb, 0, m++))
                goto err;

            if (!seed_in) {
                if (RAND_bytes(seed, seed_len) <= 0)
                    goto err;
            }
            /* step 2 */
            if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
                goto err;
            /* Take least significant bits of md */
            if (mdsize > qsize)
                pmd = md + mdsize - qsize;
            else
                pmd = md;

            if (mdsize < qsize)
                memset(md + mdsize, 0, qsize - mdsize);

            /* step 3 */
            pmd[0] |= 0x80;
            pmd[qsize - 1] |= 0x01;
            if (!BN_bin2bn(pmd, qsize, q))
                goto err;

            /* step 4 */
            r = BN_check_prime(q, ctx, cb);
            if (r > 0)
                break;
            if (r != 0)
                goto err;
            /* Provided seed didn't produce a prime: error */
            if (seed_in) {
                ok = 0;
                DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
                goto err;
            }

            /* do a callback call */
            /* step 5 */
        }
        /* Copy seed to seed_out before we mess with it */
        if (seed_out)
            memcpy(seed_out, seed, seed_len);

        if (!BN_GENCB_call(cb, 2, 0))
            goto err;
        if (!BN_GENCB_call(cb, 3, 0))
            goto err;

        /* step 6 */
        counter = 0;
        /* "offset = 1" */

        n = (L - 1) / (mdsize << 3);

        for (;;) {
            if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
                goto err;

            /* step 7 */
            BN_zero(W);
            /* now 'buf' contains "SEED + offset - 1" */
            for (k = 0; k <= n; k++) {
                /*
                 * obtain "SEED + offset + k" by incrementing:
                 */
                for (i = seed_len - 1; i >= 0; i--) {
                    seed[i]++;
                    if (seed[i] != 0)
                        break;
                }

                if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
                    goto err;

                /* step 8 */
                if (!BN_bin2bn(md, mdsize, r0))
                    goto err;
                if (!BN_lshift(r0, r0, (mdsize << 3) * k))
                    goto err;
                if (!BN_add(W, W, r0))
                    goto err;
            }

            /* more of step 8 */
            if (!BN_mask_bits(W, L - 1))
                goto err;
            if (!BN_copy(X, W))
                goto err;
            if (!BN_add(X, X, test))
                goto err;

            /* step 9 */
            if (!BN_lshift1(r0, q))
                goto err;
            if (!BN_mod(c, X, r0, ctx))
                goto err;
            if (!BN_sub(r0, c, BN_value_one()))
                goto err;
            if (!BN_sub(p, X, r0))
                goto err;

            /* step 10 */
            if (BN_cmp(p, test) >= 0) {
                /* step 11 */
                r = BN_check_prime(p, ctx, cb);
                if (r > 0)
                    goto end;   /* found it */
                if (r != 0)
                    goto err;
            }

            /* step 13 */
            counter++;
            /* "offset = offset + n + 1" */

            /* step 14 */
            if (counter >= (int)(4 * L))
                break;
        }
        if (seed_in) {
            ok = 0;
            DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
            goto err;
        }
    }
 end:
    if (!BN_GENCB_call(cb, 2, 1))
        goto err;

 g_only:

    /* We now need to generate g */
    /* Set r0=(p-1)/q */
    if (!BN_sub(test, p, BN_value_one()))
        goto err;
    if (!BN_div(r0, NULL, test, q, ctx))
        goto err;

    if (idx < 0) {
        if (!BN_set_word(test, h))
            goto err;
    } else
        h = 1;
    if (!BN_MONT_CTX_set(mont, p, ctx))
        goto err;

    for (;;) {
        static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
        if (idx >= 0) {
            md[0] = idx & 0xff;
            md[1] = (h >> 8) & 0xff;
            md[2] = h & 0xff;
            if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
                goto err;
            if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
                goto err;
            if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
                goto err;
            if (!EVP_DigestUpdate(mctx, md, 3))
                goto err;
            if (!EVP_DigestFinal_ex(mctx, md, NULL))
                goto err;
            if (!BN_bin2bn(md, mdsize, test))
                goto err;
        }
        /* g=test^r0%p */
        if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
            goto err;
        if (!BN_is_one(g))
            break;
        if (idx < 0 && !BN_add(test, test, BN_value_one()))
            goto err;
        h++;
        if (idx >= 0 && h > 0xffff)
            goto err;
    }

    if (!BN_GENCB_call(cb, 3, 1))
        goto err;

    ok = 1;
 err:
    if (ok == 1) {
        if (p != ret->p) {
            BN_free(ret->p);
            ret->p = BN_dup(p);
        }
        if (q != ret->q) {
            BN_free(ret->q);
            ret->q = BN_dup(q);
        }
        BN_free(ret->g);
        ret->g = BN_dup(g);
        if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
            ok = -1;
            goto err;
        }
        ret->dirty_cnt++;
        if (counter_ret != NULL)
            *counter_ret = counter;
        if (h_ret != NULL)
            *h_ret = h;
    }
    OPENSSL_free(seed);
    if (seed_out != seed_tmp)
        OPENSSL_free(seed_tmp);
    BN_CTX_end(ctx);
    BN_CTX_free(ctx);
    BN_MONT_CTX_free(mont);
    EVP_MD_CTX_free(mctx);
    return ok;
}
Commit	Line	Data
d2e9e320	1	/*
28428130	2	* Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
0f113f3e	3	*
3cdbea65	4	* Licensed under the Apache License 2.0 (the "License"). You may not use
d2e9e320 RS	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
d02b48c6 RE	8	*/
d02b48c6 RE	9
0f113f3e MC	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	*/
474e469b	15	#define xxxHASH EVP_sha1()
d02b48c6	16
3c27208f	17	#include <openssl/opensslconf.h>
474e469b	18	#include <stdio.h>
b39fc560	19	#include "internal/cryptlib.h"
474e469b RS	20	#include <openssl/evp.h>
	21	#include <openssl/bn.h>
	22	#include <openssl/rand.h>
	23	#include <openssl/sha.h>
706457b7	24	#include "dsa_local.h"
0e4aa0d2	25
e9224c71	26	int DSA_generate_parameters_ex(DSA *ret, int bits,
0f113f3e MC	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 {
070c2332 AG	35	const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1();
070c2332 AG	36	size_t qbits = EVP_MD_size(evpmd) * 8;
0f113f3e MC	37
	38	return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
	39	seed_in, seed_len, NULL, counter_ret,
	40	h_ret, cb);
	41	}
	42	}
0e4aa0d2	43
357d5de5	44	int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
0f113f3e MC	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
d54897cf MC	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	}
0f113f3e MC	77
	78	if (bits < 512)
	79	bits = 512;
	80
	81	bits = (bits + 63) / 64 * 64;
	82
f00a10b8	83	if (seed_in != NULL) {
af547412 SAS	84	if (seed_len < (size_t)qsize) {
af547412 SAS	85	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL);
f00a10b8	86	return 0;
af547412	87	}
f00a10b8	88	if (seed_len > (size_t)qsize) {
36ac7bc8	89	/* Only consume as much seed as is expected. */
f00a10b8 IP	90	seed_len = qsize;
f00a10b8 IP	91	}
0f113f3e	92	memcpy(seed, seed_in, seed_len);
f00a10b8	93	}
0f113f3e	94
3f6c7691 AG	95	if ((mont = BN_MONT_CTX_new()) == NULL)
	96	goto err;
	97
0f113f3e MC	98	if ((ctx = BN_CTX_new()) == NULL)
	99	goto err;
	100
99c20333 PC	101	BN_CTX_start(ctx);
99c20333 PC	102
0f113f3e MC	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
1ff7425d MC	112	if (test == NULL)
	113	goto err;
	114
0f113f3e MC	115	if (!BN_lshift(test, BN_value_one(), bits - 1))
	116	goto err;
	117
	118	for (;;) {
	119	for (;;) { /* find q */
36ac7bc8	120	int use_random_seed = (seed_in == NULL);
0f113f3e MC	121
	122	/* step 1 */
	123	if (!BN_GENCB_call(cb, 0, m++))
	124	goto err;
	125
36ac7bc8	126	if (use_random_seed) {
266483d2	127	if (RAND_bytes(seed, qsize) <= 0)
0f113f3e	128	goto err;
0f113f3e	129	} else {
f00a10b8 IP	130	/* If we come back through, use random seed next time. */
f00a10b8 IP	131	seed_in = NULL;
0f113f3e MC	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 */
42619397	157	r = BN_check_prime(q, ctx, cb);
0f113f3e MC	158	if (r > 0)
	159	break;
	160	if (r != 0)
	161	goto err;
	162
	163	/* do a callback call */
	164	/* step 5 */
	165	}
	166
	167	if (!BN_GENCB_call(cb, 2, 0))
	168	goto err;
	169	if (!BN_GENCB_call(cb, 3, 0))
	170	goto err;
	171
	172	/* step 6 */
	173	counter = 0;
	174	/* "offset = 2" */
	175
	176	n = (bits - 1) / 160;
	177
	178	for (;;) {
	179	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
	180	goto err;
	181
	182	/* step 7 */
	183	BN_zero(W);
	184	/* now 'buf' contains "SEED + offset - 1" */
	185	for (k = 0; k <= n; k++) {
	186	/*
	187	* obtain "SEED + offset + k" by incrementing:
	188	*/
	189	for (i = qsize - 1; i >= 0; i--) {
	190	buf[i]++;
	191	if (buf[i] != 0)
	192	break;
	193	}
	194
	195	if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
	196	goto err;
	197
	198	/* step 8 */
	199	if (!BN_bin2bn(md, qsize, r0))
	200	goto err;
	201	if (!BN_lshift(r0, r0, (qsize << 3) * k))
	202	goto err;
	203	if (!BN_add(W, W, r0))
	204	goto err;
	205	}
	206
	207	/* more of step 8 */
	208	if (!BN_mask_bits(W, bits - 1))
	209	goto err;
	210	if (!BN_copy(X, W))
	211	goto err;
	212	if (!BN_add(X, X, test))
	213	goto err;
	214
	215	/* step 9 */
	216	if (!BN_lshift1(r0, q))
	217	goto err;
	218	if (!BN_mod(c, X, r0, ctx))
	219	goto err;
	220	if (!BN_sub(r0, c, BN_value_one()))
	221	goto err;
222	if (!BN_sub(p, X, r0))
223	goto err;
224
225	/* step 10 */
226	if (BN_cmp(p, test) >= 0) {
227	/* step 11 */
42619397	228	r = BN_check_prime(p, ctx, cb);
0f113f3e MC	229	if (r > 0)
	230	goto end; /* found it */
	231	if (r != 0)
	232	goto err;
	233	}
	234
	235	/* step 13 */
	236	counter++;
	237	/* "offset = offset + n + 1" */
	238
	239	/* step 14 */
	240	if (counter >= 4096)
	241	break;
	242	}
	243	}
	244	end:
	245	if (!BN_GENCB_call(cb, 2, 1))
	246	goto err;
	247
	248	/* We now need to generate g */
	249	/* Set r0=(p-1)/q */
	250	if (!BN_sub(test, p, BN_value_one()))
	251	goto err;
	252	if (!BN_div(r0, NULL, test, q, ctx))
	253	goto err;
	254
	255	if (!BN_set_word(test, h))
	256	goto err;
	257	if (!BN_MONT_CTX_set(mont, p, ctx))
	258	goto err;
	259
	260	for (;;) {
	261	/* g=test^r0%p */
	262	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
	263	goto err;
	264	if (!BN_is_one(g))
	265	break;
	266	if (!BN_add(test, test, BN_value_one()))
	267	goto err;
	268	h++;
	269	}
	270
	271	if (!BN_GENCB_call(cb, 3, 1))
	272	goto err;
	273
	274	ok = 1;
	275	err:
	276	if (ok) {
23a1d5e9 RS	277	BN_free(ret->p);
	278	BN_free(ret->q);
	279	BN_free(ret->g);
0f113f3e MC	280	ret->p = BN_dup(p);
	281	ret->q = BN_dup(q);
	282	ret->g = BN_dup(g);
4889dadc	283	ret->dirty_cnt++;
0f113f3e MC	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	}
ce1415ed	295	BN_CTX_end(ctx);
23a1d5e9 RS	296	BN_CTX_free(ctx);
23a1d5e9 RS	297	BN_MONT_CTX_free(mont);
0f113f3e MC	298	return ok;
	299	}
	300
	301	/*
	302	* This is a parameter generation algorithm for the DSA2 algorithm as
3dd9b31d DSH	303	* described in FIPS 186-3.
	304	*/
	305
	306	int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
0f113f3e MC	307	const EVP_MD evpmd, const unsigned char seed_in,
	308	size_t seed_len, int idx, unsigned char *seed_out,
	309	int counter_ret, unsigned long h_ret,
	310	BN_GENCB *cb)
	311	{
	312	int ok = -1;
	313	unsigned char seed = NULL, seed_tmp = NULL;
	314	unsigned char md[EVP_MAX_MD_SIZE];
	315	int mdsize;
	316	BIGNUM r0, W, X, c, *test;
	317	BIGNUM g = NULL, q = NULL, *p = NULL;
	318	BN_MONT_CTX *mont = NULL;
	319	int i, k, n = 0, m = 0, qsize = N >> 3;
	320	int counter = 0;
	321	int r = 0;
	322	BN_CTX *ctx = NULL;
bfb0641f	323	EVP_MD_CTX *mctx = EVP_MD_CTX_new();
0f113f3e MC	324	unsigned int h = 2;
0f113f3e MC	325
6e59a892 RL	326	if (mctx == NULL)
6e59a892 RL	327	goto err;
0f113f3e	328
3afd38b2 VC	329	/* make sure L > N, otherwise we'll get trapped in an infinite loop */
	330	if (L <= N) {
	331	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
	332	goto err;
	333	}
	334
0f113f3e MC	335	if (evpmd == NULL) {
	336	if (N == 160)
	337	evpmd = EVP_sha1();
	338	else if (N == 224)
	339	evpmd = EVP_sha224();
	340	else
	341	evpmd = EVP_sha256();
	342	}
	343
6e59a892	344	mdsize = EVP_MD_size(evpmd);
0d4fb843	345	/* If unverifiable g generation only don't need seed */
0f113f3e MC	346	if (!ret->p \|\| !ret->q \|\| idx >= 0) {
	347	if (seed_len == 0)
	348	seed_len = mdsize;
	349
	350	seed = OPENSSL_malloc(seed_len);
	351
	352	if (seed_out)
	353	seed_tmp = seed_out;
	354	else
	355	seed_tmp = OPENSSL_malloc(seed_len);
	356
90945fa3	357	if (seed == NULL \|\| seed_tmp == NULL)
0f113f3e MC	358	goto err;
	359
	360	if (seed_in)
	361	memcpy(seed, seed_in, seed_len);
	362
	363	}
	364
	365	if ((ctx = BN_CTX_new()) == NULL)
	366	goto err;
	367
	368	if ((mont = BN_MONT_CTX_new()) == NULL)
	369	goto err;
	370
	371	BN_CTX_start(ctx);
	372	r0 = BN_CTX_get(ctx);
	373	g = BN_CTX_get(ctx);
	374	W = BN_CTX_get(ctx);
	375	X = BN_CTX_get(ctx);
	376	c = BN_CTX_get(ctx);
	377	test = BN_CTX_get(ctx);
f08e8034 MC	378	if (test == NULL)
f08e8034 MC	379	goto err;
0f113f3e MC	380
	381	/* if p, q already supplied generate g only */
	382	if (ret->p && ret->q) {
	383	p = ret->p;
	384	q = ret->q;
	385	if (idx >= 0)
	386	memcpy(seed_tmp, seed, seed_len);
	387	goto g_only;
	388	} else {
	389	p = BN_CTX_get(ctx);
	390	q = BN_CTX_get(ctx);
fb0a6412 BE	391	if (q == NULL)
fb0a6412 BE	392	goto err;
0f113f3e MC	393	}
	394
	395	if (!BN_lshift(test, BN_value_one(), L - 1))
	396	goto err;
	397	for (;;) {
	398	for (;;) { /* find q */
	399	unsigned char *pmd;
	400	/* step 1 */
	401	if (!BN_GENCB_call(cb, 0, m++))
	402	goto err;
	403
	404	if (!seed_in) {
266483d2	405	if (RAND_bytes(seed, seed_len) <= 0)
0f113f3e MC	406	goto err;
	407	}
	408	/* step 2 */
	409	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
	410	goto err;
	411	/* Take least significant bits of md */
	412	if (mdsize > qsize)
	413	pmd = md + mdsize - qsize;
	414	else
	415	pmd = md;
	416
	417	if (mdsize < qsize)
	418	memset(md + mdsize, 0, qsize - mdsize);
	419
	420	/* step 3 */
	421	pmd[0] \|= 0x80;
	422	pmd[qsize - 1] \|= 0x01;
	423	if (!BN_bin2bn(pmd, qsize, q))
	424	goto err;
	425
	426	/* step 4 */
42619397	427	r = BN_check_prime(q, ctx, cb);
0f113f3e MC	428	if (r > 0)
	429	break;
	430	if (r != 0)
	431	goto err;
	432	/* Provided seed didn't produce a prime: error */
	433	if (seed_in) {
	434	ok = 0;
	435	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
	436	goto err;
	437	}
	438
	439	/* do a callback call */
	440	/* step 5 */
	441	}
	442	/* Copy seed to seed_out before we mess with it */
	443	if (seed_out)
	444	memcpy(seed_out, seed, seed_len);
	445
	446	if (!BN_GENCB_call(cb, 2, 0))
	447	goto err;
	448	if (!BN_GENCB_call(cb, 3, 0))
	449	goto err;
	450
	451	/* step 6 */
	452	counter = 0;
	453	/* "offset = 1" */
	454
	455	n = (L - 1) / (mdsize << 3);
	456
	457	for (;;) {
	458	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
	459	goto err;
	460
	461	/* step 7 */
	462	BN_zero(W);
	463	/* now 'buf' contains "SEED + offset - 1" */
	464	for (k = 0; k <= n; k++) {
	465	/*
	466	* obtain "SEED + offset + k" by incrementing:
	467	*/
	468	for (i = seed_len - 1; i >= 0; i--) {
	469	seed[i]++;
	470	if (seed[i] != 0)
	471	break;
	472	}
	473
	474	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
	475	goto err;
	476
	477	/* step 8 */
	478	if (!BN_bin2bn(md, mdsize, r0))
	479	goto err;
	480	if (!BN_lshift(r0, r0, (mdsize << 3) * k))
	481	goto err;
	482	if (!BN_add(W, W, r0))
	483	goto err;
	484	}
	485
	486	/* more of step 8 */
	487	if (!BN_mask_bits(W, L - 1))
	488	goto err;
	489	if (!BN_copy(X, W))
	490	goto err;
	491	if (!BN_add(X, X, test))
492	goto err;
493
494	/* step 9 */
495	if (!BN_lshift1(r0, q))
496	goto err;
497	if (!BN_mod(c, X, r0, ctx))
498	goto err;
499	if (!BN_sub(r0, c, BN_value_one()))
500	goto err;
501	if (!BN_sub(p, X, r0))
502	goto err;
503
504	/* step 10 */
505	if (BN_cmp(p, test) >= 0) {
506	/* step 11 */
42619397	507	r = BN_check_prime(p, ctx, cb);
0f113f3e MC	508	if (r > 0)
	509	goto end; /* found it */
	510	if (r != 0)
	511	goto err;
	512	}
	513
	514	/* step 13 */
	515	counter++;
	516	/* "offset = offset + n + 1" */
	517
	518	/* step 14 */
	519	if (counter >= (int)(4 * L))
	520	break;
	521	}
	522	if (seed_in) {
	523	ok = 0;
	524	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
	525	goto err;
	526	}
	527	}
	528	end:
	529	if (!BN_GENCB_call(cb, 2, 1))
	530	goto err;
	531
	532	g_only:
	533
	534	/* We now need to generate g */
	535	/* Set r0=(p-1)/q */
	536	if (!BN_sub(test, p, BN_value_one()))
	537	goto err;
	538	if (!BN_div(r0, NULL, test, q, ctx))
	539	goto err;
	540
	541	if (idx < 0) {
	542	if (!BN_set_word(test, h))
	543	goto err;
	544	} else
	545	h = 1;
	546	if (!BN_MONT_CTX_set(mont, p, ctx))
	547	goto err;
	548
	549	for (;;) {
	550	static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
	551	if (idx >= 0) {
	552	md[0] = idx & 0xff;
	553	md[1] = (h >> 8) & 0xff;
	554	md[2] = h & 0xff;
6e59a892	555	if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
0f113f3e	556	goto err;
6e59a892	557	if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
0f113f3e	558	goto err;
6e59a892	559	if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
0f113f3e	560	goto err;
6e59a892	561	if (!EVP_DigestUpdate(mctx, md, 3))
0f113f3e	562	goto err;
6e59a892	563	if (!EVP_DigestFinal_ex(mctx, md, NULL))
0f113f3e MC	564	goto err;
	565	if (!BN_bin2bn(md, mdsize, test))
	566	goto err;
	567	}
	568	/* g=test^r0%p */
	569	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
	570	goto err;
	571	if (!BN_is_one(g))
	572	break;
	573	if (idx < 0 && !BN_add(test, test, BN_value_one()))
	574	goto err;
	575	h++;
	576	if (idx >= 0 && h > 0xffff)
	577	goto err;
	578	}
	579
	580	if (!BN_GENCB_call(cb, 3, 1))
	581	goto err;
	582
	583	ok = 1;
	584	err:
	585	if (ok == 1) {
	586	if (p != ret->p) {
23a1d5e9	587	BN_free(ret->p);
0f113f3e MC	588	ret->p = BN_dup(p);
	589	}
	590	if (q != ret->q) {
23a1d5e9	591	BN_free(ret->q);
0f113f3e MC	592	ret->q = BN_dup(q);
0f113f3e MC	593	}
23a1d5e9	594	BN_free(ret->g);
0f113f3e MC	595	ret->g = BN_dup(g);
	596	if (ret->p == NULL \|\| ret->q == NULL \|\| ret->g == NULL) {
	597	ok = -1;
	598	goto err;
	599	}
4889dadc	600	ret->dirty_cnt++;
0f113f3e MC	601	if (counter_ret != NULL)
	602	*counter_ret = counter;
	603	if (h_ret != NULL)
	604	*h_ret = h;
	605	}
b548a1f1	606	OPENSSL_free(seed);
0f113f3e MC	607	if (seed_out != seed_tmp)
0f113f3e MC	608	OPENSSL_free(seed_tmp);
ce1415ed	609	BN_CTX_end(ctx);
23a1d5e9 RS	610	BN_CTX_free(ctx);
23a1d5e9 RS	611	BN_MONT_CTX_free(mont);
bfb0641f	612	EVP_MD_CTX_free(mctx);
0f113f3e MC	613	return ok;
0f113f3e MC	614	}