Use uniformly chosen witnesses for Miller-Rabin test

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

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 25bafd1f9c85558bb3e44a71c4ed42de7afa4104..5bfc0b682be598c32e52ab65d7ee98dae6cef60b 100644 (file)
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -125,12 +125,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, int bits,
-       BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
+       const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
-       BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
+       const BIGNUM *add, const BIGNUM *rem, 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)
+BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe,
+       const BIGNUM *add, const BIGNUM *rem,
+       void (*callback)(int,int,void *), void *cb_arg)
        {
        BIGNUM *rnd=NULL;
        BIGNUM t;
@@ -225,12 +226,15 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
        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))
-               return(0);
+               return 0;
        if (do_trial_division)
                {
                for (i = 1; i < NUMPRIMES; i++)
@@ -244,19 +248,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 +293,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 +310,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);
 
@@ -374,13 +377,14 @@ again:
        return(1);
        }
 
-static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
-            BN_CTX *ctx)
+static int probable_prime_dh(BIGNUM *rnd, int bits,
+       const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
        {
        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,20 +410,22 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
                }
        ret=1;
 err:
-       ctx->tos--;
+       BN_CTX_end(ctx);
        return(ret);
        }
 
-static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd,
-            BIGNUM *rem, BN_CTX *ctx)
+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=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 +461,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);
        }