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);
235 std::vector<uint8_t> base_pt;
236 std::vector<uint8_t> seed;
239 .decode_and_check<
size_t>(1,
"Unknown ECC param version code")
241 .decode_and_check(OID({1, 2, 840, 10045, 1, 1}),
"Only prime ECC fields supported")
245 .decode_octet_string_bigint(a)
246 .decode_octet_string_bigint(b)
255 if(p.bits() < 112 || p.bits() > 521 || p.is_negative()) {
256 throw Decoding_Error(
"ECC p parameter is invalid size");
262 throw Decoding_Error(
"ECC p parameter is not a prime");
265 if(a.is_negative() || a >= p) {
266 throw Decoding_Error(
"Invalid ECC a parameter");
269 if(b <= 0 || b >= p) {
270 throw Decoding_Error(
"Invalid ECC b parameter");
273 if(order.is_negative() || order.is_zero() || order >= 2 * p) {
274 throw Decoding_Error(
"Invalid ECC group order");
280 throw Decoding_Error(
"Invalid ECC order parameter");
284 if(cofactor <= 0 || cofactor >= 16) {
285 throw Decoding_Error(
"Invalid ECC cofactor parameter");
288 const size_t p_bytes = p.bytes();
289 if(base_pt.size() != 1 + p_bytes && base_pt.size() != 1 + 2 * p_bytes) {
290 throw Decoding_Error(
"Invalid ECC base point encoding");
293 auto [g_x, g_y] = [&]() {
294 const uint8_t hdr = base_pt[0];
296 if(hdr == 0x04 && base_pt.size() == 1 + 2 * p_bytes) {
301 return std::make_pair(x, y);
303 }
else if((hdr == 0x02 || hdr == 0x03) && base_pt.size() == 1 + p_bytes) {
308 if(x < p && y >= 0) {
309 const bool y_mod_2 = (hdr & 0x01) == 1;
310 if(y.get_bit(0) != y_mod_2) {
314 return std::make_pair(x, y);
318 throw Decoding_Error(
"Invalid ECC base point encoding");
322 auto y2 = mod_p.square(g_y);
323 auto x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
325 throw Decoding_Error(
"Invalid ECC base point");
328 auto data = ec_group_data().lookup_or_create_without_oid(p, a, b, g_x, g_y, order, cofactor,
source);
329 return std::make_pair(data,
true);
331 throw Decoding_Error(
"Decoding ImplicitCA ECC parameters is not supported");
333 throw Decoding_Error(
356#if defined(BOTAN_HAS_LEGACY_EC_POINT) || defined(BOTAN_HAS_PCURVES_GENERIC)
365#if defined(BOTAN_HAS_LEGACY_EC_POINT)
374 auto data = ec_group_data().lookup(oid);
385 std::shared_ptr<EC_Group_Data> data;
388 data = ec_group_data().lookup(oid.value());
406 m_data = ec_group_data().lookup(oid);
410 if(m_data ==
nullptr) {
411 if(str.size() > 30 && str.starts_with(
"-----BEGIN EC PARAMETERS-----")) {
416 this->m_data = data.first;
417 this->m_explicit_encoding = data.second;
421 if(m_data ==
nullptr) {
441 m_data = ec_group_data().lookup_or_create(
444 m_data = ec_group_data().lookup_or_create_without_oid(
459#if defined(BOTAN_DISABLE_DEPRECATED_FEATURES)
460 constexpr size_t p_bits_lower_bound = 192;
462 constexpr size_t p_bits_lower_bound = 128;
468 if(p.
bits() == 521) {
470 BOTAN_ARG_CHECK(p == p521,
"EC_Group with p of 521 bits must be 2**521-1");
471 }
else if(p.
bits() == 239) {
472 const auto x962_p239 = []() {
474 for(
size_t i = 0; i != 239; ++i) {
475 if(i < 47 || ((i >= 94) && (i != 143))) {
482 BOTAN_ARG_CHECK(p == x962_p239,
"EC_Group with p of 239 bits must be the X9.62 prime");
487 BOTAN_ARG_CHECK(p % 4 == 3,
"EC_Group p must be congruent to 3 modulo 4");
491 BOTAN_ARG_CHECK(base_x >= 0 && base_x < p,
"EC_Group base_x is invalid");
492 BOTAN_ARG_CHECK(base_y >= 0 && base_y < p,
"EC_Group base_y is invalid");
506 const auto discriminant = mod_p.reduce(mod_p.multiply(
BigInt::from_s32(4), mod_p.cube(a)) +
508 BOTAN_ARG_CHECK(discriminant != 0,
"EC_Group discriminant is invalid");
511 auto y2 = mod_p.square(base_y);
512 auto x3_ax_b = mod_p.reduce(mod_p.cube(base_x) + mod_p.multiply(a, base_x) + b);
513 BOTAN_ARG_CHECK(y2 == x3_ax_b,
"EC_Group generator is not on the curve");
524 m_explicit_encoding = data.second;
528 if(m_data ==
nullptr) {
535 return data().p_bits();
539 return data().p_bytes();
543 return data().order_bits();
547 return data().order_bytes();
562#if defined(BOTAN_HAS_LEGACY_EC_POINT)
563const EC_Point& EC_Group::get_base_point()
const {
564 return data().base_point();
567const EC_Point& EC_Group::generator()
const {
568 return data().base_point();
571bool EC_Group::verify_public_element(
const EC_Point& point)
const {
573 if(point.is_zero()) {
578 if(point.on_the_curve() ==
false) {
583 if((point *
get_order()).is_zero() ==
false) {
599 return data().order();
611 return data().cofactor();
615 return data().has_cofactor();
623 return data().source();
627 return data().engine();
631 const auto& der_named_curve = data().der_named_curve();
633 if(der_named_curve.empty()) {
634 throw Encoding_Error(
"Cannot encode EC_Group as OID because OID not set");
637 return der_named_curve;
642 std::vector<uint8_t> output;
644 const size_t ecpVers1 = 1;
645 const OID curve_type(
"1.2.840.10045.1.1");
676 const std::vector<uint8_t> der =
DER_encode(form);
681 if(m_data == other.m_data) {
693 if(is_builtin && !strong) {
706 if(p <= 3 || order <= 0) {
709 if(a < 0 || a >= p) {
712 if(b <= 0 || b >= p) {
716 const size_t test_prob = 128;
717 const bool is_randomly_generated = is_builtin;
720 if(!
is_prime(p, rng, test_prob, is_randomly_generated)) {
725 if(!
is_prime(order, rng, test_prob, is_randomly_generated)) {
735 if(discriminant == 0) {
744#if defined(BOTAN_HAS_LEGACY_EC_POINT)
745 const EC_Point& base_point = get_base_point();
754 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)
static BigInt from_s32(int32_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.
Table for computing g*x + h*y.
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
BigInt mod_order(const BigInt &x) const
bool operator==(const EC_Group &other) const
static bool supports_application_specific_group_with_cofactor()
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)