11#include <botan/ec_group.h>
13#include <botan/ber_dec.h>
14#include <botan/der_enc.h>
15#include <botan/mutex.h>
16#include <botan/numthry.h>
19#include <botan/internal/barrett.h>
20#include <botan/internal/ec_inner_data.h>
21#include <botan/internal/fmt.h>
22#include <botan/internal/primality.h>
27class EC_Group_Data_Map final {
29 EC_Group_Data_Map() =
default;
33 const size_t count = m_registered_curves.size();
34 m_registered_curves.clear();
38 bool unregister(
const OID& oid) {
41 throw Invalid_Argument(
"OID must not be empty");
45 for(
size_t i = 0; i < m_registered_curves.size(); i++) {
46 if(m_registered_curves[i]->oid() == oid) {
47 m_registered_curves.erase(m_registered_curves.begin() + i);
54 std::shared_ptr<EC_Group_Data> lookup(
const OID& oid) {
57 for(
auto i : m_registered_curves) {
69 if(data->oid() != oid) {
70 for(
const auto& i : m_registered_curves) {
71 if(i->oid() == data->oid()) {
77 m_registered_curves.push_back(data);
82 return std::shared_ptr<EC_Group_Data>();
85 std::shared_ptr<EC_Group_Data> lookup_or_create(
const BigInt& p,
91 const BigInt& cofactor,
98 for(
auto i : m_registered_curves) {
108 if(!i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
109 throw Invalid_Argument(
"Attempting to register a curve using OID " + oid.to_string() +
110 " but a distinct curve is already registered using that OID");
123 if(i->oid().empty() && i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
132 auto new_group = [&] {
139 "Attempting to register an EC group under OID of hardcoded group");
152 "EC_Group generator does not have the claimed order");
155 m_registered_curves.push_back(new_group);
159 std::shared_ptr<EC_Group_Data> lookup_from_params(
const BigInt& p,
162 std::span<const uint8_t> base_pt,
164 const BigInt& cofactor) {
167 for(
auto i : m_registered_curves) {
168 if(i->params_match(p, a, b, base_pt, order, cofactor)) {
175 if(oid_from_order.has_value()) {
179 if(new_group && new_group->params_match(p, a, b, base_pt, order, cofactor)) {
180 m_registered_curves.push_back(new_group);
189 std::shared_ptr<EC_Group_Data> lookup_or_create_without_oid(
const BigInt& p,
195 const BigInt& cofactor,
199 for(
auto i : m_registered_curves) {
200 if(i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
207 if(oid_from_order.has_value()) {
211 if(new_group && new_group->params_match(p, a, b, g_x, g_y, order, cofactor)) {
212 m_registered_curves.push_back(new_group);
227 "EC_Group generator does not have the claimed order");
229 m_registered_curves.push_back(new_group);
236 std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
240EC_Group_Data_Map& EC_Group::ec_group_data() {
246 static const Allocator_Initializer g_init_allocator;
253 return ec_group_data().clear();
257std::shared_ptr<EC_Group_Data> EC_Group::load_EC_group_info(
const char* p_str,
262 const char* order_str,
269 const BigInt g_x(g_x_str);
270 const BigInt g_y(g_y_str);
271 const BigInt order(order_str);
278std::pair<std::shared_ptr<EC_Group_Data>,
bool> EC_Group::DER_decode_EC_group(std::span<const uint8_t> der,
282 const auto next_obj_type = dec.peek_next_object().type_tag();
286 dec.decode(oid).verify_end();
288 const auto data = ec_group_data().lookup(oid);
290 throw Decoding_Error(
fmt(
"Unknown namedCurve OID '{}'", oid.to_string()));
293 return std::make_pair(data,
false);
300 std::vector<uint8_t> base_pt;
301 std::vector<uint8_t> seed;
304 .decode_and_check<
size_t>(1,
"Unknown ECC param version code")
306 .decode_and_check(OID({1, 2, 840, 10045, 1, 1}),
"Only prime ECC fields supported")
310 .decode_octet_string_bigint(a)
311 .decode_octet_string_bigint(b)
321 if(cofactor <= 0 || cofactor >= 16) {
322 throw Decoding_Error(
"Invalid ECC cofactor parameter");
325 if(p.bits() < 112 || p.bits() > 521 || p.signum() < 0) {
326 throw Decoding_Error(
"ECC p parameter is invalid size");
330 if(a.signum() < 0 || a >= p) {
331 throw Decoding_Error(
"Invalid ECC a parameter");
338 if(b.signum() <= 0 || b >= p) {
339 throw Decoding_Error(
"Invalid ECC b parameter");
342 if(order.signum() <= 0 || order >= 2 * p) {
343 throw Decoding_Error(
"Invalid ECC group order");
347 throw Decoding_Error(
"Anomalous elliptic curves are not supported");
350 if(
const auto data = ec_group_data().lookup_from_params(p, a, b, base_pt, order, cofactor)) {
351 return std::make_pair(data,
true);
362 throw Decoding_Error(
"ECC p parameter is not a prime");
366 throw Decoding_Error(
"Invalid ECC order parameter");
369 if((p - cofactor * order).
abs().bits() > (p.bits() / 2) + 1) {
370 throw Decoding_Error(
"Invalid ECC Hasse bound");
373 const auto discriminant = mod_p.reduce(mod_p.multiply(
BigInt::from_s32(4), mod_p.cube(a)) +
375 if(discriminant == 0) {
376 throw Decoding_Error(
"Invalid ECC curve discriminant");
379 const size_t p_bytes = p.bytes();
380 if(base_pt.size() != 1 + p_bytes && base_pt.size() != 1 + 2 * p_bytes) {
381 throw Decoding_Error(
"Invalid ECC base point encoding");
384 auto [g_x, g_y] = [&]() {
385 const uint8_t hdr = base_pt[0];
387 if(hdr == 0x04 && base_pt.size() == 1 + 2 * p_bytes) {
389 const BigInt y =
BigInt::from_bytes(std::span{base_pt}.subspan(1 + p_bytes, p_bytes));
392 return std::make_pair(x, y);
394 }
else if((hdr == 0x02 || hdr == 0x03) && base_pt.size() == 1 + p_bytes) {
399 if(x < p && y >= 0) {
400 const bool y_mod_2 = (hdr & 0x01) == 1;
401 if(y.get_bit(0) != y_mod_2) {
405 return std::make_pair(x, y);
409 throw Decoding_Error(
"Invalid ECC base point encoding");
413 const auto y2 = mod_p.square(g_y);
414 const auto x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
416 throw Decoding_Error(
"Invalid ECC base point");
427 if(!EC_Group::verify_generator_order(data)) {
428 throw Decoding_Error(
"ECC generator does not have the claimed order");
431 return std::make_pair(data,
true);
433 throw Decoding_Error(
"Decoding ImplicitCA ECC parameters is not supported");
435 throw Decoding_Error(
449EC_Group::EC_Group(std::shared_ptr<const EC_Group_Data> data) : m_data(std::move(data)) {}
452bool EC_Group::verify_generator_order(std::shared_ptr<const EC_Group_Data> data) {
453 const EC_Group group(std::move(data));
455#if defined(BOTAN_HAS_LEGACY_EC_POINT)
457 return (group.get_base_point() * group.get_order()).is_zero();
469 return n_minus_one_g == g_pt->negate();
486 if(ec_group_data().lookup(oid.value()) !=
nullptr) {
501#if defined(BOTAN_HAS_LEGACY_EC_POINT) || defined(BOTAN_HAS_PCURVES_GENERIC)
510#if defined(BOTAN_HAS_LEGACY_EC_POINT)
519 auto data = ec_group_data().lookup(oid);
530 std::shared_ptr<EC_Group_Data> data;
533 data = ec_group_data().lookup(oid.value());
551 m_data = ec_group_data().lookup(oid);
555 if(m_data ==
nullptr) {
556 if(str.size() > 30 && str.starts_with(
"-----BEGIN EC PARAMETERS-----")) {
561 this->m_data = data.first;
562 this->m_explicit_encoding = data.second;
566 if(m_data ==
nullptr) {
587 BOTAN_ARG_CHECK(base_x >= 0 && base_x < p,
"EC_Group base_x is invalid");
588 BOTAN_ARG_CHECK(base_y >= 0 && base_y < p,
"EC_Group base_y is invalid");
590 BOTAN_ARG_CHECK(cofactor >= 1 && cofactor < 16,
"EC_Group cofactor is invalid");
597 BOTAN_ARG_CHECK(p != order,
"Anomalous elliptic curves are not supported");
602 const auto discriminant = mod_p.reduce(mod_p.multiply(
BigInt::from_s32(4), mod_p.cube(a)) +
604 BOTAN_ARG_CHECK(discriminant != 0,
"EC_Group discriminant is invalid");
607 const auto y2 = mod_p.square(base_y);
608 const auto x3_ax_b = mod_p.reduce(mod_p.cube(base_x) + mod_p.multiply(a, base_x) + b);
609 BOTAN_ARG_CHECK(y2 == x3_ax_b,
"EC_Group generator is not on the curve");
612 m_data = ec_group_data().lookup_or_create(
615 m_data = ec_group_data().lookup_or_create_without_oid(
640#if defined(BOTAN_DISABLE_DEPRECATED_FEATURES)
641 constexpr size_t p_bits_lower_bound = 192;
643 constexpr size_t p_bits_lower_bound = 128;
649 if(p.
bits() == 521) {
651 BOTAN_ARG_CHECK(p == p521,
"EC_Group with p of 521 bits must be 2**521-1");
652 }
else if(p.
bits() == 239) {
653 const auto x962_p239 = []() {
655 for(
size_t i = 0; i != 239; ++i) {
656 if(i < 47 || ((i >= 94) && (i != 143))) {
663 BOTAN_ARG_CHECK(p == x962_p239,
"EC_Group with p of 239 bits must be the X9.62 prime");
668 BOTAN_ARG_CHECK(p % 4 == 3,
"EC_Group p must be congruent to 3 modulo 4");
672 BOTAN_ARG_CHECK(base_x >= 0 && base_x < p,
"EC_Group base_x is invalid");
673 BOTAN_ARG_CHECK(base_y >= 0 && base_y < p,
"EC_Group base_y is invalid");
681 BOTAN_ARG_CHECK(p != order,
"Anomalous elliptic curves are not supported");
688 const auto discriminant = mod_p.reduce(mod_p.multiply(
BigInt::from_s32(4), mod_p.cube(a)) +
690 BOTAN_ARG_CHECK(discriminant != 0,
"EC_Group discriminant is invalid");
693 const auto y2 = mod_p.square(base_y);
694 const auto x3_ax_b = mod_p.reduce(mod_p.cube(base_x) + mod_p.multiply(a, base_x) + b);
695 BOTAN_ARG_CHECK(y2 == x3_ax_b,
"EC_Group generator is not on the curve");
706 m_explicit_encoding = data.second;
711 return ec_group_data().unregister(oid);
715 if(m_data ==
nullptr) {
722 return data().p_bits();
726 return data().p_bytes();
730 return data().order_bits();
734 return data().order_bytes();
749#if defined(BOTAN_HAS_LEGACY_EC_POINT)
750const EC_Point& EC_Group::get_base_point()
const {
751 return data().base_point();
754const EC_Point& EC_Group::generator()
const {
755 return data().base_point();
758bool EC_Group::verify_public_element(
const EC_Point& point)
const {
760 if(point.is_zero()) {
765 if(point.on_the_curve() ==
false) {
770 if((point *
get_order()).is_zero() ==
false) {
786 return data().order();
798 return data().cofactor();
802 return data().has_cofactor();
810 return data().source();
814 return data().engine();
818 return data().hash_to_curve_supported(hash_fn);
822 const auto& der_named_curve = data().der_named_curve();
824 if(der_named_curve.empty()) {
825 throw Encoding_Error(
"Cannot encode EC_Group as OID because OID not set");
828 return der_named_curve;
833 std::vector<uint8_t> output;
835 const size_t ecpVers1 = 1;
836 const OID curve_type(
"1.2.840.10045.1.1");
867 const std::vector<uint8_t> der =
DER_encode(form);
872 if(m_data == other.m_data) {
896 if(p <= 3 || order <= 0) {
902 if(a < 0 || a >= p) {
905 if(b <= 0 || b >= p) {
909 const size_t test_prob = strong ? 128 : 12;
910 const bool is_randomly_generated =
false;
928 if(discriminant == 0) {
941 const BigInt x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
947 if(!EC_Group::verify_generator_order(m_data)) {
951#if defined(BOTAN_HAS_LEGACY_EC_POINT)
955 const EC_Point& base_point = get_base_point();
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
static Barrett_Reduction for_public_modulus(const BigInt &m)
static BigInt from_bytes(std::span< const uint8_t > bytes)
static BigInt power_of_2(size_t n)
static BigInt from_s32(int32_t n)
BigInt & square(secure_vector< word > &ws)
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
static std::optional< EC_AffinePoint > from_bigint_xy(const EC_Group &group, const BigInt &x, const BigInt &y)
static EC_AffinePoint g_mul(const EC_Scalar &scalar, RandomNumberGenerator &rng)
Multiply by the group generator returning a complete point.
T serialize_uncompressed() const
static EC_AffinePoint _from_inner(std::unique_ptr< EC_AffinePoint_Data > inner)
static EC_AffinePoint generator(const EC_Group &group)
Return the standard group generator.
Mul2Table & operator=(const Mul2Table &other)=delete
std::optional< EC_AffinePoint > mul2_vartime(const EC_Scalar &x, const EC_Scalar &y) const
BOTAN_FUTURE_EXPLICIT Mul2Table(const EC_AffinePoint &h)
bool mul2_vartime_x_mod_order_eq(const EC_Scalar &v, const EC_Scalar &x, const EC_Scalar &y) const
static std::shared_ptr< EC_Group_Data > 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, EC_Group_Source source)
static EC_Group from_name(std::string_view name)
static EC_Group from_PEM(std::string_view pem)
const BigInt & get_b() const
const BigInt & get_a() const
const BigInt & get_g_y() const
const BigInt & get_cofactor() const
bool operator==(const EC_Group &other) const
static bool supports_application_specific_group_with_cofactor()
static EC_Group register_custom_group(const OID &oid, const BigInt &p, const BigInt &a, const BigInt &b, const BigInt &base_x, const BigInt &base_y, const BigInt &order)
EC_Group_Engine engine() const
EC_Group_Source source() const
const BigInt & get_p() const
bool verify_group(RandomNumberGenerator &rng, bool strong=false) const
const BigInt & get_order() const
size_t get_p_bits() const
static EC_Group from_OID(const OID &oid)
static std::shared_ptr< EC_Group_Data > EC_group_info(const OID &oid)
std::vector< uint8_t > DER_encode() const
const BigInt & get_g_x() const
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=OID())
const OID & get_curve_oid() const
static bool supports_application_specific_group()
static const std::set< std::string > & known_named_groups()
bool has_cofactor() const
static size_t clear_registered_curve_data()
static bool unregister(const OID &oid)
friend class EC_Group_Data_Map
static bool supports_named_group(std::string_view name)
EC_Group & operator=(const EC_Group &)
size_t get_p_bytes() const
static OID EC_group_identity_from_order(const BigInt &order)
std::string PEM_encode(EC_Group_Encoding form=EC_Group_Encoding::Explicit) const
bool hash_to_curve_supported(std::string_view hash_fn) const
friend class EC_AffinePoint
size_t get_order_bits() const
size_t get_order_bytes() const
static EC_Scalar one(const EC_Group &group)
const EC_Scalar_Data & _inner() const
static std::optional< OID > from_name(std::string_view name)
std::string to_string() const
static OID from_string(std::string_view str)
std::string encode(const uint8_t der[], size_t length, std::string_view label, size_t width)
secure_vector< uint8_t > decode_check_label(DataSource &source, std::string_view label_want)
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
bool is_prime_vartime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
std::string asn1_tag_to_string(ASN1_Type type)
std::string fmt(std::string_view format, const T &... args)
BigInt abs(const BigInt &n)
secure_vector< T > lock(const std::vector< T > &in)
bool is_bailie_psw_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
lock_guard< T > lock_guard_type
BigInt sqrt_modulo_prime(const BigInt &a, const BigInt &p)