Extract and test the deterministic part of Miller-Rabin.
This way we test not only that we match expectations for primes and
composites but that the core test correctly reports false witnesses. I
made an initial attempt to gather some interesting test input, but
probably one can do better.
Change-Id: I7c29afb534bd6980ef42a893e86d86bd44af8349
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38164
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index 0be8396..ea3967b 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -2279,6 +2279,32 @@
EXPECT_EQ(1, is_probably_prime_1);
}
+TEST_F(BNTest, MillerRabinIteration) {
+ FileTestGTest(
+ "crypto/fipsmodule/bn/miller_rabin_tests.txt", [&](FileTest *t) {
+ BIGNUMFileTest bn_test(t, /*large_mask=*/0);
+
+ bssl::UniquePtr<BIGNUM> w = bn_test.GetBIGNUM("W");
+ ASSERT_TRUE(w);
+ bssl::UniquePtr<BIGNUM> b = bn_test.GetBIGNUM("B");
+ ASSERT_TRUE(b);
+ bssl::UniquePtr<BN_MONT_CTX> mont(
+ BN_MONT_CTX_new_consttime(w.get(), ctx()));
+ ASSERT_TRUE(mont);
+
+ bssl::BN_CTXScope scope(ctx());
+ BN_MILLER_RABIN miller_rabin;
+ ASSERT_TRUE(bn_miller_rabin_init(&miller_rabin, mont.get(), ctx()));
+ int possibly_prime;
+ ASSERT_TRUE(bn_miller_rabin_iteration(&miller_rabin, &possibly_prime,
+ b.get(), mont.get(), ctx()));
+
+ std::string result;
+ ASSERT_TRUE(t->GetAttribute(&result, "Result"));
+ EXPECT_EQ(result, possibly_prime ? "PossiblyPrime" : "Composite");
+ });
+}
+
TEST_F(BNTest, NumBitsWord) {
constexpr BN_ULONG kOne = 1;
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index c1e60fe..d58a2ac 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -437,6 +437,40 @@
// of the first several odd primes and zero otherwise.
int bn_odd_number_is_obviously_composite(const BIGNUM *bn);
+// A BN_MILLER_RABIN stores state common to each Miller-Rabin iteration. It is
+// initialized within an existing |BN_CTX| scope and may not be used after
+// that scope is released with |BN_CTX_end|. Field names match those in FIPS
+// 186-4, section C.3.1.
+typedef struct {
+ // w1 is w-1.
+ BIGNUM *w1;
+ // m is (w-1)/2^a.
+ BIGNUM *m;
+ // one_mont is 1 (mod w) in Montgomery form.
+ BIGNUM *one_mont;
+ // w1_mont is w-1 (mod w) in Montgomery form.
+ BIGNUM *w1_mont;
+ // w_bits is BN_num_bits(w).
+ int w_bits;
+ // a is the largest integer such that 2^a divides w-1.
+ int a;
+} BN_MILLER_RABIN;
+
+// bn_miller_rabin_init initializes |miller_rabin| for testing if |mont->N| is
+// prime. It returns one on success and zero on error.
+OPENSSL_EXPORT int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin,
+ const BN_MONT_CTX *mont, BN_CTX *ctx);
+
+// bn_miller_rabin_iteration performs one Miller-Rabin iteration, checking if
+// |b| is a composite witness for |mont->N|. |miller_rabin| must have been
+// initialized with |bn_miller_rabin_setup|. On success, it returns one and sets
+// |*out_is_possibly_prime| to one if |mont->N| may still be prime or zero if
+// |b| shows it is composite. On allocation or internal failure, it returns
+// zero.
+OPENSSL_EXPORT int bn_miller_rabin_iteration(
+ const BN_MILLER_RABIN *miller_rabin, int *out_is_possibly_prime,
+ const BIGNUM *b, const BN_MONT_CTX *mont, BN_CTX *ctx);
+
// bn_rshift1_words sets |r| to |a| >> 1, where both arrays are |num| bits wide.
void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num);
diff --git a/crypto/fipsmodule/bn/miller_rabin_tests.txt b/crypto/fipsmodule/bn/miller_rabin_tests.txt
new file mode 100644
index 0000000..437d0f9
--- /dev/null
+++ b/crypto/fipsmodule/bn/miller_rabin_tests.txt
@@ -0,0 +1,322 @@
+# This file contains test vectors for whether B is a Miller-Rabin composite
+# witness for W. W must be odd and B must satisfy 1 <= B <= W-1.
+#
+# The following Python function may be used to check values.
+#
+# def is_miller_rabin_witness(w, b):
+# # Variable names taken from FIPS 186-4 C.3.1 but the algorithm skips a
+# # couple of optimizations in the FIPS formulation.
+# m = w - 1
+# a = 0
+# while m&1 == 0:
+# a += 1
+# m //= 2
+# # b is a composite witness for w iff the following are true:
+# # - b^m != 1 (mod w)
+# # - b^(m*2^j) != -1 (mod w), for 0 <= j < a
+# z = pow(b, m, w)
+# if z == 1:
+# # b^m = 1 (mod w)
+# return False
+# for j in range(a):
+# if z == w-1:
+# # b^(m*2^j) = -1 (mod w)
+# return False
+# z = (z * z) % w
+# # At this point, z is b^(w-1) (mod w). If z is not 1, w has failed the
+# # Fermat test and is composite. If z is 1, the value of z immediately
+# # before it became 1 is a non-trivial root of unity and w is composite.
+# return True
+
+# Exhaustively test a small prime.
+
+Result = PossiblyPrime
+W = 7
+B = 1
+
+Result = PossiblyPrime
+W = 7
+B = 2
+
+Result = PossiblyPrime
+W = 7
+B = 3
+
+Result = PossiblyPrime
+W = 7
+B = 4
+
+Result = PossiblyPrime
+W = 7
+B = 5
+
+Result = PossiblyPrime
+W = 7
+B = 6
+
+
+# Random large inputs which try to cover a few cases. The nontrivial square root
+# case appears to be difficult to hit randomly.
+
+# b^m = w-1
+Result = PossiblyPrime
+W = d6b4ffc7cf70b2a2fc5d6023015875504d40e3dcce7c2e6b762c3de7bb806a5074144e7054198dabf53d23108679ccc541d5a99efeb1d1abaf89e0dbcead2a8b
+B = fabbafdbec6494ddb5ea4bf458536e87082369b0e53a200ed413f3e64b2fddc7c57c565710fbe73fae5b188fce97d8dcca74c2b5d90906c96d3c2c358a735cd
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 52cc61c42b341ad56dc11495e7cb2fe31e506b9e99522efbf44cd7c28468d3833c5e360f3c77b0aa43c0495c4e14665ab0d7cee9294c722f0de47d4401828401
+B = 3bdc9639c0fc2e77ab48d46e0b4ac6529c11c900e8fe4d82d75767c0556feb23d3f42d4924d16876a743feb386b7b84c7fd16a6c252f662faf0024d19972e62f
+
+# b^m = w-1
+Result = PossiblyPrime
+W = cff9897aa7dce0f2afad262b2de57d301305de717f3539c537c4ce062f8cb70df13fbc1eb4a3b9f0958a8810d1ca9042b4f23334b285a15fee3fc66498761d4b
+B = 9ceb43132fddf9ee4104ea1cb3eb2253c1d7f803f05f0305de9e31a17dd75832f47b8bf189a9b7ca0905f2a7470d9c6349080f481ff1708696fa12d972e7d7ba
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 67d1825dad5344170e65247a87aef1634a1b32bdc22f2f04d9d2959767bb5a27610fba55cd607e0f9fdd9fbb0f7f98e40d5e1eb2f52318fb5be4dbfd30d38861
+B = 260fb14724ff80984736859d8755ee98b25bcb56db9fde1db001a1e1273374034c5b75fd60b3710c7a08ce7d390776f010f384d4e32943cf0c477497d53e9e05
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = ad0bc85b58aaa204177aa9431a40929beb1cbea2dd6f66a25cc54600013213b225ba881805661df43f4208965ada7aacc8095d07d3cbef1a7bbfaae8b745f731
+B = 3d9310f20e9c80269fa6830c7e1a6f02fc5c58646001a9ef6b8b3e496602ff22c3dcb2ddb6a221723fc1722ce237fb46f7a7bb2945e415c8839b15a972f076c9
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = b25c917f55f6c7b596921daba919f35039e5d805119c1587e99849dd7104460c86214f162a6f17aea847bc7f3859e59f2991d457059511972ef373d4bc75e309
+B = a1f10b261dee84619b0423201d46af19eef9ec0612cf947c4d5c36c0c4b28207f75967e69452eabad0a5dcd28f27f7a8a7ed9c8b3e5026c6e0ba5634d94c2d44
+
+# b^m = 1
+Result = PossiblyPrime
+W = d3eeb0eff05b6992e9fa61b02755e155f4aae28c6e45ddb874edd86acdd2d83d18a20e0e00d8b8bc94b92d14fc3f41ced6ababe8ac98c7730c075dbe0f699369
+B = 6b7717269c6225203681a1cacec87cacd83003ec6e9e3f04effcc4f86634770c0860e1f2770b8f303719a44949664a1094205a99d95a0856758fed66d690105e
+
+# b^m = 1
+Result = PossiblyPrime
+W = 64561b8d9aa50340c3a01ccb3e6e17f5023513661c012be288f3900a3ca76890e67290b9560fa1d480f9d2aacccca581b5690636665f243fa13aff5d0bff12d3
+B = 1f5ff70d3d60671ebc5fbfca731898a04438053dbc3c841e6335f487e457d92d9efb5d506d5bef6872d58d12b9a41c950bfc38d12ed977c90eacdd6535b811a0
+
+# b^m = 1
+Result = PossiblyPrime
+W = 69c63fbf44df21b0ed0ee929a740c12d1f3f064da0dcd9d509f31fa45fa27d1a759ab5a9f6f1040d7ee90a0b1e68f779273c41ea1c1198fd547ff6bd70c7e787
+B = 5f7996a9bbfd8fd88e472220b70077bfdacdd63d88885134431f024c2acb7126827b174eb093eb5313f07bb5461de9b0feb7d77ca2c39c2a323a150f33ea525f
+
+# End of iteration
+Result = Composite
+W = 28cc3e08c44571c6dcb98a9ab8b4f3e2b16e1f884997d94a3188bcbb7f1b7cdaecdae8329c013ec8f75dc00004da0039943e4262cd080b16a42910102e00dddb
+B = 512061ab1c69931c2fa0bb89d8d09f3c9209230bf927ddd6fb6a72075f967ed3c4dbb5f437bf4d31ca7344782b22011ad56609dc19aed65319bababfc13dd7
+
+# End of iteration
+Result = Composite
+W = 4eeb7b4d371c45fe8586fee3b1efd792176b70f6cc2698dfa1dd028366626febe0199c3c5f77a5c3cad0057a04767383051d41965255d03681b2a37edad34a9b
+B = 4afc2e85f84017b3fd6967a227eb74c8297b40ea02733d9513bff9b3f01081963f25872f4254afc4e9321eea35b2a1e42eadb186fcc84f2f30f4a994350b93b8
+
+# End of iteration
+Result = Composite
+W = 8e35a959555dd2eb66c65cee3c264071d20671f159e1f9896f1d0ceb041905fcf053eacc189de317c3ee6f93901223cbf30d5b7ddbbdab981790e2f6397e6803
+B = 44c0153759309ec4e5b1e59d57c1b126545ef7ea302b6e43561df4d16068b922389d6924f01c945d9080d1f93a0732599bdedae72d6d590839dc0884dd860441
+
+
+# 0x6c1 = 1729 = 7 * 13 * 19 is a Fermat pseudoprime.
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = b8
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 111
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 11d
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 19c
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 223
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 3aa
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 653
+
+
+# 1729 has a number of false witnesses.
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 78
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = eb
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 178
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 178
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 1aa
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 271
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 2b2
+
+
+# 1 and W-1 are always nonwitnesses.
+Result = PossiblyPrime
+W = 6c1
+B = 1
+
+Result = PossiblyPrime
+W = 6c1
+B = 6c0
+
+
+# https://kconrad.math.uconn.edu/blurbs/ugradnumthy/millerrabin.pdf, examples
+# 3.1 and 3.2 has a complete list of false witnesses for 65 = 0x41 and
+# 85 = 0x55.
+
+# b^m = 1
+Result = PossiblyPrime
+W = 41
+B = 1
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 8
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 12
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 2f
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 39
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 41
+B = 40
+
+# b^m = 1
+Result = PossiblyPrime
+W = 55
+B = 1
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = d
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 26
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 2f
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 48
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 55
+B = 54
+
+# Other witnesses for 65 and 85 will report composite:
+
+# Found non-trivial square root
+Result = Composite
+W = 41
+B = 2c
+
+# End of iteration
+Result = Composite
+W = 41
+B = 16
+
+# End of iteration
+Result = Composite
+W = 41
+B = 14
+
+# End of iteration
+Result = Composite
+W = 41
+B = 2
+
+# End of iteration
+Result = Composite
+W = 41
+B = 3a
+
+# End of iteration
+Result = Composite
+W = 55
+B = 40
+
+# End of iteration
+Result = Composite
+W = 55
+B = 7
+
+# End of iteration
+Result = Composite
+W = 55
+B = 23
+
+# End of iteration
+Result = Composite
+W = 55
+B = 2e
+
+# End of iteration
+Result = Composite
+W = 55
+B = 2a
diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index c030c9e..1dd0870 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -594,6 +594,113 @@
return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime);
}
+int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont,
+ BN_CTX *ctx) {
+ // This function corresponds to steps 1 through 3 of FIPS 186-4, C.3.1.
+ const BIGNUM *w = &mont->N;
+ // Note we do not call |BN_CTX_start| in this function. We intentionally
+ // allocate values in the containing scope so they outlive this function.
+ miller_rabin->w1 = BN_CTX_get(ctx);
+ miller_rabin->m = BN_CTX_get(ctx);
+ miller_rabin->one_mont = BN_CTX_get(ctx);
+ miller_rabin->w1_mont = BN_CTX_get(ctx);
+ if (miller_rabin->w1 == NULL ||
+ miller_rabin->m == NULL ||
+ miller_rabin->one_mont == NULL ||
+ miller_rabin->w1_mont == NULL) {
+ return 0;
+ }
+
+ // See FIPS 186-4, C.3.1, steps 1 through 3.
+ if (!bn_usub_consttime(miller_rabin->w1, w, BN_value_one())) {
+ return 0;
+ }
+ miller_rabin->a = BN_count_low_zero_bits(miller_rabin->w1);
+ if (!bn_rshift_secret_shift(miller_rabin->m, miller_rabin->w1,
+ miller_rabin->a, ctx)) {
+ return 0;
+ }
+ miller_rabin->w_bits = BN_num_bits(w);
+
+ // Precompute some values in Montgomery form.
+ if (!bn_one_to_montgomery(miller_rabin->one_mont, mont, ctx) ||
+ // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
+ // with a subtraction. (|one_mont| cannot be zero.)
+ !bn_usub_consttime(miller_rabin->w1_mont, w, miller_rabin->one_mont)) {
+ return 0;
+ }
+
+ return 1;
+}
+
+int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin,
+ int *out_is_possibly_prime, const BIGNUM *b,
+ const BN_MONT_CTX *mont, BN_CTX *ctx) {
+ // This function corresponds to steps 4.3 through 4.5 of FIPS 186-4, C.3.1.
+ int ret = 0;
+ BN_CTX_start(ctx);
+
+ // Step 4.3. We use Montgomery-encoding for better performance and to avoid
+ // timing leaks.
+ const BIGNUM *w = &mont->N;
+ BIGNUM *z = BN_CTX_get(ctx);
+ if (z == NULL ||
+ !BN_mod_exp_mont_consttime(z, b, miller_rabin->m, w, ctx, mont) ||
+ !BN_to_montgomery(z, z, mont, ctx)) {
+ goto err;
+ }
+
+ // loop_done is all ones if the loop has completed and all zeros otherwise.
+ crypto_word_t loop_done = 0;
+ // is_possibly_prime is all ones if we have determined |b| is not a composite
+ // witness for |w|. This is equivalent to going to step 4.7 in the original
+ // algorithm.
+ crypto_word_t is_possibly_prime = 0;
+
+ // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still
+ // possibly prime.
+ loop_done = BN_equal_consttime(z, miller_rabin->one_mont) |
+ BN_equal_consttime(z, miller_rabin->w1_mont);
+ loop_done = 0 - loop_done; // Make it all zeros or all ones.
+ is_possibly_prime = loop_done; // Go to step 4.7 if |loop_done|.
+
+ // Step 4.5.
+ //
+ // To avoid leaking |a|, we run the loop to |w_bits| and mask off all
+ // iterations once |j| = |a|.
+ for (int j = 1; j < miller_rabin->w_bits; j++) {
+ loop_done |= constant_time_eq_int(j, miller_rabin->a);
+
+ // Step 4.5.1.
+ if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
+ goto err;
+ }
+
+ // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite
+ // witness.
+ crypto_word_t z_is_w1_mont =
+ BN_equal_consttime(z, miller_rabin->w1_mont) & ~loop_done;
+ z_is_w1_mont = 0 - z_is_w1_mont; // Make it all zeros or all ones.
+ loop_done |= z_is_w1_mont;
+ is_possibly_prime |= z_is_w1_mont; // Go to step 4.7 if |z_is_w1_mont|.
+
+ // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
+ // was not -1. There are no non-trivial square roots of 1 modulo a prime, so
+ // w is composite and we may exit in variable time.
+ if (BN_equal_consttime(z, miller_rabin->one_mont) & ~loop_done) {
+ assert(!is_possibly_prime);
+ break;
+ }
+ }
+
+ *out_is_possibly_prime = is_possibly_prime & 1;
+ ret = 1;
+
+err:
+ BN_CTX_end(ctx);
+ return ret;
+}
+
int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w,
int iterations, BN_CTX *ctx, int do_trial_division,
BN_GENCB *cb) {
@@ -646,36 +753,13 @@
// See C.3.1 from FIPS 186-4.
int ret = 0;
- BN_MONT_CTX *mont = NULL;
BN_CTX_start(ctx);
- BIGNUM *w1 = BN_CTX_get(ctx);
- if (w1 == NULL ||
- !bn_usub_consttime(w1, w, BN_value_one())) {
- goto err;
- }
-
- // Write w1 as m * 2^a (Steps 1 and 2).
- int w_len = BN_num_bits(w);
- int a = BN_count_low_zero_bits(w1);
- BIGNUM *m = BN_CTX_get(ctx);
- if (m == NULL ||
- !bn_rshift_secret_shift(m, w1, a, ctx)) {
- goto err;
- }
-
- // Montgomery setup for computations mod w. Additionally, compute 1 and w - 1
- // in the Montgomery domain for later comparisons.
BIGNUM *b = BN_CTX_get(ctx);
- BIGNUM *z = BN_CTX_get(ctx);
- BIGNUM *one_mont = BN_CTX_get(ctx);
- BIGNUM *w1_mont = BN_CTX_get(ctx);
- mont = BN_MONT_CTX_new_consttime(w, ctx);
- if (b == NULL || z == NULL || one_mont == NULL || w1_mont == NULL ||
- mont == NULL ||
- !bn_one_to_montgomery(one_mont, mont, ctx) ||
- // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
- // with a subtraction. (|one_mont| cannot be zero.)
- !bn_usub_consttime(w1_mont, w, one_mont)) {
+ BN_MONT_CTX *mont = BN_MONT_CTX_new_consttime(w, ctx);
+ BN_MILLER_RABIN miller_rabin;
+ if (b == NULL || mont == NULL ||
+ // Steps 1-3.
+ !bn_miller_rabin_init(&miller_rabin, mont, ctx)) {
goto err;
}
@@ -713,64 +797,22 @@
for (int i = 1; (i <= BN_PRIME_CHECKS_BLINDED) |
constant_time_lt_w(uniform_iterations, iterations);
i++) {
+ // Step 4.1-4.2
int is_uniform;
- if (// Step 4.1-4.2
- !bn_rand_secret_range(b, &is_uniform, 2, w1) ||
- // Step 4.3
- !BN_mod_exp_mont_consttime(z, b, m, w, ctx, mont)) {
- goto err;
+ if (!bn_rand_secret_range(b, &is_uniform, 2, miller_rabin.w1)) {
+ goto err;
}
uniform_iterations += is_uniform;
- // loop_done is all ones if the loop has completed and all zeros otherwise.
- crypto_word_t loop_done = 0;
- // next_iteration is all ones if we should continue to the next iteration
- // (|b| is not a composite witness for |w|). This is equivalent to going to
- // step 4.7 in the original algorithm.
- crypto_word_t next_iteration = 0;
-
- // Step 4.4. If z = 1 or z = w-1, mask off the loop and continue to the next
- // iteration (go to step 4.7).
- loop_done = BN_equal_consttime(z, BN_value_one()) |
- BN_equal_consttime(z, w1);
- loop_done = 0 - loop_done; // Make it all zeros or all ones.
- next_iteration = loop_done; // Go to step 4.7 if |loop_done|.
-
- // Step 4.5. We use Montgomery-encoding for better performance and to avoid
- // timing leaks.
- if (!BN_to_montgomery(z, z, mont, ctx)) {
+ // Steps 4.3-4.5
+ int is_possibly_prime = 0;
+ if (!bn_miller_rabin_iteration(&miller_rabin, &is_possibly_prime, b, mont,
+ ctx)) {
goto err;
}
- // To avoid leaking |a|, we run the loop to |w_len| and mask off all
- // iterations once |j| = |a|.
- for (int j = 1; j < w_len; j++) {
- loop_done |= constant_time_eq_int(j, a);
-
- // Step 4.5.1.
- if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
- goto err;
- }
-
- // Step 4.5.2. If z = w-1 and the loop is not done, run through the next
- // iteration.
- crypto_word_t z_is_w1_mont = BN_equal_consttime(z, w1_mont) & ~loop_done;
- z_is_w1_mont = 0 - z_is_w1_mont; // Make it all zeros or all ones.
- loop_done |= z_is_w1_mont;
- next_iteration |= z_is_w1_mont; // Go to step 4.7 if |z_is_w1_mont|.
-
- // Step 4.5.3. If z = 1 and the loop is not done, w is composite and we
- // may exit in variable time.
- if (BN_equal_consttime(z, one_mont) & ~loop_done) {
- assert(!next_iteration);
- break;
- }
- }
-
- if (!next_iteration) {
+ if (!is_possibly_prime) {
// Step 4.6. We did not see z = w-1 before z = 1, so w must be composite.
- // (For any prime, the value of z immediately preceding 1 must be -1.
- // There are no non-trivial square roots of 1 modulo a prime.)
*out_is_probably_prime = 0;
ret = 1;
goto err;
diff --git a/sources.cmake b/sources.cmake
index 8dc65e6..db14456 100644
--- a/sources.cmake
+++ b/sources.cmake
@@ -47,6 +47,7 @@
crypto/evp/scrypt_tests.txt
crypto/fipsmodule/aes/aes_tests.txt
crypto/fipsmodule/bn/bn_tests.txt
+ crypto/fipsmodule/bn/miller_rabin_tests.txt
crypto/fipsmodule/ec/ec_scalar_base_mult_tests.txt
crypto/fipsmodule/ec/p256-x86_64_tests.txt
crypto/fipsmodule/ecdsa/ecdsa_sign_tests.txt
