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 size_t count = m_registered_curves.size();
34 m_registered_curves.clear();
38 std::shared_ptr<EC_Group_Data> lookup(
const OID& oid) {
41 for(
auto i : m_registered_curves) {
51 m_registered_curves.push_back(data);
56 return std::shared_ptr<EC_Group_Data>();
59 std::shared_ptr<EC_Group_Data> lookup_or_create(
const BigInt& p,
65 const BigInt& cofactor,
72 for(
auto i : m_registered_curves) {
82 if(!i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
83 throw Invalid_Argument(
"Attempting to register a curve using OID " + oid.to_string() +
84 " but a distinct curve is already registered using that OID");
97 if(i->oid().empty() && i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
106 auto new_group = [&] {
113 "Attempting to register an EC group under OID of hardcoded group");
124 m_registered_curves.push_back(new_group);
128 std::shared_ptr<EC_Group_Data> lookup_or_create_without_oid(
const BigInt& p,
134 const BigInt& cofactor,
138 for(
auto i : m_registered_curves) {
139 if(i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
146 if(oid_from_order.has_value()) {
150 if(new_group && new_group->params_match(p, a, b, g_x, g_y, order, cofactor)) {
151 m_registered_curves.push_back(new_group);
164 m_registered_curves.push_back(new_group);
171 std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
175EC_Group_Data_Map& EC_Group::ec_group_data() {
181 static Allocator_Initializer g_init_allocator;
182 static EC_Group_Data_Map g_ec_data;
188 return ec_group_data().clear();
192std::shared_ptr<EC_Group_Data> EC_Group::load_EC_group_info(
const char* p_str,
197 const char* order_str,
204 const BigInt g_x(g_x_str);
205 const BigInt g_y(g_y_str);
206 const BigInt order(order_str);
213std::pair<std::shared_ptr<EC_Group_Data>,
bool> EC_Group::BER_decode_EC_group(std::span<const uint8_t> bits,
215 BER_Decoder ber(bits);
217 auto next_obj_type = ber.peek_next_object().type_tag();
223 auto data = ec_group_data().lookup(oid);
225 throw Decoding_Error(
fmt(
"Unknown namedCurve OID '{}'", oid.to_string()));
228 return std::make_pair(data,
false);
230 BigInt p, a, b, order, cofactor;
231 std::vector<uint8_t> base_pt;
232 std::vector<uint8_t> seed;
235 .decode_and_check<
size_t>(1,
"Unknown ECC param version code")
237 .decode_and_check(OID({1, 2, 840, 10045, 1, 1}),
"Only prime ECC fields supported")
241 .decode_octet_string_bigint(a)
242 .decode_octet_string_bigint(b)
251 if(p.bits() < 112 || p.bits() > 521 || p.is_negative()) {
252 throw Decoding_Error(
"ECC p parameter is invalid size");
258 throw Decoding_Error(
"ECC p parameter is not a prime");
261 if(a.is_negative() || a >= p) {
262 throw Decoding_Error(
"Invalid ECC a parameter");
265 if(b <= 0 || b >= p) {
266 throw Decoding_Error(
"Invalid ECC b parameter");
269 if(order.is_negative() || order.is_zero() || order >= 2 * p) {
270 throw Decoding_Error(
"Invalid ECC group order");
276 throw Decoding_Error(
"Invalid ECC order parameter");
280 if(cofactor <= 0 || cofactor >= 16) {
281 throw Decoding_Error(
"Invalid ECC cofactor parameter");
284 const size_t p_bytes = p.bytes();
285 if(base_pt.size() != 1 + p_bytes && base_pt.size() != 1 + 2 * p_bytes) {
286 throw Decoding_Error(
"Invalid ECC base point encoding");
289 auto [g_x, g_y] = [&]() {
290 const uint8_t hdr = base_pt[0];
292 if(hdr == 0x04 && base_pt.size() == 1 + 2 * p_bytes) {
297 return std::make_pair(x, y);
299 }
else if((hdr == 0x02 || hdr == 0x03) && base_pt.size() == 1 + p_bytes) {
304 if(x < p && y >= 0) {
305 const bool y_mod_2 = (hdr & 0x01) == 1;
306 if(y.get_bit(0) != y_mod_2) {
310 return std::make_pair(x, y);
314 throw Decoding_Error(
"Invalid ECC base point encoding");
318 auto y2 = mod_p.square(g_y);
319 auto x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
321 throw Decoding_Error(
"Invalid ECC base point");
324 auto data = ec_group_data().lookup_or_create_without_oid(p, a, b, g_x, g_y, order, cofactor,
source);
325 return std::make_pair(data,
true);
327 throw Decoding_Error(
"Decoding ImplicitCA ECC parameters is not supported");
329 throw Decoding_Error(
352#if defined(BOTAN_HAS_LEGACY_EC_POINT) || defined(BOTAN_HAS_PCURVES_GENERIC)
361 auto data = ec_group_data().lookup(oid);
372 std::shared_ptr<EC_Group_Data> data;
375 data = ec_group_data().lookup(oid.value());
393 m_data = ec_group_data().lookup(oid);
397 if(m_data ==
nullptr) {
398 if(str.size() > 30 && str.substr(0, 29) ==
"-----BEGIN EC PARAMETERS-----") {
403 this->m_data = data.first;
404 this->m_explicit_encoding = data.second;
408 if(m_data ==
nullptr) {
428 m_data = ec_group_data().lookup_or_create(
431 m_data = ec_group_data().lookup_or_create_without_oid(
446#if defined(BOTAN_DISABLE_DEPRECATED_FEATURES)
447 constexpr size_t p_bits_lower_bound = 192;
449 constexpr size_t p_bits_lower_bound = 128;
455 if(p.
bits() == 521) {
457 BOTAN_ARG_CHECK(p == p521,
"EC_Group with p of 521 bits must be 2**521-1");
458 }
else if(p.
bits() == 239) {
459 const auto x962_p239 = []() {
461 for(
size_t i = 0; i != 239; ++i) {
462 if(i < 47 || ((i >= 94) && (i != 143))) {
469 BOTAN_ARG_CHECK(p == x962_p239,
"EC_Group with p of 239 bits must be the X9.62 prime");
474 BOTAN_ARG_CHECK(p % 4 == 3,
"EC_Group p must be congruent to 3 modulo 4");
478 BOTAN_ARG_CHECK(base_x >= 0 && base_x < p,
"EC_Group base_x is invalid");
479 BOTAN_ARG_CHECK(base_y >= 0 && base_y < p,
"EC_Group base_y is invalid");
493 const auto discriminant = mod_p.reduce(mod_p.multiply(4, mod_p.cube(a)) + mod_p.multiply(27, mod_p.square(b)));
494 BOTAN_ARG_CHECK(discriminant != 0,
"EC_Group discriminant is invalid");
497 auto y2 = mod_p.square(base_y);
498 auto x3_ax_b = mod_p.reduce(mod_p.cube(base_x) + mod_p.multiply(a, base_x) + b);
499 BOTAN_ARG_CHECK(y2 == x3_ax_b,
"EC_Group generator is not on the curve");
510 m_explicit_encoding = data.second;
514 if(m_data ==
nullptr) {
521 return data().p_bits();
525 return data().p_bytes();
529 return data().order_bits();
533 return data().order_bytes();
548#if defined(BOTAN_HAS_LEGACY_EC_POINT)
549const EC_Point& EC_Group::get_base_point()
const {
550 return data().base_point();
553const EC_Point& EC_Group::generator()
const {
554 return data().base_point();
557bool EC_Group::verify_public_element(
const EC_Point& point)
const {
559 if(point.is_zero()) {
564 if(point.on_the_curve() ==
false) {
569 if((point *
get_order()).is_zero() ==
false) {
585 return data().order();
597 return data().cofactor();
601 return data().has_cofactor();
609 return data().source();
613 return data().engine();
617 const auto& der_named_curve = data().der_named_curve();
619 if(der_named_curve.empty()) {
620 throw Encoding_Error(
"Cannot encode EC_Group as OID because OID not set");
623 return der_named_curve;
628 std::vector<uint8_t> output;
630 const size_t ecpVers1 = 1;
631 const OID curve_type(
"1.2.840.10045.1.1");
662 const std::vector<uint8_t> der =
DER_encode(form);
667 if(m_data == other.m_data) {
679 if(is_builtin && !strong) {
692 if(p <= 3 || order <= 0) {
695 if(a < 0 || a >= p) {
698 if(b <= 0 || b >= p) {
702 const size_t test_prob = 128;
703 const bool is_randomly_generated = is_builtin;
706 if(!
is_prime(p, rng, test_prob, is_randomly_generated)) {
711 if(!
is_prime(order, rng, test_prob, is_randomly_generated)) {
718 const BigInt discriminant = mod_p.reduce(mod_p.multiply(4, mod_p.cube(a)) + mod_p.multiply(27, mod_p.square(b)));
720 if(discriminant == 0) {
729#if defined(BOTAN_HAS_LEGACY_EC_POINT)
730 const EC_Point& base_point = get_base_point();
739 if(!(base_point * order).is_zero()) {
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
static Barrett_Reduction for_public_modulus(const BigInt &m)
static BigInt decode(const uint8_t buf[], size_t length)
static BigInt power_of_2(size_t n)
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
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.
std::optional< EC_AffinePoint > mul2_vartime(const EC_Scalar &x, const EC_Scalar &y) const
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
BigInt mod_order(const BigInt &x) const
bool operator==(const EC_Group &other) const
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 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
size_t get_order_bits() const
size_t get_order_bytes() const
bool on_the_curve() const
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)
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(const BigInt &n, const Barrett_Reduction &mod_n)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
lock_guard< T > lock_guard_type
BigInt sqrt_modulo_prime(const BigInt &a, const BigInt &p)