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, 15 insertions, 0 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 495907d1a..5283c893c 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -341,6 +341,21 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
       m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
    }
 
+void BigInt::ct_cond_assign(bool predicate, BigInt& other)
+   {
+   const size_t t_words = size();
+   const size_t o_words = other.size();
+
+   const size_t r_words = std::max(t_words, o_words);
+
+   const word mask = CT::expand_mask<word>(predicate);
+
+   for(size_t i = 0; i != r_words; ++i)
+      {
+      this->set_word_at(i, CT::select<word>(mask, other.word_at(i), this->word_at(i)));
+      }
+   }
+
 #if defined(BOTAN_HAS_VALGRIND)
 void BigInt::const_time_poison() const
    {