From 358d288f7538f00e6b421a2cfb47655d7ed31f28 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 28 Jun 2018 16:17:51 -0400 Subject: Move reduction mod q to DL_Group Avoids computing Barrett params many times and gives option for more optimizations in future. --- src/lib/pubkey/dl_group/dl_group.cpp | 65 +++++++++++++++++++++++++++++++----- src/lib/pubkey/dl_group/dl_group.h | 37 ++++++++++++++++++++ src/lib/pubkey/dsa/dsa.cpp | 31 ++++++++--------- 3 files changed, 107 insertions(+), 26 deletions(-) (limited to 'src/lib/pubkey') 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(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 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 m_monty_params; std::shared_ptr 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,8 +179,45 @@ 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 * 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); } } -- cgit v1.2.3