Tolerate negative numbers in BN_is_prime.

openssl · Feb 2, 2000 · aff0825 · aff0825
1 parent e74231e
commit aff0825
Show file tree

Hide file tree

Showing 5 changed files with 46 additions and 31 deletions.
diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
@@ -404,9 +404,10 @@ int	BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx);
 BIGNUM *BN_mod_inverse(BIGNUM *ret,BIGNUM *a, const BIGNUM *n,BN_CTX *ctx);
 BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe,BIGNUM *add,
 		BIGNUM *rem,void (*callback)(int,int,void *),void *cb_arg);
-int	BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int,void *),
+int	BN_is_prime(const BIGNUM *p,int nchecks,
+		void (*callback)(int,int,void *),
 		BN_CTX *ctx,void *cb_arg);
-int	BN_is_prime_fasttest(BIGNUM *p,int nchecks,
+int	BN_is_prime_fasttest(const BIGNUM *p,int nchecks,
 		void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg,
 		int do_trial_division);
 void	ERR_load_BN_strings(void );

diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
@@ -203,7 +203,7 @@ extern "C" {
 	BN_ULLONG t; \
 	t=(BN_ULLONG)(a)*(a); \
 	(r0)=Lw(t); \
-	(r1)=Hw(t); ]
+	(r1)=Hw(t); \
 	}
 
 #elif defined(BN_UMULT_HIGH)

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
@@ -154,29 +154,27 @@ BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add,
 	return(found ? rnd : NULL);
 	}
 
-int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
+int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *),
 	BN_CTX *ctx_passed, void *cb_arg)
 	{
 	return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0);
 	}
 
-int BN_is_prime_fasttest(BIGNUM *a, int checks,
+int BN_is_prime_fasttest(const BIGNUM *a, int checks,
 		void (*callback)(int,int,void *),
 		BN_CTX *ctx_passed, void *cb_arg,
 		int do_trial_division)
 	{
 	int i, j, ret = -1;
 	int k;
 	BN_CTX *ctx = NULL;
-	BIGNUM *a1, *a1_odd, *check; /* taken from ctx */
+	BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 	BN_MONT_CTX *mont = NULL;
+	BIGNUM *A;
 
 	if (checks == BN_prime_checks)
 		checks = BN_prime_checks_for_size(BN_num_bits(a));
 
-	if (a->neg) /* for now, refuse to handle negative numbers */
-		return -1;
-
 	/* first look for small factors */
 	if (!BN_is_odd(a))
 		return(0);
@@ -193,47 +191,56 @@ int BN_is_prime_fasttest(BIGNUM *a, int checks,
 	else
 		if ((ctx=BN_CTX_new()) == NULL)
 			goto err;
-	a1 = &(ctx->bn[ctx->tos++]);
-	a1_odd = &(ctx->bn[ctx->tos++]);
+	/* A := abs(a) */
+	if (a->neg)
+		{
+		A = &(ctx->bn[ctx->tos++]);
+		BN_copy(A, a);
+		A->neg = 0;
+		}
+	else
+		A = a;
+	A1 = &(ctx->bn[ctx->tos++]);
+	A1_odd = &(ctx->bn[ctx->tos++]);
 	check = &(ctx->bn[ctx->tos++]);;
 
-	/* compute a1 := a - 1 */
-	if (!BN_copy(a1, a))
+	/* compute A1 := A - 1 */
+	if (!BN_copy(A1, A))
 		goto err;
-	if (!BN_sub_word(a1, 1))
+	if (!BN_sub_word(A1, 1))
 		goto err;
-	if (BN_is_zero(a1))
+	if (BN_is_zero(A1))
 		{
 		ret = 0;
 		goto err;
 		}
 
-	/* write  a1  as  a1_odd * 2^k */
+	/* write  A1  as  A1_odd * 2^k */
 	k = 1;
-	while (!BN_is_bit_set(a1, k))
+	while (!BN_is_bit_set(A1, k))
 		k++;
-	if (!BN_rshift(a1_odd, a1, k))
+	if (!BN_rshift(A1_odd, A1, k))
 		goto err;
 
-	/* Montgomery setup for computations mod a */
+	/* Montgomery setup for computations mod A */
 	mont = BN_MONT_CTX_new();
 	if (mont == NULL)
 		goto err;
-	if (!BN_MONT_CTX_set(mont, a, ctx))
+	if (!BN_MONT_CTX_set(mont, A, ctx))
 		goto err;
 
 	for (i = 0; i < checks; i++)
 		{
-		if (!BN_pseudo_rand(check, BN_num_bits(a1), 0, 0))
+		if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0))
 			goto err;
-		if (BN_cmp(check, a1) >= 0)
-			if (!BN_sub(check, check, a1))
+		if (BN_cmp(check, A1) >= 0)
+			if (!BN_sub(check, check, A1))
 				goto err;
 		if (!BN_add_word(check, 1))
 			goto err;
-		/* now 1 <= check < a */
+		/* now 1 <= check < A */
 
-		j = witness(check, a, a1, a1_odd, k, ctx, mont);
+		j = witness(check, A, A1, A1_odd, k, ctx, mont);
 		if (j == -1) goto err;
 		if (j)
 			{
@@ -245,7 +252,11 @@ int BN_is_prime_fasttest(BIGNUM *a, int checks,
 	ret=1;
 err:
 	if (ctx_passed != NULL)
-		ctx_passed->tos -= 3; /* a1, a1_odd, check */
+		{
+		ctx_passed->tos -= 3; /* A1, A1_odd, check */
+		if (a != A)
+			--ctx_passed->tos; /* A */
+		}
 	else if (ctx != NULL)
 		BN_CTX_free(ctx);
 	if (mont != NULL)

diff --git a/crypto/dsa/dsa_gen.c b/crypto/dsa/dsa_gen.c
@@ -167,10 +167,12 @@ DSA *DSA_generate_parameters(int bits, unsigned char *seed_in, int seed_len,
 
 			/* step 4 */
 			r = BN_is_prime_fasttest(q, DSS_prime_checks, callback, ctx3, cb_arg, seed_is_random);
+			if (ctx3->tos)
+				goto err;
 			if (r > 0)
-					break;
+				break;
 			if (r != 0)
-					goto err;
+				goto err;
 
 			/* do a callback call */
 			/* step 5 */

diff --git a/doc/crypto/BN_generate_prime.pod b/doc/crypto/BN_generate_prime.pod
@@ -11,11 +11,12 @@ BN_generate_prime, BN_is_prime, BN_is_prime_fasttest - Generate primes and test
  BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add,
      BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg);
 
- int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int, int, 
+ int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int, int, 
      void *), BN_CTX *ctx, void *cb_arg);
 
- int BN_is_prime_fasttest(BIGNUM *a, int checks, void (*callback)(int,
-     int, void *), BN_CTX *ctx, void *cb_arg, int do_trial_division);
+ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
+     void (*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg,
+     int do_trial_division);
 
 =head1 DESCRIPTION