bn/asm/rsaz-avx2.pl: Windows-specific fix.

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

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 4430e90df5553495faf4d6fe948bada2a0f605bd..339dbec57051b2f751b1f9cde8caffe6d244662b 100644 (file)
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -159,15 +159,30 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
        const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
        {
-       BIGNUM t;
+       BIGNUM *t;
        int found=0;
        int i,j,c1=0;
        BN_CTX *ctx;
        int checks = BN_prime_checks_for_size(bits);
 
-       BN_init(&t);
+       if (bits < 2)
+               {
+               /* There are no prime numbers this small. */
+               BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
+               return 0;
+               }
+       else if (bits == 2 && safe)
+               {
+               /* The smallest safe prime (7) is three bits. */
+               BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
+               return 0;
+               }
+
        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)
@@ -204,7 +219,7 @@ loop:
                 * 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;
+               if (!BN_rshift1(t,ret)) goto err;
 
                for (i=0; i<checks; i++)
                        {
@@ -212,7 +227,7 @@ loop:
                        if (j == -1) goto err;
                        if (j == 0) goto loop;
 
-                       j=BN_is_prime_fasttest_ex(&t,1,ctx,0,cb);
+                       j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
                        if (j == -1) goto err;
                        if (j == 0) goto loop;
 
@@ -224,8 +239,11 @@ loop:
        /* we have a prime :-) */
        found = 1;
 err:
-       BN_free(&t);
-       if (ctx != NULL) BN_CTX_free(ctx);
+       if (ctx != NULL)
+               {
+               BN_CTX_end(ctx);
+               BN_CTX_free(ctx);
+               }
        bn_check_top(ret);
        return found;
        }
@@ -253,7 +271,8 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 
        /* first look for small factors */
        if (!BN_is_odd(a))
-               return 0;
+               /* 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++)
@@ -371,31 +390,66 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 static int probable_prime(BIGNUM *rnd, int bits)
        {
        int i;
-       BN_ULONG mods[NUMPRIMES];
-       BN_ULONG delta,d;
+       prime_t mods[NUMPRIMES];
+       BN_ULONG delta;
+       BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1];
+       char is_single_word = bits <= BN_BITS2;
 
 again:
        if (!BN_rand(rnd,bits,1,1)) return(0);
-       /* we now have a random number 'rand' to test. */
+       /* we now have a random number 'rnd' to test. */
        for (i=1; i<NUMPRIMES; i++)
-               mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
+               mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);
+       /* If bits is so small that it fits into a single word then we
+        * additionally don't want to exceed that many bits. */
+       if (is_single_word)
+               {
+               BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;
+               if (size_limit < maxdelta)
+                       maxdelta = size_limit;
+               }
        delta=0;
-       loop: for (i=1; i<NUMPRIMES; i++)
+       loop:
+       if (is_single_word)
                {
-               /* 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)
+               BN_ULONG rnd_word = BN_get_word(rnd);
+
+               /* In the case that the candidate prime is a single word then
+                * we check that:
+                *   1) It's greater than primes[i] because we shouldn't reject
+                *      3 as being a prime number because it's a multiple of
+                *      three.
+                *   2) That it's not a multiple of a known prime. We don't
+                *      check that rnd-1 is also coprime to all the known
+                *      primes because there aren't many small primes where
+                *      that's true. */
+               for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)
                        {
-                       d=delta;
-                       delta+=2;
-                       /* perhaps need to check for overflow of
-                        * delta (but delta can be up to 2^32)
-                        * 21-May-98 eay - added overflow check */
-                       if (delta < d) goto again;
-                       goto loop;
+                       if ((mods[i]+delta)%primes[i] == 0)
+                               {
+                               delta+=2;
+                               if (delta > maxdelta) goto again;
+                               goto loop;
+                               }
+                       }
+               }
+       else
+               {
+               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);
+       if (BN_num_bits(rnd) != bits)
+               goto again;
        bn_check_top(rnd);
        return(1);
        }