[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);
    }
    if (ctx)
        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);
    if (ctx)
        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	}
23a1d5e9	295	if (ctx)
0f113f3e	296	BN_CTX_end(ctx);
23a1d5e9 RS	297	BN_CTX_free(ctx);
23a1d5e9 RS	298	BN_MONT_CTX_free(mont);
0f113f3e MC	299	return ok;
	300	}
	301
	302	/*
	303	* This is a parameter generation algorithm for the DSA2 algorithm as
3dd9b31d DSH	304	* described in FIPS 186-3.
	305	*/
	306
	307	int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
0f113f3e MC	308	const EVP_MD evpmd, const unsigned char seed_in,
	309	size_t seed_len, int idx, unsigned char *seed_out,
	310	int counter_ret, unsigned long h_ret,
	311	BN_GENCB *cb)
	312	{
	313	int ok = -1;
	314	unsigned char seed = NULL, seed_tmp = NULL;
	315	unsigned char md[EVP_MAX_MD_SIZE];
	316	int mdsize;
	317	BIGNUM r0, W, X, c, *test;
	318	BIGNUM g = NULL, q = NULL, *p = NULL;
	319	BN_MONT_CTX *mont = NULL;
	320	int i, k, n = 0, m = 0, qsize = N >> 3;
	321	int counter = 0;
	322	int r = 0;
	323	BN_CTX *ctx = NULL;
bfb0641f	324	EVP_MD_CTX *mctx = EVP_MD_CTX_new();
0f113f3e MC	325	unsigned int h = 2;
0f113f3e MC	326
6e59a892 RL	327	if (mctx == NULL)
6e59a892 RL	328	goto err;
0f113f3e	329
3afd38b2 VC	330	/* make sure L > N, otherwise we'll get trapped in an infinite loop */
	331	if (L <= N) {
	332	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
	333	goto err;
	334	}
	335
0f113f3e MC	336	if (evpmd == NULL) {
	337	if (N == 160)
	338	evpmd = EVP_sha1();
	339	else if (N == 224)
	340	evpmd = EVP_sha224();
	341	else
	342	evpmd = EVP_sha256();
	343	}
	344
6e59a892	345	mdsize = EVP_MD_size(evpmd);
0d4fb843	346	/* If unverifiable g generation only don't need seed */
0f113f3e MC	347	if (!ret->p \|\| !ret->q \|\| idx >= 0) {
	348	if (seed_len == 0)
	349	seed_len = mdsize;
	350
	351	seed = OPENSSL_malloc(seed_len);
	352
	353	if (seed_out)
	354	seed_tmp = seed_out;
	355	else
	356	seed_tmp = OPENSSL_malloc(seed_len);
	357
90945fa3	358	if (seed == NULL \|\| seed_tmp == NULL)
0f113f3e MC	359	goto err;
	360
	361	if (seed_in)
	362	memcpy(seed, seed_in, seed_len);
	363
	364	}
	365
	366	if ((ctx = BN_CTX_new()) == NULL)
	367	goto err;
	368
	369	if ((mont = BN_MONT_CTX_new()) == NULL)
	370	goto err;
	371
	372	BN_CTX_start(ctx);
	373	r0 = BN_CTX_get(ctx);
	374	g = BN_CTX_get(ctx);
	375	W = BN_CTX_get(ctx);
	376	X = BN_CTX_get(ctx);
	377	c = BN_CTX_get(ctx);
	378	test = BN_CTX_get(ctx);
f08e8034 MC	379	if (test == NULL)
f08e8034 MC	380	goto err;
0f113f3e MC	381
	382	/* if p, q already supplied generate g only */
	383	if (ret->p && ret->q) {
	384	p = ret->p;
	385	q = ret->q;
	386	if (idx >= 0)
	387	memcpy(seed_tmp, seed, seed_len);
	388	goto g_only;
	389	} else {
	390	p = BN_CTX_get(ctx);
	391	q = BN_CTX_get(ctx);
fb0a6412 BE	392	if (q == NULL)
fb0a6412 BE	393	goto err;
0f113f3e MC	394	}
	395
	396	if (!BN_lshift(test, BN_value_one(), L - 1))
	397	goto err;
	398	for (;;) {
	399	for (;;) { /* find q */
	400	unsigned char *pmd;
	401	/* step 1 */
	402	if (!BN_GENCB_call(cb, 0, m++))
	403	goto err;
	404
	405	if (!seed_in) {
266483d2	406	if (RAND_bytes(seed, seed_len) <= 0)
0f113f3e MC	407	goto err;
	408	}
	409	/* step 2 */
	410	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
	411	goto err;
	412	/* Take least significant bits of md */
	413	if (mdsize > qsize)
	414	pmd = md + mdsize - qsize;
	415	else
	416	pmd = md;
	417
	418	if (mdsize < qsize)
	419	memset(md + mdsize, 0, qsize - mdsize);
	420
	421	/* step 3 */
	422	pmd[0] \|= 0x80;
	423	pmd[qsize - 1] \|= 0x01;
	424	if (!BN_bin2bn(pmd, qsize, q))
	425	goto err;
	426
	427	/* step 4 */
	428	r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
	429	seed_in ? 1 : 0, cb);
	430	if (r > 0)
	431	break;
	432	if (r != 0)
	433	goto err;
	434	/* Provided seed didn't produce a prime: error */
	435	if (seed_in) {
	436	ok = 0;
	437	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
	438	goto err;
	439	}
	440
	441	/* do a callback call */
	442	/* step 5 */
	443	}
	444	/* Copy seed to seed_out before we mess with it */
	445	if (seed_out)
	446	memcpy(seed_out, seed, seed_len);
	447
	448	if (!BN_GENCB_call(cb, 2, 0))
	449	goto err;
	450	if (!BN_GENCB_call(cb, 3, 0))
	451	goto err;
	452
	453	/* step 6 */
	454	counter = 0;
	455	/* "offset = 1" */
	456
	457	n = (L - 1) / (mdsize << 3);
	458
	459	for (;;) {
	460	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
	461	goto err;
	462
	463	/* step 7 */
	464	BN_zero(W);
	465	/* now 'buf' contains "SEED + offset - 1" */
	466	for (k = 0; k <= n; k++) {
	467	/*
	468	* obtain "SEED + offset + k" by incrementing:
	469	*/
	470	for (i = seed_len - 1; i >= 0; i--) {
471	seed[i]++;
472	if (seed[i] != 0)
473	break;
474	}
475
476	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
477	goto err;
478
479	/* step 8 */
480	if (!BN_bin2bn(md, mdsize, r0))
481	goto err;
482	if (!BN_lshift(r0, r0, (mdsize << 3) * k))
483	goto err;
484	if (!BN_add(W, W, r0))
485	goto err;
486	}
487
488	/* more of step 8 */
489	if (!BN_mask_bits(W, L - 1))
490	goto err;
491	if (!BN_copy(X, W))
492	goto err;
493	if (!BN_add(X, X, test))
494	goto err;
495
496	/* step 9 */
497	if (!BN_lshift1(r0, q))
498	goto err;
499	if (!BN_mod(c, X, r0, ctx))
500	goto err;
501	if (!BN_sub(r0, c, BN_value_one()))
502	goto err;
503	if (!BN_sub(p, X, r0))
504	goto err;
505
506	/* step 10 */
507	if (BN_cmp(p, test) >= 0) {
508	/* step 11 */
509	r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
510	if (r > 0)
511	goto end; /* found it */
512	if (r != 0)
513	goto err;
514	}
515
516	/* step 13 */
517	counter++;
518	/* "offset = offset + n + 1" */
519
520	/* step 14 */
521	if (counter >= (int)(4 * L))
522	break;
523	}
524	if (seed_in) {
525	ok = 0;
526	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
527	goto err;
528	}
529	}
530	end:
531	if (!BN_GENCB_call(cb, 2, 1))
532	goto err;
533
534	g_only:
535
536	/* We now need to generate g */
537	/* Set r0=(p-1)/q */
538	if (!BN_sub(test, p, BN_value_one()))
539	goto err;
540	if (!BN_div(r0, NULL, test, q, ctx))
541	goto err;
542
543	if (idx < 0) {
544	if (!BN_set_word(test, h))
545	goto err;
546	} else
547	h = 1;
548	if (!BN_MONT_CTX_set(mont, p, ctx))
549	goto err;
550
551	for (;;) {
552	static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
553	if (idx >= 0) {
554	md[0] = idx & 0xff;
555	md[1] = (h >> 8) & 0xff;
556	md[2] = h & 0xff;
6e59a892	557	if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
0f113f3e	558	goto err;
6e59a892	559	if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
0f113f3e	560	goto err;
6e59a892	561	if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
0f113f3e	562	goto err;
6e59a892	563	if (!EVP_DigestUpdate(mctx, md, 3))
0f113f3e	564	goto err;
6e59a892	565	if (!EVP_DigestFinal_ex(mctx, md, NULL))
0f113f3e MC	566	goto err;
	567	if (!BN_bin2bn(md, mdsize, test))
	568	goto err;
	569	}
	570	/* g=test^r0%p */
	571	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
	572	goto err;
	573	if (!BN_is_one(g))
	574	break;
	575	if (idx < 0 && !BN_add(test, test, BN_value_one()))
	576	goto err;
	577	h++;
	578	if (idx >= 0 && h > 0xffff)
	579	goto err;
	580	}
	581
	582	if (!BN_GENCB_call(cb, 3, 1))
	583	goto err;
	584
	585	ok = 1;
	586	err:
	587	if (ok == 1) {
	588	if (p != ret->p) {
23a1d5e9	589	BN_free(ret->p);
0f113f3e MC	590	ret->p = BN_dup(p);
	591	}
	592	if (q != ret->q) {
23a1d5e9	593	BN_free(ret->q);
0f113f3e MC	594	ret->q = BN_dup(q);
0f113f3e MC	595	}
23a1d5e9	596	BN_free(ret->g);
0f113f3e MC	597	ret->g = BN_dup(g);
	598	if (ret->p == NULL \|\| ret->q == NULL \|\| ret->g == NULL) {
	599	ok = -1;
	600	goto err;
	601	}
	602	if (counter_ret != NULL)
	603	*counter_ret = counter;
	604	if (h_ret != NULL)
	605	*h_ret = h;
	606	}
b548a1f1	607	OPENSSL_free(seed);
0f113f3e MC	608	if (seed_out != seed_tmp)
0f113f3e MC	609	OPENSSL_free(seed_tmp);
23a1d5e9	610	if (ctx)
0f113f3e	611	BN_CTX_end(ctx);
23a1d5e9 RS	612	BN_CTX_free(ctx);
23a1d5e9 RS	613	BN_MONT_CTX_free(mont);
bfb0641f	614	EVP_MD_CTX_free(mctx);
0f113f3e MC	615	return ok;
0f113f3e MC	616	}