Fix Barrett reduction input bound

In the long ago when I wrote the Barrett code I must have missed that
Barrett works for any input < 2^2k where k is the word size of the
modulus. Fixing this has several nice effects, it is faster because it
replaces a multiprecision comparison with a single size_t compare, and
now the branch does not reveal information about the input or modulus,
but only their word lengths, which is not considered sensitive.

Fixing this allows reverting the change make in a57ce5a4fd2 and now
RSA signing is even slightly faster than in 2.8, rather than 30% slower.

2 files changed, 5 insertions, 5 deletions

diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index c37a1daeb..deb3874d3 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -28,9 +28,9 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
       m_modulus = mod;
       m_mod_words = m_modulus.sig_words();
 
-      m_modulus_2 = Botan::square(m_modulus);
-
-      m_mu = ct_divide(BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words), m_modulus);
+      // Compute mu = floor(2^{2k} / m)
+      m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words);
+      m_mu = ct_divide(m_mu, m_modulus);
       }
    }
 
@@ -76,7 +76,7 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
 
    const size_t x_sw = x.sig_words();
 
-   if(x.cmp(m_modulus_2, false) >= 0)
+   if(x_sw > 2*m_mod_words)
       {
       // too big, fall back to slow boat division
       t1 = ct_modulo(x, m_modulus);
diff --git a/src/lib/math/numbertheory/reducer.h b/src/lib/math/numbertheory/reducer.h
index 5276adbbc..65d9956f2 100644
--- a/src/lib/math/numbertheory/reducer.h
+++ b/src/lib/math/numbertheory/reducer.h
@@ -54,7 +54,7 @@ class BOTAN_PUBLIC_API(2,0) Modular_Reducer
       Modular_Reducer() { m_mod_words = 0; }
       explicit Modular_Reducer(const BigInt& mod);
    private:
-      BigInt m_modulus, m_modulus_2, m_mu;
+      BigInt m_modulus, m_mu;
       size_t m_mod_words;
    };