Any fixed MR iterations is probably wrong for somebody. Allow the user

to specify a probability as well as if n was randomly chosen or not.
If the input is random use a better bounds to reduce the number of
needed tests.

6 files changed, 57 insertions, 16 deletions

diff --git a/src/lib/math/numbertheory/dsa_gen.cpp b/src/lib/math/numbertheory/dsa_gen.cpp
index f14481f9c..796fb6ec2 100644
--- a/src/lib/math/numbertheory/dsa_gen.cpp
+++ b/src/lib/math/numbertheory/dsa_gen.cpp
@@ -82,7 +82,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
    q.set_bit(qbits-1);
    q.set_bit(0);
 
-   if(!check_prime(q, rng))
+   if(!is_prime(q, rng))
       return false;
 
    const size_t n = (pbits-1) / (HASH_SIZE * 8),
@@ -106,7 +106,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
 
       p = X - (X % (2*q) - 1);
 
-      if(p.bits() == pbits && check_prime(p, rng))
+      if(p.bits() == pbits && is_prime(p, rng))
          return true;
       }
    return false;
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index dc94420ab..2c8cd086d 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -75,7 +75,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
          if(!passes_sieve || gcd(p - 1, coprime) != 1)
             continue;
-         if(check_prime(p, rng))
+         if(is_prime(p, rng, 64, true))
             return p;
          }
       }
@@ -93,7 +93,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
    BigInt p;
    do
       p = (random_prime(rng, bits - 1) << 1) + 1;
-   while(!check_prime(p, rng));
+   while(!is_prime(p, rng, 64, true));
    return p;
    }
 
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 998b0b53b..ce25b5047 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -253,12 +253,39 @@ bool mr_witness(BigInt&& y,
    return true; // fails Fermat test
    }
 
+size_t mr_test_iterations(size_t n_bits, size_t prob, bool random)
+   {
+   const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
+
+   /*
+   * For randomly chosen numbers we can use the estimates from
+   * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf‎
+   *
+   * These values are derived from the inequality for p(k,t) given on
+   * the second page.
+   */
+   if(random && prob <= 80)
+      {
+      if(n_bits >= 1536)
+         return 2; // < 2^-89
+      if(n_bits >= 1024)
+         return 4; // < 2^-89
+      if(n_bits >= 512)
+         return 5; // < 2^-80
+      if(n_bits >= 256)
+         return 11; // < 2^-80
+      }
+
+   return base;
+   }
+
 }
 
 /*
 * Test for primaility using Miller-Rabin
 */
-bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
+              size_t prob, bool is_random)
    {
    if(n == 2)
       return true;
@@ -273,7 +300,7 @@ bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
       return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
       }
 
-   const size_t test_iterations = 20;
+   const size_t test_iterations = mr_test_iterations(n.bits(), prob, is_random);
 
    const BigInt n_minus_1 = n - 1;
    const size_t s = low_zero_bits(n_minus_1);
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index cb73356b2..5499ff76f 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -126,9 +126,24 @@ size_t BOTAN_DLL low_zero_bits(const BigInt& x);
 * Check for primality
 * @param n a positive integer to test for primality
 * @param rng a random number generator
+* @param prob chance of false positive is bounded by 1/2**prob
+* @param is_random true if n was randomly chosen by us
 * @return true if all primality tests passed, otherwise false
 */
-bool BOTAN_DLL check_prime(const BigInt& n, RandomNumberGenerator& rng);
+bool BOTAN_DLL is_prime(const BigInt& n,
+                        RandomNumberGenerator& rng,
+                        size_t prob = 56,
+                        bool is_random = false);
+
+inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 32); }
+
+inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 56); }
+
+inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 80); }
+
 
 /**
 * Randomly generate a prime
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index 6fd1beeaa..13079a898 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -61,7 +61,7 @@ DL_Group::DL_Group(RandomNumberGenerator& rng,
 
       q = random_prime(rng, qbits);
       BigInt X;
-      while(p.bits() != pbits || !check_prime(p, rng))
+      while(p.bits() != pbits || !is_prime(p, rng))
          {
          X.randomize(rng, pbits);
          p = X - (X % (2*q) - 1);
@@ -159,12 +159,11 @@ bool DL_Group::verify_group(RandomNumberGenerator& rng,
    if((q != 0) && ((p - 1) % q != 0))
       return false;
 
-   if(!strong)
-      return true;
+   const size_t prob = (strong) ? 56 : 10;
 
-   if(!check_prime(p, rng))
+   if(!is_prime(p, rng, prob))
       return false;
-   if((q > 0) && !check_prime(q, rng))
+   if((q > 0) && !is_prime(q, rng, prob))
       return false;
    return true;
    }
diff --git a/src/lib/pubkey/if_algo/if_algo.cpp b/src/lib/pubkey/if_algo/if_algo.cpp
index f6aeb69db..339c4e317 100644
--- a/src/lib/pubkey/if_algo/if_algo.cpp
+++ b/src/lib/pubkey/if_algo/if_algo.cpp
@@ -130,12 +130,12 @@ bool IF_Scheme_PrivateKey::check_key(RandomNumberGenerator& rng,
    if(n < 35 || n.is_even() || e < 2 || d < 2 || p < 3 || q < 3 || p*q != n)
       return false;
 
-   if(!strong)
-      return true;
-
    if(d1 != d % (p - 1) || d2 != d % (q - 1) || c != inverse_mod(q, p))
       return false;
-   if(!check_prime(p, rng) || !check_prime(q, rng))
+
+   const size_t prob = (strong) ? 56 : 12;
+
+   if(!is_prime(p, rng, prob) || !is_prime(q, rng, prob))
       return false;
    return true;
    }