Fix a bug in Barrett reduction

-x*n % n would reduce to n instead of zero.

Also some small optimizations and cleanups.

2 files changed, 33 insertions, 26 deletions

diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 64ab24e7d..0b826c8f5 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -256,6 +256,9 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      bool operator !() const { return (!is_nonzero()); }
 
+     BigInt& add(const word y[], size_t y_words, Sign sign);
+     BigInt& sub(const word y[], size_t y_words, Sign sign);
+
      /**
      * Multiply this with y
      * @param y the BigInt to multiply with this
@@ -724,10 +727,6 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
         size_t idx);
 
    private:
-
-      BigInt& add(const word y[], size_t y_words, Sign sign);
-      BigInt& sub(const word y[], size_t y_words, Sign sign);
-
       secure_vector<word> m_reg;
       Sign m_signedness = Positive;
    };
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index 9dbcfb9a3..b59a8d989 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -1,6 +1,6 @@
 /*
 * Modular Reducer
-* (C) 1999-2011 Jack Lloyd
+* (C) 1999-2011,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -35,43 +35,51 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
 
    const size_t x_sw = x.sig_words();
 
-   if(x_sw < m_mod_words || x.cmp(m_modulus, false) < 0)
+   if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
+      {
+      // too big, fall back to normal division
+      return (x % m_modulus);
+      }
+
+   if(x_sw < m_mod_words - 1)
       {
       if(x.is_negative())
          return x + m_modulus; // make positive
       return x;
       }
-   else if(x.cmp(m_modulus_2, false) < 0)
-      {
-      secure_vector<word> ws;
 
-      BigInt t1(x.data() + m_mod_words - 1, x_sw - (m_mod_words - 1));
+   secure_vector<word> ws;
 
-      t1.mul(m_mu, ws);
-      t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
+   BigInt t1(x.data() + (m_mod_words - 1), x_sw - (m_mod_words - 1));
 
-      t1.mul(m_modulus, ws);
-      t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
+   t1.mul(m_mu, ws);
+   t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
 
-      t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
+   // TODO add masked mul to avoid computing high bits
+   t1.mul(m_modulus, ws);
+   t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
 
-      if(t1.is_negative())
-         {
-         t1 += BigInt::power_of_2(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
-         }
+   t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
 
-      t1.reduce_below(m_modulus, ws);
+   if(t1.is_negative())
+      {
+      if(ws.size() < m_mod_words + 2)
+         ws.resize(m_mod_words + 2);
+      clear_mem(ws.data(), ws.size());
 
-      if(x.is_negative())
-         t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
+      ws[m_mod_words + 1] = 1;
 
-      return t1;
+      t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
       }
-   else
+
+   t1.reduce_below(m_modulus, ws);
+
+   if(x.is_negative() && t1.is_nonzero())
       {
-      // too big, fall back to normal division
-      return (x % m_modulus);
+      t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
       }
+
+   return t1;
    }
 
 }