/* crypto/bn/bn_prime.c */

/* 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 "cryptlib.h"

#include "bn_lcl.h"

#include <openssl/rand.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);

EXPORT_C 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;

	}

EXPORT_C 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 = BN_prime_checks_for_size(bits);

	ctx=BN_CTX_new();

	if (ctx == NULL) goto err;

	BN_CTX_start(ctx);

	t = BN_CTX_get(ctx);

	if(!t) goto err;

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;

	}

EXPORT_C 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);

	}

EXPORT_C 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++)

			if (BN_mod_word(a, primes[i]) == 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;

	A1 = BN_CTX_get(ctx);

	A1_odd = BN_CTX_get(ctx);

	check = BN_CTX_get(ctx);

	if (check == 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);

		}

	if (mont != NULL)

		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(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++)

		mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);

	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(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 */

		if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 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);

	t1 = BN_CTX_get(ctx);

	q = BN_CTX_get(ctx);

	qadd = BN_CTX_get(ctx);

	if (qadd == 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(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) */

		if (	(BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||

			(BN_mod_word(q,(BN_ULONG)primes[i]) == 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);

	}