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 | 753 |
1 files changed, 0 insertions, 753 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 deleted file mode 100644 index f4419c7f0b..0000000000 --- a/src/libs/3rdparty/botan/src/lib/pubkey/ec_group/ec_group.cpp +++ /dev/null @@ -1,753 +0,0 @@ -/* -* 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/internal/primality.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> - -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(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p)) - 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 || !is_bailie_psw_probable_prime(order)) - 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(); - } - -size_t EC_Group::point_size(PointGFp::Compression_Type format) const - { - // Hybrid and standard format are (x,y), compressed is y, +1 format byte - if(format == PointGFp::COMPRESSED) - return (1 + get_p_bytes()); - else - return (1 + 2*get_p_bytes()); - } - -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; - } - -} |