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 d57f6582110f6c74bec114939fa51ca4cf42a25a..339dbec57051b2f751b1f9cde8caffe6d244662b 100644 (file)
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -165,6 +165,19 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
        BN_CTX *ctx;
        int checks = BN_prime_checks_for_size(bits);
 
+       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);
@@ -377,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);
        }