Make binary extended Euclidean algorithm less branchy

This is still leaky, but much less than before.

3 files changed, 62 insertions, 12 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index ae3ab24b0..a4545e4a1 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -395,6 +395,13 @@ void BigInt::ct_cond_swap(bool predicate, BigInt& other)
    bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
    }
 
+void BigInt::cond_flip_sign(bool predicate)
+   {
+   // FIXME!
+   if(predicate)
+      flip_sign();
+   }
+
 void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
    {
    const size_t t_words = size();
@@ -413,6 +420,11 @@ void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
       const word t_word = this->word_at(i);
       this->set_word_at(i, mask.select(o_word, t_word));
       }
+
+   if(sign() != other.sign())
+      {
+      cond_flip_sign(predicate);
+      }
    }
 
 #if defined(BOTAN_HAS_VALGRIND)
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 46e0cd250..f0aa04391 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -689,6 +689,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void ct_cond_swap(bool predicate, BigInt& other);
 
+     /**
+     * If predicate is true flip the sign of *this
+     */
+     void cond_flip_sign(bool predicate);
+
 #if defined(BOTAN_HAS_VALGRIND)
      void const_time_poison() const;
      void const_time_unpoison() const;
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index eba924b7c..a05403d82 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -314,36 +314,69 @@ BigInt inverse_euclid(const BigInt& n, const BigInt& mod)
 
    BigInt u = mod, v = n;
    BigInt A = 1, B = 0, C = 0, D = 1;
+   BigInt T0, T1, T2;
 
    while(u.is_nonzero())
       {
       const size_t u_zero_bits = low_zero_bits(u);
       u >>= u_zero_bits;
+
+      const size_t v_zero_bits = low_zero_bits(v);
+      v >>= v_zero_bits;
+
+      const bool u_gte_v = (u >= v);
+
       for(size_t i = 0; i != u_zero_bits; ++i)
          {
-         if(A.is_odd() || B.is_odd())
-            { A += n; B -= mod; }
-         A >>= 1; B >>= 1;
+         const bool needs_adjust = A.is_odd() || B.is_odd();
+
+         T0 = A + n;
+         T1 = B - mod;
+
+         A.ct_cond_assign(needs_adjust, T0);
+         B.ct_cond_assign(needs_adjust, T1);
+
+         A >>= 1;
+         B >>= 1;
          }
 
-      const size_t v_zero_bits = low_zero_bits(v);
-      v >>= v_zero_bits;
       for(size_t i = 0; i != v_zero_bits; ++i)
          {
-         if(C.is_odd() || D.is_odd())
-            { C += n; D -= mod; }
-         C >>= 1; D >>= 1;
+         const bool needs_adjust = C.is_odd() || D.is_odd();
+         T0 = C + n;
+         T1 = D - mod;
+
+         C.ct_cond_assign(needs_adjust, T0);
+         D.ct_cond_assign(needs_adjust, T1);
+
+         C >>= 1;
+         D >>= 1;
          }
 
-      if(u >= v) { u -= v; A -= C; B -= D; }
-      else       { v -= u; C -= A; D -= B; }
+      T0 = u - v;
+      T1 = A - C;
+      T2 = B - D;
+
+      T0.cond_flip_sign(!u_gte_v);
+      T1.cond_flip_sign(!u_gte_v);
+      T2.cond_flip_sign(!u_gte_v);
+
+      u.ct_cond_assign(u_gte_v, T0);
+      A.ct_cond_assign(u_gte_v, T1);
+      B.ct_cond_assign(u_gte_v, T2);
+
+      v.ct_cond_assign(!u_gte_v, T0);
+      C.ct_cond_assign(!u_gte_v, T1);
+      D.ct_cond_assign(!u_gte_v, T2);
       }
 
    if(v != 1)
       return 0; // no modular inverse
 
-   while(D.is_negative()) D += mod;
-   while(D >= mod) D -= mod;
+   while(D.is_negative())
+      D += mod;
+   while(D >= mod)
+      D -= mod;
 
    return D;
    }