[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_locl.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_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
                                        use_random_seed, 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_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, 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);
        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_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
                                        seed_in ? 1 : 0, 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_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, 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;
        }
        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>
474e469b	24	#include "dsa_locl.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 */
	157	r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
36ac7bc8	158	use_random_seed, cb);
0f113f3e MC	159	if (r > 0)
	160	break;
	161	if (r != 0)
	162	goto err;
	163
	164	/* do a callback call */
	165	/* step 5 */
	166	}
	167
	168	if (!BN_GENCB_call(cb, 2, 0))
	169	goto err;
	170	if (!BN_GENCB_call(cb, 3, 0))
	171	goto err;
	172
	173	/* step 6 */
	174	counter = 0;
	175	/* "offset = 2" */
	176
	177	n = (bits - 1) / 160;
	178
	179	for (;;) {
	180	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
	181	goto err;
	182
	183	/* step 7 */
	184	BN_zero(W);
	185	/* now 'buf' contains "SEED + offset - 1" */
	186	for (k = 0; k <= n; k++) {
	187	/*
	188	* obtain "SEED + offset + k" by incrementing:
	189	*/
	190	for (i = qsize - 1; i >= 0; i--) {
	191	buf[i]++;
	192	if (buf[i] != 0)
	193	break;
	194	}
	195
	196	if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
	197	goto err;
	198
	199	/* step 8 */
	200	if (!BN_bin2bn(md, qsize, r0))
	201	goto err;
	202	if (!BN_lshift(r0, r0, (qsize << 3) * k))
	203	goto err;
	204	if (!BN_add(W, W, r0))
	205	goto err;
	206	}
	207
	208	/* more of step 8 */
	209	if (!BN_mask_bits(W, bits - 1))
	210	goto err;
	211	if (!BN_copy(X, W))
	212	goto err;
	213	if (!BN_add(X, X, test))
	214	goto err;
	215
	216	/* step 9 */
	217	if (!BN_lshift1(r0, q))
	218	goto err;
	219	if (!BN_mod(c, X, r0, ctx))
	220	goto err;
	221	if (!BN_sub(r0, c, BN_value_one()))
	222	goto err;
223	if (!BN_sub(p, X, r0))
224	goto err;
225
226	/* step 10 */
227	if (BN_cmp(p, test) >= 0) {
228	/* step 11 */
229	r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
230	if (r > 0)
231	goto end; /* found it */
232	if (r != 0)
233	goto err;
234	}
235
236	/* step 13 */
237	counter++;
238	/* "offset = offset + n + 1" */
239
240	/* step 14 */
241	if (counter >= 4096)
242	break;
243	}
244	}
245	end:
246	if (!BN_GENCB_call(cb, 2, 1))
247	goto err;
248
249	/* We now need to generate g */
250	/* Set r0=(p-1)/q */
251	if (!BN_sub(test, p, BN_value_one()))
252	goto err;
253	if (!BN_div(r0, NULL, test, q, ctx))
254	goto err;
255
256	if (!BN_set_word(test, h))
257	goto err;
258	if (!BN_MONT_CTX_set(mont, p, ctx))
259	goto err;
260
261	for (;;) {
262	/* g=test^r0%p */
263	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
264	goto err;
265	if (!BN_is_one(g))
266	break;
267	if (!BN_add(test, test, BN_value_one()))
268	goto err;
269	h++;
270	}
271
272	if (!BN_GENCB_call(cb, 3, 1))
273	goto err;
274
275	ok = 1;
276	err:
277	if (ok) {
23a1d5e9 RS	278	BN_free(ret->p);
	279	BN_free(ret->q);
	280	BN_free(ret->g);
0f113f3e MC	281	ret->p = BN_dup(p);
	282	ret->q = BN_dup(q);
	283	ret->g = BN_dup(g);
	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 */
	427	r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
	428	seed_in ? 1 : 0, cb);
	429	if (r > 0)
	430	break;
	431	if (r != 0)
	432	goto err;
	433	/* Provided seed didn't produce a prime: error */
	434	if (seed_in) {
	435	ok = 0;
	436	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
	437	goto err;
	438	}
	439
	440	/* do a callback call */
	441	/* step 5 */
	442	}
	443	/* Copy seed to seed_out before we mess with it */
	444	if (seed_out)
	445	memcpy(seed_out, seed, seed_len);
	446
	447	if (!BN_GENCB_call(cb, 2, 0))
	448	goto err;
	449	if (!BN_GENCB_call(cb, 3, 0))
	450	goto err;
	451
	452	/* step 6 */
	453	counter = 0;
	454	/* "offset = 1" */
	455
	456	n = (L - 1) / (mdsize << 3);
	457
	458	for (;;) {
	459	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
	460	goto err;
	461
	462	/* step 7 */
	463	BN_zero(W);
	464	/* now 'buf' contains "SEED + offset - 1" */
	465	for (k = 0; k <= n; k++) {
	466	/*
	467	* obtain "SEED + offset + k" by incrementing:
	468	*/
	469	for (i = seed_len - 1; i >= 0; i--) {
470	seed[i]++;
471	if (seed[i] != 0)
472	break;
473	}
474
475	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
476	goto err;
477
478	/* step 8 */
479	if (!BN_bin2bn(md, mdsize, r0))
480	goto err;
481	if (!BN_lshift(r0, r0, (mdsize << 3) * k))
482	goto err;
483	if (!BN_add(W, W, r0))
484	goto err;
485	}
486
487	/* more of step 8 */
488	if (!BN_mask_bits(W, L - 1))
489	goto err;
490	if (!BN_copy(X, W))
491	goto err;
492	if (!BN_add(X, X, test))
493	goto err;
494
495	/* step 9 */
496	if (!BN_lshift1(r0, q))
497	goto err;
498	if (!BN_mod(c, X, r0, ctx))
499	goto err;
500	if (!BN_sub(r0, c, BN_value_one()))
501	goto err;
502	if (!BN_sub(p, X, r0))
503	goto err;
504
505	/* step 10 */
506	if (BN_cmp(p, test) >= 0) {
507	/* step 11 */
508	r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
509	if (r > 0)
510	goto end; /* found it */
511	if (r != 0)
512	goto err;
513	}
514
515	/* step 13 */
516	counter++;
517	/* "offset = offset + n + 1" */
518
519	/* step 14 */
520	if (counter >= (int)(4 * L))
521	break;
522	}
523	if (seed_in) {
524	ok = 0;
525	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
526	goto err;
527	}
528	}
529	end:
530	if (!BN_GENCB_call(cb, 2, 1))
531	goto err;
532
533	g_only:
534
535	/* We now need to generate g */
536	/* Set r0=(p-1)/q */
537	if (!BN_sub(test, p, BN_value_one()))
538	goto err;
539	if (!BN_div(r0, NULL, test, q, ctx))
540	goto err;
541
542	if (idx < 0) {
543	if (!BN_set_word(test, h))
544	goto err;
545	} else
546	h = 1;
547	if (!BN_MONT_CTX_set(mont, p, ctx))
548	goto err;
549
550	for (;;) {
551	static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
552	if (idx >= 0) {
553	md[0] = idx & 0xff;
554	md[1] = (h >> 8) & 0xff;
555	md[2] = h & 0xff;
6e59a892	556	if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
0f113f3e	557	goto err;
6e59a892	558	if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
0f113f3e	559	goto err;
6e59a892	560	if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
0f113f3e	561	goto err;
6e59a892	562	if (!EVP_DigestUpdate(mctx, md, 3))
0f113f3e	563	goto err;
6e59a892	564	if (!EVP_DigestFinal_ex(mctx, md, NULL))
0f113f3e MC	565	goto err;
	566	if (!BN_bin2bn(md, mdsize, test))
	567	goto err;
	568	}
	569	/* g=test^r0%p */
	570	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
	571	goto err;
	572	if (!BN_is_one(g))
	573	break;
	574	if (idx < 0 && !BN_add(test, test, BN_value_one()))
	575	goto err;
	576	h++;
	577	if (idx >= 0 && h > 0xffff)
	578	goto err;
	579	}
	580
	581	if (!BN_GENCB_call(cb, 3, 1))
	582	goto err;
	583
	584	ok = 1;
	585	err:
	586	if (ok == 1) {
	587	if (p != ret->p) {
23a1d5e9	588	BN_free(ret->p);
0f113f3e MC	589	ret->p = BN_dup(p);
	590	}
	591	if (q != ret->q) {
23a1d5e9	592	BN_free(ret->q);
0f113f3e MC	593	ret->q = BN_dup(q);
0f113f3e MC	594	}
23a1d5e9	595	BN_free(ret->g);
0f113f3e MC	596	ret->g = BN_dup(g);
	597	if (ret->p == NULL \|\| ret->q == NULL \|\| ret->g == NULL) {
	598	ok = -1;
	599	goto err;
	600	}
	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	}