Use const time reductions in Barrett and LCM computations

3 files changed, 23 insertions, 4 deletions

diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index ac9c43e81..e365dabb3 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -48,6 +48,23 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
 *
 * @param x an integer
 * @param y a non-zero integer
+* @return x/y with remainder discarded
+*/
+inline BigInt ct_divide(const BigInt& x, const BigInt& y)
+   {
+   BigInt q, r;
+   ct_divide(x, y, q, r);
+   return q;
+   }
+
+/**
+* BigInt division, const time variant
+*
+* This runs with control flow independent of the values of x/y.
+* Warning: the loop bounds still leak the sizes of x and y.
+*
+* @param x an integer
+* @param y a non-zero integer
 * @param q will be set to x / y
 * @param r will be set to x % y
 */
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 399a49cea..eba924b7c 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -9,6 +9,7 @@
 #include <botan/pow_mod.h>
 #include <botan/reducer.h>
 #include <botan/monty.h>
+#include <botan/divide.h>
 #include <botan/rng.h>
 #include <botan/internal/bit_ops.h>
 #include <botan/internal/mp_core.h>
@@ -83,7 +84,7 @@ BigInt gcd(const BigInt& a, const BigInt& b)
 */
 BigInt lcm(const BigInt& a, const BigInt& b)
    {
-   return ((a * b) / gcd(a, b));
+   return ct_divide(a * b, gcd(a, b));
    }
 
 /*
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index a5321c47c..0468d004b 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -7,6 +7,7 @@
 
 #include <botan/reducer.h>
 #include <botan/internal/ct_utils.h>
+#include <botan/divide.h>
 
 namespace Botan {
 
@@ -28,7 +29,7 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
 
       m_modulus_2 = Botan::square(m_modulus);
 
-      m_mu = BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words) / m_modulus;
+      m_mu = ct_divide(BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words), m_modulus);
       }
    }
 
@@ -51,8 +52,8 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
 
    if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
       {
-      // too big, fall back to normal division
-      t1 = x % m_modulus;
+      // too big, fall back to slow boat division
+      t1 = ct_modulo(x, m_modulus);
       return;
       }