Add ct_modulo and BigInt::ct_cond_swap

4 files changed, 62 insertions, 7 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 0e0dfe0d5..ae3ab24b0 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -386,7 +386,16 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
    m_data.swap(reg);
    }
 
-void BigInt::ct_cond_assign(bool predicate, BigInt& other)
+void BigInt::ct_cond_swap(bool predicate, BigInt& other)
+   {
+   const size_t max_words = std::max(size(), other.size());
+   grow_to(max_words);
+   other.grow_to(max_words);
+
+   bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
+   }
+
+void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
    {
    const size_t t_words = size();
    const size_t o_words = other.size();
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 64f81765a..46e0cd250 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -681,7 +681,13 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * If predicate is true assign other to *this
      * Uses a masked operation to avoid side channels
      */
-     void ct_cond_assign(bool predicate, BigInt& other);
+     void ct_cond_assign(bool predicate, const BigInt& other);
+
+     /**
+     * If predicate is true swap *this and other
+     * Uses a masked operation to avoid side channels
+     */
+     void ct_cond_swap(bool predicate, BigInt& other);
 
 #if defined(BOTAN_HAS_VALGRIND)
      void const_time_poison() const;
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index a11e8b70b..5e2dd92d9 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -58,6 +58,7 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
 
    BigInt q(BigInt::Positive, x_words);
    BigInt r(BigInt::Positive, y_words);
+   BigInt t(BigInt::Positive, y_words); // a temporary
 
    for(size_t i = 0; i != x_bits; ++i)
       {
@@ -67,11 +68,10 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
       r *= 2;
       r.conditionally_set_bit(0, x_b);
 
-      // y <= r -> r >= y
-      const auto r_gte_y = bigint_ct_is_lt(y.data(), y_words, r.data(), r.size(), true);
+      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
 
-      q.conditionally_set_bit(b, r_gte_y.is_set());
-      bigint_cnd_sub(r_gte_y.value(), r.mutable_data(), r.size(), y.data(), y_words);
+      q.conditionally_set_bit(b, r_gte_y);
+      r.ct_cond_swap(r_gte_y, t);
       }
 
    sign_fixup(x, y, q, r);
@@ -83,7 +83,6 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
    {
    const size_t x_words = x.sig_words();
    const size_t x_bits = x.bits();
-   const size_t y_words = 1;
 
    BigInt q(BigInt::Positive, x_words);
    uint32_t r = 0;
@@ -116,6 +115,34 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
    q_out = q;
    }
 
+BigInt ct_modulo(const BigInt& x, const BigInt& y)
+   {
+   if(x.is_negative() || y.is_negative() || y.is_zero())
+      throw Invalid_Argument("ct_modulo requires x >= 0 and y > 0");
+
+   const size_t y_words = y.sig_words();
+
+   const size_t x_bits = x.bits();
+
+   BigInt r(BigInt::Positive, y_words);
+   BigInt t(BigInt::Positive, y_words);
+
+   for(size_t i = 0; i != x_bits; ++i)
+      {
+      const size_t b = x_bits - 1 - i;
+      const bool x_b = x.get_bit(b);
+
+      r *= 2;
+      r.conditionally_set_bit(0, x_b);
+
+      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
+
+      r.ct_cond_swap(r_gte_y, t);
+      }
+
+   return r;
+   }
+
 /*
 * Solve x = q * y + r
 */
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index d83f4b695..ac9c43e81 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -56,6 +56,19 @@ void BOTAN_PUBLIC_API(2,9) ct_divide_u8(const BigInt& x,
                                         BigInt& q,
                                         uint8_t& r);
 
+/**
+* BigInt modulo, const time variant
+*
+* Using this function is (slightly) cheaper than calling ct_divide and
+* using only the remainder.
+*
+* @param x a non-negative integer
+* @param modulo a positive integer
+* @return result x % modulo
+*/
+BigInt BOTAN_PUBLIC_API(2,9) ct_modulo(const BigInt& x,
+                                       const BigInt& modulo);
+
 }
 
 #endif