diff options
author | Jack Lloyd <[email protected]> | 2018-06-23 19:08:49 -0400 |
---|---|---|
committer | Jack Lloyd <[email protected]> | 2018-06-23 19:10:59 -0400 |
commit | 5d3fb558a86976187f5edcac70bb28bfa61238cd (patch) | |
tree | f6248bbaf601b8493f09ac2e5ce47ae27dcb409c | |
parent | ad9554ded323741f72d9e8a0ae527603940e0252 (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
-rw-r--r-- | src/lib/math/numbertheory/monty.cpp | 7 | ||||
-rw-r--r-- | src/lib/math/numbertheory/monty.h | 2 | ||||
-rw-r--r-- | src/lib/math/numbertheory/monty_exp.cpp | 34 |
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(); |