1 files changed, 322 insertions, 0 deletions
diff --git a/src/crypto/fipsmodule/bn/miller_rabin_tests.txt b/src/crypto/fipsmodule/bn/miller_rabin_tests.txt
new file mode 100644
index 00000000..437d0f97
--- /dev/null
+++ b/src/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