Add some Miller-Rabin tests from Wycheproof.
Wycheproof's primality testing vectors include worst case values where
1/4 of witnesses are false. Add some test cases for true and false
witnesses.
Change-Id: I66050fd34694ca1cc145f950500d110c22d8bd42
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/39194
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/miller_rabin_tests.txt b/crypto/fipsmodule/bn/miller_rabin_tests.txt
index 437d0f9..cc1c91d 100644
--- a/crypto/fipsmodule/bn/miller_rabin_tests.txt
+++ b/crypto/fipsmodule/bn/miller_rabin_tests.txt
@@ -320,3 +320,87 @@
Result = Composite
W = 55
B = 2a
+
+# W below is composite, but it is one of the worst case scenarios for
+# Miller-Rabin, from Wycheproof tests. 1/4 of witnesses report the value is
+# prime. Test that we correctly classify false and true witnesses.
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 379c6027f818b5164bc13dff5e996ec7210976f33570d5c60275918b8988d97a63bb6582af85682c45667a8b94b7acab4d919ede00f5bd2ba7abc8634d66f8875fd930f35ec8013d37b958e65f07de015c0574e64198d73aab5466f3a971b74830b7f1671cb9277fbc95c1ba8c29dc903d8cea1b74c22ab9164f9c438ab9ba7d9919f832e40c3e36faca7343e2314669b0104d9c4f2e1b011cdbd9c686baef0
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 3cc4b644965b2133caffc2bb6258b1ecd5b586b900a09b010382fcef709e4cd37ee3e3182bf8d393c1ab6f9a933d46338b3d960923d8c9607c2b2763d5680230a2bc0c91138e9d0ecb35e7154a06aaa902d34b9b14964b81f4d8232641492d83b22cd805a115e75ddd8e63b864c00e4c90ba36a41e7966e97e063a60a6a6cfd53e1f62a57852c7443e88dcf6245557a4b65494c3e88e466ad75316aaa9727def
+
+# b^m = 1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 40c03b6ba22bd62c0379b1c36dfccd34d61e3d15f7af1d5f6a60ab972a9d0e956e2bb9e275294e0f1c879eb7a4555443429c99a8d74f7bd359a1046ac30072c04b0e2cbd005be15ff4ce0c93276de2c513fbc5771b5059904a87f180530f6773498114b5aaf70da01967d8294742e451df6377dd5e64b2a8968f4ba61b51a154317d63958ff3788defbeeebee21af5027c2291e8c5df8c0b66770d91b683cffe
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 3c7c71b84f0c6c3817f57511946315cec7d0120a9c30ceabda801fbaec329a8f10c7b9f0ae90a3dada9885bf73a3cabed86784af9682f3dea50a7817f65cfc9190cf997f12784223c4965ed6e52a1be26d4dde31741cd3d1a2e2f3a74040d0f3868eef849727aa855f66c94791194ad5d360298364e2de9ca9288e6423f644b01d52e1bd66a9f7f00bd7995a9ca2ed16f40e902852c6250a3b52bbbf5bfd33e8
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 36e6aa9acb399a50f52be0324dcef05f3cff3117f94538f6d0952b7d7be88ba4dc75d843ff7ff775e11f55c86ba6b2a6ddebd8850c33424b4d35c66321af426662e7074f0a2409a9ccf1c66ef7d823efc8240b8f3c7e9e8dd65a64e8a3ca5b26695ef17171ffe136c0593b179414c5b5ad0d66f2a25146c38b2f97e60b0472ed72de34bff1b6ac186f23645a1bbe909cdfc2b2d861eb44931568f1bb117d8a0c
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 278f2215d3ab836043fbfa472216bbdcedb775a6a0ed711754d05aa75089a9e5d8201e113d68656f37381e44483cd365f5d383bdca5ae8d1f2e6575d7873851cfff0e12b1cfe100a04cb300cbd924353fcbd3307d01242cf6a5e86e752c6f4586bcabf48b018bb97e65c3ed409fd6f67f98987517356d88344b3c8945ccd753148a37b648dd2db44d19522a69a9ad8eb23edc55340e85a198abf179ad731db41
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = afa1478bebbfe1157568f4ae53549b4c3a6a8771b816970bfac6ce5c8b962231db7a41da4d5f1d8bf504dcfe440325b54e1888bdae344eb969436a35e5c6ce5300d46313cb2fcb57fc83305f65f53d392de400e9231cbbc2ac8243defcaf7063c632b9601a81d83138274702ff336d727d3e82ccacce069843ac9c1c590c772c8c586b65c7085a1df5a47fc960d4098a22418b41f0062c77b5d55d17149d167
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 10f7030590b629e0313a61bdf46936a1f25db91b2b421f7ebb671f7844c22561b44b2f7699db61e5228ebb5817afad416325f9439eff7a82d8a630c504de12eaa44d97c79ee56e726ae74ee0b472f0d5fa8f20aee426e689cd33dd084f96bf4d928a21e815f7e8aaca4a5752f39c4a76bdfaa8227dc05d0dfa885d8b26d46fbcbf0d2e0d999d2c31ad84c306c9126539dbdf447f8dc707d29c7fa8021a767668
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 97dbb6a55c039ec926aaa5ff15a2917a2b4cafc3ca07c4c6b05f931d86c9bf60ee05cbbace194e5ca97682ec67c36394018d68c3536fbf13b50f8a7e31eaed87307759a0a48c6c58d21bc7c38b878c53db5d7a8e1fdd81abefc50470a3800852e74d76fdd1933e45f39ee97b8efb68837721890d867b32a894dd0ceb4c5844a05d384145865c10973ce748ccdd8fee73f1bf8611ce0535430b6b98fb36cad7a
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 225f58add44ed2b0a64a1d8452866d0f3c0cd45c8375e1bb33c188915c77fa11b81250b920245dda7f6126e5e0c79e6f98f89dc15db86394cf81b44f0d801e613fa4d5c6fef66fa31f26cfe6153f2e8159aad6b0351dcc0e93f9a68f649b2a77cff747b605b542d22419166befebec6cde3201e3c0cacaa2bc9d87073b8d1f1aa2b114d61de45ac8b0ad2141b43434a629ef284cd999fd82b310db7c57cf5c81
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 2780926c9cf7c1eb2aaa935d90b6d4dea44eeefdfcf9ccd4a33feb215e3a1cb2d358136a490fed18403947f3d98807819737c66e12d42c3cc8c0e246b96b3c3b0795ab875fbaf668b81b5b05bf23e258ea00a0a140a790f76e04ab619800b7597f614ffc1a1c94be2f3f1a71d64eb47d98e4653d76eabedacff3a97ecf590e6a1fd55096b7bc9314629f698d0fbe9b01a1f2bc0bf3a2c097f99f1fd222b52ed2
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 129cc5b0d9f8001b3895f1fcb4833779763636aeeeb3f980e63ea506202e6bde868444b6a58ff1dca08625f025a7e95a5eaaf1a8899eee640e3f05fbdb2867e2483bdc27c87b58684416e521c107f3667ed8dd23f0381edab767c5205a4378118bc011947cb6bdfe3fa4af50b8de876b555c9a0b2b0dae01261847f63e1e0cac2d032530bf19d5da60a04dfe22ce6343f60defbb94ccf0bdf010f89a4029720
+
+# b^m = 1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 4e2a47cf67c3331b1e9976f583f6339cf76a8d48682d01355c25b2aed90c5544e737ecfa849c17d27a64fad7e659ef48df9a3ac0410e5c7ca8d087fc3a3ba23e5a3f000be009fcc8227ead28158c5b5d66f2efb47111638ef61cea4984de42fbd476bc2236ad02154d3ce85805c45e49d16b496e313a4052a37d4b88a3b13e598d2074a3e36a37e90278601f2b2305e034f9bf3aea8e939c3ba274e8ff4d8a14
+
+# b^m = 1
+Result = PossiblyPrime
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 2455c4ab826e2ae72708a8ff51348ce4821cb86fa89e298c751c1754211c63b2e9a712d40f0235f310606fcf296726a86973f19f890d571f5b90f026e8d24d07bc0478a3c1333171587387f1f7fe4a770b593216f2743318aabacb3320c40a4e52b9f409e1176fe8db099e93a7991eb8568168e2e486fa5aa228bb1dce9df3290ef13fd21c331479bb0f8b7a7e7f03c5211ae8cc46fa4d0f46e86b2dadeddd5b
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 9951c2c02dd7deedce29bd0c78dd80066b1d69c0e6fe4a17f7d03c6a640d866d01fc8214bafb6737efd93d80a35b8993f5367ce287459b07954e9771ffbc72ccdd812d26a9bf4be0292a24eb5c3b56f09619b1c1b481f7566f7e50e65f69f5feb591bd107fec72a783429dbde6e2607f3db2c58d4b070a45b4d6b43537e19942ce890b04ae1e91069c04a96ed03ddb2f4fc456f136b98102c70a15700dbd911
+
+# End of iteration
+Result = Composite
+W = 550fda19f97cdfbd13930911ef6e9e1cb2b7b5215a35c215d51ebffeb435642174cbe998f4451bde2d4bd2ce92ab5b9493b657f1d77d9ad4d348550247b903906109c608ecba7f88c239c76f0afc231e7f1ac1cee87b4c34448a16f7979ff4c18e65e05d5a86909615fe56587576962a2cb3ba467d9806445a0f039907601af77ba7d07578eff612364fbcac11d35e243734aa6d9a6cdcf912a2dd0a12ba7e87
+B = 4cb8217d229d5f95f6d94807a99363823655d6bba6bdafa4f0dbfe7a5c538aa79c918710aad4f55caaee5ab405ebdcef29dfb76cae99fca8d5a955b6315f71a3cb2d69a217ff45aed66ba87cdc5c0de5d512c6dd12e641e9fe6a2557dd2f03bf3a18650ff139efa179f0fbe69cbb4b54e50d13177bfe7bb90de36b548d5ccfef74b05d3c08a7e2a3bb4dc8d7eb338a7a1b068c433ea204d171eda5e7c6b6722c
