aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorJack Lloyd <jack@randombit.net>2018-06-23 19:08:49 -0400
committerJack Lloyd <jack@randombit.net>2018-06-23 19:10:59 -0400
commit5d3fb558a86976187f5edcac70bb28bfa61238cd (patch)
treef6248bbaf601b8493f09ac2e5ce47ae27dcb409c /src
parentad9554ded323741f72d9e8a0ae527603940e0252 (diff)
Minor optimization for Montgomery exponentiation
The loop started off by squaring the result value, but at that point it is always one (or the Montgomery representation thereof). Avoiding those squarings does not leak any information about the exponent, because we haven't even looked at the exponent at that point. Improves RSA verify performance by about 5%, everything else ~1% speedup
Diffstat (limited to 'src')
-rw-r--r--src/lib/math/numbertheory/monty.cpp7
-rw-r--r--src/lib/math/numbertheory/monty.h2
-rw-r--r--src/lib/math/numbertheory/monty_exp.cpp34
3 files changed, 26 insertions, 17 deletions
diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index 0560cc59e..2dbcbaa95 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -375,6 +375,13 @@ Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other)
return mul_by(other, ws);
}
+Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n)
+ {
+ for(size_t i = 0; i != n; ++i)
+ m_params->square_this(m_v, ws);
+ return (*this);
+ }
+
Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws)
{
m_params->square_this(m_v, ws);
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index 7586b634f..23c36864e 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -94,6 +94,8 @@ class BOTAN_UNSTABLE_API Montgomery_Int final
Montgomery_Int& square_this(secure_vector<word>& ws);
+ Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
+
Montgomery_Int multiplicative_inverse() const;
Montgomery_Int additive_inverse() const;
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index b5336ef14..c6a3be563 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -106,18 +106,17 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size
secure_vector<word> e_bits(m_params->p_words());
secure_vector<word> ws;
- for(size_t i = exp_nibbles; i > 0; --i)
+ if(exp_nibbles > 0)
{
- for(size_t j = 0; j != m_window_bits; ++j)
+ const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
+ x.mul_by(e_bits, ws);
+
+ for(size_t i = exp_nibbles - 1; i > 0; --i)
{
- x.square_this(ws);
+ x.square_this_n_times(ws, m_window_bits);
+ const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits));
+ x.mul_by(e_bits, ws);
}
-
- const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
-
- const_time_lookup(e_bits, m_g, nibble);
-
- x.mul_by(e_bits, ws);
}
x.const_time_unpoison();
@@ -134,17 +133,18 @@ BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scal
secure_vector<word> ws;
- for(size_t i = exp_nibbles; i > 0; --i)
+ if(exp_nibbles > 0)
{
- for(size_t j = 0; j != m_window_bits; ++j)
+ const uint32_t nibble = scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits);
+ x.mul_by(m_g[nibble], ws);
+
+ for(size_t i = exp_nibbles - 1; i > 0; --i)
{
- x.square_this(ws);
+ x.square_this_n_times(ws, m_window_bits);
+ const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
+ if(nibble > 0)
+ x.mul_by(m_g[nibble], ws);
}
-
- const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
-
- if(nibble > 0)
- x.mul_by(m_g[nibble], ws);
}
x.const_time_unpoison();