Add Lucas test from FIPS 186-4

This eliminates an issue identified in the paper
"Prime and Prejudice: Primality Testing Under Adversarial Conditions"
by Albrecht, Massimo, Paterson and Somorovsky

where DL_Group::verify_group with strong=false would accept a composite
q with probability 1/4096, which is exactly as the error bound is
documented, but still unfortunate.

1 files changed, 3 insertions, 24 deletions

diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 586603507..30a0bb141 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -10,6 +10,7 @@
 
 #include <botan/ec_group.h>
 #include <botan/internal/point_mul.h>
+#include <botan/internal/primality.h>
 #include <botan/ber_dec.h>
 #include <botan/der_enc.h>
 #include <botan/oids.h>
@@ -19,12 +20,6 @@
 #include <botan/rng.h>
 #include <vector>
 
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-   #include <botan/system_rng.h>
-#elif defined(BOTAN_HAS_HMAC_DRBG) && defined(BOTAN_HAS_SHA2_32)
-   #include <botan/hmac_drbg.h>
-#endif
-
 namespace Botan {
 
 class EC_Group_Data final
@@ -318,23 +313,7 @@ std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[
          .end_cons()
          .verify_end();
 
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-      System_RNG rng;
-#elif defined(BOTAN_HAS_HMAC_DRBG) && defined(BOTAN_HAS_SHA2_32)
-      /*
-      * This is not ideal because the data is attacker controlled, but
-      * it seems like it would be difficult for someone to come up
-      * with an valid ASN.1 encoding where the prime happened to pass
-      * Miller-Rabin test with exactly the values chosen when
-      * HMAC_DRBG is seeded with the overall data.
-      */
-      HMAC_DRBG rng("SHA-256");
-      rng.add_entropy(bits, len);
-#else
-      Null_RNG rng;
-#endif
-
-      if(p.bits() < 64 || p.is_negative() || (is_prime(p, rng) == false))
+      if(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p))
          throw Decoding_Error("Invalid ECC p parameter");
 
       if(a.is_negative() || a >= p)
@@ -343,7 +322,7 @@ std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[
       if(b <= 0 || b >= p)
          throw Decoding_Error("Invalid ECC b parameter");
 
-      if(order <= 0)
+      if(order <= 0 || !is_bailie_psw_probable_prime(order))
          throw Decoding_Error("Invalid ECC order parameter");
 
       if(cofactor <= 0 || cofactor >= 16)