Use uniformly chosen witnesses for Miller-Rabin test

[oweals/openssl.git] / crypto / bn / bn_prime.c

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 0f07c222fa0e1ae9c6cea35ead17295934af5fbe..8eda6c0755f069d0f89d5265ed9315fec99f9a52 100644 (file)
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -223,14 +223,17 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
        BN_CTX *ctx = NULL;
        BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
        BN_MONT_CTX *mont = NULL;
-       const BIGNUM *A;
+       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))
-               return(0);
+               return 0;
        if (do_trial_division)
                {
                for (i = 1; i < NUMPRIMES; i++)
@@ -244,19 +247,23 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
        else
                if ((ctx=BN_CTX_new()) == NULL)
                        goto err;
+       BN_CTX_start(ctx);
+
        /* A := abs(a) */
        if (a->neg)
                {
-               BIGNUM *t = &(ctx->bn[ctx->tos++]);
+               BIGNUM *t;
+               if ((t = BN_CTX_get(ctx)) == NULL) goto err;
                BN_copy(t, a);
                t->neg = 0;
                A = t;
                }
        else
                A = a;
-       A1 = &(ctx->bn[ctx->tos++]);
-       A1_odd = &(ctx->bn[ctx->tos++]);
-       check = &(ctx->bn[ctx->tos++]);;
+       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))
@@ -285,11 +292,8 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
        
        for (i = 0; i < checks; i++)
                {
-               if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0))
+               if (!BN_pseudo_rand_range(check, A1))
                        goto err;
-               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 */
@@ -305,14 +309,12 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
                }
        ret=1;
 err:
-       if (ctx_passed != NULL)
+       if (ctx != NULL)
                {
-               ctx_passed->tos -= 3; /* A1, A1_odd, check */
-               if (a != A)
-                       --ctx_passed->tos; /* A */
+               BN_CTX_end(ctx);
+               if (ctx_passed == NULL)
+                       BN_CTX_free(ctx);
                }
-       else if (ctx != NULL)
-               BN_CTX_free(ctx);
        if (mont != NULL)
                BN_MONT_CTX_free(mont);
 
@@ -364,7 +366,7 @@ again:
                        d=delta;
                        delta+=2;
                        /* perhaps need to check for overflow of
-                        * delta (but delta can be upto 2^32)
+                        * delta (but delta can be up to 2^32)
                         * 21-May-98 eay - added overflow check */
                        if (delta < d) goto again;
                        goto loop;
@@ -380,7 +382,8 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
        int i,ret=0;
        BIGNUM *t1;
 
-       t1= &(ctx->bn[ctx->tos++]);
+       BN_CTX_start(ctx);
+       if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
 
        if (!BN_rand(rnd,bits,0,1)) goto err;
 
@@ -406,7 +409,7 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
                }
        ret=1;
 err:
-       ctx->tos--;
+       BN_CTX_end(ctx);
        return(ret);
        }
 
@@ -414,12 +417,14 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd,
             BIGNUM *rem, BN_CTX *ctx)
        {
        int i,ret=0;
-       BIGNUM *t1,*qadd=NULL,*q=NULL;
+       BIGNUM *t1,*qadd,*q;
 
        bits--;
-       t1= &(ctx->bn[ctx->tos++]);
-       q= &(ctx->bn[ctx->tos++]);
-       qadd= &(ctx->bn[ctx->tos++]);
+       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;
                
@@ -455,6 +460,6 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd,
                }
        ret=1;
 err:
-       ctx->tos-=3;
+       BN_CTX_end(ctx);
        return(ret);
        }