Add some tests of Miller-Rabin to cryptsuite.

I'm about to rewrite the Miller-Rabin testing code, so let's start by
introducing a test suite that the old version passes, and then I can
make sure the new one does too.

6 files changed, 112 insertions, 8 deletions

diff --git a/keygen/millerrabin.c b/keygen/millerrabin.c
index 3358bc51..19ca1bd3 100644
--- a/keygen/millerrabin.c
+++ b/keygen/millerrabin.c
@@ -135,17 +135,19 @@ void miller_rabin_free(MillerRabin *mr)
     sfree(mr);
 }
 
-struct mr_result {
-    bool passed;
-    bool potential_primitive_root;
-};
-
-static struct mr_result miller_rabin_test_inner(MillerRabin *mr, mp_int *w)
+/*
+ * The main internal function that implements a single M-R test.
+ *
+ * Expects the witness integer to be in Montgomery representation.
+ * (Since in live use witnesses are invented at random, this imposes
+ * no extra cost on the callers, and saves effort in here.)
+ */
+static struct mr_result miller_rabin_test_inner(MillerRabin *mr, mp_int *mw)
 {
     /*
      * Compute w^q mod p.
      */
-    mp_int *wqp = monty_pow(mr->mc, w, mr->q);
+    mp_int *wqp = monty_pow(mr->mc, mw, mr->q);
 
     /*
      * See if this is 1, or if it is -1, or if it becomes -1
@@ -175,6 +177,19 @@ static struct mr_result miller_rabin_test_inner(MillerRabin *mr, mp_int *w)
     return result;
 }
 
+/*
+ * Wrapper on miller_rabin_test_inner for the convenience of
+ * testcrypt. Expects the witness integer to be literal, so we
+ * monty_import it before running the real test.
+ */
+struct mr_result miller_rabin_test(MillerRabin *mr, mp_int *w)
+{
+    mp_int *mw = monty_import(mr->mc, w);
+    struct mr_result result = miller_rabin_test_inner(mr, mw);
+    mp_free(mw);
+    return result;
+}
+
 bool miller_rabin_test_random(MillerRabin *mr)
 {
     mp_int *mw = mp_random_in_range(mr->two, mr->pm1);
diff --git a/sshkeygen.h b/sshkeygen.h
index dc0024b9..fae6fa83 100644
--- a/sshkeygen.h
+++ b/sshkeygen.h
@@ -94,6 +94,14 @@ typedef struct MillerRabin MillerRabin;
 MillerRabin *miller_rabin_new(mp_int *p);
 void miller_rabin_free(MillerRabin *mr);
 
+/* Perform a single Miller-Rabin test, using a specified witness value.
+ * Used in the test suite. */
+struct mr_result {
+    bool passed;
+    bool potential_primitive_root;
+};
+struct mr_result miller_rabin_test(MillerRabin *mr, mp_int *w);
+
 /* Perform a single Miller-Rabin test, using a random witness value. */
 bool miller_rabin_test_random(MillerRabin *mr);
 
diff --git a/test/cryptsuite.py b/test/cryptsuite.py
index c4df264f..2993dbd4 100755
--- a/test/cryptsuite.py
+++ b/test/cryptsuite.py
@@ -1188,6 +1188,73 @@ class keygen(MyTestBase):
         self.assertEqual(pockle_add_prime(po, 1, [2], 1),
                          'POCKLE_PRIME_SMALLER_THAN_2')
 
+    def testMillerRabin(self):
+        # A prime congruent to 3 mod 4, so M-R can only do one
+        # iteration: either a^{(p-1)/2} == +1, or -1. Either counts as
+        # a pass; the latter also means the number is potentially a
+        # primitive root.
+        n = 0xe76e6aaa42b5d7423aa4da5613eb21c3
+        mr = miller_rabin_new(n)
+        self.assertEqual(miller_rabin_test(mr, 2), "passed+ppr")
+        self.assertEqual(miller_rabin_test(mr, 4), "passed")
+
+        # The 'potential primitive root' test only means that M-R
+        # didn't _rule out_ the number being a primitive root, by
+        # finding that any of the powers _it tested_ less than n-1
+        # came out to be 1. In this case, 2 really is a primitive
+        # root, but since 13 | n-1, the 13th powers mod n form a
+        # multiplicative subgroup. So 2^13 is not a primitive root,
+        # and yet, M-R can't tell the difference, because it only
+        # tried the exponent (n-1)/2, not the actual counterexample
+        # (n-1)/13.
+        self.assertEqual(miller_rabin_test(mr, 2**13), "passed+ppr")
+
+        # A prime congruent to 1 mod a reasonably large power of 2, so
+        # M-R has lots of scope to have different things happen. 3 is
+        # a primitive root, so we expect that 3, 3^2, 3^4, ..., 3^256
+        # should all pass for different reasons, with only the first
+        # of them returning passed+ppr.
+        n = 0xb1b65ebe489ff0ab4597bb67c3d22d01
+        mr = miller_rabin_new(n)
+        w = 3
+        self.assertEqual(miller_rabin_test(mr, w), "passed+ppr")
+        for i in range(1, 10):
+            w = w * w % n
+            self.assertEqual(miller_rabin_test(mr, w), "passed")
+
+        # A prime with an _absurdly_ large power-of-2 factor in its
+        # multiplicative group.
+        n = 0x600000000000000000000000000000000000000000000001
+        mr = miller_rabin_new(n)
+        w = 10
+        self.assertEqual(miller_rabin_test(mr, w), "passed+ppr")
+        for i in range(1, 200):
+            w = w * w % n
+            self.assertEqual(miller_rabin_test(mr, w), "passed")
+
+        # A blatantly composite number. But we still expect to see a
+        # pass if we give the witness 1 (which will give a maximal
+        # trailing string of 1s), or -1 (which will give -1 when
+        # raised to the maximal odd factor of n-1, or indeed any other
+        # odd power).
+        n = 0x1010101010101010101010101010101
+        mr = miller_rabin_new(n)
+        self.assertEqual(miller_rabin_test(mr, 1), "passed")
+        self.assertEqual(miller_rabin_test(mr, n-1), "passed")
+        self.assertEqual(miller_rabin_test(mr, 2), "failed")
+
+        # A Carmichael number, as a proper test that M-R detects
+        # things the Fermat test would not.
+        #
+        # (Its prime factorisation is 26823115100268314289505807 *
+        # 53646230200536628579011613 * 80469345300804942868517419,
+        # which is enough to re-check its Carmichaelness.)
+        n = 0xffffffffffffffffcf8032f3e044b4a8b1b1bf0b526538eae953d90f44d65511
+        mr = miller_rabin_new(n)
+        self.assertEqual(miller_rabin_test(mr, 16), "passed")
+        assert(pow(2, n-1, n) == 1) # Fermat test would pass, but ...
+        self.assertEqual(miller_rabin_test(mr, 2), "failed") # ... this fails
+
 class crypt(MyTestBase):
     def testSSH1Fingerprint(self):
         # Example key and reference fingerprint value generated by
diff --git a/test/testcrypt.py b/test/testcrypt.py
index 686302c8..66611ed3 100644
--- a/test/testcrypt.py
+++ b/test/testcrypt.py
@@ -235,7 +235,7 @@ def make_retval(rettype, word, unpack_strings):
     elif rettype == "boolean":
         assert word == b"true" or word == b"false"
         return word == b"true"
-    elif rettype == "pocklestatus":
+    elif rettype in {"pocklestatus", "mr_result"}:
         return word.decode("ASCII")
     raise TypeError("Can't deal with return value {!r} of type {!r}"
                     .format(word, rettype))
diff --git a/testcrypt.c b/testcrypt.c
index c5c66b4b..1b875c2b 100644
--- a/testcrypt.c
+++ b/testcrypt.c
@@ -94,6 +94,7 @@ uint64_t prng_reseed_time_ms(void)
     X(pcs, PrimeCandidateSource *, pcs_free(v))                         \
     X(pgc, PrimeGenerationContext *, primegen_free_context(v))          \
     X(pockle, Pockle *, pockle_free(v))                                 \
+    X(millerrabin, MillerRabin *, miller_rabin_free(v))                 \
     /* end of list */
 
 typedef struct Value Value;
@@ -707,6 +708,16 @@ static void return_pocklestatus(strbuf *out, PockleStatus status)
     }
 }
 
+static void return_mr_result(strbuf *out, struct mr_result result)
+{
+    if (!result.passed)
+        strbuf_catf(out, "failed\n");
+    else if (!result.potential_primitive_root)
+        strbuf_catf(out, "passed\n");
+    else
+        strbuf_catf(out, "passed+ppr\n");
+}
+
 static void return_val_string_asciz_const(strbuf *out, const char *s)
 {
     strbuf *sb = strbuf_new();
@@ -1370,6 +1381,7 @@ typedef key_components *TD_keycomponents;
 typedef const PrimeGenerationPolicy *TD_primegenpolicy;
 typedef struct mpint_list TD_mpint_list;
 typedef PockleStatus TD_pocklestatus;
+typedef struct mr_result TD_mr_result;
 typedef Argon2Flavour TD_argon2flavour;
 typedef FingerprintType TD_fptype;
 
diff --git a/testcrypt.h b/testcrypt.h
index 2e6e993b..7e0ef3cf 100644
--- a/testcrypt.h
+++ b/testcrypt.h
@@ -297,6 +297,8 @@ FUNC2(void, pockle_release, val_pockle, uint)
 FUNC2(pocklestatus, pockle_add_small_prime, val_pockle, val_mpint)
 FUNC4(pocklestatus, pockle_add_prime, val_pockle, val_mpint, mpint_list, val_mpint)
 FUNC2(val_string, pockle_mpu, val_pockle, val_mpint)
+FUNC1(val_millerrabin, miller_rabin_new, val_mpint)
+FUNC2(mr_result, miller_rabin_test, val_millerrabin, val_mpint)
 
 /*
  * Miscellaneous.