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.

12 files changed, 91 insertions, 37 deletions

diff --git a/doc/manual/bigint.rst b/doc/manual/bigint.rst
index 66a055eb7..c2036fcfd 100644
--- a/doc/manual/bigint.rst
+++ b/doc/manual/bigint.rst
@@ -74,23 +74,33 @@ Number theoretic functions available include:
   Returns the square root modulo a prime, that is, returns a number y
   such that (y*y) % p == x. Returns -1 if no such integer exists.
 
+.. cpp:function:: bool is_prime(BigInt n, RandomNumberGenerator& rng, \
+                                size_t prob = 56, double is_random = false)
+
+  Test *n* for primality using a probablistic algorithm (Miller-Rabin).  With
+  this algorithm, there is some non-zero probability that true will be returned
+  even if *n* is actually composite. Modifying *prob* allows you to decrease the
+  chance of such a false positive, at the cost of increased runtime. Sufficient
+  tests will be run such that the chance *n* is composite is no more than 1 in
+  2\ :sup:`prob`. Set *is_random* to true if (and only if) *n* was randomly
+  chosen (ie, there is no danger it was chosen maliciously) as far fewer tests
+  are needed in that case.
+
 .. cpp:function:: bool quick_check_prime(BigInt n, RandomNumberGenerator& rng)
 
 .. cpp:function:: bool check_prime(BigInt n, RandomNumberGenerator& rng)
 
 .. cpp:function:: bool verify_prime(BigInt n, RandomNumberGenerator& rng)
 
-  Three variations on primality testing. All take an integer to test along with
-  a random number generator, and return true if the integer seems like it might
-  be prime; there is a chance that this function will return true even with
-  a composite number. The probability decreases with the amount of work performed,
-  so it is much less likely that ``verify_prime`` will return a false positive
-  than ``check_prime`` will.
+  Three variations on *is_prime*, with probabilities set to 32, 56, and 80
+  respectively.
 
-.. cpp:function BigInt random_prime(RandomNumberGenerator& rng, \
-   size_t bits, BigInt coprime = 1, size_t equiv = 1, size_t equiv_mod = 2)
+ .. cpp:function:: BigInt random_prime(RandomNumberGenerator& rng, \
+                                       size_t bits, \
+                                       BigInt coprime = 1, \
+                                       size_t equiv = 1, \
+                                       size_t equiv_mod = 2)
 
   Return a random prime number of ``bits`` bits long that is
   relatively prime to ``coprime``, and equivalent to ``equiv`` modulo
   ``equiv_mod``.
-
diff --git a/doc/relnotes/1_11_10.rst b/doc/relnotes/1_11_10.rst
index 9704cc48a..14ff7a3c8 100644
--- a/doc/relnotes/1_11_10.rst
+++ b/doc/relnotes/1_11_10.rst
@@ -1,5 +1,6 @@
 Version 1.11.10, Not Yet Released
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-* Miller-Rabin tests have changed to use a fixed number of iterations,
-  currently set to 20.
+* The Miller-Rabin primality test function now takes a parameter
+  allowing the user to directly specify the maximum false negative
+  probability they are willing to accept.
diff --git a/src/cmd/apps.h b/src/cmd/apps.h
index d72220322..48f1f770e 100644
--- a/src/cmd/apps.h
+++ b/src/cmd/apps.h
@@ -15,24 +15,25 @@ int unimplemented(int argc, char* argv[], const char* what);
 #define DEFINE_APP(cmd) int cmd ## _main(int argc, char* argv[]);
 
 DEFINE_APP(asn1);
+DEFINE_APP(base64);
 DEFINE_APP(bcrypt);
 DEFINE_APP(bzip);
-DEFINE_APP(base64);
 DEFINE_APP(ca);
+DEFINE_APP(cert_verify);
+DEFINE_APP(dsa_sign);
+DEFINE_APP(dsa_verify);
 DEFINE_APP(factor);
 DEFINE_APP(fpe);
 DEFINE_APP(hash);
+DEFINE_APP(is_prime);
 DEFINE_APP(keygen);
-DEFINE_APP(dsa_sign);
-DEFINE_APP(dsa_verify);
-DEFINE_APP(cert_verify);
 DEFINE_APP(ocsp_check);
 DEFINE_APP(pkcs10);
 DEFINE_APP(read_ssh);
 DEFINE_APP(rng);
 DEFINE_APP(self_sig);
+DEFINE_APP(speed);
 DEFINE_APP(tls_client);
 DEFINE_APP(tls_server);
 DEFINE_APP(tls_server_asio);
 DEFINE_APP(x509);
-DEFINE_APP(speed);
diff --git a/src/cmd/factor.cpp b/src/cmd/factor.cpp
index 7a5018d62..5f6d82f8c 100644
--- a/src/cmd/factor.cpp
+++ b/src/cmd/factor.cpp
@@ -100,7 +100,7 @@ std::vector<BigInt> factorize(const BigInt& n_in,
 
    while(n != 1)
       {
-      if(check_prime(n, rng))
+      if(is_prime(n, rng))
          {
          factors.push_back(n);
          break;
diff --git a/src/cmd/main.cpp b/src/cmd/main.cpp
index 92ecc051e..929cdbb4a 100644
--- a/src/cmd/main.cpp
+++ b/src/cmd/main.cpp
@@ -158,6 +158,7 @@ int main(int argc, char* argv[])
       CALL_APP(dsa_sign);
       CALL_APP(dsa_verify);
       CALL_APP(factor);
+      CALL_APP(is_prime);
       CALL_APP(fpe);
       CALL_APP(hash);
       CALL_APP(keygen);
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;
    }
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 87de4aff3..2404dad5a 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -329,17 +329,17 @@ size_t check_powmod(const std::vector<std::string>& args)
    }
 
 /* Make sure that n is prime or not prime, according to should_be_prime */
-size_t check_primetest(const std::vector<std::string>& args,
+size_t is_primetest(const std::vector<std::string>& args,
                        Botan::RandomNumberGenerator& rng)
    {
    BigInt n(args[0]);
    bool should_be_prime = (args[1] == "1");
 
-   bool is_prime = Botan::verify_prime(n, rng);
+   bool is_prime = Botan::is_prime(n, rng);
 
    if(is_prime != should_be_prime)
       {
-      std::cout << "ERROR: verify_prime" << std::endl;
+      std::cout << "ERROR: is_prime" << std::endl;
       std::cout << "n = " << n << std::endl;
       std::cout << is_prime << " != " << should_be_prime << std::endl;
       }
@@ -429,7 +429,7 @@ size_t test_bigint()
       else if(algorithm.find("ModExp") != std::string::npos)
          new_errors = check_powmod(substr);
       else if(algorithm.find("PrimeTest") != std::string::npos)
-         new_errors = check_primetest(substr, rng);
+         new_errors = is_primetest(substr, rng);
       else
          std::cout << "Unknown MPI test " << algorithm << std::endl;