Fix a bug in Barrett reduction

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

Also some small optimizations and cleanups.

4 files changed, 45 insertions, 30 deletions

diff --git a/src/fuzzer/barrett.cpp b/src/fuzzer/barrett.cpp
index 1c5d88f87..09aed517e 100644
--- a/src/fuzzer/barrett.cpp
+++ b/src/fuzzer/barrett.cpp
@@ -12,20 +12,24 @@ void fuzz(const uint8_t in[], size_t len)
    {
    static const size_t max_bits = 2048;
 
-   if(len % 2 != 0)
+   if(len <= 1 || len % 3 != 1)
       return;
 
-   const size_t part_size = len / 2;
+   const size_t part_size = len / 3;
 
    if(part_size * 8 > max_bits)
       return;
 
-   const Botan::BigInt x = Botan::BigInt::decode(in, part_size);
-   const Botan::BigInt p = Botan::BigInt::decode(in + part_size, part_size);
+   uint8_t flags = in[0];
+   Botan::BigInt x = Botan::BigInt::decode(in + 1, part_size * 2);
+   const Botan::BigInt p = Botan::BigInt::decode(in + 1 + part_size * 2, part_size);
 
    if(p.is_zero())
       return;
 
+   if(flags & 1)
+      x.flip_sign();
+
    const Botan::BigInt ref = x % p;
 
    const Botan::Modular_Reducer mod_p(p);
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;
    }
 
 }
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index b62fa307d..8074a4f3b 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -9,6 +9,7 @@
 #if defined(BOTAN_HAS_NUMBERTHEORY)
    #include <botan/bigint.h>
    #include <botan/numthry.h>
+   #include <botan/reducer.h>
    #include <botan/pow_mod.h>
    #include <botan/parsing.h>
    #include "test_rng.h"
@@ -398,6 +399,9 @@ class BigInt_Mod_Test final : public Text_Based_Test
          e %= b;
          result.test_eq("a %= b", e, c);
 
+         const Botan::Modular_Reducer mod_b(b);
+         result.test_eq("Barrett", mod_b.reduce(a), c);
+
          // if b fits into a Botan::word test %= operator for words
          if(b.bytes() <= sizeof(Botan::word))
             {