Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libcrypto/bn/bn_prime.c	Lines:	158	185	85.4 %
Date:	2017-11-07	Branches:	174	265	65.7 %


/* $OpenBSD: bn_prime.c,v 1.18 2017/01/29 17:49:22 beck Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 *
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 *
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 *
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */
/* ====================================================================
 * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    openssl-core@openssl.org.
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 *
 * This product includes cryptographic software written by Eric Young
 * (eay@cryptsoft.com).  This product includes software written by Tim
 * Hudson (tjh@cryptsoft.com).
 *
 */

#include <stdio.h>
#include <time.h>

#include <openssl/err.h>

#include "bn_lcl.h"

/* NB: these functions have been "upgraded", the deprecated versions (which are
 * compatibility wrappers using these functions) are in bn_depr.c.
 * - Geoff
 */

/* The quick sieve algorithm approach to weeding out primes is
 * Philip Zimmermann's, as implemented in PGP.  I have had a read of
 * his comments and implemented my own version.
 */
#include "bn_prime.h"

static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
    const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
static int probable_prime(BIGNUM *rnd, int bits);
static int probable_prime_dh(BIGNUM *rnd, int bits,
    const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
    const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);

int
BN_GENCB_call(BN_GENCB *cb, int a, int b)
{
	/* No callback means continue */
	if (!cb)
		return 1;
	switch (cb->ver) {
	case 1:
		/* Deprecated-style callbacks */
		if (!cb->cb.cb_1)
			return 1;
		cb->cb.cb_1(a, b, cb->arg);
		return 1;
	case 2:
		/* New-style callbacks */
		return cb->cb.cb_2(a, b, cb);
	default:
		break;
	}
	/* Unrecognised callback type */
	return 0;
}

int
BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
    const BIGNUM *rem, BN_GENCB *cb)
{
	BIGNUM *t;
	int found = 0;
	int i, j, c1 = 0;
	BN_CTX *ctx;
	int checks;

	if (bits < 2 || (bits == 2 && safe)) {
		/*
		 * There are no prime numbers smaller than 2, and the smallest
		 * safe prime (7) spans three bits.
		 */
		BNerror(BN_R_BITS_TOO_SMALL);
		return 0;
	}

	ctx = BN_CTX_new();
	if (ctx == NULL)
		goto err;
	BN_CTX_start(ctx);
	if ((t = BN_CTX_get(ctx)) == NULL)
		goto err;

	checks = BN_prime_checks_for_size(bits);

loop:
	/* make a random number and set the top and bottom bits */
	if (add == NULL) {
		if (!probable_prime(ret, bits))
			goto err;
	} else {
		if (safe) {
			if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
				goto err;
		} else {
			if (!probable_prime_dh(ret, bits, add, rem, ctx))
				goto err;
		}
	}
	/* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
	if (!BN_GENCB_call(cb, 0, c1++))
		/* aborted */
		goto err;

	if (!safe) {
		i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
		if (i == -1)
			goto err;
		if (i == 0)
			goto loop;
	} else {
		/* for "safe prime" generation,
		 * check that (p-1)/2 is prime.
		 * Since a prime is odd, We just
		 * need to divide by 2 */
		if (!BN_rshift1(t, ret))
			goto err;

		for (i = 0; i < checks; i++) {
			j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
			if (j == -1)
				goto err;
			if (j == 0)
				goto loop;

			j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
			if (j == -1)
				goto err;
			if (j == 0)
				goto loop;

			if (!BN_GENCB_call(cb, 2, c1 - 1))
				goto err;
			/* We have a safe prime test pass */
		}
	}
	/* we have a prime :-) */
	found = 1;

err:
	if (ctx != NULL) {
		BN_CTX_end(ctx);
		BN_CTX_free(ctx);
	}
	bn_check_top(ret);
	return found;
}

int
BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
{
	return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
}

int
BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
    int do_trial_division, BN_GENCB *cb)
{
	int i, j, ret = -1;
	int k;
	BN_CTX *ctx = NULL;
	BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
	BN_MONT_CTX *mont = NULL;
	const BIGNUM *A = NULL;

	if (BN_cmp(a, BN_value_one()) <= 0)
		return 0;

	if (checks == BN_prime_checks)
		checks = BN_prime_checks_for_size(BN_num_bits(a));

	/* first look for small factors */
	if (!BN_is_odd(a))
		/* a is even => a is prime if and only if a == 2 */
		return BN_is_word(a, 2);
	if (do_trial_division) {
		for (i = 1; i < NUMPRIMES; i++) {
			BN_ULONG mod = BN_mod_word(a, primes[i]);
			if (mod == (BN_ULONG)-1)
				goto err;
			if (mod == 0)
				return 0;
		}
		if (!BN_GENCB_call(cb, 1, -1))
			goto err;
	}

	if (ctx_passed != NULL)
		ctx = ctx_passed;
	else if ((ctx = BN_CTX_new()) == NULL)
		goto err;
	BN_CTX_start(ctx);

	/* A := abs(a) */
	if (a->neg) {
		BIGNUM *t;
		if ((t = BN_CTX_get(ctx)) == NULL)
			goto err;
		BN_copy(t, a);
		t->neg = 0;
		A = t;
	} else
		A = a;
	if ((A1 = BN_CTX_get(ctx)) == NULL)
		goto err;
	if ((A1_odd = BN_CTX_get(ctx)) == NULL)
		goto err;
	if ((check = BN_CTX_get(ctx)) == NULL)
		goto err;

	/* compute A1 := A - 1 */
	if (!BN_copy(A1, A))
		goto err;
	if (!BN_sub_word(A1, 1))
		goto err;
	if (BN_is_zero(A1)) {
		ret = 0;
		goto err;
	}

	/* write  A1  as  A1_odd * 2^k */
	k = 1;
	while (!BN_is_bit_set(A1, k))
		k++;
	if (!BN_rshift(A1_odd, A1, k))
		goto err;

	/* Montgomery setup for computations mod A */
	mont = BN_MONT_CTX_new();
	if (mont == NULL)
		goto err;
	if (!BN_MONT_CTX_set(mont, A, ctx))
		goto err;

	for (i = 0; i < checks; i++) {
		if (!BN_pseudo_rand_range(check, A1))
			goto err;
		if (!BN_add_word(check, 1))
			goto err;
		/* now 1 <= check < A */

		j = witness(check, A, A1, A1_odd, k, ctx, mont);
		if (j == -1)
			goto err;
		if (j) {
			ret = 0;
			goto err;
		}
		if (!BN_GENCB_call(cb, 1, i))
			goto err;
	}
	ret = 1;

err:
	if (ctx != NULL) {
		BN_CTX_end(ctx);
		if (ctx_passed == NULL)
			BN_CTX_free(ctx);
	}
	BN_MONT_CTX_free(mont);

	return (ret);
}

static int
witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd,
    int k, BN_CTX *ctx, BN_MONT_CTX *mont)
{
	if (!BN_mod_exp_mont_ct(w, w, a1_odd, a, ctx, mont))
		/* w := w^a1_odd mod a */
		return -1;
	if (BN_is_one(w))
		return 0; /* probably prime */
	if (BN_cmp(w, a1) == 0)
		return 0; /* w == -1 (mod a),  'a' is probably prime */
	while (--k) {
		if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
			return -1;
		if (BN_is_one(w))
			return 1; /* 'a' is composite, otherwise a previous 'w' would
			           * have been == -1 (mod 'a') */
		if (BN_cmp(w, a1) == 0)
			return 0; /* w == -1 (mod a), 'a' is probably prime */
	}
	/* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
	 * and it is neither -1 nor +1 -- so 'a' cannot be prime */
	bn_check_top(w);
	return 1;
}

static int
probable_prime(BIGNUM *rnd, int bits)
{
	int i;
	prime_t mods[NUMPRIMES];
	BN_ULONG delta, maxdelta;

again:
	if (!BN_rand(rnd, bits, 1, 1))
		return (0);
	/* we now have a random number 'rand' to test. */
	for (i = 1; i < NUMPRIMES; i++) {
		BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
		if (mod == (BN_ULONG)-1)
			return (0);
		mods[i] = (prime_t)mod;
	}
	maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
	delta = 0;
loop:
	for (i = 1; i < NUMPRIMES; i++) {
		/* check that rnd is not a prime and also
		 * that gcd(rnd-1,primes) == 1 (except for 2) */
		if (((mods[i] + delta) % primes[i]) <= 1) {
			delta += 2;
			if (delta > maxdelta)
				goto again;
			goto loop;
		}
	}
	if (!BN_add_word(rnd, delta))
		return (0);
	bn_check_top(rnd);
	return (1);
}

static int
probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem,
    BN_CTX *ctx)
{
	int i, ret = 0;
	BIGNUM *t1;

	BN_CTX_start(ctx);
	if ((t1 = BN_CTX_get(ctx)) == NULL)
		goto err;

	if (!BN_rand(rnd, bits, 0, 1))
		goto err;

	/* we need ((rnd-rem) % add) == 0 */

	if (!BN_mod_ct(t1, rnd, add, ctx))
		goto err;
	if (!BN_sub(rnd, rnd, t1))
		goto err;
	if (rem == NULL) {
		if (!BN_add_word(rnd, 1))
			goto err;
	} else {
		if (!BN_add(rnd, rnd, rem))
			goto err;
	}

	/* we now have a random number 'rand' to test. */

loop:
	for (i = 1; i < NUMPRIMES; i++) {
		/* check that rnd is a prime */
		BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
		if (mod == (BN_ULONG)-1)
			goto err;
		if (mod <= 1) {
			if (!BN_add(rnd, rnd, add))
				goto err;
			goto loop;
		}
	}
	ret = 1;

err:
	BN_CTX_end(ctx);
	bn_check_top(rnd);
	return (ret);
}

static int
probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
    const BIGNUM *rem, BN_CTX *ctx)
{
	int i, ret = 0;
	BIGNUM *t1, *qadd, *q;

	bits--;
	BN_CTX_start(ctx);
	if ((t1 = BN_CTX_get(ctx)) == NULL)
		goto err;
	if ((q = BN_CTX_get(ctx)) == NULL)
		goto err;
	if ((qadd = BN_CTX_get(ctx)) == NULL)
		goto err;

	if (!BN_rshift1(qadd, padd))
		goto err;

	if (!BN_rand(q, bits, 0, 1))
		goto err;

	/* we need ((rnd-rem) % add) == 0 */
	if (!BN_mod_ct(t1, q,qadd, ctx))
		goto err;
	if (!BN_sub(q, q, t1))
		goto err;
	if (rem == NULL) {
		if (!BN_add_word(q, 1))
			goto err;
	} else {
		if (!BN_rshift1(t1, rem))
			goto err;
		if (!BN_add(q, q, t1))
			goto err;
	}

	/* we now have a random number 'rand' to test. */
	if (!BN_lshift1(p, q))
		goto err;
	if (!BN_add_word(p, 1))
		goto err;

loop:
	for (i = 1; i < NUMPRIMES; i++) {
		/* check that p and q are prime */
		/* check that for p and q
		 * gcd(p-1,primes) == 1 (except for 2) */
		BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
		BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
		if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
			goto err;
		if (pmod == 0 || qmod == 0) {
			if (!BN_add(p, p, padd))
				goto err;
			if (!BN_add(q, q, qadd))
				goto err;
			goto loop;
		}
	}
	ret = 1;

err:
	BN_CTX_end(ctx);
	bn_check_top(p);
	return (ret);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: bn_prime.c,v 1.18 2017/01/29 17:49:22 beck Exp $ */
2			/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3			* All rights reserved.
4			*
5			* This package is an SSL implementation written
6			* by Eric Young (eay@cryptsoft.com).
7			* The implementation was written so as to conform with Netscapes SSL.
8			*
9			* This library is free for commercial and non-commercial use as long as
10			* the following conditions are aheared to. The following conditions
11			* apply to all code found in this distribution, be it the RC4, RSA,
12			* lhash, DES, etc., code; not just the SSL code. The SSL documentation
13			* included with this distribution is covered by the same copyright terms
14			* except that the holder is Tim Hudson (tjh@cryptsoft.com).
15			*
16			* Copyright remains Eric Young's, and as such any Copyright notices in
17			* the code are not to be removed.
18			* If this package is used in a product, Eric Young should be given attribution
19			* as the author of the parts of the library used.
20			* This can be in the form of a textual message at program startup or
21			* in documentation (online or textual) provided with the package.
22			*
23			* Redistribution and use in source and binary forms, with or without
24			* modification, are permitted provided that the following conditions
25			* are met:
26			* 1. Redistributions of source code must retain the copyright
27			* notice, this list of conditions and the following disclaimer.
28			* 2. Redistributions in binary form must reproduce the above copyright
29			* notice, this list of conditions and the following disclaimer in the
30			* documentation and/or other materials provided with the distribution.
31			* 3. All advertising materials mentioning features or use of this software
32			* must display the following acknowledgement:
33			* "This product includes cryptographic software written by
34			* Eric Young (eay@cryptsoft.com)"
35			* The word 'cryptographic' can be left out if the rouines from the library
36			* being used are not cryptographic related :-).
37			* 4. If you include any Windows specific code (or a derivative thereof) from
38			* the apps directory (application code) you must include an acknowledgement:
39			* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40			*
41			* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44			* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51			* SUCH DAMAGE.
52			*
53			* The licence and distribution terms for any publically available version or
54			* derivative of this code cannot be changed. i.e. this code cannot simply be
55			* copied and put under another distribution licence
56			* [including the GNU Public Licence.]
57			*/
58			/* ====================================================================
59			* Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60			*
61			* Redistribution and use in source and binary forms, with or without
62			* modification, are permitted provided that the following conditions
63			* are met:
64			*
65			* 1. Redistributions of source code must retain the above copyright
66			* notice, this list of conditions and the following disclaimer.
67			*
68			* 2. Redistributions in binary form must reproduce the above copyright
69			* notice, this list of conditions and the following disclaimer in
70			* the documentation and/or other materials provided with the
71			* distribution.
72			*
73			* 3. All advertising materials mentioning features or use of this
74			* software must display the following acknowledgment:
75			* "This product includes software developed by the OpenSSL Project
76			* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77			*
78			* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79			* endorse or promote products derived from this software without
80			* prior written permission. For written permission, please contact
81			* openssl-core@openssl.org.
82			*
83			* 5. Products derived from this software may not be called "OpenSSL"
84			* nor may "OpenSSL" appear in their names without prior written
85			* permission of the OpenSSL Project.
86			*
87			* 6. Redistributions of any form whatsoever must retain the following
88			* acknowledgment:
89			* "This product includes software developed by the OpenSSL Project
90			* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91			*
92			* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93			* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95			* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98			* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99			* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101			* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102			* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103			* OF THE POSSIBILITY OF SUCH DAMAGE.
104			* ====================================================================
105			*
106			* This product includes cryptographic software written by Eric Young
107			* (eay@cryptsoft.com). This product includes software written by Tim
108			* Hudson (tjh@cryptsoft.com).
109			*
110			*/
111
112			#include <stdio.h>
113			#include <time.h>
114
115			#include <openssl/err.h>
116
117			#include "bn_lcl.h"
118
119			/* NB: these functions have been "upgraded", the deprecated versions (which are
120			* compatibility wrappers using these functions) are in bn_depr.c.
121			* - Geoff
122			*/
123
124			/* The quick sieve algorithm approach to weeding out primes is
125			* Philip Zimmermann's, as implemented in PGP. I have had a read of
126			* his comments and implemented my own version.
127			*/
128			#include "bn_prime.h"
129
130			static int witness(BIGNUM w, const BIGNUM a, const BIGNUM *a1,
131			const BIGNUM a1_odd, int k, BN_CTX ctx, BN_MONT_CTX *mont);
132			static int probable_prime(BIGNUM *rnd, int bits);
133			static int probable_prime_dh(BIGNUM *rnd, int bits,
134			const BIGNUM add, const BIGNUM rem, BN_CTX *ctx);
135			static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
136			const BIGNUM add, const BIGNUM rem, BN_CTX *ctx);
137
138			int
139			BN_GENCB_call(BN_GENCB *cb, int a, int b)
140			{
141			/* No callback means continue */
142	✓✓	76964	if (!cb)
143		10468	return 1;
144	✗✓✗	28014	switch (cb->ver) {
145			case 1:
146			/* Deprecated-style callbacks */
147			if (!cb->cb.cb_1)
148			return 1;
149			cb->cb.cb_1(a, b, cb->arg);
150			return 1;
151			case 2:
152			/* New-style callbacks */
153		28014	return cb->cb.cb_2(a, b, cb);
154			default:
155			break;
156			}
157			/* Unrecognised callback type */
158			return 0;
159		38482	}
160
161			int
162			BN_generate_prime_ex(BIGNUM ret, int bits, int safe, const BIGNUM add,
163			const BIGNUM rem, BN_GENCB cb)
164			{
165			BIGNUM *t;
166			int found = 0;
167			int i, j, c1 = 0;
168			BN_CTX *ctx;
169			int checks;
170
171	✓✗✗✓	768	if (bits < 2 \|\| (bits == 2 && safe)) {
172			/*
173			* There are no prime numbers smaller than 2, and the smallest
174			* safe prime (7) spans three bits.
175			*/
176			BNerror(BN_R_BITS_TOO_SMALL);
177			return 0;
178			}
179
180		256	ctx = BN_CTX_new();
181	✓✗	256	if (ctx == NULL)
182			goto err;
183		256	BN_CTX_start(ctx);
184	✓✗	256	if ((t = BN_CTX_get(ctx)) == NULL)
185			goto err;
186
187	✓✓✓✓ ✓✗✓✗ ✓✓✓✗ ✓✗✓✗ ✓✓✓✗	2170	checks = BN_prime_checks_for_size(bits);
188
189			loop:
190			/* make a random number and set the top and bottom bits */
191	✓✓	21558	if (add == NULL) {
192	✓✗	3413	if (!probable_prime(ret, bits))
193			goto err;
194			} else {
195	✓✓	18145	if (safe) {
196	✓✗	17665	if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
197			goto err;
198			} else {
199	✓✗	480	if (!probable_prime_dh(ret, bits, add, rem, ctx))
200			goto err;
201			}
202			}
203			/* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
204	✓✗	21558	if (!BN_GENCB_call(cb, 0, c1++))
205			/* aborted */
206			goto err;
207
208	✓✓	21558	if (!safe) {
209		3889	i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
210	✓✗	3889	if (i == -1)
211			goto err;
212	✓✓	3889	if (i == 0)
213			goto loop;
214			} else {
215			/* for "safe prime" generation,
216			* check that (p-1)/2 is prime.
217			* Since a prime is odd, We just
218			* need to divide by 2 */
219	✓✗	17669	if (!BN_rshift1(t, ret))
220			goto err;
221
222	✓✓	41322	for (i = 0; i < checks; i++) {
223		20545	j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
224	✓✗	20545	if (j == -1)
225			goto err;
226	✓✓	20545	if (j == 0)
227			goto loop;
228
229		3407	j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
230	✓✗	3407	if (j == -1)
231			goto err;
232	✓✓	3407	if (j == 0)
233			goto loop;
234
235	✓✗	2992	if (!BN_GENCB_call(cb, 2, c1 - 1))
236			goto err;
237			/* We have a safe prime test pass */
238			}
239			}
240			/* we have a prime :-) */
241		256	found = 1;
242
243			err:
244	✓✗	256	if (ctx != NULL) {
245		256	BN_CTX_end(ctx);
246		256	BN_CTX_free(ctx);
247		256	}
248			bn_check_top(ret);
249		256	return found;
250		256	}
251
252			int
253			BN_is_prime_ex(const BIGNUM a, int checks, BN_CTX ctx_passed, BN_GENCB *cb)
254			{
255		136	return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
256			}
257
258			int
259			BN_is_prime_fasttest_ex(const BIGNUM a, int checks, BN_CTX ctx_passed,
260			int do_trial_division, BN_GENCB *cb)
261			{
262			int i, j, ret = -1;
263			int k;
264			BN_CTX *ctx = NULL;
265			BIGNUM A1, A1_odd, check; / taken from ctx */
266			BN_MONT_CTX *mont = NULL;
267			const BIGNUM *A = NULL;
268
269	✓✓	62136	if (BN_cmp(a, BN_value_one()) <= 0)
270		2	return 0;
271
272	✓✓	31066	if (checks == BN_prime_checks)
273	✓✓✓✓ ✓✗✓✗ ✓✓✓✗ ✓✓✓✗ ✓✓✓✓	590	checks = BN_prime_checks_for_size(BN_num_bits(a));
274
275			/* first look for small factors */
276	✓✗✓✓	62132	if (!BN_is_odd(a))
277			/* a is even => a is prime if and only if a == 2 */
278	✓✗✓✓	23	return BN_is_word(a, 2);
279	✓✓	31059	if (do_trial_division) {
280	✓✓	1505036	for (i = 1; i < NUMPRIMES; i++) {
281		752211	BN_ULONG mod = BN_mod_word(a, primes[i]);
282	✗✓	752211	if (mod == (BN_ULONG)-1)
283			goto err;
284	✓✓	752211	if (mod == 0)
285		2840	return 0;
286	✓✓✓	749371	}
287	✓✗	307	if (!BN_GENCB_call(cb, 1, -1))
288			goto err;
289			}
290
291	✓✓	28219	if (ctx_passed != NULL)
292		28215	ctx = ctx_passed;
293	✓✗	4	else if ((ctx = BN_CTX_new()) == NULL)
294			goto err;
295		28219	BN_CTX_start(ctx);
296
297			/* A := abs(a) */
298	✗✓	28219	if (a->neg) {
299			BIGNUM *t;
300			if ((t = BN_CTX_get(ctx)) == NULL)
301			goto err;
302			BN_copy(t, a);
303			t->neg = 0;
304			A = t;
305			} else
306			A = a;
307	✓✗	28219	if ((A1 = BN_CTX_get(ctx)) == NULL)
308			goto err;
309	✓✗	28219	if ((A1_odd = BN_CTX_get(ctx)) == NULL)
310			goto err;
311	✓✗	28219	if ((check = BN_CTX_get(ctx)) == NULL)
312			goto err;
313
314			/* compute A1 := A - 1 */
315	✓✗	28219	if (!BN_copy(A1, A))
316			goto err;
317	✓✗	28219	if (!BN_sub_word(A1, 1))
318			goto err;
319	✗✓	28219	if (BN_is_zero(A1)) {
320			ret = 0;
321			goto err;
322			}
323
324			/* write A1 as A1_odd * 2^k */
325			k = 1;
326	✓✓	78706	while (!BN_is_bit_set(A1, k))
327		11134	k++;
328	✓✗	28219	if (!BN_rshift(A1_odd, A1, k))
329			goto err;
330
331			/* Montgomery setup for computations mod A */
332		28219	mont = BN_MONT_CTX_new();
333	✓✗	28219	if (mont == NULL)
334			goto err;
335	✓✗	28219	if (!BN_MONT_CTX_set(mont, A, ctx))
336			goto err;
337
338	✓✓	76868	for (i = 0; i < checks; i++) {
339	✓✗	31793	if (!BN_pseudo_rand_range(check, A1))
340			goto err;
341	✓✗	31793	if (!BN_add_word(check, 1))
342			goto err;
343			/* now 1 <= check < A */
344
345		31793	j = witness(check, A, A1, A1_odd, k, ctx, mont);
346	✓✗	31793	if (j == -1)
347			goto err;
348	✓✓	31793	if (j) {
349			ret = 0;
350		21578	goto err;
351			}
352	✓✗	10215	if (!BN_GENCB_call(cb, 1, i))
353			goto err;
354			}
355		6641	ret = 1;
356
357			err:
358	✓✗	28219	if (ctx != NULL) {
359		28219	BN_CTX_end(ctx);
360	✓✓	28219	if (ctx_passed == NULL)
361		4	BN_CTX_free(ctx);
362			}
363		28219	BN_MONT_CTX_free(mont);
364
365		28219	return (ret);
366		31068	}
367
368			static int
369			witness(BIGNUM w, const BIGNUM a, const BIGNUM a1, const BIGNUM a1_odd,
370			int k, BN_CTX ctx, BN_MONT_CTX mont)
371			{
372	✗✓	63586	if (!BN_mod_exp_mont_ct(w, w, a1_odd, a, ctx, mont))
373			/* w := w^a1_odd mod a */
374			return -1;
375	✓✓✓✓ ✓✗	43030	if (BN_is_one(w))
376		3457	return 0; /* probably prime */
377	✓✓	28336	if (BN_cmp(w, a1) == 0)
378		3513	return 0; /* w == -1 (mod a), 'a' is probably prime */
379	✓✓	41303	while (--k) {
380	✗✓	19725	if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
381			return -1;
382	✓✓✗✓ ✗✗	23619	if (BN_is_one(w))
383			return 1; /* 'a' is composite, otherwise a previous 'w' would
384			* have been == -1 (mod 'a') */
385	✓✓	19725	if (BN_cmp(w, a1) == 0)
386		3245	return 0; /* w == -1 (mod a), 'a' is probably prime */
387			}
388			/* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
389			* and it is neither -1 nor +1 -- so 'a' cannot be prime */
390			bn_check_top(w);
391		21578	return 1;
392		31793	}
393
394			static int
395			probable_prime(BIGNUM *rnd, int bits)
396			{
397			int i;
398		6826	prime_t mods[NUMPRIMES];
399		3413	BN_ULONG delta, maxdelta;
400
401			again:
402	✗✓	3413	if (!BN_rand(rnd, bits, 1, 1))
403			return (0);
404			/* we now have a random number 'rand' to test. */
405	✓✓	13979648	for (i = 1; i < NUMPRIMES; i++) {
406		6986411	BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
407	✗✓	6986411	if (mod == (BN_ULONG)-1)
408			return (0);
409		6986411	mods[i] = (prime_t)mod;
410	✓✗	6986411	}
411			maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
412		3413	delta = 0;
413			loop:
414	✓✓	20634654	for (i = 1; i < NUMPRIMES; i++) {
415			/* check that rnd is not a prime and also
416			* that gcd(rnd-1,primes) == 1 (except for 2) */
417	✓✓	10313914	if (((mods[i] + delta) % primes[i]) <= 1) {
418		370410	delta += 2;
419	✗✓	370410	if (delta > maxdelta)
420			goto again;
421			goto loop;
422			}
423			}
424	✗✓	3413	if (!BN_add_word(rnd, delta))
425			return (0);
426			bn_check_top(rnd);
427		3413	return (1);
428		3413	}
429
430			static int
431			probable_prime_dh(BIGNUM rnd, int bits, const BIGNUM add, const BIGNUM *rem,
432			BN_CTX *ctx)
433			{
434			int i, ret = 0;
435			BIGNUM *t1;
436
437		960	BN_CTX_start(ctx);
438	✓✗	480	if ((t1 = BN_CTX_get(ctx)) == NULL)
439			goto err;
440
441	✓✗	480	if (!BN_rand(rnd, bits, 0, 1))
442			goto err;
443
444			/* we need ((rnd-rem) % add) == 0 */
445
446	✓✗	480	if (!BN_mod_ct(t1, rnd, add, ctx))
447			goto err;
448	✓✗	480	if (!BN_sub(rnd, rnd, t1))
449			goto err;
450	✗✓	480	if (rem == NULL) {
451			if (!BN_add_word(rnd, 1))
452			goto err;
453			} else {
454	✓✗	480	if (!BN_add(rnd, rnd, rem))
455			goto err;
456			}
457
458			/* we now have a random number 'rand' to test. */
459
460			loop:
461	✓✓	2901788	for (i = 1; i < NUMPRIMES; i++) {
462			/* check that rnd is a prime */
463		1450414	BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
464	✗✓	1450414	if (mod == (BN_ULONG)-1)
465			goto err;
466	✓✓	1450414	if (mod <= 1) {
467	✗✓	51533	if (!BN_add(rnd, rnd, add))
468			goto err;
469		51533	goto loop;
470			}
471	✓✓✓✓	1398881	}
472		480	ret = 1;
473
474			err:
475		480	BN_CTX_end(ctx);
476			bn_check_top(rnd);
477		480	return (ret);
478		480	}
479
480			static int
481			probable_prime_dh_safe(BIGNUM p, int bits, const BIGNUM padd,
482			const BIGNUM rem, BN_CTX ctx)
483			{
484			int i, ret = 0;
485			BIGNUM t1, qadd, *q;
486
487		35330	bits--;
488		17665	BN_CTX_start(ctx);
489	✓✗	17665	if ((t1 = BN_CTX_get(ctx)) == NULL)
490			goto err;
491	✓✗	17665	if ((q = BN_CTX_get(ctx)) == NULL)
492			goto err;
493	✓✗	17665	if ((qadd = BN_CTX_get(ctx)) == NULL)
494			goto err;
495
496	✓✗	17665	if (!BN_rshift1(qadd, padd))
497			goto err;
498
499	✓✗	17665	if (!BN_rand(q, bits, 0, 1))
500			goto err;
501
502			/* we need ((rnd-rem) % add) == 0 */
503	✓✗	17665	if (!BN_mod_ct(t1, q,qadd, ctx))
504			goto err;
505	✓✗	17665	if (!BN_sub(q, q, t1))
506			goto err;
507	✗✓	17665	if (rem == NULL) {
508			if (!BN_add_word(q, 1))
509			goto err;
510			} else {
511	✓✗	17665	if (!BN_rshift1(t1, rem))
512			goto err;
513	✓✗	17665	if (!BN_add(q, q, t1))
514			goto err;
515			}
516
517			/* we now have a random number 'rand' to test. */
518	✓✗	17665	if (!BN_lshift1(p, q))
519			goto err;
520	✓✗	17665	if (!BN_add_word(p, 1))
521			goto err;
522
523			loop:
524	✓✓	104332366	for (i = 1; i < NUMPRIMES; i++) {
525			/* check that p and q are prime */
526			/* check that for p and q
527			* gcd(p-1,primes) == 1 (except for 2) */
528		52148518	BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
529		52148518	BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
530	✗✓	52148518	if (pmod == (BN_ULONG)-1 \|\| qmod == (BN_ULONG)-1)
531			goto err;
532	✓✓	52148518	if (pmod == 0 \|\| qmod == 0) {
533	✗✓	635412	if (!BN_add(p, p, padd))
534			goto err;
535	✗✓	635412	if (!BN_add(q, q, qadd))
536			goto err;
537		635412	goto loop;
538			}
539	✓✓✓✓	51513106	}
540		17665	ret = 1;
541
542			err:
543		17665	BN_CTX_end(ctx);
544			bn_check_top(p);
545		17665	return (ret);
546		17665	}