Add BigInt::mod_mul

9 files changed, 104 insertions, 56 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 6ce14f8f1..5e4ee949c 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -126,19 +126,39 @@ BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>&
       swap_reg(ws);
       }
 #else
-   // is t < s or not?
-   const auto is_lt = bigint_ct_is_lt(data(), mod_sw, s.data(), mod_sw);
+   if(mod_sw == 4)
+      bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
+   else
+      bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
+#endif
+
+   return (*this);
+   }
 
-   // ws = p - s
-   const word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), mod_sw);
+BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws)
+   {
+   BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
+   BOTAN_ARG_CHECK(y < 16, "y too large");
 
-   // Compute either (t - s) or (t + (p - s)) depending on mask
-   const word carry = bigint_cnd_addsub(is_lt, mutable_data(), ws.data(), s.data(), mod_sw);
+   BOTAN_DEBUG_ASSERT(*this < mod);
 
-   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
-   BOTAN_UNUSED(carry, borrow);
-#endif
+   switch(y)
+      {
+      case 2:
+         *this <<= 1;
+         break;
+      case 4:
+         *this <<= 2;
+         break;
+      case 8:
+         *this <<= 3;
+         break;
+      default:
+         *this *= static_cast<word>(y);
+         break;
+      }
 
+   this->reduce_below(mod, ws);
    return (*this);
    }
 
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 667035686..d64082476 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -335,8 +335,6 @@ void BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
    for(;;)
       {
       word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
-
-      //CT::unpoison(borrow); // fixme
       if(borrow)
          break;
 
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 58c45dd67..9b385348e 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -328,7 +328,17 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
 
      /**
-     * Return *this below mod
+     * Set *this to (*this * y) % mod
+     * This function assumes *this is >= 0 && < mod
+     * y should be small, less than 16
+     * @param y the small integer to multiply by
+     * @param mod the positive modulus
+     * @param ws a temp workspace
+     */
+     BigInt& mod_mul(uint8_t y, 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
@@ -933,7 +943,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
               if(n > size())
                  {
                  if(n <= m_reg.capacity())
-                    m_reg.resize(m_reg.capacity());
+                    m_reg.resize(n);
                  else
                     m_reg.resize(n + (8 - (n % 8)));
                  }
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 6e2fba049..2824a3456 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -685,6 +685,47 @@ bigint_sub_abs(word z[],
    }
 
 /**
+* Set t to t-s modulo mod
+*
+* @param t first integer
+* @param s second integer
+* @param mod the modulus
+* @param mod_sw size of t, s, and mod
+* @param ws workspace of size mod_sw
+*/
+inline void
+bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
+   {
+   // is t < s or not?
+   const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
+
+   // ws = p - s
+   const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw);
+
+   // Compute either (t - s) or (t + (p - s)) depending on mask
+   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
+
+   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
+   BOTAN_UNUSED(carry, borrow);
+   }
+
+template<size_t N>
+inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
+   {
+   // is t < s or not?
+   const auto is_lt = bigint_ct_is_lt(t, N, s, N);
+
+   // ws = p - s
+   const word borrow = bigint_sub3(ws, mod, N, s, N);
+
+   // Compute either (t - s) or (t + (p - s)) depending on mask
+   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
+
+   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
+   BOTAN_UNUSED(carry, borrow);
+   }
+
+/**
 * Compute ((n1<<bits) + n0) / d
 */
 inline word bigint_divop(word n1, word n0, word d)
diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index 61a10eae5..f3d85e44c 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -312,17 +312,17 @@ BigInt Montgomery_Int::value() const
 
 Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const
    {
-   BigInt z = m_v + other.m_v;
    secure_vector<word> ws;
-   z.reduce_below(m_params->p(), ws);
+   BigInt z = m_v;
+   z.mod_add(other.m_v, m_params->p(), ws);
    return Montgomery_Int(m_params, z, false);
    }
 
 Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const
    {
-   BigInt z = m_v - other.m_v;
-   if(z.is_negative())
-      z += m_params->p();
+   secure_vector<word> ws;
+   BigInt z = m_v;
+   z.mod_sub(other.m_v, m_params->p(), ws);
    return Montgomery_Int(m_params, z, false);
    }
 
@@ -420,29 +420,25 @@ Montgomery_Int Montgomery_Int::additive_inverse() const
 
 Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws)
    {
-   m_v <<= 1;
-   m_v.reduce_below(m_params->p(), ws);
+   m_v.mod_mul(2, m_params->p(), ws);
    return (*this);
    }
 
 Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws)
    {
-   m_v *= 3;
-   m_v.reduce_below(m_params->p(), ws);
+   m_v.mod_mul(3, m_params->p(), ws);
    return (*this);
    }
 
 Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws)
    {
-   m_v <<= 2;
-   m_v.reduce_below(m_params->p(), ws);
+   m_v.mod_mul(4, m_params->p(), ws);
    return (*this);
    }
 
 Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws)
    {
-   m_v <<= 3;
-   m_v.reduce_below(m_params->p(), ws);
+   m_v.mod_mul(8, m_params->p(), ws);
    return (*this);
    }
 
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp
index a74c4de9f..d5935584d 100644
--- a/src/lib/math/numbertheory/nistp_redc.cpp
+++ b/src/lib/math/numbertheory/nistp_redc.cpp
@@ -48,13 +48,14 @@ void redc_p521(BigInt& x, secure_vector<word>& ws)
    if(bit_522_set)
       {
 #if (BOTAN_MP_WORD_BITS == 64)
-      static const word p521_words[9] = {
+      static const word p521_words[p_words] = {
          0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
          0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
          0x1FF };
 
-      bigint_sub2(x.mutable_data(), p_words, p521_words, 9);
+      bigint_sub2(x.mutable_data(), p_words, p521_words, p_words);
 #else
+      // FIXME use bigint_sub2
       x -= prime_p521();
 #endif
       }
@@ -576,5 +577,4 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
 
 #endif
 
-
 }
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index bd68a3ed7..f2f5607e1 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -60,8 +60,6 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
 
       size_t get_ws_size() const override { return 2*m_p_words + 4; }
 
-      void redc_mod_p(BigInt& z, secure_vector<word>& ws) const override;
-
       BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
 
       void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
@@ -93,11 +91,6 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
       bool m_a_is_minus_3;
    };
 
-void CurveGFp_Montgomery::redc_mod_p(BigInt& z, secure_vector<word>& ws) const
-   {
-   z.reduce_below(m_p, ws);
-   }
-
 BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
    {
    // Should we use Montgomery inverse instead?
@@ -207,6 +200,8 @@ class CurveGFp_NIST : public CurveGFp_Repr
       void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
          { redc_mod_p(x, ws); }
 
+      virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0;
+
       BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
 
       void curve_mul_words(BigInt& z,
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index d03247244..fe7a0a54d 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -49,8 +49,6 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
       */
       virtual const BigInt& get_1_rep() const = 0;
 
-      virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0;
-
       virtual BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const = 0;
 
       virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0;
@@ -171,11 +169,6 @@ class BOTAN_UNSTABLE_API CurveGFp final
 
       // TODO: from_rep taking && ref
 
-      void redc_mod_p(BigInt& z, secure_vector<word>& ws) const
-         {
-         m_repr->redc_mod_p(z, ws);
-         }
-
       void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const
          {
          m_repr->curve_mul(z, x, y, ws);
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 7bc6c4975..b4b3871cb 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -2,7 +2,7 @@
 * Point arithmetic on elliptic curves over GF(p)
 *
 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-*     2008-2011,2012,2014,2015 Jack Lloyd
+*     2008-2011,2012,2014,2015,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -152,6 +152,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size,
 
    m_curve.sqr(m_coord_x, T0, ws);
    m_coord_x.mod_sub(T1, p, sub_ws);
+
    m_coord_x.mod_sub(T3, p, sub_ws);
    m_coord_x.mod_sub(T3, p, sub_ws);
 
@@ -303,15 +304,13 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    m_curve.sqr(T0, m_coord_y, ws);
 
    m_curve.mul(T1, m_coord_x, T0, ws);
-   T1 <<= 2; // * 4
-   m_curve.redc_mod_p(T1, sub_ws);
+   T1.mod_mul(4, p, sub_ws);
 
    if(m_curve.a_is_zero())
       {
       // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
       m_curve.sqr(T4, m_coord_x, ws); // x^2
-      T4 *= 3; // 3*x^2
-      m_curve.redc_mod_p(T4, sub_ws);
+      T4.mod_mul(3, p, sub_ws); // 3*x^2
       }
    else if(m_curve.a_is_minus_3())
       {
@@ -330,8 +329,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
 
       m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
 
-      T4 *= 3; // 3*(x-z^2)*(x+z^2)
-      m_curve.redc_mod_p(T4, sub_ws);
+      T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)
       }
    else
       {
@@ -340,8 +338,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
       m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
 
       m_curve.sqr(T4, m_coord_x, ws); // x^2
-      T4 *= 3; // 3*x^2
-      T4.reduce_below(p, sub_ws);
+      T4.mod_mul(3, p, sub_ws);
       T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
       }
 
@@ -350,8 +347,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    T2.mod_sub(T1, p, sub_ws);
 
    m_curve.sqr(T3, T0, ws);
-   T3 <<= 3;
-   m_curve.redc_mod_p(T3, sub_ws);
+   T3.mod_mul(8, p, sub_ws);
 
    T1.mod_sub(T2, p, sub_ws);
 
@@ -361,8 +357,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    m_coord_x = T2;
 
    m_curve.mul(T2, m_coord_y, m_coord_z, ws);
-   T2 <<= 1;
-   m_curve.redc_mod_p(T2, sub_ws);
+   T2.mod_mul(2, p, sub_ws);
 
    m_coord_y = T0;
    m_coord_z = T2;