Move reduction mod q to DL_Group

Avoids computing Barrett params many times and gives option for
more optimizations in future.

3 files changed, 107 insertions, 26 deletions

diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index 75bdef6a2..abc14ec0c 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -23,13 +23,15 @@ class DL_Group_Data final
       DL_Group_Data(const BigInt& p, const BigInt& q, const BigInt& g) :
          m_p(p), m_q(q), m_g(g),
          m_mod_p(p),
+         m_mod_q(q),
          m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
          m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
          m_p_bits(p.bits()),
          m_q_bits(q.bits()),
          m_estimated_strength(dl_work_factor(m_p_bits)),
          m_exponent_bits(dl_exponent_size(m_p_bits))
-         {}
+         {
+         }
 
       ~DL_Group_Data() = default;
 
@@ -47,19 +49,25 @@ class DL_Group_Data final
          return m_mod_p.multiply(x, y);
          }
 
+      BigInt mod_q(const BigInt& x) const { return m_mod_q.reduce(x); }
+
+      BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const
+         {
+         return m_mod_q.multiply(x, y);
+         }
+
+      BigInt square_mod_q(const BigInt& x) const
+         {
+         return m_mod_q.square(x);
+         }
+
       std::shared_ptr<const Montgomery_Params> monty_params_p() const
          { return m_monty_params; }
 
       size_t p_bits() const { return m_p_bits; }
+      size_t q_bits() const { return m_q_bits; }
       size_t p_bytes() const { return (m_p_bits + 7) / 8; }
 
-      size_t q_bits() const
-         {
-         if(m_q_bits == 0)
-            throw Invalid_State("DL_Group::q_bits q value is unset on this group");
-         return m_q_bits;
-         }
-
       size_t estimated_strength() const { return m_estimated_strength; }
 
       size_t exponent_bits() const { return m_exponent_bits; }
@@ -69,11 +77,20 @@ class DL_Group_Data final
          return monty_execute(*m_monty, k, max_k_bits);
          }
 
+      bool q_is_set() const { return m_q_bits > 0; }
+
+      void assert_q_is_set(const std::string& function) const
+         {
+         if(q_is_set() == false)
+            throw Invalid_State("DL_Group::" + function + " q is not set for this group");
+         }
+
    private:
       BigInt m_p;
       BigInt m_q;
       BigInt m_g;
       Modular_Reducer m_mod_p;
+      Modular_Reducer m_mod_q;
       std::shared_ptr<const Montgomery_Params> m_monty_params;
       std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
       size_t m_p_bits;
@@ -427,6 +444,7 @@ size_t DL_Group::p_bytes() const
 
 size_t DL_Group::q_bits() const
    {
+   data().assert_q_is_set("q_bits");
    return data().q_bits();
    }
 
@@ -456,6 +474,37 @@ BigInt DL_Group::multiply_mod_p(const BigInt& x, const BigInt& y) const
    return data().multiply_mod_p(x, y);
    }
 
+BigInt DL_Group::inverse_mod_q(const BigInt& x) const
+   {
+   data().assert_q_is_set("inverse_mod_q");
+   // precompute??
+   return inverse_mod(x, get_q());
+   }
+
+BigInt DL_Group::mod_q(const BigInt& x) const
+   {
+   data().assert_q_is_set("mod_q");
+   return data().mod_q(x);
+   }
+
+BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y) const
+   {
+   data().assert_q_is_set("multiply_mod_q");
+   return data().multiply_mod_q(x, y);
+   }
+
+BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const
+   {
+   data().assert_q_is_set("multiply_mod_q");
+   return data().multiply_mod_q(data().multiply_mod_q(x, y), z);
+   }
+
+BigInt DL_Group::square_mod_q(const BigInt& x) const
+   {
+   data().assert_q_is_set("square_mod_q");
+   return data().square_mod_q(x);
+   }
+
 BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const
    {
    return monty_multi_exp(data().monty_params_p(), get_g(), x, y, z);
diff --git a/src/lib/pubkey/dl_group/dl_group.h b/src/lib/pubkey/dl_group/dl_group.h
index b206e5546..6bc918761 100644
--- a/src/lib/pubkey/dl_group/dl_group.h
+++ b/src/lib/pubkey/dl_group/dl_group.h
@@ -179,9 +179,46 @@ class BOTAN_PUBLIC_API(2,0) DL_Group final
       */
       BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const;
 
+      /**
+      * Return the inverse of x mod p
+      */
       BigInt inverse_mod_p(const BigInt& x) const;
 
       /**
+      * Reduce an integer modulo q
+      * Throws if q is unset on this DL_Group
+      * @return x % q
+      */
+      BigInt mod_q(const BigInt& x) const;
+
+      /**
+      * Multiply and reduce an integer modulo q
+      * Throws if q is unset on this DL_Group
+      * @return (x*y) % q
+      */
+      BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const;
+
+      /**
+      * Multiply and reduce an integer modulo q
+      * Throws if q is unset on this DL_Group
+      * @return (x*y*z) % q
+      */
+      BigInt multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const;
+
+      /**
+      * Square and reduce an integer modulo q
+      * Throws if q is unset on this DL_Group
+      * @return (x*x) % q
+      */
+      BigInt square_mod_q(const BigInt& x) const;
+
+      /**
+      * Return the inverse of x mod q
+      * Throws if q is unset on this DL_Group
+      */
+      BigInt inverse_mod_q(const BigInt& x) const;
+
+      /**
       * Modular exponentiation
       *
       * @warning this function leaks the size of x via the number of
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index e43c14de2..35240292c 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -79,15 +79,14 @@ class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
                               RandomNumberGenerator& rng) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(dsa.get_group()),
-         m_x(dsa.get_x()),
-         m_mod_q(dsa.group_q())
+         m_x(dsa.get_x())
          {
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
          m_rfc6979_hash = hash_for_emsa(emsa);
 #endif
 
          m_b = BigInt::random_integer(rng, 2, dsa.group_q());
-         m_b_inv = inverse_mod(m_b, dsa.group_q());
+         m_b_inv = m_group.inverse_mod_q(m_b);
          }
 
       size_t max_input_bits() const override { return m_group.get_q().bits(); }
@@ -97,7 +96,6 @@ class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
    private:
       const DL_Group m_group;
       const BigInt& m_x;
-      Modular_Reducer m_mod_q;
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
       std::string m_rfc6979_hash;
 #endif
@@ -123,20 +121,20 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    const BigInt k = BigInt::random_integer(rng, 1, q);
 #endif
 
-   const BigInt k_inv = inverse_mod(k, q);
+   const BigInt k_inv = m_group.inverse_mod_q(k);
 
-   const BigInt r = m_mod_q.reduce(m_group.power_g_p(k, m_group.q_bits()));
+   const BigInt r = m_group.mod_q(m_group.power_g_p(k, m_group.q_bits()));
 
    /*
    * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
    */
-   m_b = m_mod_q.square(m_b);
-   m_b_inv = m_mod_q.square(m_b_inv);
+   m_b = m_group.square_mod_q(m_b);
+   m_b_inv = m_group.square_mod_q(m_b_inv);
 
-   m = m_mod_q.multiply(m_b, m);
-   const BigInt xr = m_mod_q.multiply(m_mod_q.multiply(m_x, m_b), r);
+   m = m_group.multiply_mod_q(m_b, m);
+   const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r);
 
-   const BigInt s = m_mod_q.multiply(m_b_inv, m_mod_q.multiply(k_inv, xr + m));
+   const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m));
 
    // With overwhelming probability, a bug rather than actual zero r/s
    if(r.is_zero() || s.is_zero())
@@ -155,8 +153,7 @@ class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
                                  const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(emsa),
          m_group(dsa.get_group()),
-         m_y(dsa.get_y()),
-         m_mod_q(dsa.group_q())
+         m_y(dsa.get_y())
          {
          }
 
@@ -169,8 +166,6 @@ class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
    private:
       const DL_Group m_group;
       const BigInt& m_y;
-
-      Modular_Reducer m_mod_q;
    };
 
 bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
@@ -191,12 +186,12 @@ bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
 
    s = inverse_mod(s, q);
 
-   const BigInt sr = m_mod_q.multiply(s, r);
-   const BigInt si = m_mod_q.multiply(s, i);
+   const BigInt sr = m_group.multiply_mod_q(s, r);
+   const BigInt si = m_group.multiply_mod_q(s, i);
 
    s = m_group.multi_exponentiate(si, m_y, sr);
 
-   return (m_mod_q.reduce(s) == r);
+   return (m_group.mod_q(s) == r);
    }
 
 }