diff options
| -rw-r--r-- | news.rst | 3 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/monty_exp.cpp | 32 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/monty_exp.h | 6 | ||||
| -rw-r--r-- | src/lib/pubkey/rsa/rsa.cpp | 21 |
4 files changed, 54 insertions, 8 deletions
@@ -6,7 +6,8 @@ Version 2.6.0, Not Yet Released * Add support for OAEP labels (GH #1508) -* RSA signing optimizations, about 15% faster (GH #1523) +* RSA signing is about 15% faster (GH #1523) and RSA verification is + about 50% faster. * Add exponent blinding to RSA (GH #1523) diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp index 18fb6d081..4bf281fa9 100644 --- a/src/lib/math/numbertheory/monty_exp.cpp +++ b/src/lib/math/numbertheory/monty_exp.cpp @@ -23,6 +23,8 @@ class Montgomery_Exponentation_State size_t window_bits); BigInt exponentiation(const BigInt& k) const; + + BigInt exponentiation_vartime(const BigInt& k) const; private: std::shared_ptr<const Montgomery_Params> m_params; std::vector<Montgomery_Int> m_g; @@ -112,6 +114,30 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) cons return x.value(); } +BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const + { + const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits; + + Montgomery_Int x(m_params, m_params->R1(), false); + + secure_vector<word> ws; + + for(size_t i = exp_nibbles; i > 0; --i) + { + for(size_t j = 0; j != m_window_bits; ++j) + { + x.square_this(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); + } + + return x.value(); + } + std::shared_ptr<const Montgomery_Exponentation_State> monty_precompute(std::shared_ptr<const Montgomery_Params> params, const BigInt& g, @@ -126,6 +152,12 @@ BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state, return precomputed_state.exponentiation(k); } +BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state, + const BigInt& k) + { + return precomputed_state.exponentiation_vartime(k); + } + BigInt monty_multi_exp(std::shared_ptr<const Montgomery_Params> params_p, const BigInt& x_bn, const BigInt& z1, diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h index 6eeec8bb4..6eeb88e7f 100644 --- a/src/lib/math/numbertheory/monty_exp.h +++ b/src/lib/math/numbertheory/monty_exp.h @@ -32,6 +32,12 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params_p, BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state, const BigInt& k); +/* +* Return g^x mod p taking variable time +*/ +BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state, + const BigInt& k); + /** * Return (x^z1 * y^z2) % p */ diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp index fd95f187f..69d7052dc 100644 --- a/src/lib/pubkey/rsa/rsa.cpp +++ b/src/lib/pubkey/rsa/rsa.cpp @@ -341,7 +341,9 @@ class RSA_Public_Operation { public: explicit RSA_Public_Operation(const RSA_PublicKey& rsa) : - m_n(rsa.get_n()), m_powermod_e_n(rsa.get_e(), rsa.get_n()) + m_n(rsa.get_n()), + m_e(rsa.get_e()), + m_monty_n(std::make_shared<Montgomery_Params>(m_n)) {} size_t get_max_input_bits() const { return (m_n.bits() - 1); } @@ -351,17 +353,22 @@ class RSA_Public_Operation { if(m >= m_n) throw Invalid_Argument("RSA public op - input is too large"); - return m_powermod_e_n(m); + + const size_t powm_window = 1; + + auto powm_m_n = monty_precompute(m_monty_n, m, powm_window); + return monty_execute_vartime(*powm_m_n, m_e); } const BigInt& get_n() const { return m_n; } const BigInt& m_n; - Fixed_Exponent_Power_Mod m_powermod_e_n; + const BigInt& m_e; + std::shared_ptr<Montgomery_Params> m_monty_n; }; class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME, - private RSA_Public_Operation + private RSA_Public_Operation { public: @@ -374,7 +381,7 @@ class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME, size_t max_raw_input_bits() const override { return get_max_input_bits(); } secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len, - RandomNumberGenerator&) override + RandomNumberGenerator&) override { BigInt m(msg, msg_len); return BigInt::encode_1363(public_op(m), m_n.bytes()); @@ -382,7 +389,7 @@ class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME, }; class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA, - private RSA_Public_Operation + private RSA_Public_Operation { public: @@ -404,7 +411,7 @@ class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA, }; class RSA_KEM_Encryption_Operation final : public PK_Ops::KEM_Encryption_with_KDF, - private RSA_Public_Operation + private RSA_Public_Operation { public: |