From b0513819e043b13692c9e923adf5aafa26cddec0 Mon Sep 17 00:00:00 2001
From: Felix Laurie von Massenbach <felix@erbridge.co.uk>
Date: Tue, 27 May 2014 00:37:03 +0100
Subject: [PATCH] Add a method to generate a prime that is guaranteed not to be
 divisible by 3 or 5.

Possibly some reduction in bias, but no speed gains.
---
 apps/speed.c         | 23 ++++++++++++
 crypto/bn/bn_lcl.h   |  2 ++
 crypto/bn/bn_prime.c | 84 +++++++++++++++++++++++++++++---------------
 3 files changed, 80 insertions(+), 29 deletions(-)

diff --git a/apps/speed.c b/apps/speed.c
index 885784ee1d..84d0829ad2 100644
--- a/apps/speed.c
+++ b/apps/speed.c
@@ -2041,6 +2041,29 @@ int MAIN(int argc, char **argv)
 		BN_free(rnd);
 		
 		}
+	
+	if (prime_doit[D_PRIME_COPRIME])
+		{
+		BIGNUM *rnd = BN_new();
+		BIGNUM *add = BN_new();
+		BN_CTX *ctx = BN_CTX_new();
+		
+		BN_set_word(add, 2);
+		prime_print_message(prime_names[D_PRIME_COPRIME],
+							prime_c[D_PRIME_COPRIME]);
+			
+		Time_F(START);
+		for (count=0, run=1; COND(prime_c[D_PRIME_COPRIME]); count++)
+			bn_probable_prime_dh_coprime(rnd, 1024, add, NULL, ctx);
+		
+		d=Time_F(STOP);
+		prime_print_result(D_PRIME_COPRIME, count, d);
+		
+		BN_CTX_free(ctx);
+		BN_free(add);
+		BN_free(rnd);
+		
+		}
 
 	RAND_pseudo_bytes(buf,36);
 #ifndef OPENSSL_NO_RSA
diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
index 40ef22b73f..fc54dcecdc 100644
--- a/crypto/bn/bn_lcl.h
+++ b/crypto/bn/bn_lcl.h
@@ -536,6 +536,8 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in,
 
 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 	const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
+int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits,
+	const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
 
 #ifdef  __cplusplus
 }
diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index ac6ae30fa2..b303a48726 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -129,9 +129,13 @@
 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, const BIGNUM *add,
+	const BIGNUM *rem, BN_CTX *ctx, int first_prime_index);
 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
 	const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
 
+static int prime_offsets[8] = { 7, 11, 13, 17, 19, 23, 29, 31 };
+
 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 	{
 	/* No callback means continue */
@@ -363,40 +367,25 @@ err:
 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 	const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 	{
-	int i,ret=0;
-	BIGNUM *t1;
+	if (!BN_rand(rnd, bits, 0, 1)) return(0);
 
-	BN_CTX_start(ctx);
-	if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
-
-	if (!BN_rand(rnd,bits,0,1)) goto err;
+	return(probable_prime_dh(rnd, add, rem, ctx, 1));
+	}
 
-	/* we need ((rnd-rem) % add) == 0 */
+int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits,
+	const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
+	{
+	BIGNUM *offset_index = BN_new();
 
-	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; }
+	if (!BN_rand(rnd, bits, 0, 1)) return(0);
+	if (!BN_rand(offset_index, 3, -1, -1)) return(0);
 
-	/* we now have a random number 'rand' to test. */
+	BN_mul_word(rnd, 30);
+	BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
+	
+	BN_free(offset_index);
 
-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);
+	return(probable_prime_dh(rnd, add, rem, ctx, 3));
 	}
 
 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
@@ -491,6 +480,43 @@ loop:
 	return(1);
 	}
 
+static int probable_prime_dh(BIGNUM *rnd, const BIGNUM *add,
+	const BIGNUM *rem, BN_CTX *ctx, int first_prime_index)
+	{
+	int i,ret=0;
+	BIGNUM *t1;
+
+	BN_CTX_start(ctx);
+	if ((t1 = BN_CTX_get(ctx)) == NULL) 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=first_prime_index; 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)
 	{
-- 
2.40.0