diff options
Diffstat (limited to 'src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp')
| -rw-r--r-- | src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp | 765 |
1 files changed, 765 insertions, 0 deletions
diff --git a/src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp b/src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp new file mode 100644 index 0000000000..586603507e --- /dev/null +++ b/src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp @@ -0,0 +1,765 @@ +/* +* ECC Domain Parameters +* +* (C) 2007 Falko Strenzke, FlexSecure GmbH +* (C) 2008,2018 Jack Lloyd +* (C) 2018 Tobias Niemann +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include <botan/ec_group.h> +#include <botan/internal/point_mul.h> +#include <botan/ber_dec.h> +#include <botan/der_enc.h> +#include <botan/oids.h> +#include <botan/pem.h> +#include <botan/reducer.h> +#include <botan/mutex.h> +#include <botan/rng.h> +#include <vector> + +#if defined(BOTAN_HAS_SYSTEM_RNG) + #include <botan/system_rng.h> +#elif defined(BOTAN_HAS_HMAC_DRBG) && defined(BOTAN_HAS_SHA2_32) + #include <botan/hmac_drbg.h> +#endif + +namespace Botan { + +class EC_Group_Data final + { + public: + + EC_Group_Data(const BigInt& p, + const BigInt& a, + const BigInt& b, + const BigInt& g_x, + const BigInt& g_y, + const BigInt& order, + const BigInt& cofactor, + const OID& oid) : + m_curve(p, a, b), + m_base_point(m_curve, g_x, g_y), + m_g_x(g_x), + m_g_y(g_y), + m_order(order), + m_cofactor(cofactor), + m_mod_order(order), + m_base_mult(m_base_point, m_mod_order), + m_oid(oid), + m_p_bits(p.bits()), + m_order_bits(order.bits()), + m_a_is_minus_3(a == p - 3), + m_a_is_zero(a.is_zero()) + { + } + + bool match(const BigInt& p, const BigInt& a, const BigInt& b, + const BigInt& g_x, const BigInt& g_y, + const BigInt& order, const BigInt& cofactor) const + { + return (this->p() == p && + this->a() == a && + this->b() == b && + this->order() == order && + this->cofactor() == cofactor && + this->g_x() == g_x && + this->g_y() == g_y); + } + + const OID& oid() const { return m_oid; } + const BigInt& p() const { return m_curve.get_p(); } + const BigInt& a() const { return m_curve.get_a(); } + const BigInt& b() const { return m_curve.get_b(); } + const BigInt& order() const { return m_order; } + const BigInt& cofactor() const { return m_cofactor; } + const BigInt& g_x() const { return m_g_x; } + const BigInt& g_y() const { return m_g_y; } + + size_t p_bits() const { return m_p_bits; } + size_t p_bytes() const { return (m_p_bits + 7) / 8; } + + size_t order_bits() const { return m_order_bits; } + size_t order_bytes() const { return (m_order_bits + 7) / 8; } + + const CurveGFp& curve() const { return m_curve; } + 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); } + + BigInt square_mod_order(const BigInt& x) const + { + return m_mod_order.square(x); + } + + BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const + { + return m_mod_order.multiply(x, y); + } + + BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const + { + return m_mod_order.multiply(m_mod_order.multiply(x, y), z); + } + + 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 + { + return m_base_mult.mul(k, rng, m_order, ws); + } + + private: + CurveGFp m_curve; + PointGFp m_base_point; + + BigInt m_g_x; + BigInt m_g_y; + BigInt m_order; + BigInt m_cofactor; + Modular_Reducer m_mod_order; + PointGFp_Base_Point_Precompute m_base_mult; + OID m_oid; + 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 + { + public: + EC_Group_Data_Map() {} + + size_t clear() + { + lock_guard_type<mutex_type> lock(m_mutex); + size_t count = m_registered_curves.size(); + m_registered_curves.clear(); + return count; + } + + std::shared_ptr<EC_Group_Data> lookup(const OID& oid) + { + lock_guard_type<mutex_type> lock(m_mutex); + + for(auto i : m_registered_curves) + { + if(i->oid() == oid) + return i; + } + + // Not found, check hardcoded data + std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); + + if(data) + { + m_registered_curves.push_back(data); + return data; + } + + // Nope, unknown curve + return std::shared_ptr<EC_Group_Data>(); + } + + std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p, + const BigInt& a, + const BigInt& b, + const BigInt& g_x, + const BigInt& g_y, + const BigInt& order, + const BigInt& cofactor, + const OID& oid) + { + lock_guard_type<mutex_type> lock(m_mutex); + + for(auto i : m_registered_curves) + { + if(oid.has_value()) + { + if(i->oid() == oid) + return i; + else if(i->oid().has_value()) + continue; + } + + if(i->match(p, a, b, g_x, g_y, order, cofactor)) + return i; + } + + // Not found - if OID is set try looking up that way + + if(oid.has_value()) + { + // Not located in existing store - try hardcoded data set + std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); + + if(data) + { + m_registered_curves.push_back(data); + return data; + } + } + + // Not found or no OID, add data and return + return add_curve(p, a, b, g_x, g_y, order, cofactor, oid); + } + + private: + + std::shared_ptr<EC_Group_Data> add_curve(const BigInt& p, + const BigInt& a, + const BigInt& b, + const BigInt& g_x, + const BigInt& g_y, + const BigInt& order, + const BigInt& cofactor, + const OID& oid) + { + std::shared_ptr<EC_Group_Data> d = + std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid); + + // This function is always called with the lock held + m_registered_curves.push_back(d); + return d; + } + + mutex_type m_mutex; + std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves; + }; + +//static +EC_Group_Data_Map& EC_Group::ec_group_data() + { + /* + * This exists purely to ensure the allocator is constructed before g_ec_data, + * which ensures that its destructor runs after ~g_ec_data is complete. + */ + + static Allocator_Initializer g_init_allocator; + static EC_Group_Data_Map g_ec_data; + return g_ec_data; + } + +//static +size_t EC_Group::clear_registered_curve_data() + { + return ec_group_data().clear(); + } + +//static +std::shared_ptr<EC_Group_Data> +EC_Group::load_EC_group_info(const char* p_str, + const char* a_str, + const char* b_str, + const char* g_x_str, + const char* g_y_str, + const char* order_str, + const OID& oid) + { + const BigInt p(p_str); + const BigInt a(a_str); + const BigInt b(b_str); + const BigInt g_x(g_x_str); + const BigInt g_y(g_y_str); + const BigInt order(order_str); + const BigInt cofactor(1); // implicit + + return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid); + } + +//static +std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[], size_t len) + { + BER_Decoder ber(bits, len); + BER_Object obj = ber.get_next_object(); + + if(obj.type() == NULL_TAG) + { + throw Decoding_Error("Cannot handle ImplicitCA ECC parameters"); + } + else if(obj.type() == OBJECT_ID) + { + OID dom_par_oid; + BER_Decoder(bits, len).decode(dom_par_oid); + return ec_group_data().lookup(dom_par_oid); + } + else if(obj.type() == SEQUENCE) + { + BigInt p, a, b, order, cofactor; + std::vector<uint8_t> base_pt; + std::vector<uint8_t> seed; + + BER_Decoder(bits, len) + .start_cons(SEQUENCE) + .decode_and_check<size_t>(1, "Unknown ECC param version code") + .start_cons(SEQUENCE) + .decode_and_check(OID("1.2.840.10045.1.1"), + "Only prime ECC fields supported") + .decode(p) + .end_cons() + .start_cons(SEQUENCE) + .decode_octet_string_bigint(a) + .decode_octet_string_bigint(b) + .decode_optional_string(seed, BIT_STRING, BIT_STRING) + .end_cons() + .decode(base_pt, OCTET_STRING) + .decode(order) + .decode(cofactor) + .end_cons() + .verify_end(); + +#if defined(BOTAN_HAS_SYSTEM_RNG) + System_RNG rng; +#elif defined(BOTAN_HAS_HMAC_DRBG) && defined(BOTAN_HAS_SHA2_32) + /* + * This is not ideal because the data is attacker controlled, but + * it seems like it would be difficult for someone to come up + * with an valid ASN.1 encoding where the prime happened to pass + * Miller-Rabin test with exactly the values chosen when + * HMAC_DRBG is seeded with the overall data. + */ + HMAC_DRBG rng("SHA-256"); + rng.add_entropy(bits, len); +#else + Null_RNG rng; +#endif + + if(p.bits() < 64 || p.is_negative() || (is_prime(p, rng) == false)) + throw Decoding_Error("Invalid ECC p parameter"); + + if(a.is_negative() || a >= p) + throw Decoding_Error("Invalid ECC a parameter"); + + if(b <= 0 || b >= p) + throw Decoding_Error("Invalid ECC b parameter"); + + if(order <= 0) + throw Decoding_Error("Invalid ECC order parameter"); + + if(cofactor <= 0 || cofactor >= 16) + throw Decoding_Error("Invalid ECC cofactor parameter"); + + std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b); + + return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second, order, cofactor, OID()); + } + else + { + throw Decoding_Error("Unexpected tag while decoding ECC domain params"); + } + } + +EC_Group::EC_Group() + { + } + +EC_Group::~EC_Group() + { + // shared_ptr possibly freed here + } + +EC_Group::EC_Group(const OID& domain_oid) + { + this->m_data = ec_group_data().lookup(domain_oid); + if(!this->m_data) + throw Invalid_Argument("Unknown EC_Group " + domain_oid.as_string()); + } + +EC_Group::EC_Group(const std::string& str) + { + if(str == "") + return; // no initialization / uninitialized + + try + { + OID oid = OIDS::lookup(str); + if(oid.empty() == false) + m_data = ec_group_data().lookup(oid); + } + catch(Invalid_OID&) + { + } + + if(m_data == nullptr) + { + if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----") + { + // OK try it as PEM ... + secure_vector<uint8_t> ber = PEM_Code::decode_check_label(str, "EC PARAMETERS"); + this->m_data = BER_decode_EC_group(ber.data(), ber.size()); + } + } + + if(m_data == nullptr) + throw Invalid_Argument("Unknown ECC group '" + str + "'"); + } + +//static +std::string EC_Group::PEM_for_named_group(const std::string& name) + { + try + { + EC_Group group(name); + return group.PEM_encode(); + } + catch(...) + { + return ""; + } + } + +EC_Group::EC_Group(const BigInt& p, + const BigInt& a, + const BigInt& b, + const BigInt& base_x, + const BigInt& base_y, + const BigInt& order, + const BigInt& cofactor, + const OID& oid) + { + m_data = ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid); + } + +EC_Group::EC_Group(const std::vector<uint8_t>& ber) + { + m_data = BER_decode_EC_group(ber.data(), ber.size()); + } + +const EC_Group_Data& EC_Group::data() const + { + if(m_data == nullptr) + throw Invalid_State("EC_Group uninitialized"); + return *m_data; + } + +const CurveGFp& EC_Group::get_curve() const + { + return data().curve(); + } + +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(); + } + +size_t EC_Group::get_p_bytes() const + { + return data().p_bytes(); + } + +size_t EC_Group::get_order_bits() const + { + return data().order_bits(); + } + +size_t EC_Group::get_order_bytes() const + { + return data().order_bytes(); + } + +const BigInt& EC_Group::get_p() const + { + return data().p(); + } + +const BigInt& EC_Group::get_a() const + { + return data().a(); + } + +const BigInt& EC_Group::get_b() const + { + return data().b(); + } + +const PointGFp& EC_Group::get_base_point() const + { + return data().base_point(); + } + +const BigInt& EC_Group::get_order() const + { + return data().order(); + } + +const BigInt& EC_Group::get_g_x() const + { + return data().g_x(); + } + +const BigInt& EC_Group::get_g_y() const + { + return data().g_y(); + } + +const BigInt& EC_Group::get_cofactor() const + { + return data().cofactor(); + } + +BigInt EC_Group::mod_order(const BigInt& k) const + { + return data().mod_order(k); + } + +BigInt EC_Group::square_mod_order(const BigInt& x) const + { + return data().square_mod_order(x); + } + +BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const + { + return data().multiply_mod_order(x, y); + } + +BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const + { + return data().multiply_mod_order(x, y, z); + } + +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(); + } + +PointGFp EC_Group::OS2ECP(const uint8_t bits[], size_t len) const + { + return Botan::OS2ECP(bits, len, data().curve()); + } + +PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const + { + // TODO: randomize the representation? + return PointGFp(data().curve(), x, y); + } + +PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const + { + PointGFp_Multi_Point_Precompute xy_mul(get_base_point(), pt); + return xy_mul.multi_exp(x, y); + } + +PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k, + RandomNumberGenerator& rng, + std::vector<BigInt>& ws) const + { + return data().blinded_base_point_multiply(k, rng, ws); + } + +BigInt EC_Group::blinded_base_point_multiply_x(const BigInt& k, + RandomNumberGenerator& rng, + std::vector<BigInt>& ws) const + { + const PointGFp pt = data().blinded_base_point_multiply(k, rng, ws); + + if(pt.is_zero()) + return 0; + return pt.get_affine_x(); + } + +BigInt EC_Group::random_scalar(RandomNumberGenerator& rng) const + { + return BigInt::random_integer(rng, 1, get_order()); + } + +PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point, + const BigInt& k, + RandomNumberGenerator& rng, + std::vector<BigInt>& ws) const + { + PointGFp_Var_Point_Precompute mul(point, rng, ws); + return mul.mul(k, rng, get_order(), ws); + } + +PointGFp EC_Group::zero_point() const + { + return PointGFp(data().curve()); + } + +std::vector<uint8_t> +EC_Group::DER_encode(EC_Group_Encoding form) const + { + std::vector<uint8_t> output; + + DER_Encoder der(output); + + if(form == EC_DOMPAR_ENC_EXPLICIT) + { + const size_t ecpVers1 = 1; + const OID curve_type("1.2.840.10045.1.1"); // prime field + + const size_t p_bytes = get_p_bytes(); + + der.start_cons(SEQUENCE) + .encode(ecpVers1) + .start_cons(SEQUENCE) + .encode(curve_type) + .encode(get_p()) + .end_cons() + .start_cons(SEQUENCE) + .encode(BigInt::encode_1363(get_a(), p_bytes), + OCTET_STRING) + .encode(BigInt::encode_1363(get_b(), p_bytes), + OCTET_STRING) + .end_cons() + .encode(get_base_point().encode(PointGFp::UNCOMPRESSED), OCTET_STRING) + .encode(get_order()) + .encode(get_cofactor()) + .end_cons(); + } + else if(form == EC_DOMPAR_ENC_OID) + { + const OID oid = get_curve_oid(); + if(oid.empty()) + { + throw Encoding_Error("Cannot encode EC_Group as OID because OID not set"); + } + der.encode(oid); + } + else if(form == EC_DOMPAR_ENC_IMPLICITCA) + { + der.encode_null(); + } + else + { + throw Internal_Error("EC_Group::DER_encode: Unknown encoding"); + } + + return output; + } + +std::string EC_Group::PEM_encode() const + { + const std::vector<uint8_t> der = DER_encode(EC_DOMPAR_ENC_EXPLICIT); + return PEM_Code::encode(der, "EC PARAMETERS"); + } + +bool EC_Group::operator==(const EC_Group& other) const + { + if(m_data == other.m_data) + return true; // same shared rep + + /* + * No point comparing order/cofactor as they are uniquely determined + * by the curve equation (p,a,b) and the base point. + */ + return (get_p() == other.get_p() && + get_a() == other.get_a() && + get_b() == other.get_b() && + get_g_x() == other.get_g_x() && + get_g_y() == other.get_g_y()); + } + +bool EC_Group::verify_public_element(const PointGFp& point) const + { + //check that public point is not at infinity + if(point.is_zero()) + return false; + + //check that public point is on the curve + if(point.on_the_curve() == false) + return false; + + //check that public point has order q + if((point * get_order()).is_zero() == false) + return false; + + if(get_cofactor() > 1) + { + if((point * get_cofactor()).is_zero()) + return false; + } + + return true; + } + +bool EC_Group::verify_group(RandomNumberGenerator& rng, + bool) const + { + const BigInt& p = get_p(); + const BigInt& a = get_a(); + const BigInt& b = get_b(); + const BigInt& order = get_order(); + const PointGFp& base_point = get_base_point(); + + if(a < 0 || a >= p) + return false; + if(b <= 0 || b >= p) + return false; + if(order <= 0) + return false; + + //check if field modulus is prime + if(!is_prime(p, rng, 128)) + { + return false; + } + + //check if order is prime + if(!is_prime(order, rng, 128)) + { + return false; + } + + //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero + const Modular_Reducer mod_p(p); + + const BigInt discriminant = mod_p.reduce( + mod_p.multiply(4, mod_p.cube(a)) + + mod_p.multiply(27, mod_p.square(b))); + + if(discriminant == 0) + { + return false; + } + + //check for valid cofactor + if(get_cofactor() < 1) + { + return false; + } + + //check if the base point is on the curve + if(!base_point.on_the_curve()) + { + return false; + } + if((base_point * get_cofactor()).is_zero()) + { + return false; + } + //check if order of the base point is correct + if(!(base_point * order).is_zero()) + { + return false; + } + + return true; + } + +} |