11#include <botan/ec_group.h>
12#include <botan/internal/point_mul.h>
13#include <botan/internal/primality.h>
14#include <botan/ber_dec.h>
15#include <botan/der_enc.h>
17#include <botan/reducer.h>
18#include <botan/mutex.h>
22#if defined(BOTAN_HAS_EC_HASH_TO_CURVE)
23 #include <botan/internal/ec_h2c.h>
28class EC_Group_Data
final
32 EC_Group_Data(
const BigInt& p,
38 const BigInt& cofactor,
42 m_base_point(m_curve, g_x, g_y),
48 m_base_mult(m_base_point, m_mod_order),
51 m_order_bits(order.bits()),
52 m_a_is_minus_3(a == p - 3),
53 m_a_is_zero(a.is_zero()),
58 bool params_match(
const BigInt& p,
const BigInt& a,
const BigInt&
b,
59 const BigInt& g_x,
const BigInt& g_y,
60 const BigInt& order,
const BigInt& cofactor)
const
62 return (this->p() == p &&
65 this->order() == order &&
66 this->cofactor() == cofactor &&
71 bool params_match(
const EC_Group_Data& other)
const
73 return params_match(other.p(), other.a(), other.b(),
74 other.g_x(), other.g_y(),
75 other.order(), other.cofactor());
78 void set_oid(
const OID& oid)
84 const OID& oid()
const {
return m_oid; }
85 const BigInt& p()
const {
return m_curve.get_p(); }
86 const BigInt& a()
const {
return m_curve.get_a(); }
87 const BigInt&
b()
const {
return m_curve.get_b(); }
88 const BigInt& order()
const {
return m_order; }
89 const BigInt& cofactor()
const {
return m_cofactor; }
90 const BigInt& g_x()
const {
return m_g_x; }
91 const BigInt& g_y()
const {
return m_g_y; }
93 size_t p_bits()
const {
return m_p_bits; }
94 size_t p_bytes()
const {
return (m_p_bits + 7) / 8; }
96 size_t order_bits()
const {
return m_order_bits; }
97 size_t order_bytes()
const {
return (m_order_bits + 7) / 8; }
99 const CurveGFp& curve()
const {
return m_curve; }
100 const PointGFp& base_point()
const {
return m_base_point; }
102 bool a_is_minus_3()
const {
return m_a_is_minus_3; }
103 bool a_is_zero()
const {
return m_a_is_zero; }
105 BigInt mod_order(
const BigInt& x)
const {
return m_mod_order.reduce(x); }
107 BigInt square_mod_order(
const BigInt& x)
const
109 return m_mod_order.square(x);
112 BigInt multiply_mod_order(
const BigInt& x,
const BigInt& y)
const
114 return m_mod_order.multiply(x, y);
117 BigInt multiply_mod_order(
const BigInt& x,
const BigInt& y,
const BigInt& z)
const
119 return m_mod_order.multiply(m_mod_order.multiply(x, y), z);
122 BigInt inverse_mod_order(
const BigInt& x)
const
127 PointGFp blinded_base_point_multiply(
const BigInt& k,
128 RandomNumberGenerator& rng,
129 std::vector<BigInt>& ws)
const
131 return m_base_mult.mul(k, rng, m_order, ws);
138 PointGFp m_base_point;
144 Modular_Reducer m_mod_order;
145 PointGFp_Base_Point_Precompute m_base_mult;
154class EC_Group_Data_Map
final
157 EC_Group_Data_Map() {}
161 lock_guard_type<mutex_type> lock(m_mutex);
162 size_t count = m_registered_curves.size();
163 m_registered_curves.clear();
167 std::shared_ptr<EC_Group_Data> lookup(
const OID& oid)
169 lock_guard_type<mutex_type> lock(m_mutex);
171 for(
auto i : m_registered_curves)
182 for(
auto curve : m_registered_curves)
184 if(curve->oid().empty() ==
true && curve->params_match(*data))
191 m_registered_curves.push_back(data);
196 return std::shared_ptr<EC_Group_Data>();
199 std::shared_ptr<EC_Group_Data> lookup_or_create(
const BigInt& p,
205 const BigInt& cofactor,
209 lock_guard_type<mutex_type> lock(m_mutex);
211 for(
auto i : m_registered_curves)
218 if(!oid.empty() && !i->oid().empty() && i->oid() != oid)
223 const bool same_oid = !oid.empty() && i->oid() == oid;
224 const bool same_params = i->params_match(p, a,
b, g_x, g_y, order, cofactor);
230 if(same_params && same_oid)
238 if(same_params && oid.empty())
246 if(same_oid && !same_params)
248 throw Invalid_Argument(
"Attempting to register a curve using OID " + oid.to_string() +
249 " but a distinct curve is already registered using that OID");
256 if(same_params && i->oid().empty() && !oid.empty())
270 std::shared_ptr<EC_Group_Data> new_group =
271 std::make_shared<EC_Group_Data>(p, a,
b, g_x, g_y, order, cofactor, oid, source);
276 if(data !=
nullptr && !new_group->params_match(*data))
277 throw Invalid_Argument(
"Attempting to register an EC group under OID of hardcoded group");
283 if(oid_from_store.has_value())
298 if(new_group->params_match(*data))
300 new_group->set_oid(oid_from_store);
305 m_registered_curves.push_back(new_group);
311 std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
315EC_Group_Data_Map& EC_Group::ec_group_data()
322 static Allocator_Initializer g_init_allocator;
323 static EC_Group_Data_Map g_ec_data;
330 return ec_group_data().clear();
334std::shared_ptr<EC_Group_Data>
335EC_Group::load_EC_group_info(
const char* p_str,
340 const char* order_str,
346 const BigInt g_x(g_x_str);
347 const BigInt g_y(g_y_str);
348 const BigInt order(order_str);
355std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(
const uint8_t bits[],
size_t len,
358 BER_Decoder ber(bits, len);
359 BER_Object obj = ber.get_next_object();
363 throw Decoding_Error(
"Cannot handle ImplicitCA ECC parameters");
368 BER_Decoder(bits, len).decode(dom_par_oid);
369 return ec_group_data().lookup(dom_par_oid);
373 BigInt p, a,
b, order, cofactor;
374 std::vector<uint8_t> base_pt;
375 std::vector<uint8_t> seed;
377 BER_Decoder(bits, len)
379 .decode_and_check<
size_t>(1,
"Unknown ECC param version code")
381 .decode_and_check(OID(
"1.2.840.10045.1.1"),
382 "Only prime ECC fields supported")
386 .decode_octet_string_bigint(a)
387 .decode_octet_string_bigint(
b)
397 throw Decoding_Error(
"Invalid ECC p parameter");
399 if(a.is_negative() || a >= p)
400 throw Decoding_Error(
"Invalid ECC a parameter");
403 throw Decoding_Error(
"Invalid ECC b parameter");
406 throw Decoding_Error(
"Invalid ECC order parameter");
408 if(cofactor <= 0 || cofactor >= 16)
409 throw Decoding_Error(
"Invalid ECC cofactor parameter");
411 std::pair<BigInt, BigInt> base_xy =
Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a,
b);
413 return ec_group_data().lookup_or_create(p, a,
b, base_xy.first, base_xy.second,
414 order, cofactor, OID(),
source);
418 throw Decoding_Error(
"Unexpected tag while decoding ECC domain params");
433 this->m_data = ec_group_data().lookup(domain_oid);
447 m_data = ec_group_data().lookup(oid);
453 if(m_data ==
nullptr)
455 if(str.size() > 30 && str.substr(0, 29) ==
"-----BEGIN EC PARAMETERS-----")
463 if(m_data ==
nullptr)
471 return EC_Group(ber.data(), ber.size());
483 m_data = ec_group_data().lookup_or_create(p, a,
b, base_x, base_y, order, cofactor, oid,
492const EC_Group_Data& EC_Group::data()
const
494 if(m_data ==
nullptr)
501 return data().a_is_minus_3();
506 return data().a_is_zero();
511 return data().p_bits();
516 return data().p_bytes();
521 return data().order_bits();
526 return data().order_bytes();
546 return data().base_point();
551 return data().order();
566 return data().cofactor();
571 return data().mod_order(k);
576 return data().square_mod_order(x);
581 return data().multiply_mod_order(x, y);
586 return data().multiply_mod_order(x, y, z);
591 return data().inverse_mod_order(x);
601 return data().source();
626 printf(
"invalid point in EC_Group::point\n");
630 return PointGFp(data().curve(), x, y);
641 std::vector<BigInt>& ws)
const
643 return data().blinded_base_point_multiply(k, rng, ws);
648 std::vector<BigInt>& ws)
const
650 const PointGFp pt = data().blinded_base_point_multiply(k, rng, ws);
665 std::vector<BigInt>& ws)
const
677 const uint8_t input[],
679 const std::string& domain,
680 bool random_oracle)
const
685 reinterpret_cast<const uint8_t*
>(domain.c_str()),
691 const uint8_t input[],
693 const uint8_t domain_sep[],
694 size_t domain_sep_len,
695 bool random_oracle)
const
697#if defined(BOTAN_HAS_EC_HASH_TO_CURVE)
702 throw Not_Implemented(
"EC_Group::hash_to_curve not available for this curve type");
707 domain_sep, domain_sep_len,
711 BOTAN_UNUSED(hash_fn, random_oracle, input, input_len, domain_sep, domain_sep_len);
712 throw Not_Implemented(
"EC_Group::hash_to_curve functionality not available in this configuration");
719 std::vector<uint8_t> output;
725 const size_t ecpVers1 = 1;
726 const OID curve_type(
"1.2.840.10045.1.1");
752 throw Encoding_Error(
"Cannot encode EC_Group as OID because OID not set");
776 if(m_data == other.m_data)
816 if(is_builtin && !strong)
825 if(p <= 3 || order <= 0)
832 const size_t test_prob = 128;
833 const bool is_randomly_generated = is_builtin;
836 if(!
is_prime(p, rng, test_prob, is_randomly_generated))
842 if(!
is_prime(order, rng, test_prob, is_randomly_generated))
854 if(discriminant == 0)
875 if(!(base_point * order).is_zero())
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_UNUSED(...)
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
DER_Encoder & start_sequence()
DER_Encoder & encode_null()
DER_Encoder & encode(bool b)
PointGFp OS2ECP(const uint8_t bits[], size_t len) const
bool a_is_minus_3() const
PointGFp hash_to_curve(const std::string &hash_fn, const uint8_t input[], size_t input_len, const uint8_t domain_sep[], size_t domain_sep_len, bool random_oracle=true) const
BigInt blinded_base_point_multiply_x(const BigInt &k, RandomNumberGenerator &rng, std::vector< BigInt > &ws) const
const BigInt & get_b() const
const BigInt & get_a() const
const BigInt & get_g_y() const
PointGFp blinded_base_point_multiply(const BigInt &k, RandomNumberGenerator &rng, std::vector< BigInt > &ws) const
const BigInt & get_cofactor() const
BigInt mod_order(const BigInt &x) const
bool operator==(const EC_Group &other) const
BigInt multiply_mod_order(const BigInt &x, const BigInt &y) const
EC_Group_Source source() const
PointGFp point_multiply(const BigInt &x, const PointGFp &pt, const BigInt &y) const
const BigInt & get_p() const
static EC_Group EC_Group_from_PEM(const std::string &pem)
bool verify_group(RandomNumberGenerator &rng, bool strong=false) const
PointGFp point(const BigInt &x, const BigInt &y) const
size_t point_size(PointGFp::Compression_Type format) const
const BigInt & get_order() const
size_t get_p_bits() const
bool verify_public_element(const PointGFp &y) const
static std::shared_ptr< EC_Group_Data > EC_group_info(const OID &oid)
std::string PEM_encode() const
const BigInt & get_g_x() const
const OID & get_curve_oid() const
BigInt square_mod_order(const BigInt &x) const
const PointGFp & get_base_point() const
static size_t clear_registered_curve_data()
std::vector< uint8_t > DER_encode(EC_Group_Encoding form) const
BigInt inverse_mod_order(const BigInt &x) const
PointGFp zero_point() const
size_t get_p_bytes() const
PointGFp blinded_var_point_multiply(const PointGFp &point, const BigInt &k, RandomNumberGenerator &rng, std::vector< BigInt > &ws) const
static OID EC_group_identity_from_order(const BigInt &order)
BigInt random_scalar(RandomNumberGenerator &rng) const
size_t get_order_bits() const
size_t get_order_bytes() const
BigInt cube(const BigInt &x) const
BigInt square(const BigInt &x) const
BigInt multiply(const BigInt &x, const BigInt &y) const
BigInt reduce(const BigInt &x) const
static OID from_string(const std::string &str)
std::string to_string() const
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
bool on_the_curve() const
BigInt get_affine_x() const
int(* final)(unsigned char *, CTX *)
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
secure_vector< uint8_t > decode_check_label(DataSource &source, const std::string &label_want)
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
PointGFp hash_to_curve_sswu(const EC_Group &group, const std::string &hash_fn, const uint8_t input[], size_t input_len, const uint8_t domain_sep[], size_t domain_sep_len, bool random_oracle)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
std::vector< T, secure_allocator< T > > secure_vector