Some DL_Group and Montgomery exp improvements

Leverage precomputation better

6 files changed, 86 insertions, 25 deletions

diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index cbf17d180..112041be2 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -30,7 +30,6 @@ class Montgomery_Exponentation_State
       std::shared_ptr<const Montgomery_Params> m_params;
       std::vector<Montgomery_Int> m_g;
       size_t m_window_bits;
-      bool m_const_time;
    };
 
 Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
@@ -38,8 +37,7 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c
                                                                size_t window_bits,
                                                                bool const_time) :
    m_params(params),
-   m_window_bits(window_bits == 0 ? 4 : window_bits),
-   m_const_time(const_time)
+   m_window_bits(window_bits == 0 ? 4 : window_bits)
    {
    BOTAN_ARG_CHECK(g < m_params->p(), "Montgomery base too big");
 
@@ -129,8 +127,6 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size
 
 BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const
    {
-   BOTAN_ASSERT_NOMSG(m_const_time == false);
-
    const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
 
    secure_vector<word> ws;
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
index 632d7f7d6..091815a6e 100644
--- a/src/lib/math/numbertheory/monty_exp.h
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -8,10 +8,10 @@
 #define BOTAN_MONTY_EXP_H_
 
 #include <memory>
+#include <botan/bigint.h>
 
 namespace Botan {
 
-class BigInt;
 class Modular_Reducer;
 
 class Montgomery_Params;
@@ -40,6 +40,22 @@ BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
                              const BigInt& k);
 
+inline
+BigInt monty_exp(std::shared_ptr<const Montgomery_Params> params_p,
+                 const BigInt& g, const BigInt& k, size_t max_k_bits)
+   {
+   auto precomputed = monty_precompute(params_p, g, 4, true);
+   return monty_execute(*precomputed, k, max_k_bits);
+   }
+
+inline
+BigInt monty_exp_vartime(std::shared_ptr<const Montgomery_Params> params_p,
+                         const BigInt& g, const BigInt& k)
+   {
+   auto precomputed = monty_precompute(params_p, g, 4, false);
+   return monty_execute_vartime(*precomputed, k);
+   }
+
 /**
 * Return (x^z1 * y^z2) % p
 */
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 77856f978..3d4d8ba33 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -55,9 +55,12 @@ BigInt ressol(const BigInt& a, const BigInt& p)
    if(jacobi(a, p) != 1) // not a quadratic residue
       return -BigInt(1);
 
+   Modular_Reducer mod_p(p);
+   auto monty_p = std::make_shared<Montgomery_Params>(p, mod_p);
+
    if(p % 4 == 3) // The easy case
       {
-      return power_mod(a, ((p+1) >> 2), p);
+      return monty_exp_vartime(monty_p, a, ((p+1) >> 2));
       }
 
    size_t s = low_zero_bits(p - 1);
@@ -66,9 +69,7 @@ BigInt ressol(const BigInt& a, const BigInt& p)
    q -= 1;
    q >>= 1;
 
-   Modular_Reducer mod_p(p);
-
-   BigInt r = power_mod(a, q, p);
+   BigInt r = monty_exp_vartime(monty_p, a, q);
    BigInt n = mod_p.multiply(a, mod_p.square(r));
    r = mod_p.multiply(r, a);
 
@@ -93,7 +94,7 @@ BigInt ressol(const BigInt& a, const BigInt& p)
          return -BigInt(1);
       }
 
-   BigInt c = power_mod(z, (q << 1) + 1, p);
+   BigInt c = monty_exp_vartime(monty_p, z, (q << 1) + 1);
 
    while(n > 1)
       {
@@ -111,7 +112,7 @@ BigInt ressol(const BigInt& a, const BigInt& p)
             }
          }
 
-      c = power_mod(c, BigInt::power_of_2(s-i-1), p);
+      c = monty_exp_vartime(monty_p, c, BigInt::power_of_2(s-i-1));
       r = mod_p.multiply(r, c);
       c = mod_p.square(c);
       n = mod_p.multiply(n, c);
@@ -289,11 +290,8 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
 
    if(mod.is_odd())
       {
-      const size_t powm_window = 4;
-
-      auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod);
-      auto powm_base_mod = monty_precompute(monty_mod, reduce_mod.reduce(base), powm_window);
-      return monty_execute(*powm_base_mod, exp, exp_bits);
+      auto monty_params = std::make_shared<Montgomery_Params>(mod, reduce_mod);
+      return monty_exp(monty_params, reduce_mod.reduce(base), exp, exp_bits);
       }
 
    /*
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index e1a16a570..684022a1c 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -81,8 +81,11 @@ BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
                                        const BigInt& m);
 
 /**
-* Compute the square root of x modulo a prime using the
-* Tonelli-Shanks algorithm
+* Compute the square root of x modulo a prime using the Tonelli-Shanks
+* algorithm. This algorithm is primarily used for EC point
+* decompression which takes only public inputs, as a consequence it is
+* not written to be constant-time and may leak side-channel information
+* about its arguments.
 *
 * @param x the input
 * @param p the prime
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index 1f411e234..7ff0a1958 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -81,6 +81,21 @@ class DL_Group_Data final
          return monty_execute(*m_monty, k, max_k_bits);
          }
 
+      BigInt power_g_p_vartime(const BigInt& k) const
+         {
+         return monty_execute_vartime(*m_monty, k);
+         }
+
+      BigInt power_b_p(const BigInt& b, const BigInt& k, size_t max_k_bits) const
+         {
+         return monty_exp(m_monty_params, b, k, max_k_bits);
+         }
+
+      BigInt power_b_p_vartime(const BigInt& b, const BigInt& k) const
+         {
+         return monty_exp_vartime(m_monty_params, b, k);
+         }
+
       bool q_is_set() const { return m_q_bits > 0; }
 
       void assert_q_is_set(const std::string& function) const
@@ -355,7 +370,7 @@ bool DL_Group::verify_public_element(const BigInt& y) const
 
    if(q.is_zero() == false)
       {
-      if(power_mod(y, q, p) != 1)
+      if(data().power_b_p_vartime(y, q) != 1)
          return false;
       }
 
@@ -369,7 +384,7 @@ bool DL_Group::verify_element_pair(const BigInt& y, const BigInt& x) const
    if(y <= 1 || y >= p || x <= 1 || x >= p)
       return false;
 
-   if(y != power_g_p(x))
+   if(y != this->power_g_p(x))
       return false;
 
    return true;
@@ -396,13 +411,18 @@ bool DL_Group::verify_group(RandomNumberGenerator& rng,
    const size_t test_prob = 128;
    const bool is_randomly_generated = (source() != DL_Group_Source::ExternalSource);
 
+   if(!is_prime(p, rng, test_prob, is_randomly_generated))
+      {
+      return false;
+      }
+
    if(q != 0)
       {
       if((p - 1) % q != 0)
          {
          return false;
          }
-      if(this->power_g_p(q) != 1)
+      if(data().power_g_p_vartime(q) != 1)
          {
          return false;
          }
@@ -411,10 +431,23 @@ bool DL_Group::verify_group(RandomNumberGenerator& rng,
          return false;
          }
       }
-
-   if(!is_prime(p, rng, test_prob, is_randomly_generated))
+   else
       {
-      return false;
+      if(!from_builtin && !is_randomly_generated)
+         {
+         // If we got this p,g from some unknown source, try to verify
+         // that the group order is not too absurdly small.
+
+         const size_t upper_bound = strong ? 1000 : 100;
+
+         for(size_t i = 2; i != upper_bound; ++i)
+            {
+            if(data().power_g_p_vartime(i) == 1)
+               {
+               return false;
+               }
+            }
+         }
       }
 
    return true;
@@ -543,6 +576,11 @@ BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const
    return data().power_g_p(x, max_x_bits);
    }
 
+BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const
+   {
+   return data().power_b_p(b, x, max_x_bits);
+   }
+
 DL_Group_Source DL_Group::source() const
    {
    return data().source();
diff --git a/src/lib/pubkey/dl_group/dl_group.h b/src/lib/pubkey/dl_group/dl_group.h
index 14ad5c7b3..c3b9443b7 100644
--- a/src/lib/pubkey/dl_group/dl_group.h
+++ b/src/lib/pubkey/dl_group/dl_group.h
@@ -251,6 +251,16 @@ class BOTAN_PUBLIC_API(2,0) DL_Group final
       BigInt power_g_p(const BigInt& x, size_t max_x_bits) const;
 
       /**
+      * Modular exponentiation
+      * @param b the base
+      * @param x the exponent
+      * @param max_x_bits x is assumed to be at most this many bits long.
+      *
+      * @return (b^x) % p
+      */
+      BigInt power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const;
+
+      /**
       * Multi-exponentiate
       * Return (g^x * y^z) % p
       */