Fix a bug in Miller-Rabin primality testing introduced in 1.8.3

where we chose a single random nonce and tested it repeatedly, rather
than choosing new nonces each time. Reported by Jeff Marrison.

Also remove a pointless comparison (also pointed out by Jeff) and add
an initial test using a witness of 2.

2 files changed, 14 insertions, 6 deletions

diff --git a/doc/relnotes/1_11_9.rst b/doc/relnotes/1_11_9.rst
index de88987eb..9bbeb1ba4 100644
--- a/doc/relnotes/1_11_9.rst
+++ b/doc/relnotes/1_11_9.rst
@@ -1,6 +1,13 @@
-Version 1.11.9, Not Yet Released
+Version 1.11.9, 2014-04-10
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+ * Fix a bug in primality testing introduced in 1.8.3 which caused
+   only a single random base, rather than a sequence of random bases,
+   to be used in the Miller-Rabin test. This increased the probability
+   that a non-prime would be accepted, for instance a 1024 bit number
+   would be incorrectly classed as prime with probability around
+   2^-40. Reported by Jeff Marrison.
+
  * X.509 path validation now returns a set of all errors that occurred
    during validation, rather than immediately returning the first
    detected error. This prevents a seemingly innocuous error (such as
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index e3c673ea5..5946aa994 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -54,10 +54,7 @@ bool MillerRabin_Test::is_witness(const BigInt& a)
          return false;
       }
 
-   if(y != n_minus_1) // fails Fermat test
-      return true;
-
-   return false;
+   return true; // fails Fermat test
    }
 
 /*
@@ -392,17 +389,21 @@ bool primality_test(const BigInt& n,
 
    MillerRabin_Test mr(n);
 
+   if(mr.is_witness(2))
+      return false;
+
    const size_t tests = miller_rabin_test_iterations(n.bits(), level);
 
-   BigInt nonce;
    for(size_t i = 0; i != tests; ++i)
       {
+      BigInt nonce;
       while(nonce < 2 || nonce >= (n-1))
          nonce.randomize(rng, NONCE_BITS);
 
       if(mr.is_witness(nonce))
          return false;
       }
+
    return true;
    }