Merge GH #2297 Add BigInt::ct_cond_add

4 files changed, 38 insertions, 25 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 3ada94dce..fac82defa 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -453,6 +453,15 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
    m_data.swap(reg);
    }
 
+void BigInt::ct_cond_add(bool predicate, const BigInt& value)
+   {
+   this->grow_to(1 + value.sig_words());
+
+   bigint_cnd_add(static_cast<word>(predicate),
+                  this->mutable_data(), this->size(),
+                  value.data(), value.sig_words());
+   }
+
 void BigInt::ct_cond_swap(bool predicate, BigInt& other)
    {
    const size_t max_words = std::max(size(), other.size());
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index ac0a57038..9fda4ceb0 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -721,6 +721,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      void ct_cond_swap(bool predicate, BigInt& other);
 
      /**
+     * If predicate is true add value to *this
+     */
+     void ct_cond_add(bool predicate, const BigInt& value);
+
+     /**
      * If predicate is true flip the sign of *this
      */
      void cond_flip_sign(bool predicate);
@@ -982,7 +987,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
                  {
                  const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
                  const size_t len = size() - (top_word + 1);
-                 if (len > 0)
+                 if(len > 0)
                     {
                     clear_mem(&m_reg[top_word+1], len);
                     }
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 9fbaf8429..7c6e398a8 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -10,6 +10,7 @@
 #include <botan/monty.h>
 #include <botan/divide.h>
 #include <botan/rng.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/internal/mp_core.h>
 #include <botan/internal/monty_exp.h>
 #include <botan/internal/primality.h>
@@ -39,23 +40,25 @@ size_t low_zero_bits(const BigInt& n)
    {
    size_t low_zero = 0;
 
-   if(n.is_positive() && n.is_nonzero())
+   auto seen_nonempty_word = CT::Mask<word>::cleared();
+
+   for(size_t i = 0; i != n.size(); ++i)
       {
-      for(size_t i = 0; i != n.size(); ++i)
-         {
-         const word x = n.word_at(i);
-
-         if(x)
-            {
-            low_zero += ctz(x);
-            break;
-            }
-         else
-            low_zero += BOTAN_MP_WORD_BITS;
-         }
+      const word x = n.word_at(i);
+
+      // ctz(0) will return sizeof(word)
+      const size_t tz_x = ctz(x);
+
+      // if x > 0 we want to count tz_x in total but not any
+      // further words, so set the mask after the addition
+      low_zero += seen_nonempty_word.if_not_set_return(tz_x);
+
+      seen_nonempty_word |= CT::Mask<word>::expand(x);
       }
 
-   return low_zero;
+   // if we saw no words with x > 0 then n == 0 and the value we have
+   // computed is meaningless. Instead return 0 in that case.
+   return seen_nonempty_word.if_set_return(low_zero);
    }
 
 /*
@@ -68,6 +71,8 @@ BigInt gcd(const BigInt& a, const BigInt& b)
    if(a == 1 || b == 1)
       return 1;
 
+   // See https://gcd.cr.yp.to/safegcd-20190413.pdf fig 1.2
+
    BigInt f = a;
    BigInt g = b;
    f.set_sign(BigInt::Positive);
@@ -100,10 +105,7 @@ BigInt gcd(const BigInt& a, const BigInt& b)
 
       delta += 1;
 
-      t = g;
-      t += f;
-      g.ct_cond_assign(g.is_odd(), t);
-
+      g.ct_cond_add(g.is_odd(), f);
       g >>= 1;
       }
 
diff --git a/src/lib/math/numbertheory/primality.cpp b/src/lib/math/numbertheory/primality.cpp
index 028e2a7ef..eb2be42b1 100644
--- a/src/lib/math/numbertheory/primality.cpp
+++ b/src/lib/math/numbertheory/primality.cpp
@@ -67,8 +67,7 @@ bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C)
       Ut = mod_C.multiply(U, V);
 
       Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U)));
-      if(Vt.is_odd())
-         Vt += C;
+      Vt.ct_cond_add(Vt.is_odd(), C);
       Vt >>= 1;
       Vt = mod_C.reduce(Vt);
 
@@ -76,13 +75,11 @@ bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C)
       V = Vt;
 
       U2 = mod_C.reduce(Ut + Vt);
-      if(U2.is_odd())
-         U2 += C;
+      U2.ct_cond_add(U2.is_odd(), C);
       U2 >>= 1;
 
       V2 = mod_C.reduce(Vt + Ut*D);
-      if(V2.is_odd())
-         V2 += C;
+      V2.ct_cond_add(V2.is_odd(), C);
       V2 >>= 1;
 
       U.ct_cond_assign(k_bit, U2);