Botan 3.14.1
Crypto and TLS for C&
ec_group.cpp
Go to the documentation of this file.
1/*
2* ECC Domain Parameters
3*
4* (C) 2007 Falko Strenzke, FlexSecure GmbH
5* (C) 2008,2018,2024 Jack Lloyd
6* (C) 2018 Tobias Niemann
7*
8* Botan is released under the Simplified BSD License (see license.txt)
9*/
10
11#include <botan/ec_group.h>
12
13#include <botan/ber_dec.h>
14#include <botan/der_enc.h>
15#include <botan/mutex.h>
16#include <botan/numthry.h>
17#include <botan/pem.h>
18#include <botan/rng.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>
23#include <vector>
24
25namespace Botan {
26
27class EC_Group_Data_Map final {
28 public:
29 EC_Group_Data_Map() = default;
30
31 size_t clear() {
32 const lock_guard_type<mutex_type> lock(m_mutex);
33 const size_t count = m_registered_curves.size();
34 m_registered_curves.clear();
35 return count;
36 }
37
38 bool unregister(const OID& oid) {
39 // TODO(Botan4)
40 if(oid.empty()) {
41 throw Invalid_Argument("OID must not be empty");
42 }
43
44 const lock_guard_type<mutex_type> lock(m_mutex);
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);
48 return true;
49 }
50 }
51 return false;
52 }
53
54 std::shared_ptr<EC_Group_Data> lookup(const OID& oid) {
55 const lock_guard_type<mutex_type> lock(m_mutex);
56
57 for(auto i : m_registered_curves) {
58 if(i->oid() == oid) {
59 return i;
60 }
61 }
62
63 // Not found, check hardcoded data
64 std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);
65
66 if(data) {
67 // The requested OID may be an alias for a curve whose canonical OID differs
68 // TODO(Botan4) remove this once we require exactly one canonical OID per curve
69 if(data->oid() != oid) {
70 for(const auto& i : m_registered_curves) {
71 if(i->oid() == data->oid()) {
72 return i;
73 }
74 }
75 }
76
77 m_registered_curves.push_back(data);
78 return data;
79 }
80
81 // Nope, unknown curve
82 return std::shared_ptr<EC_Group_Data>();
83 }
84
85 std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p,
86 const BigInt& a,
87 const BigInt& b,
88 const BigInt& g_x,
89 const BigInt& g_y,
90 const BigInt& order,
91 const BigInt& cofactor,
92 const OID& oid,
93 EC_Group_Source source) {
94 BOTAN_ASSERT_NOMSG(oid.has_value());
95
96 const lock_guard_type<mutex_type> lock(m_mutex);
97
98 for(auto i : m_registered_curves) {
99 if(i->oid() == oid) {
100 /*
101 * If both OID and params are the same then we are done, just return
102 * the already registered curve obj.
103 *
104 * First verify that the params match, to catch an application
105 * that is attempting to register a EC_Group under the same OID as
106 * another group currently in use
107 */
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");
111 }
112
113 return i;
114 }
115
116 /*
117 * If the same curve was previously created without an OID but is now
118 * being registered again using an OID, save that OID.
119 *
120 * TODO(Botan4) remove this block; this situation won't be possible since
121 * we will require all groups to have an OID
122 */
123 if(i->oid().empty() && i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
124 i->set_oid(oid);
125 return i;
126 }
127 }
128
129 /*
130 * Not found in current list, so we need to create a new entry
131 */
132 auto new_group = [&] {
133 if(auto g = EC_Group::EC_group_info(oid); g != nullptr) {
134 /*
135 * This turned out to be the OID of one of the builtin groups. Verify
136 * that all of the provided parameters match that builtin group.
137 */
138 BOTAN_ARG_CHECK(g->params_match(p, a, b, g_x, g_y, order, cofactor),
139 "Attempting to register an EC group under OID of hardcoded group");
140
141 return g;
142 } else {
143 /*
144 * This path is taken for an application registering a new EC_Group with an OID specified
145 */
146 return EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, source);
147 }
148 }();
149
150 if(new_group->source() != EC_Group_Source::Builtin) {
151 BOTAN_ARG_CHECK(EC_Group::verify_generator_order(new_group),
152 "EC_Group generator does not have the claimed order");
153 }
154
155 m_registered_curves.push_back(new_group);
156 return new_group;
157 }
158
159 std::shared_ptr<EC_Group_Data> lookup_from_params(const BigInt& p,
160 const BigInt& a,
161 const BigInt& b,
162 std::span<const uint8_t> base_pt,
163 const BigInt& order,
164 const BigInt& cofactor) {
165 const lock_guard_type<mutex_type> lock(m_mutex);
166
167 for(auto i : m_registered_curves) {
168 if(i->params_match(p, a, b, base_pt, order, cofactor)) {
169 return i;
170 }
171 }
172
173 // Try to use the order as a hint to look up the group id
174 const OID oid_from_order = EC_Group::EC_group_identity_from_order(order);
175 if(oid_from_order.has_value()) {
176 auto new_group = EC_Group::EC_group_info(oid_from_order);
177
178 // Have to check all params in the (unlikely/malicious) event of an order collision
179 if(new_group && new_group->params_match(p, a, b, base_pt, order, cofactor)) {
180 m_registered_curves.push_back(new_group);
181 return new_group;
182 }
183 }
184
185 return {};
186 }
187
188 // TODO(Botan4) this entire function can be removed since OIDs will be required
189 std::shared_ptr<EC_Group_Data> lookup_or_create_without_oid(const BigInt& p,
190 const BigInt& a,
191 const BigInt& b,
192 const BigInt& g_x,
193 const BigInt& g_y,
194 const BigInt& order,
195 const BigInt& cofactor,
196 EC_Group_Source source) {
197 const lock_guard_type<mutex_type> lock(m_mutex);
198
199 for(auto i : m_registered_curves) {
200 if(i->params_match(p, a, b, g_x, g_y, order, cofactor)) {
201 return i;
202 }
203 }
204
205 // Try to use the order as a hint to look up the group id
206 const OID oid_from_order = EC_Group::EC_group_identity_from_order(order);
207 if(oid_from_order.has_value()) {
208 auto new_group = EC_Group::EC_group_info(oid_from_order);
209
210 // Have to check all params in the (unlikely/malicious) event of an order collision
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);
213 return new_group;
214 }
215 }
216
217 /*
218 * At this point we have failed to identify the group; it is not any of
219 * the builtin values, nor is it a group that the user had previously
220 * registered explicitly. We create the group data without an OID.
221 *
222 * TODO(Botan4) remove this; throw an exception instead
223 */
224 auto new_group = EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, OID(), source);
225
226 BOTAN_ARG_CHECK(EC_Group::verify_generator_order(new_group),
227 "EC_Group generator does not have the claimed order");
228
229 m_registered_curves.push_back(new_group);
230 return new_group;
231 }
232
233 private:
234 mutex_type m_mutex;
235 // TODO(Botan4): Once OID is required we could make this into a map
236 std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
237};
238
239//static
240EC_Group_Data_Map& EC_Group::ec_group_data() {
241 /*
242 * This exists purely to ensure the allocator is constructed before g_ec_data,
243 * which ensures that its destructor runs after ~g_ec_data is complete.
244 */
245
246 static const Allocator_Initializer g_init_allocator;
247 static EC_Group_Data_Map g_ec_data;
248 return g_ec_data;
249}
250
251//static
253 return ec_group_data().clear();
254}
255
256//static
257std::shared_ptr<EC_Group_Data> EC_Group::load_EC_group_info(const char* p_str,
258 const char* a_str,
259 const char* b_str,
260 const char* g_x_str,
261 const char* g_y_str,
262 const char* order_str,
263 const OID& oid) {
264 BOTAN_ARG_CHECK(oid.has_value(), "EC_Group::load_EC_group_info OID must be set");
265
266 const BigInt p(p_str);
267 const BigInt a(a_str);
268 const BigInt b(b_str);
269 const BigInt g_x(g_x_str);
270 const BigInt g_y(g_y_str);
271 const BigInt order(order_str);
272 const BigInt cofactor(1); // implicit
273
274 return EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin);
275}
276
277//static
278std::pair<std::shared_ptr<EC_Group_Data>, bool> EC_Group::DER_decode_EC_group(std::span<const uint8_t> der,
279 EC_Group_Source source) {
280 BER_Decoder dec(der, BER_Decoder::Limits::DER());
281
282 const auto next_obj_type = dec.peek_next_object().type_tag();
283
284 if(next_obj_type == ASN1_Type::ObjectId) {
285 OID oid;
286 dec.decode(oid).verify_end();
287
288 const auto data = ec_group_data().lookup(oid);
289 if(!data) {
290 throw Decoding_Error(fmt("Unknown namedCurve OID '{}'", oid.to_string()));
291 }
292
293 return std::make_pair(data, false);
294 } else if(next_obj_type == ASN1_Type::Sequence) {
295 BigInt p;
296 BigInt a;
297 BigInt b;
298 BigInt order;
299 BigInt cofactor;
300 std::vector<uint8_t> base_pt;
301 std::vector<uint8_t> seed;
302
303 dec.start_sequence()
304 .decode_and_check<size_t>(1, "Unknown ECC param version code")
305 .start_sequence()
306 .decode_and_check(OID({1, 2, 840, 10045, 1, 1}), "Only prime ECC fields supported")
307 .decode(p)
308 .end_cons()
309 .start_sequence()
310 .decode_octet_string_bigint(a)
311 .decode_octet_string_bigint(b)
313 .end_cons()
314 .decode(base_pt, ASN1_Type::OctetString)
315 .decode(order)
316 .decode(cofactor)
317 .end_cons()
318 .verify_end();
319
320 // TODO(Botan4) Require cofactor == 1
321 if(cofactor <= 0 || cofactor >= 16) {
322 throw Decoding_Error("Invalid ECC cofactor parameter");
323 }
324
325 if(p.bits() < 112 || p.bits() > 521 || p.signum() < 0) {
326 throw Decoding_Error("ECC p parameter is invalid size");
327 }
328
329 // A can be zero
330 if(a.signum() < 0 || a >= p) {
331 throw Decoding_Error("Invalid ECC a parameter");
332 }
333
334 // B must be > 0
335 //
336 // Technically this is not true but we have historically rejected this and
337 // nobody has noted it as an issue, so it is retained.
338 if(b.signum() <= 0 || b >= p) {
339 throw Decoding_Error("Invalid ECC b parameter");
340 }
341
342 if(order.signum() <= 0 || order >= 2 * p) {
343 throw Decoding_Error("Invalid ECC group order");
344 }
345
346 if(p == order) {
347 throw Decoding_Error("Anomalous elliptic curves are not supported");
348 }
349
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);
352 }
353
354 /*
355 TODO(Botan4) the remaining code is used only to handle the case of decoding an EC_Group
356 which is neither a builtin group nor a group that was registered by the application.
357 It can all be removed and replaced with a throw
358 */
359
360 const auto mod_p = Barrett_Reduction::for_public_modulus(p);
362 throw Decoding_Error("ECC p parameter is not a prime");
363 }
364
366 throw Decoding_Error("Invalid ECC order parameter");
367 }
368
369 if((p - cofactor * order).abs().bits() > (p.bits() / 2) + 1) {
370 throw Decoding_Error("Invalid ECC Hasse bound");
371 }
372
373 const auto discriminant = mod_p.reduce(mod_p.multiply(BigInt::from_s32(4), mod_p.cube(a)) +
374 mod_p.multiply(BigInt::from_s32(27), mod_p.square(b)));
375 if(discriminant == 0) {
376 throw Decoding_Error("Invalid ECC curve discriminant");
377 }
378
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");
382 }
383
384 auto [g_x, g_y] = [&]() {
385 const uint8_t hdr = base_pt[0];
386
387 if(hdr == 0x04 && base_pt.size() == 1 + 2 * p_bytes) {
388 const BigInt x = BigInt::from_bytes(std::span{base_pt}.subspan(1, p_bytes));
389 const BigInt y = BigInt::from_bytes(std::span{base_pt}.subspan(1 + p_bytes, p_bytes));
390
391 if(x < p && y < p) {
392 return std::make_pair(x, y);
393 }
394 } else if((hdr == 0x02 || hdr == 0x03) && base_pt.size() == 1 + p_bytes) {
395 // TODO(Botan4) remove this branch; we won't support compressed points
396 const BigInt x = BigInt::from_bytes(std::span{base_pt}.subspan(1, p_bytes));
397 BigInt y = sqrt_modulo_prime(((x * x + a) * x + b) % p, p);
398
399 if(x < p && y >= 0) {
400 const bool y_mod_2 = (hdr & 0x01) == 1;
401 if(y.get_bit(0) != y_mod_2) {
402 y = p - y;
403 }
404
405 return std::make_pair(x, y);
406 }
407 }
408
409 throw Decoding_Error("Invalid ECC base point encoding");
410 }();
411
412 // TODO(Botan4) we can remove this check since we'll only accept pre-registered groups
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);
415 if(y2 != x3_ax_b) {
416 throw Decoding_Error("Invalid ECC base point");
417 }
418
419 /*
420 * Create the group data without registering it in the global map.
421 *
422 * Applications that need persistent custom groups should register them
423 * via the relevant EC_Group constructor
424 */
425 const auto data = EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, OID(), source);
426
427 if(!EC_Group::verify_generator_order(data)) {
428 throw Decoding_Error("ECC generator does not have the claimed order");
429 }
430
431 return std::make_pair(data, true);
432 } else if(next_obj_type == ASN1_Type::Null) {
433 throw Decoding_Error("Decoding ImplicitCA ECC parameters is not supported");
434 } else {
435 throw Decoding_Error(
436 fmt("Unexpected tag {} while decoding ECC domain params", asn1_tag_to_string(next_obj_type)));
437 }
438}
439
440EC_Group::EC_Group() = default;
441
442EC_Group::~EC_Group() = default;
443
444EC_Group::EC_Group(const EC_Group&) = default;
445
446EC_Group& EC_Group::operator=(const EC_Group&) = default;
447
448// Internal constructor
449EC_Group::EC_Group(std::shared_ptr<const EC_Group_Data> data) : m_data(std::move(data)) {}
450
451//static
452bool EC_Group::verify_generator_order(std::shared_ptr<const EC_Group_Data> data) {
453 const EC_Group group(std::move(data));
454
455#if defined(BOTAN_HAS_LEGACY_EC_POINT)
456 if(group.engine() == EC_Group_Engine::Legacy) {
457 return (group.get_base_point() * group.get_order()).is_zero();
458 }
459#endif
460
461 auto g_pt = EC_AffinePoint::from_bigint_xy(group, group.get_g_x(), group.get_g_y());
462 if(!g_pt) {
463 return false;
464 }
465
466 Null_RNG null_rng;
467 const auto neg_one = EC_Scalar::one(group).negate();
468 const auto n_minus_one_g = EC_AffinePoint::g_mul(neg_one, null_rng);
469 return n_minus_one_g == g_pt->negate();
470}
471
472//static
473bool EC_Group::supports_named_group(std::string_view name) {
474 if(name.empty()) {
475 return false;
476 }
477
478 // Is it one of the groups compiled into the library?
479 if(EC_Group::known_named_groups().contains(std::string(name))) {
480 return true;
481 }
482
483 // Is it a custom group registered by the application?
484 if(auto oid = OID::from_name(name)) {
485 try {
486 if(ec_group_data().lookup(oid.value()) != nullptr) {
487 return true;
488 }
489 } catch(Not_Implemented&) {
490 // This would be thrown for example if the group is a known curve
491 // but the relevant module that enables it is not compiled in
492 }
493 }
494
495 // Not known
496 return false;
497}
498
499//static
501#if defined(BOTAN_HAS_LEGACY_EC_POINT) || defined(BOTAN_HAS_PCURVES_GENERIC)
502 return true;
503#else
504 return false;
505#endif
506}
507
508//static
510#if defined(BOTAN_HAS_LEGACY_EC_POINT)
511 return true;
512#else
513 return false;
514#endif
515}
516
517//static
519 auto data = ec_group_data().lookup(oid);
520
521 if(!data) {
522 throw Invalid_Argument(fmt("No EC_Group associated with OID '{}'", oid.to_string()));
523 }
524
525 return EC_Group(std::move(data));
526}
527
528//static
530 std::shared_ptr<EC_Group_Data> data;
531
532 if(auto oid = OID::from_name(name)) {
533 data = ec_group_data().lookup(oid.value());
534 }
535
536 if(!data) {
537 throw Invalid_Argument(fmt("Unknown EC_Group '{}'", name));
538 }
539
540 return EC_Group(std::move(data));
541}
542
543EC_Group::EC_Group(std::string_view str) {
544 if(str.empty()) {
545 return; // no initialization / uninitialized
546 }
547
548 try {
549 const OID oid = OID::from_string(str);
550 if(oid.has_value()) {
551 m_data = ec_group_data().lookup(oid);
552 }
553 } catch(...) {}
554
555 if(m_data == nullptr) {
556 if(str.size() > 30 && str.starts_with("-----BEGIN EC PARAMETERS-----")) {
557 // OK try it as PEM ...
558 const auto der = PEM_Code::decode_check_label(str, "EC PARAMETERS");
559
560 const auto data = DER_decode_EC_group(der, EC_Group_Source::ExternalSource);
561 this->m_data = data.first;
562 this->m_explicit_encoding = data.second;
563 }
564 }
565
566 if(m_data == nullptr) {
567 throw Invalid_Argument(fmt("Unknown ECC group '{}'", str));
568 }
569}
570
571//static
572EC_Group EC_Group::from_PEM(std::string_view pem) {
573 const auto der = PEM_Code::decode_check_label(pem, "EC PARAMETERS");
574 return EC_Group(der);
575}
576
578 const BigInt& a,
579 const BigInt& b,
580 const BigInt& base_x,
581 const BigInt& base_y,
582 const BigInt& order,
583 const BigInt& cofactor,
584 const OID& oid) {
585 BOTAN_ARG_CHECK(a >= 0 && a < p, "EC_Group a is invalid");
586 BOTAN_ARG_CHECK(b > 0 && b < p, "EC_Group b is invalid");
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");
589
590 BOTAN_ARG_CHECK(cofactor >= 1 && cofactor < 16, "EC_Group cofactor is invalid");
591
592 const auto mod_p = Barrett_Reduction::for_public_modulus(p);
593 BOTAN_ARG_CHECK(is_bailie_psw_probable_prime_vartime(p), "EC_Group p is not prime");
594
595 BOTAN_ARG_CHECK(is_bailie_psw_probable_prime_vartime(order), "EC_Group order is not prime");
596
597 BOTAN_ARG_CHECK(p != order, "Anomalous elliptic curves are not supported");
598
599 BOTAN_ARG_CHECK((p - cofactor * order).abs().bits() <= (p.bits() / 2) + 1, "Hasse bound invalid");
600
601 // Check that 4*a^3 + 27*b^2 != 0
602 const auto discriminant = mod_p.reduce(mod_p.multiply(BigInt::from_s32(4), mod_p.cube(a)) +
603 mod_p.multiply(BigInt::from_s32(27), mod_p.square(b)));
604 BOTAN_ARG_CHECK(discriminant != 0, "EC_Group discriminant is invalid");
605
606 // Check that the generator (base_x,base_y) is on the curve; y^2 = x^3 + a*x + b
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");
610
611 if(oid.has_value()) {
612 m_data = ec_group_data().lookup_or_create(
613 p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource);
614 } else {
615 m_data = ec_group_data().lookup_or_create_without_oid(
616 p, a, b, base_x, base_y, order, cofactor, EC_Group_Source::ExternalSource);
617 }
618}
619
621 const BigInt& p,
622 const BigInt& a,
623 const BigInt& b,
624 const BigInt& base_x,
625 const BigInt& base_y,
626 const BigInt& order) :
627 EC_Group(std::move(EC_Group::register_custom_group(oid, p, a, b, base_x, base_y, order).m_data)) {}
628
629//static
631 const BigInt& p,
632 const BigInt& a,
633 const BigInt& b,
634 const BigInt& base_x,
635 const BigInt& base_y,
636 const BigInt& order) {
637 BOTAN_ARG_CHECK(oid.has_value(), "An OID is required for creating an EC_Group");
638
639 // TODO(Botan4) remove this and require 192 bits minimum
640#if defined(BOTAN_DISABLE_DEPRECATED_FEATURES)
641 constexpr size_t p_bits_lower_bound = 192;
642#else
643 constexpr size_t p_bits_lower_bound = 128;
644#endif
645
646 BOTAN_ARG_CHECK(p.bits() >= p_bits_lower_bound, "EC_Group p too small");
647 BOTAN_ARG_CHECK(p.bits() <= 521, "EC_Group p too large");
648
649 if(p.bits() == 521) {
650 const auto p521 = BigInt::power_of_2(521) - 1;
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 = []() {
654 BigInt p239;
655 for(size_t i = 0; i != 239; ++i) {
656 if(i < 47 || ((i >= 94) && (i != 143))) {
657 p239.set_bit(i);
658 }
659 }
660 return p239;
661 }();
662
663 BOTAN_ARG_CHECK(p == x962_p239, "EC_Group with p of 239 bits must be the X9.62 prime");
664 } else {
665 BOTAN_ARG_CHECK(p.bits() % 32 == 0, "EC_Group p must be a multiple of 32 bits");
666 }
667
668 BOTAN_ARG_CHECK(p % 4 == 3, "EC_Group p must be congruent to 3 modulo 4");
669
670 BOTAN_ARG_CHECK(a >= 0 && a < p, "EC_Group a is invalid");
671 BOTAN_ARG_CHECK(b > 0 && b < p, "EC_Group b is invalid");
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");
674 BOTAN_ARG_CHECK(p.bits() == order.bits(), "EC_Group p and order must have the same number of bits");
675
676 const auto mod_p = Barrett_Reduction::for_public_modulus(p);
677 BOTAN_ARG_CHECK(is_bailie_psw_probable_prime_vartime(p), "EC_Group p is not prime");
678
679 BOTAN_ARG_CHECK(is_bailie_psw_probable_prime_vartime(order), "EC_Group order is not prime");
680
681 BOTAN_ARG_CHECK(p != order, "Anomalous elliptic curves are not supported");
682
683 // This catches someone "ignoring" a cofactor and just trying to
684 // provide the subgroup order
685 BOTAN_ARG_CHECK((p - order).abs().bits() <= (p.bits() / 2) + 1, "Hasse bound invalid");
686
687 // Check that 4*a^3 + 27*b^2 != 0
688 const auto discriminant = mod_p.reduce(mod_p.multiply(BigInt::from_s32(4), mod_p.cube(a)) +
689 mod_p.multiply(BigInt::from_s32(27), mod_p.square(b)));
690 BOTAN_ARG_CHECK(discriminant != 0, "EC_Group discriminant is invalid");
691
692 // Check that the generator (base_x,base_y) is on the curve; y^2 = x^3 + a*x + b
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");
696
697 const BigInt cofactor(1);
698
699 return EC_Group(
700 ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource));
701}
702
703EC_Group::EC_Group(std::span<const uint8_t> der) {
704 const auto data = DER_decode_EC_group(der, EC_Group_Source::ExternalSource);
705 m_data = data.first;
706 m_explicit_encoding = data.second;
707}
708
709// static
710bool EC_Group::unregister(const OID& oid) {
711 return ec_group_data().unregister(oid);
712}
713
714const EC_Group_Data& EC_Group::data() const {
715 if(m_data == nullptr) {
716 throw Invalid_State("EC_Group uninitialized");
717 }
718 return *m_data;
719}
720
721size_t EC_Group::get_p_bits() const {
722 return data().p_bits();
723}
724
725size_t EC_Group::get_p_bytes() const {
726 return data().p_bytes();
727}
728
730 return data().order_bits();
731}
732
734 return data().order_bytes();
735}
736
737const BigInt& EC_Group::get_p() const {
738 return data().p();
739}
740
741const BigInt& EC_Group::get_a() const {
742 return data().a();
743}
744
745const BigInt& EC_Group::get_b() const {
746 return data().b();
747}
748
749#if defined(BOTAN_HAS_LEGACY_EC_POINT)
750const EC_Point& EC_Group::get_base_point() const {
751 return data().base_point();
752}
753
754const EC_Point& EC_Group::generator() const {
755 return data().base_point();
756}
757
758bool EC_Group::verify_public_element(const EC_Point& point) const {
759 //check that public point is not at infinity
760 if(point.is_zero()) {
761 return false;
762 }
763
764 //check that public point is on the curve
765 if(point.on_the_curve() == false) {
766 return false;
767 }
768
769 //check that public point has order q
770 if((point * get_order()).is_zero() == false) {
771 return false;
772 }
773
774 if(has_cofactor()) {
775 if((point * get_cofactor()).is_zero()) {
776 return false;
777 }
778 }
779
780 return true;
781}
782
783#endif
784
786 return data().order();
787}
788
789const BigInt& EC_Group::get_g_x() const {
790 return data().g_x();
791}
792
793const BigInt& EC_Group::get_g_y() const {
794 return data().g_y();
795}
796
798 return data().cofactor();
799}
800
802 return data().has_cofactor();
803}
804
806 return data().oid();
807}
808
810 return data().source();
811}
812
814 return data().engine();
815}
816
817bool EC_Group::hash_to_curve_supported(std::string_view hash_fn) const {
818 return data().hash_to_curve_supported(hash_fn);
819}
820
821std::vector<uint8_t> EC_Group::DER_encode() const {
822 const auto& der_named_curve = data().der_named_curve();
823 // TODO(Botan4) this can be removed because an OID will always be defined
824 if(der_named_curve.empty()) {
825 throw Encoding_Error("Cannot encode EC_Group as OID because OID not set");
826 }
827
828 return der_named_curve;
829}
830
831std::vector<uint8_t> EC_Group::DER_encode(EC_Group_Encoding form) const {
832 if(form == EC_Group_Encoding::Explicit) {
833 std::vector<uint8_t> output;
834 DER_Encoder der(output);
835 const size_t ecpVers1 = 1;
836 const OID curve_type("1.2.840.10045.1.1"); // prime field
837
838 const size_t p_bytes = get_p_bytes();
839
840 const auto generator = EC_AffinePoint::generator(*this).serialize_uncompressed();
841
842 der.start_sequence()
843 .encode(ecpVers1)
845 .encode(curve_type)
846 .encode(get_p())
847 .end_cons()
849 .encode(get_a().serialize(p_bytes), ASN1_Type::OctetString)
850 .encode(get_b().serialize(p_bytes), ASN1_Type::OctetString)
851 .end_cons()
852 .encode(generator, ASN1_Type::OctetString)
853 .encode(get_order())
855 .end_cons();
856 return output;
857 } else if(form == EC_Group_Encoding::NamedCurve) {
858 return this->DER_encode();
859 } else if(form == EC_Group_Encoding::ImplicitCA) {
860 return {0x00, 0x05};
861 } else {
862 throw Internal_Error("EC_Group::DER_encode: Unknown encoding");
863 }
864}
865
867 const std::vector<uint8_t> der = DER_encode(form);
868 return PEM_Code::encode(der, "EC PARAMETERS");
869}
870
871bool EC_Group::operator==(const EC_Group& other) const {
872 if(m_data == other.m_data) {
873 return true; // same shared rep
874 }
875
876 return (get_p() == other.get_p() && get_a() == other.get_a() && get_b() == other.get_b() &&
877 get_g_x() == other.get_g_x() && get_g_y() == other.get_g_y() && get_order() == other.get_order() &&
878 get_cofactor() == other.get_cofactor());
879}
880
881bool EC_Group::verify_group(RandomNumberGenerator& rng, bool strong) const {
882 // Trusted parameters, assumed correct
884 return true;
885 }
886
887 // TODO(Botan4) this can probably all be removed once the deprecated EC_Group
888 // constructor is removed, since at that point it no longer becomes possible
889 // to create an EC_Group which fails to satisfy these conditions
890
891 const BigInt& p = get_p();
892 const BigInt& a = get_a();
893 const BigInt& b = get_b();
894 const BigInt& order = get_order();
895
896 if(p <= 3 || order <= 0) {
897 return false;
898 }
899 if(p == order) {
900 return false;
901 }
902 if(a < 0 || a >= p) {
903 return false;
904 }
905 if(b <= 0 || b >= p) {
906 return false;
907 }
908
909 const size_t test_prob = strong ? 128 : 12; // matching bounds used elsewhere
910 const bool is_randomly_generated = false;
911
912 //check if field modulus is prime
913 if(!is_prime_vartime(p, rng, test_prob, is_randomly_generated)) {
914 return false;
915 }
916
917 //check if order is prime
918 if(!is_prime_vartime(order, rng, test_prob, is_randomly_generated)) {
919 return false;
920 }
921
922 //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero
923 const auto mod_p = Barrett_Reduction::for_public_modulus(p);
924
925 const BigInt discriminant = mod_p.reduce(mod_p.multiply(BigInt::from_s32(4), mod_p.cube(a)) +
926 mod_p.multiply(BigInt::from_s32(27), mod_p.square(b)));
927
928 if(discriminant == 0) {
929 return false;
930 }
931
932 //check for valid cofactor
933 if(get_cofactor() < 1) {
934 return false;
935 }
936
937 // Check that the generator (g_x, g_y) is on the curve: y^2 == x^3 + a*x + b
938 const BigInt& g_x = get_g_x();
939 const BigInt& g_y = get_g_y();
940 const BigInt y2 = mod_p.square(g_y);
941 const BigInt x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
942 if(y2 != x3_ax_b) {
943 return false;
944 }
945
946 // Check that the generator has the claimed order: [order]G == identity
947 if(!EC_Group::verify_generator_order(m_data)) {
948 return false;
949 }
950
951#if defined(BOTAN_HAS_LEGACY_EC_POINT)
952 // Reject if [cofactor]G is the identity. pcurves does not support cofactor != 1
953 // so this can only matter when the legacy backend is in use.
954 if(has_cofactor()) {
955 const EC_Point& base_point = get_base_point();
956 if((base_point * get_cofactor()).is_zero()) {
957 return false;
958 }
959 }
960#endif
961
962 // check the Hasse bound (roughly)
963 if((p - get_cofactor() * order).abs().bits() > (p.bits() / 2) + 1) {
964 return false;
965 }
966
967 return true;
968}
969
970EC_Group::Mul2Table::Mul2Table(EC_Group::Mul2Table&& other) noexcept = default;
971
973
974EC_Group::Mul2Table::Mul2Table(const EC_AffinePoint& h) : m_tbl(h._group()->make_mul2_table(h._inner())) {}
975
977
978std::optional<EC_AffinePoint> EC_Group::Mul2Table::mul2_vartime(const EC_Scalar& x, const EC_Scalar& y) const {
979 auto pt = m_tbl->mul2_vartime(x._inner(), y._inner());
980 if(pt) {
981 return EC_AffinePoint::_from_inner(std::move(pt));
982 } else {
983 return {};
984 }
985}
986
988 const EC_Scalar& x,
989 const EC_Scalar& y) const {
990 return m_tbl->mul2_vartime_x_mod_order_eq(v._inner(), x._inner(), y._inner());
991}
992
994 const EC_Scalar& c,
995 const EC_Scalar& x,
996 const EC_Scalar& y) const {
997 return this->mul2_vartime_x_mod_order_eq(v, c * x, c * y);
998}
999
1000} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static Limits DER()
Definition ber_dec.h:44
static Barrett_Reduction for_public_modulus(const BigInt &m)
Definition barrett.cpp:33
void set_bit(size_t n)
Definition bigint.h:516
static BigInt from_bytes(std::span< const uint8_t > bytes)
Definition bigint.cpp:84
size_t bits() const
Definition bigint.cpp:308
static BigInt power_of_2(size_t n)
Definition bigint.h:906
static BigInt from_s32(int32_t n)
Definition bigint.cpp:43
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:192
DER_Encoder & start_sequence()
Definition der_enc.h:86
DER_Encoder & end_cons()
Definition der_enc.cpp:208
DER_Encoder & encode(bool b)
Definition der_enc.cpp:313
static std::optional< EC_AffinePoint > from_bigint_xy(const EC_Group &group, const BigInt &x, const BigInt &y)
Definition ec_apoint.cpp:93
static EC_AffinePoint g_mul(const EC_Scalar &scalar, RandomNumberGenerator &rng)
Multiply by the group generator returning a complete point.
T serialize_uncompressed() const
Definition ec_apoint.h:238
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.
Definition ec_apoint.cpp:84
Mul2Table & operator=(const Mul2Table &other)=delete
std::optional< EC_AffinePoint > mul2_vartime(const EC_Scalar &x, const EC_Scalar &y) const
Definition ec_group.cpp:978
BOTAN_FUTURE_EXPLICIT Mul2Table(const EC_AffinePoint &h)
Definition ec_group.cpp:974
bool mul2_vartime_x_mod_order_eq(const EC_Scalar &v, const EC_Scalar &x, const EC_Scalar &y) const
Definition ec_group.cpp:987
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)
Definition ec_group.cpp:529
static EC_Group from_PEM(std::string_view pem)
Definition ec_group.cpp:572
const BigInt & get_b() const
Definition ec_group.cpp:745
const BigInt & get_a() const
Definition ec_group.cpp:741
const BigInt & get_g_y() const
Definition ec_group.cpp:793
friend class EC_Scalar
Definition ec_group.h:893
const BigInt & get_cofactor() const
Definition ec_group.cpp:797
bool operator==(const EC_Group &other) const
Definition ec_group.cpp:871
static bool supports_application_specific_group_with_cofactor()
Definition ec_group.cpp:509
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)
Definition ec_group.cpp:630
EC_Group_Engine engine() const
Definition ec_group.cpp:813
EC_Group_Source source() const
Definition ec_group.cpp:809
const BigInt & get_p() const
Definition ec_group.cpp:737
bool verify_group(RandomNumberGenerator &rng, bool strong=false) const
Definition ec_group.cpp:881
const BigInt & get_order() const
Definition ec_group.cpp:785
size_t get_p_bits() const
Definition ec_group.cpp:721
static EC_Group from_OID(const OID &oid)
Definition ec_group.cpp:518
static std::shared_ptr< EC_Group_Data > EC_group_info(const OID &oid)
Definition ec_named.cpp:16
std::vector< uint8_t > DER_encode() const
Definition ec_group.cpp:821
const BigInt & get_g_x() const
Definition ec_group.cpp:789
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())
Definition ec_group.cpp:577
const OID & get_curve_oid() const
Definition ec_group.cpp:805
static bool supports_application_specific_group()
Definition ec_group.cpp:500
static const std::set< std::string > & known_named_groups()
Definition ec_named.cpp:477
bool has_cofactor() const
Definition ec_group.cpp:801
static size_t clear_registered_curve_data()
Definition ec_group.cpp:252
static bool unregister(const OID &oid)
Definition ec_group.cpp:710
friend class EC_Group_Data_Map
Definition ec_group.h:892
static bool supports_named_group(std::string_view name)
Definition ec_group.cpp:473
EC_Group & operator=(const EC_Group &)
size_t get_p_bytes() const
Definition ec_group.cpp:725
static OID EC_group_identity_from_order(const BigInt &order)
Definition ec_named.cpp:357
std::string PEM_encode(EC_Group_Encoding form=EC_Group_Encoding::Explicit) const
Definition ec_group.cpp:866
bool hash_to_curve_supported(std::string_view hash_fn) const
Definition ec_group.cpp:817
friend class EC_AffinePoint
Definition ec_group.h:894
size_t get_order_bits() const
Definition ec_group.cpp:729
size_t get_order_bytes() const
Definition ec_group.cpp:733
static EC_Scalar one(const EC_Group &group)
Definition ec_scalar.cpp:80
const EC_Scalar_Data & _inner() const
Definition ec_scalar.h:282
EC_Scalar negate() const
static std::optional< OID > from_name(std::string_view name)
Definition asn1_oid.cpp:66
bool has_value() const
Definition asn1_obj.h:474
std::string to_string() const
Definition asn1_oid.cpp:123
static OID from_string(std::string_view str)
Definition asn1_oid.cpp:80
const char * name
Definition ffi_tls.h:59
std::string encode(const uint8_t der[], size_t length, std::string_view label, size_t width)
Definition pem.cpp:41
secure_vector< uint8_t > decode_check_label(DataSource &source, std::string_view label_want)
Definition pem.cpp:51
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition pem.cpp:64
bool is_prime_vartime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:453
noop_mutex mutex_type
Definition mutex.h:40
std::string asn1_tag_to_string(ASN1_Type type)
Definition asn1_obj.cpp:129
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
BigInt abs(const BigInt &n)
Definition numthry.h:22
secure_vector< T > lock(const std::vector< T > &in)
Definition secmem.h:145
bool is_bailie_psw_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
EC_Group_Engine
Definition ec_group.h:48
lock_guard< T > lock_guard_type
Definition mutex.h:58
BigInt sqrt_modulo_prime(const BigInt &a, const BigInt &p)
Definition numthry.cpp:27
EC_Group_Source
Definition ec_group.h:38