diff options
Diffstat (limited to 'src/lib/pubkey')
22 files changed, 539 insertions, 188 deletions
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp index a3a6b9a52..172804972 100644 --- a/src/lib/pubkey/dsa/dsa.cpp +++ b/src/lib/pubkey/dsa/dsa.cpp @@ -8,7 +8,6 @@ #include <botan/dsa.h> #include <botan/keypair.h> -#include <botan/pow_mod.h> #include <botan/reducer.h> #include <botan/rng.h> #include <botan/internal/pk_ops_impl.h> diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp index 8953edba4..112213d6c 100644 --- a/src/lib/pubkey/ec_group/curve_gfp.cpp +++ b/src/lib/pubkey/ec_group/curve_gfp.cpp @@ -34,8 +34,14 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr m_r3 = mod_p.multiply(m_r, m_r2); m_a_r = mod_p.multiply(m_r, m_a); m_b_r = mod_p.multiply(m_r, m_b); + + m_a_is_zero = m_a.is_zero(); + m_a_is_minus_3 = (m_a + 3 == m_p); } + bool a_is_zero() const override { return m_a_is_zero; } + bool a_is_minus_3() const override { return m_a_is_minus_3; } + const BigInt& get_a() const override { return m_a; } const BigInt& get_b() const override { return m_b; } @@ -46,6 +52,8 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr const BigInt& get_b_rep() const override { return m_b_r; } + const BigInt& get_1_rep() const override { return m_r; } + bool is_one(const BigInt& x) const override { return x == m_r; } size_t get_p_words() const override { return m_p_words; } @@ -78,6 +86,9 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr // Montgomery parameters BigInt m_r, m_r2, m_r3; word m_p_dash; + + bool m_a_is_zero; + bool m_a_is_minus_3; }; BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const @@ -188,14 +199,20 @@ class CurveGFp_NIST : public CurveGFp_Repr { public: CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : - m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) + m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) { + // All Solinas prime curves are assumed a == -3 } + bool a_is_zero() const override { return false; } + bool a_is_minus_3() const override { return true; } + const BigInt& get_a() const override { return m_a; } const BigInt& get_b() const override { return m_b; } + const BigInt& get_1_rep() const override { return m_1; } + size_t get_p_words() const override { return m_p_words; } size_t get_ws_size() const override { return 2*m_p_words + 4; } @@ -223,17 +240,29 @@ class CurveGFp_NIST : public CurveGFp_Repr const BigInt& y, secure_vector<word>& ws) const override; + void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const + { + curve_mul(tmp, x, y, ws); + x.swap(tmp); + } + + void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const + { + curve_sqr(tmp, x, ws); + x.swap(tmp); + } + void curve_sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const override; private: virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0; // Curve parameters + BigInt m_1; BigInt m_a, m_b; size_t m_p_words; // cache of m_p.sig_words() }; - BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const { BOTAN_UNUSED(ws); @@ -340,8 +369,71 @@ class CurveGFp_P256 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p256(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r, p2, p4, p8, p16, p32, tmp; + + curve_sqr(r, x, ws); + + curve_mul(p2, r, x, ws); + curve_sqr(r, p2, ws); + curve_sqr_tmp(r, tmp, ws); + + curve_mul(p4, r, p2, ws); + + curve_sqr(r, p4, ws); + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p8, r, p4, ws);; + + curve_sqr(r, p8, ws); + for(size_t i = 0; i != 7; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p16, r, p8, ws); + + curve_sqr(r, p16, ws); + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p32, r, p16, ws); + + curve_sqr(r, p32, ws); + for(size_t i = 0; i != 31; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + for(size_t i = 0; i != 32*4; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p32, tmp, ws); + + for(size_t i = 0; i != 32; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p32, tmp, ws); + + for(size_t i = 0; i != 16; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p16, tmp, ws); + for(size_t i = 0; i != 8; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p8, tmp, ws); + + for(size_t i = 0; i != 4; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p4, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p2, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + /** * The NIST P-384 curve */ @@ -352,8 +444,80 @@ class CurveGFp_P384 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p384(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r, x2, x3, x15, x30, tmp, rl; + + r = x; + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + x2 = r; + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + x3 = r; + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x3, tmp, ws); + + rl = r; + for(size_t i = 0; i != 6; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x3, tmp, ws); + + x15 = r; + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x15, tmp, ws); + + x30 = r; + for(size_t i = 0; i != 30; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + rl = r; + for(size_t i = 0; i != 60; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 120; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x15, tmp, ws); + + for(size_t i = 0; i != 31; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x2, tmp, ws); + + for(size_t i = 0; i != 94; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + #endif /** @@ -366,8 +530,76 @@ class CurveGFp_P521 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p521(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r; + BigInt rl; + BigInt a7; + BigInt tmp; + + curve_sqr(r, x, ws); + curve_mul_tmp(r, x, tmp, ws); + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + rl = r; + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + a7 = r; // need this value later + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + rl = r; + for(size_t i = 0; i != 8; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 16; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 32; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 64; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 128; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 256; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 7; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, a7, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + } std::shared_ptr<CurveGFp_Repr> diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h index 8a83a9c41..865bb68f8 100644 --- a/src/lib/pubkey/ec_group/curve_gfp.h +++ b/src/lib/pubkey/ec_group/curve_gfp.h @@ -30,6 +30,10 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr virtual bool is_one(const BigInt& x) const = 0; + virtual bool a_is_zero() const = 0; + + virtual bool a_is_minus_3() const = 0; + /* * Returns to_curve_rep(get_a()) */ @@ -40,6 +44,11 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr */ virtual const BigInt& get_b_rep() const = 0; + /* + * Returns to_curve_rep(1) + */ + virtual const BigInt& get_1_rep() const = 0; + virtual BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const = 0; virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0; @@ -116,6 +125,11 @@ class BOTAN_UNSTABLE_API CurveGFp final const BigInt& get_b_rep() const { return m_repr->get_b_rep(); } + const BigInt& get_1_rep() const { return m_repr->get_1_rep(); } + + bool a_is_minus_3() const { return m_repr->a_is_minus_3(); } + bool a_is_zero() const { return m_repr->a_is_zero(); } + bool is_one(const BigInt& x) const { return m_repr->is_one(x); } BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp index 1fb762e4b..ac23aa151 100644 --- a/src/lib/pubkey/ec_group/ec_group.cpp +++ b/src/lib/pubkey/ec_group/ec_group.cpp @@ -43,7 +43,8 @@ class EC_Group_Data final m_oid(oid), m_p_bits(p.bits()), m_order_bits(order.bits()), - m_a_is_minus_3(a == p - 3) + m_a_is_minus_3(a == p - 3), + m_a_is_zero(a.is_zero()) { } @@ -79,6 +80,7 @@ class EC_Group_Data final const PointGFp& base_point() const { return m_base_point; } bool a_is_minus_3() const { return m_a_is_minus_3; } + bool a_is_zero() const { return m_a_is_zero; } BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); } @@ -87,6 +89,11 @@ class EC_Group_Data final return m_mod_order.multiply(x, y); } + BigInt inverse_mod_order(const BigInt& x) const + { + return inverse_mod(x, m_order); + } + PointGFp blinded_base_point_multiply(const BigInt& k, RandomNumberGenerator& rng, std::vector<BigInt>& ws) const @@ -108,6 +115,7 @@ class EC_Group_Data final size_t m_p_bits; size_t m_order_bits; bool m_a_is_minus_3; + bool m_a_is_zero; }; class EC_Group_Data_Map final @@ -399,6 +407,11 @@ bool EC_Group::a_is_minus_3() const return data().a_is_minus_3(); } +bool EC_Group::a_is_zero() const + { + return data().a_is_zero(); + } + size_t EC_Group::get_p_bits() const { return data().p_bits(); @@ -469,6 +482,11 @@ BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const return data().multiply_mod_order(x, y); } +BigInt EC_Group::inverse_mod_order(const BigInt& x) const + { + return data().inverse_mod_order(x); + } + const OID& EC_Group::get_curve_oid() const { return data().oid(); @@ -520,7 +538,7 @@ PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point, std::vector<BigInt>& ws) const { PointGFp_Var_Point_Precompute mul(point); - mul.randomize_repr(rng); + mul.randomize_repr(rng, ws); return mul.mul(k, rng, get_order(), ws); } diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h index 031e5cc34..f273108d2 100644 --- a/src/lib/pubkey/ec_group/ec_group.h +++ b/src/lib/pubkey/ec_group/ec_group.h @@ -132,6 +132,11 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final bool a_is_minus_3() const; /** + * Return if a == 0 mod p + */ + bool a_is_zero() const; + + /** * Return the size of p in bits (same as get_p().bits()) */ size_t get_p_bits() const; @@ -194,6 +199,11 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final BigInt mod_order(const BigInt& x) const; /* + * Return inverse of x modulo the order + */ + BigInt inverse_mod_order(const BigInt& x) const; + + /* * Reduce (x*y) modulo the order */ BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const; diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp index acbda95d4..8f53bb079 100644 --- a/src/lib/pubkey/ec_group/point_gfp.cpp +++ b/src/lib/pubkey/ec_group/point_gfp.cpp @@ -17,20 +17,17 @@ namespace Botan { PointGFp::PointGFp(const CurveGFp& curve) : m_curve(curve), m_coord_x(0), - m_coord_y(1), + m_coord_y(curve.get_1_rep()), m_coord_z(0) { - secure_vector<word> monty_ws(m_curve.get_ws_size()); - m_curve.to_rep(m_coord_x, monty_ws); - m_curve.to_rep(m_coord_y, monty_ws); - m_curve.to_rep(m_coord_z, monty_ws); + // Assumes Montgomery rep of zero is zero } PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : m_curve(curve), m_coord_x(x), m_coord_y(y), - m_coord_z(1) + m_coord_z(m_curve.get_1_rep()) { if(x <= 0 || x >= curve.get_p()) throw Invalid_Argument("Invalid PointGFp affine x"); @@ -40,7 +37,6 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : secure_vector<word> monty_ws(m_curve.get_ws_size()); m_curve.to_rep(m_coord_x, monty_ws); m_curve.to_rep(m_coord_y, monty_ws); - m_curve.to_rep(m_coord_z, monty_ws); } void PointGFp::randomize_repr(RandomNumberGenerator& rng) @@ -111,20 +107,20 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, // FIXME avoid the copy here m_coord_x = BigInt(x_words, x_size); m_coord_y = BigInt(y_words, y_size); - m_coord_z = 1; - m_curve.to_rep(m_coord_z, ws_bn[0].get_word_vector()); + m_coord_z = m_curve.get_1_rep(); return; } resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[3]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 @@ -139,13 +135,9 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, m_curve.mul(T2, m_coord_z, T3, ws); // z1^3 m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3 - T4 -= m_coord_x; // x2*z1^2 - x1*z2^2 - if(T4.is_negative()) - T4 += p; + T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2 - T0 -= m_coord_y; - if(T0.is_negative()) - T0 += p; + T0.mod_sub(m_coord_y, p, sub_ws); if(T4.is_zero()) { @@ -157,7 +149,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, // setting to zero: m_coord_x = 0; - m_coord_y = 1; + m_coord_y = m_curve.get_1_rep(); m_coord_z = 0; return; } @@ -169,22 +161,16 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, m_curve.mul(T1, T2, T4, ws); m_curve.sqr(m_coord_x, T0, ws); - m_coord_x -= T1; - m_coord_x -= T3; - m_coord_x -= T3; - while(m_coord_x.is_negative()) - m_coord_x += p; + m_coord_x.mod_sub(T1, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); - T3 -= m_coord_x; - if(T3.is_negative()) - T3 += p; + T3.mod_sub(m_coord_x, p, sub_ws); T2 = m_coord_y; m_curve.mul(T2, T0, T3, ws); m_curve.mul(T3, m_coord_y, T1, ws); - T2 -= T3; - if(T2.is_negative()) - T2 += p; + T2.mod_sub(T3, p, sub_ws); m_coord_y = T2; m_curve.mul(T3, m_coord_z, T4, ws); @@ -208,13 +194,14 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[3]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; - BigInt& T5 = ws_bn[6]; + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; + BigInt& T5 = ws_bn[7]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 @@ -233,18 +220,13 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) m_curve.mul(T5, m_coord_z, T3, ws); // z1^3 m_curve.mul(T0, rhs.m_coord_y, T5, ws); // y2*z1^3 - T4 -= T1; // x2*z1^2 - x1*z2^2 - if(T4.is_negative()) - T4 += p; + T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2 - T3 = T0; - T3 -= T2; - if(T3.is_negative()) - T3 += p; + T0.mod_sub(T2, p, sub_ws); if(T4.is_zero()) { - if(T3.is_zero()) + if(T0.is_zero()) { mult2(ws_bn); return; @@ -252,36 +234,50 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) // setting to zero: m_coord_x = 0; - m_coord_y = 1; + m_coord_y = m_curve.get_1_rep(); m_coord_z = 0; return; } m_curve.sqr(T5, T4, ws); - m_curve.mul(T0, T1, T5, ws); + m_curve.mul(T3, T1, T5, ws); m_curve.mul(T1, T5, T4, ws); - m_curve.sqr(m_coord_x, T3, ws); - m_coord_x -= T1; - m_coord_x -= T0; - m_coord_x -= T0; - while(m_coord_x.is_negative()) - m_coord_x += p; - - T0 -= m_coord_x; - if(T0.is_negative()) - T0 += p; - - m_curve.mul(m_coord_y, T3, T0, ws); - m_curve.mul(T0, T2, T1, ws); - m_coord_y -= T0; - if(m_coord_y.is_negative()) - m_coord_y += p; - - m_curve.mul(T0, m_coord_z, rhs.m_coord_z, ws); - m_curve.mul(m_coord_z, T0, T4, ws); + m_curve.sqr(m_coord_x, T0, ws); + m_coord_x.mod_sub(T1, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + + T3.mod_sub(m_coord_x, p, sub_ws); + + m_curve.mul(m_coord_y, T0, T3, ws); + m_curve.mul(T3, T2, T1, ws); + + m_coord_y.mod_sub(T3, p, sub_ws); + + m_curve.mul(T3, m_coord_z, rhs.m_coord_z, ws); + m_curve.mul(m_coord_z, T3, T4, ws); + } + +void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn) + { + if(iterations == 0) + return; + + if(m_coord_y.is_zero()) + { + *this = PointGFp(m_curve); // setting myself to zero + return; + } + + /* + TODO we can save 2 squarings per iteration by computing + a*Z^4 using values cached from previous iteration + */ + for(size_t i = 0; i != iterations; ++i) + mult2(ws_bn); } // *this *= 2 @@ -299,11 +295,13 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[6]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); + + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc @@ -314,41 +312,64 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) m_curve.mul(T1, m_coord_x, T0, ws); T1 <<= 2; // * 4 - T1.reduce_below(p, T3.get_word_vector()); + T1.reduce_below(p, sub_ws); + + if(m_curve.a_is_zero()) + { + // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2 + m_curve.sqr(T4, m_coord_x, ws); // x^2 + T4 *= 3; // 3*x^2 + T4.reduce_below(p, sub_ws); + } + else if(m_curve.a_is_minus_3()) + { + /* + if a == -3 then + 3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2) + */ + m_curve.sqr(T3, m_coord_z, ws); // z^2 - m_curve.sqr(T3, m_coord_z, ws); // z^2 - m_curve.sqr(T4, T3, ws); // z^4 - m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); + // (x-z^2) + T2 = m_coord_x; + T2.mod_sub(T3, p, sub_ws); - m_curve.sqr(T4, m_coord_x, ws); - T4 *= 3; - T4 += T3; - T4.reduce_below(p, T3.get_word_vector()); + // (x+z^2) + T3.mod_add(m_coord_x, p, sub_ws); + + m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2) + + T4 *= 3; // 3*(x-z^2)*(x+z^2) + T4.reduce_below(p, sub_ws); + } + else + { + m_curve.sqr(T3, m_coord_z, ws); // z^2 + m_curve.sqr(T4, T3, ws); // z^4 + m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4 + + m_curve.sqr(T4, m_coord_x, ws); // x^2 + T4 *= 3; // 3*x^2 + T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4 + } m_curve.sqr(T2, T4, ws); - T2 -= T1; - T2 -= T1; - while(T2.is_negative()) - T2 += p; + T2.mod_sub(T1, p, sub_ws); + T2.mod_sub(T1, p, sub_ws); m_curve.sqr(T3, T0, ws); T3 <<= 3; - T3.reduce_below(p, T0.get_word_vector()); + T3.reduce_below(p, sub_ws); - T1 -= T2; - while(T1.is_negative()) - T1 += p; + T1.mod_sub(T2, p, sub_ws); m_curve.mul(T0, T4, T1, ws); - T0 -= T3; - if(T0.is_negative()) - T0 += p; + T0.mod_sub(T3, p, sub_ws); m_coord_x = T2; m_curve.mul(T2, m_coord_y, m_coord_z, ws); T2 <<= 1; - T2.reduce_below(p, T3.get_word_vector()); + T2.reduce_below(p, sub_ws); m_coord_y = T0; m_coord_z = T2; @@ -426,13 +447,11 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points, */ const CurveGFp& curve = points[0].m_curve; + const BigInt& rep_1 = curve.get_1_rep(); if(ws.size() < curve.get_ws_size()) ws.resize(curve.get_ws_size()); - BigInt rep_1 = 1; - curve.to_rep(rep_1, ws); - std::vector<BigInt> c(points.size()); c[0] = points[0].m_coord_z; @@ -479,8 +498,7 @@ void PointGFp::force_affine() const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws); m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws); m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws); - m_coord_z = 1; - m_curve.to_rep(m_coord_z, ws); + m_coord_z = m_curve.get_1_rep(); } bool PointGFp::is_affine() const diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h index 2a9948fde..cce2adcc6 100644 --- a/src/lib/pubkey/ec_group/point_gfp.h +++ b/src/lib/pubkey/ec_group/point_gfp.h @@ -49,7 +49,7 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final HYBRID = 2 }; - enum { WORKSPACE_SIZE = 7 }; + enum { WORKSPACE_SIZE = 8 }; /** * Construct an uninitialized PointGFp @@ -152,6 +152,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final const BigInt& get_y() const { return m_coord_y; } const BigInt& get_z() const { return m_coord_z; } + void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) + { + m_coord_x.swap(new_x); + m_coord_y.swap(new_y); + m_coord_z.swap(new_z); + } + /** * Force this point to affine coordinates */ @@ -236,6 +243,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final void mult2(std::vector<BigInt>& workspace); /** + * Repeated point doubling + * @param i number of doublings to perform + * @param workspace temp space, at least WORKSPACE_SIZE elements + */ + void mult2i(size_t i, std::vector<BigInt>& workspace); + + /** * Point addition * @param other the point to add to *this * @param workspace temp space, at least WORKSPACE_SIZE elements @@ -249,6 +263,18 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final } /** + * Point doubling + * @param workspace temp space, at least WORKSPACE_SIZE elements + * @return *this doubled + */ + PointGFp double_of(std::vector<BigInt>& workspace) const + { + PointGFp x = (*this); + x.mult2(workspace); + return x; + } + + /** * Return the zero (aka infinite) point associated with this curve */ PointGFp zero() const { return PointGFp(m_curve); } diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp index d052b837c..17087a6ed 100644 --- a/src/lib/pubkey/ec_group/point_mul.cpp +++ b/src/lib/pubkey/ec_group/point_mul.cpp @@ -140,22 +140,54 @@ PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& poi { m_window_bits = 4; + std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); + m_U.resize(1U << m_window_bits); m_U[0] = point.zero(); m_U[1] = point; - std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); - for(size_t i = 2; i < m_U.size(); ++i) + for(size_t i = 2; i < m_U.size(); i += 2) { - m_U[i] = m_U[i-1]; - m_U[i].add(point, ws); + m_U[i] = m_U[i/2].double_of(ws); + m_U[i+1] = m_U[i].plus(point, ws); } } -void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng) +void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng, + std::vector<BigInt>& ws_bn) { + if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS <= 1) + return; + + if(ws_bn.size() < 7) + ws_bn.resize(7); + + BigInt& mask = ws_bn[0]; + BigInt& mask2 = ws_bn[1]; + BigInt& mask3 = ws_bn[2]; + BigInt& new_x = ws_bn[3]; + BigInt& new_y = ws_bn[4]; + BigInt& new_z = ws_bn[5]; + secure_vector<word>& ws = ws_bn[6].get_word_vector(); + + const CurveGFp& curve = m_U[0].get_curve(); + + // Skipping zero point since it can't be randomized for(size_t i = 1; i != m_U.size(); ++i) - m_U[i].randomize_repr(rng); + { + mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false); + // Easy way of ensuring mask != 0 + mask.set_bit(0); + + curve.sqr(mask2, mask, ws); + curve.mul(mask3, mask, mask2, ws); + + curve.mul(new_x, m_U[i].get_x(), mask2, ws); + curve.mul(new_y, m_U[i].get_y(), mask3, ws); + curve.mul(new_z, m_U[i].get_z(), mask, ws); + + m_U[i].swap_coords(new_x, new_y, new_z); + } } PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k, @@ -193,8 +225,7 @@ PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k, while(windows) { - for(size_t i = 0; i != m_window_bits; ++i) - R.mult2(ws); + R.mult2i(m_window_bits, ws); const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_window_bits, m_window_bits); // cache side channel here, we are relying on blinding... @@ -261,8 +292,7 @@ PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1, { if(i > 0) { - H.mult2(ws); - H.mult2(ws); + H.mult2i(2, ws); } const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2); diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h index cfce05d5c..a85c2bee9 100644 --- a/src/lib/pubkey/ec_group/point_mul.h +++ b/src/lib/pubkey/ec_group/point_mul.h @@ -15,7 +15,7 @@ class Modular_Reducer; static const size_t PointGFp_SCALAR_BLINDING_BITS = 80; -class PointGFp_Base_Point_Precompute +class PointGFp_Base_Point_Precompute final { public: PointGFp_Base_Point_Precompute(const PointGFp& base_point, @@ -38,12 +38,13 @@ class PointGFp_Base_Point_Precompute std::vector<word> m_W; }; -class PointGFp_Var_Point_Precompute +class PointGFp_Var_Point_Precompute final { public: PointGFp_Var_Point_Precompute(const PointGFp& point); - void randomize_repr(RandomNumberGenerator& rng); + void randomize_repr(RandomNumberGenerator& rng, + std::vector<BigInt>& ws); PointGFp mul(const BigInt& k, RandomNumberGenerator& rng, @@ -54,7 +55,7 @@ class PointGFp_Var_Point_Precompute std::vector<PointGFp> m_U; }; -class PointGFp_Multi_Point_Precompute +class PointGFp_Multi_Point_Precompute final { public: PointGFp_Multi_Point_Precompute(const PointGFp& g1, diff --git a/src/lib/pubkey/ecc_key/ecc_key.cpp b/src/lib/pubkey/ecc_key/ecc_key.cpp index 7c46a2fa0..2c23c1b47 100644 --- a/src/lib/pubkey/ecc_key/ecc_key.cpp +++ b/src/lib/pubkey/ecc_key/ecc_key.cpp @@ -118,8 +118,6 @@ EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng, else m_domain_encoding = EC_DOMPAR_ENC_EXPLICIT; - const BigInt& order = m_domain_params.get_order(); - if(x == 0) { m_private_key = ec_group.random_scalar(rng); @@ -133,7 +131,7 @@ EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng, if(with_modular_inverse) { // ECKCDSA - m_public_key = domain().get_base_point() * inverse_mod(m_private_key, order); + m_public_key = domain().get_base_point() * m_domain_params.inverse_mod_order(m_private_key); } else { @@ -183,8 +181,7 @@ EC_PrivateKey::EC_PrivateKey(const AlgorithmIdentifier& alg_id, if(with_modular_inverse) { // ECKCDSA - const BigInt& order = m_domain_params.get_order(); - m_public_key = domain().get_base_point() * inverse_mod(m_private_key, order); + m_public_key = domain().get_base_point() * m_domain_params.inverse_mod_order(m_private_key); } else { diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp index adadb2703..59f245a00 100644 --- a/src/lib/pubkey/ecdh/ecdh.cpp +++ b/src/lib/pubkey/ecdh/ecdh.cpp @@ -31,7 +31,7 @@ class ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF m_group(key.domain()), m_rng(rng) { - m_l_times_priv = inverse_mod(m_group.get_cofactor(), m_group.get_order()) * key.private_value(); + m_l_times_priv = m_group.inverse_mod_order(m_group.get_cofactor()) * key.private_value(); } secure_vector<uint8_t> raw_agree(const uint8_t w[], size_t w_len) override diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp index 03f5e57ab..6e104f164 100644 --- a/src/lib/pubkey/ecdsa/ecdsa.cpp +++ b/src/lib/pubkey/ecdsa/ecdsa.cpp @@ -89,7 +89,7 @@ ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len, const BigInt k = m_group.random_scalar(rng); #endif - const BigInt k_inv = inverse_mod(k, m_group.get_order()); + const BigInt k_inv = m_group.inverse_mod_order(k); const BigInt r = m_group.mod_order( m_group.blinded_base_point_multiply_x(k, rng, m_ws)); @@ -142,7 +142,7 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order()) return false; - const BigInt w = inverse_mod(s, m_group.get_order()); + const BigInt w = m_group.inverse_mod_order(s); const BigInt u1 = m_group.multiply_mod_order(e, w); const BigInt u2 = m_group.multiply_mod_order(r, w); diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp index 062bb524d..61b7ae055 100644 --- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp +++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp @@ -10,6 +10,7 @@ #include <botan/keypair.h> #include <botan/reducer.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> namespace Botan { @@ -86,7 +87,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(ecgdsa.domain()), - m_public_point(ecgdsa.public_point()) + m_gy_mul(m_group.get_base_point(), ecgdsa.public_point()) { } @@ -98,7 +99,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; }; bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, @@ -115,11 +116,11 @@ bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order()) return false; - const BigInt w = inverse_mod(r, m_group.get_order()); + const BigInt w = m_group.inverse_mod_order(r); const BigInt u1 = m_group.multiply_mod_order(e, w); const BigInt u2 = m_group.multiply_mod_order(s, w); - const PointGFp R = m_group.point_multiply(u1, m_public_point, u2); + const PointGFp R = m_gy_mul.multi_exp(u1, u2); if(R.is_zero()) return false; diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp index f16fb027e..90716228a 100644 --- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp +++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp @@ -8,6 +8,7 @@ #include <botan/eckcdsa.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/keypair.h> #include <botan/reducer.h> #include <botan/emsa.h> @@ -113,11 +114,11 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(eckcdsa.domain()), - m_public_point(eckcdsa.public_point()), + m_gy_mul(m_group.get_base_point(), eckcdsa.public_point()), m_prefix() { - const BigInt public_point_x = m_public_point.get_affine_x(); - const BigInt public_point_y = m_public_point.get_affine_y(); + const BigInt public_point_x = eckcdsa.public_point().get_affine_x(); + const BigInt public_point_y = eckcdsa.public_point().get_affine_y(); m_prefix.resize(public_point_x.bytes() + public_point_y.bytes()); public_point_x.binary_encode(&m_prefix[0]); @@ -136,7 +137,7 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; secure_vector<uint8_t> m_prefix; }; @@ -169,7 +170,7 @@ bool ECKCDSA_Verification_Operation::verify(const uint8_t msg[], size_t, BigInt w(r_xor_e.data(), r_xor_e.size()); w = m_group.mod_order(w); - const PointGFp q = m_group.point_multiply(w, m_public_point, s); + const PointGFp q = m_gy_mul.multi_exp(w, s); const BigInt q_x = q.get_affine_x(); secure_vector<uint8_t> c(q_x.bytes()); q_x.binary_encode(c.data()); diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp index 0fcca1b8d..1d1b0d75e 100644 --- a/src/lib/pubkey/gost_3410/gost_3410.cpp +++ b/src/lib/pubkey/gost_3410/gost_3410.cpp @@ -9,6 +9,7 @@ #include <botan/gost_3410.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/reducer.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> @@ -151,7 +152,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_ const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(gost.domain()), - m_public_point(gost.public_point()) + m_gy_mul(m_group.get_base_point(), gost.public_point()) {} size_t max_input_bits() const override { return m_group.get_order_bits(); } @@ -162,7 +163,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_ const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; }; bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, @@ -184,12 +185,12 @@ bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_le if(e == 0) e = 1; - const BigInt v = inverse_mod(e, order); + const BigInt v = m_group.inverse_mod_order(e); const BigInt z1 = m_group.multiply_mod_order(s, v); const BigInt z2 = m_group.multiply_mod_order(-r, v); - const PointGFp R = m_group.point_multiply(z1, m_public_point, z2); + const PointGFp R = m_gy_mul.multi_exp(z1, z2); if(R.is_zero()) return false; diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp index 69d7052dc..fdc5b63d0 100644 --- a/src/lib/pubkey/rsa/rsa.cpp +++ b/src/lib/pubkey/rsa/rsa.cpp @@ -141,14 +141,19 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng, m_e = exp; + const size_t p_bits = (bits + 1) / 2; + const size_t q_bits = bits - p_bits; + do { - m_p = random_prime(rng, (bits + 1) / 2, m_e); - m_q = random_prime(rng, bits - m_p.bits(), m_e); + m_p = generate_rsa_prime(rng, rng, p_bits, m_e); + m_q = generate_rsa_prime(rng, rng, q_bits, m_e); m_n = m_p * m_q; } while(m_n.bits() != bits); + // FIXME: lcm calls gcd which is not const time const BigInt phi_n = lcm(m_p - 1, m_q - 1); + // FIXME: this uses binary ext gcd because phi_n is even m_d = inverse_mod(m_e, phi_n); m_d1 = m_d % (m_p - 1); m_d2 = m_d % (m_q - 1); @@ -356,7 +361,7 @@ class RSA_Public_Operation const size_t powm_window = 1; - auto powm_m_n = monty_precompute(m_monty_n, m, powm_window); + auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false); return monty_execute_vartime(*powm_m_n, m_e); } diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp index 4b5610c85..1096ea99f 100644 --- a/src/lib/pubkey/sm2/sm2.cpp +++ b/src/lib/pubkey/sm2/sm2.cpp @@ -8,6 +8,7 @@ #include <botan/sm2.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/numthry.h> #include <botan/keypair.h> #include <botan/hash.h> @@ -30,7 +31,7 @@ SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(const AlgorithmIdentifier& al const secure_vector<uint8_t>& key_bits) : EC_PrivateKey(alg_id, key_bits) { - m_da_inv = inverse_mod(m_private_key + 1, domain().get_order()); + m_da_inv = domain().inverse_mod_order(m_private_key + 1); } SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(RandomNumberGenerator& rng, @@ -38,7 +39,7 @@ SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(RandomNumberGenerator& rng, const BigInt& x) : EC_PrivateKey(rng, domain, x) { - m_da_inv = inverse_mod(m_private_key + 1, domain.get_order()); + m_da_inv = domain.inverse_mod_order(m_private_key + 1); } std::vector<uint8_t> sm2_compute_za(HashFunction& hash, @@ -136,11 +137,11 @@ class SM2_Verification_Operation final : public PK_Ops::Verification const std::string& ident, const std::string& hash) : m_group(sm2.domain()), - m_public_point(sm2.public_point()), + m_gy_mul(m_group.get_base_point(), sm2.public_point()), m_hash(HashFunction::create_or_throw(hash)) { // ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) - m_za = sm2_compute_za(*m_hash, ident, m_group, m_public_point); + m_za = sm2_compute_za(*m_hash, ident, m_group, sm2.public_point()); m_hash->update(m_za); } @@ -152,7 +153,7 @@ class SM2_Verification_Operation final : public PK_Ops::Verification bool is_valid_signature(const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; std::vector<uint8_t> m_za; std::unique_ptr<HashFunction> m_hash; }; @@ -178,7 +179,7 @@ bool SM2_Verification_Operation::is_valid_signature(const uint8_t sig[], size_t if(t == 0) return false; - const PointGFp R = m_group.point_multiply(s, m_public_point, t); + const PointGFp R = m_gy_mul.multi_exp(s, t); // ??? if(R.is_zero()) diff --git a/src/lib/pubkey/xmss/xmss_hash.cpp b/src/lib/pubkey/xmss/xmss_hash.cpp index a691453dc..cd714873c 100644 --- a/src/lib/pubkey/xmss/xmss_hash.cpp +++ b/src/lib/pubkey/xmss/xmss_hash.cpp @@ -56,11 +56,6 @@ void XMSS_Hash::h_msg_init(const secure_vector<uint8_t>& randomness, m_msg_hash->update(index_bytes); } -void XMSS_Hash::h_msg_update(const secure_vector<uint8_t>& data) - { - m_msg_hash->update(data); - } - void XMSS_Hash::h_msg_update(const uint8_t data[], size_t size) { m_msg_hash->update(data, size); diff --git a/src/lib/pubkey/xmss/xmss_hash.h b/src/lib/pubkey/xmss/xmss_hash.h index 85cebdc91..f45432d59 100644 --- a/src/lib/pubkey/xmss/xmss_hash.h +++ b/src/lib/pubkey/xmss/xmss_hash.h @@ -120,13 +120,6 @@ class XMSS_Hash final * Adds a message block to buffered h_msg computation. * * @param data A message block - **/ - void h_msg_update(const secure_vector<uint8_t>& data); - - /** - * Adds a message block to buffered h_msg computation. - * - * @param data A message block * @param size Length of the message block in bytes. **/ void h_msg_update(const uint8_t data[], size_t size); diff --git a/src/lib/pubkey/xmss/xmss_signature.cpp b/src/lib/pubkey/xmss/xmss_signature.cpp index 88ef42655..88809cf7b 100644 --- a/src/lib/pubkey/xmss/xmss_signature.cpp +++ b/src/lib/pubkey/xmss/xmss_signature.cpp @@ -1,6 +1,6 @@ /* * XMSS Signature - * (C) 2016,2017 Matthias Gierlings + * (C) 2016,2017,2018 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) **/ @@ -14,24 +14,23 @@ XMSS_Signature::XMSS_Signature(XMSS_Parameters::xmss_algorithm_t oid, const secure_vector<uint8_t>& raw_sig) : m_leaf_idx(0), m_randomness(0, 0x00), m_tree_sig() { - BOTAN_ASSERT(sizeof(size_t) >= std::ceil(static_cast<float>( - (XMSS_Parameters(oid)).tree_height()) / 8.f), - "System type \"size_t\" not big enough to support" - " leaf index."); - XMSS_Parameters xmss_params(oid); - uint64_t leaf_idx = 0; + + if(raw_sig.size() != (xmss_params.len() + xmss_params.tree_height() + 1) + * xmss_params.element_size() + sizeof(m_leaf_idx)) + { + throw Integrity_Failure("XMSS signature size invalid."); + } + for(size_t i = 0; i < 8; i++) - { leaf_idx = ((leaf_idx << 8) | raw_sig[i]); } + { m_leaf_idx = ((m_leaf_idx << 8) | raw_sig[i]); } - if(leaf_idx >= (1ull << (xmss_params.tree_height() - 1))) + if(m_leaf_idx >= (1ull << (xmss_params.tree_height() - 1))) { - throw Integrity_Failure("XMSS signature leaf index out of " - "bounds."); + throw Integrity_Failure("XMSS signature leaf index out of bounds."); } - m_leaf_idx = static_cast<size_t>(leaf_idx); - auto begin = raw_sig.begin() + sizeof(uint64_t); + auto begin = raw_sig.begin() + sizeof(m_leaf_idx); auto end = begin + xmss_params.element_size(); std::copy(begin, end, std::back_inserter(m_randomness)); @@ -64,14 +63,14 @@ secure_vector<uint8_t> XMSS_Signature::bytes() const { secure_vector<uint8_t> result { - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 56U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 48U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 40U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 32U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 24U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 16U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 8U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx)) + static_cast<uint8_t>(m_leaf_idx >> 56U), + static_cast<uint8_t>(m_leaf_idx >> 48U), + static_cast<uint8_t>(m_leaf_idx >> 40U), + static_cast<uint8_t>(m_leaf_idx >> 32U), + static_cast<uint8_t>(m_leaf_idx >> 24U), + static_cast<uint8_t>(m_leaf_idx >> 16U), + static_cast<uint8_t>(m_leaf_idx >> 8U), + static_cast<uint8_t>(m_leaf_idx) }; std::copy(m_randomness.begin(), diff --git a/src/lib/pubkey/xmss/xmss_signature.h b/src/lib/pubkey/xmss/xmss_signature.h index 838aae2e8..25e168fd8 100644 --- a/src/lib/pubkey/xmss/xmss_signature.h +++ b/src/lib/pubkey/xmss/xmss_signature.h @@ -117,7 +117,7 @@ class XMSS_Signature final secure_vector<uint8_t> bytes() const; private: - size_t m_leaf_idx; + uint64_t m_leaf_idx; secure_vector<uint8_t> m_randomness; XMSS_WOTS_PublicKey::TreeSignature m_tree_sig; }; diff --git a/src/lib/pubkey/xmss/xmss_tools.cpp b/src/lib/pubkey/xmss/xmss_tools.cpp index f4f762aeb..585e14f2e 100644 --- a/src/lib/pubkey/xmss/xmss_tools.cpp +++ b/src/lib/pubkey/xmss/xmss_tools.cpp @@ -19,26 +19,28 @@ size_t XMSS_Tools::max_threads() size_t XMSS_Tools::bench_threads() { - if(std::thread::hardware_concurrency() <= 1) + const size_t hardware_concurrency = std::thread::hardware_concurrency(); + + if(hardware_concurrency <= 1) { return 1; } const size_t BENCH_ITERATIONS = 1000; std::vector<std::thread> threads; - threads.reserve(std::thread::hardware_concurrency()); + threads.reserve(hardware_concurrency); std::vector<std::chrono::nanoseconds> durations; - std::vector<size_t> concurrency { std::thread::hardware_concurrency(), - std::thread::hardware_concurrency() / 2 }; + std::vector<size_t> concurrency { hardware_concurrency, + hardware_concurrency / 2 }; for(const auto& cc : concurrency) { - std::vector<XMSS_Hash> hash(std::thread::hardware_concurrency(), + std::vector<XMSS_Hash> hash(hardware_concurrency, XMSS_Hash("SHA-256")); const std::vector<uint8_t> buffer(hash[0].output_length()); std::vector<secure_vector<uint8_t>> data( - std::thread::hardware_concurrency(), + hardware_concurrency, secure_vector<uint8_t>(hash[0].output_length())); auto start = std::chrono::high_resolution_clock::now(); for(size_t i = 0; i < cc; ++i) @@ -46,7 +48,7 @@ size_t XMSS_Tools::bench_threads() auto& hs = hash[i]; auto& d = data[i]; - const size_t n_iters = BENCH_ITERATIONS * (std::thread::hardware_concurrency() / cc); + const size_t n_iters = BENCH_ITERATIONS * (hardware_concurrency / cc); threads.emplace_back(std::thread([n_iters, &hs, &d]() { for(size_t n = 0; n < n_iters; n++) @@ -66,11 +68,19 @@ size_t XMSS_Tools::bench_threads() if(durations[0].count() < durations[1].count()) { +#if defined(BOTAN_TEST_MODE) + return 4; +#else return concurrency[0]; +#endif } else { +#if defined(BOTAN_TEST_MODE) + return 4; +#else return concurrency[1]; +#endif } } |