Add BigInt::ct_reduce_below

3 files changed, 39 insertions, 3 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 9fd019d87..ca65363b4 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -319,8 +319,8 @@ BigInt BigInt::operator-() const
 
 size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
    {
-   if(p.is_negative())
-      throw Invalid_Argument("BigInt::reduce_below mod must be positive");
+   if(p.is_negative() || this->is_negative())
+      throw Invalid_Argument("BigInt::reduce_below both values must be positive");
 
    const size_t p_words = p.sig_words();
 
@@ -347,6 +347,29 @@ size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
    return reductions;
    }
 
+void BigInt::ct_reduce_below(const BigInt& mod, secure_vector<word>& ws, size_t bound)
+   {
+   if(mod.is_negative() || this->is_negative())
+      throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
+
+   const size_t mod_words = mod.sig_words();
+
+   grow_to(mod_words);
+
+   const size_t sz = size();
+
+   ws.resize(sz);
+
+   clear_mem(ws.data(), sz);
+
+   for(size_t i = 0; i != bound; ++i)
+      {
+      word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
+
+      CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
+      }
+   }
+
 /*
 * Return the absolute value of this number
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 31eee4c3c..a987fffda 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -347,6 +347,18 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      size_t reduce_below(const BigInt& mod, secure_vector<word> &ws);
 
      /**
+     * Return *this % mod
+     *
+     * Assumes that *this is (if anything) only slightly larger than mod and
+     * performs repeated subtractions. It should not be used if *this is much
+     * larger than mod, instead use modulo operator.
+     *
+     * Performs exactly bound subtractions, so if *this is >= bound*mod then the
+     * result will not be fully reduced. If bound is zero, nothing happens.
+     */
+     void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound);
+
+     /**
      * Zeroize the BigInt. The size of the underlying register is not
      * modified.
      */
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index 0468d004b..ec0071eac 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -84,7 +84,8 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
 
    t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
 
-   t1.reduce_below(m_modulus, ws);
+   // Per HAC this step requires at most 2 subtractions
+   t1.ct_reduce_below(m_modulus, ws, 2);
 
    if(x.is_negative() && t1.is_nonzero())
       {