Botan 3.9.0
Crypto and TLS for C&
ec_inner_data.cpp
Go to the documentation of this file.
1/*
2* (C) 2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/ec_inner_data.h>
8
9#include <botan/der_enc.h>
10#include <botan/internal/ec_inner_pc.h>
11#include <botan/internal/fmt.h>
12#include <botan/internal/pcurves.h>
13
14#if defined(BOTAN_HAS_LEGACY_EC_POINT)
15 #include <botan/internal/ec_inner_bn.h>
16 #include <botan/internal/point_mul.h>
17#endif
18
19#if defined(BOTAN_HAS_XMD)
20 #include <botan/internal/xmd.h>
21#endif
22
23namespace Botan {
24
26
27// Note this constructor *does not* initialize m_curve, m_base_point or m_base_mult
29 const BigInt& a,
30 const BigInt& b,
31 const BigInt& g_x,
32 const BigInt& g_y,
33 const BigInt& order,
34 const BigInt& cofactor,
35 const OID& oid,
37 m_p(p),
38 m_a(a),
39 m_b(b),
40 m_g_x(g_x),
41 m_g_y(g_y),
42 m_order(order),
43 m_cofactor(cofactor),
45 m_mod_field(Barrett_Reduction::for_public_modulus(p)),
46 m_mod_order(Barrett_Reduction::for_public_modulus(order)),
47 m_monty(m_p, m_mod_field),
48#endif
49 m_oid(oid),
50 m_p_words(p.sig_words()),
51 m_p_bits(p.bits()),
52 m_order_bits(order.bits()),
53 m_order_bytes((m_order_bits + 7) / 8),
54 m_a_is_minus_3(a == p - 3),
55 m_a_is_zero(a.is_zero()),
56 m_has_cofactor(m_cofactor != 1),
57 m_order_is_less_than_p(m_order < p),
58 m_source(source) {
59 // TODO(Botan4) we can assume/assert the OID is set
60 if(!m_oid.empty()) {
61 DER_Encoder der(m_der_named_curve);
62 der.encode(m_oid);
63
64 const std::string name = m_oid.human_name_or_empty();
65 if(!name.empty()) {
66 // returns nullptr if unknown or not supported
67 m_pcurve = PCurve::PrimeOrderCurve::for_named_curve(name);
68 }
69 if(m_pcurve) {
70 m_engine = EC_Group_Engine::Optimized;
71 }
72 }
73
74 // Try a generic pcurves instance
75 if(!m_pcurve && !m_has_cofactor) {
76 m_pcurve = PCurve::PrimeOrderCurve::from_params(p, a, b, g_x, g_y, order);
77 if(m_pcurve) {
78 m_engine = EC_Group_Engine::Generic;
79 }
80 // possibly still null here, if parameters unsuitable or if the
81 // pcurves_generic module wasn't included in the build
82 }
83
84#if defined(BOTAN_HAS_LEGACY_EC_POINT)
86 m_a_r = m_monty.mul(a, m_monty.R2(), ws);
87 m_b_r = m_monty.mul(b, m_monty.R2(), ws);
88 if(!m_pcurve) {
89 m_engine = EC_Group_Engine::Legacy;
90 }
91#else
92 if(!m_pcurve) {
93 if(m_oid.empty()) {
94 throw Not_Implemented("EC_Group this group is not supported in this build configuration");
95 } else {
96 throw Not_Implemented(
97 fmt("EC_Group the group {} is not supported in this build configuration", oid.to_string()));
98 }
99 }
100#endif
101}
102
103std::shared_ptr<EC_Group_Data> EC_Group_Data::create(const BigInt& p,
104 const BigInt& a,
105 const BigInt& b,
106 const BigInt& g_x,
107 const BigInt& g_y,
108 const BigInt& order,
109 const BigInt& cofactor,
110 const OID& oid,
112 auto group = std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source);
113
114#if defined(BOTAN_HAS_LEGACY_EC_POINT)
115 group->m_curve = CurveGFp(group.get());
116 group->m_base_point = EC_Point(group->m_curve, g_x, g_y);
117 if(!group->m_pcurve) {
118 group->m_base_mult = std::make_unique<EC_Point_Base_Point_Precompute>(group->m_base_point, group->m_mod_order);
119 }
120#endif
121
122 return group;
123}
124
126 const BigInt& a,
127 const BigInt& b,
128 const BigInt& g_x,
129 const BigInt& g_y,
130 const BigInt& order,
131 const BigInt& cofactor) const {
132 return (this->p() == p && this->a() == a && this->b() == b && this->order() == order &&
133 this->cofactor() == cofactor && this->g_x() == g_x && this->g_y() == g_y);
134}
135
137 return params_match(other.p(), other.a(), other.b(), other.g_x(), other.g_y(), other.order(), other.cofactor());
138}
139
141 BOTAN_ARG_CHECK(!oid.empty(), "OID should be set");
142 BOTAN_STATE_CHECK(m_oid.empty() && m_der_named_curve.empty());
143 m_oid = oid;
144
145 DER_Encoder der(m_der_named_curve);
146 der.encode(m_oid);
147}
148
149std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_with_trunc(std::span<const uint8_t> bytes) const {
150 const size_t bit_length = 8 * bytes.size();
151
152 if(bit_length < order_bits()) {
153 // No shifting required, but might still need to reduce by modulus
154 return this->scalar_from_bytes_mod_order(bytes);
155 } else {
156 const size_t shift = bit_length - order_bits();
157
158 const size_t new_length = bytes.size() - (shift / 8);
159 const size_t bit_shift = shift % 8;
160
161 if(bit_shift == 0) {
162 // Easy case just read different bytes
163 return this->scalar_from_bytes_mod_order(bytes.first(new_length));
164 } else {
165 std::vector<uint8_t> sbytes(new_length);
166
167 uint8_t carry = 0;
168 for(size_t i = 0; i != new_length; ++i) {
169 const uint8_t w = bytes[i];
170 sbytes[i] = (w >> bit_shift) | carry;
171 carry = w << (8 - bit_shift);
172 }
173
174 return this->scalar_from_bytes_mod_order(sbytes);
175 }
176 }
177}
178
179std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_mod_order(std::span<const uint8_t> bytes) const {
180 if(bytes.size() > 2 * order_bytes()) {
181 return {};
182 }
183
184 if(m_pcurve) {
185 if(auto s = m_pcurve->scalar_from_wide_bytes(bytes)) {
186 return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), std::move(*s));
187 } else {
188 return {};
189 }
190 } else {
191#if defined(BOTAN_HAS_LEGACY_EC_POINT)
192 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(BigInt(bytes)));
193#else
194 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
195#endif
196 }
197}
198
199std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_random(RandomNumberGenerator& rng) const {
200 if(m_pcurve) {
201 return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->random_scalar(rng));
202 } else {
203#if defined(BOTAN_HAS_LEGACY_EC_POINT)
204 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(),
205 BigInt::random_integer(rng, BigInt::one(), m_order));
206#else
207 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
208#endif
209 }
210}
211
212std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_one() const {
213 if(m_pcurve) {
214 return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->scalar_one());
215 } else {
216#if defined(BOTAN_HAS_LEGACY_EC_POINT)
217 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::one());
218#else
219 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
220#endif
221 }
222}
223
224std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bigint(const BigInt& bn) const {
225 if(bn <= 0 || bn >= m_order) {
226 return {};
227 }
228
229 if(m_pcurve) {
230 return this->scalar_deserialize(bn.serialize(m_order_bytes));
231 } else {
232#if defined(BOTAN_HAS_LEGACY_EC_POINT)
233 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), bn);
234#else
235 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
236#endif
237 }
238}
239
240std::unique_ptr<EC_Scalar_Data> EC_Group_Data::gk_x_mod_order(const EC_Scalar_Data& scalar,
241 RandomNumberGenerator& rng) const {
242 if(m_pcurve) {
243 const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);
244 auto gk_x_mod_order = m_pcurve->base_point_mul_x_mod_order(k.value(), rng);
245 return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), gk_x_mod_order);
246 } else {
247#if defined(BOTAN_HAS_LEGACY_EC_POINT)
248 const auto& k = EC_Scalar_Data_BN::checked_ref(scalar);
249 BOTAN_STATE_CHECK(m_base_mult != nullptr);
250 std::vector<BigInt> ws;
251 const auto pt = m_base_mult->mul(k.value(), rng, m_order, ws);
252
253 if(pt.is_zero()) {
254 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::zero());
255 } else {
256 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(pt.get_affine_x()));
257 }
258#else
259 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
260#endif
261 }
262}
263
264std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_deserialize(std::span<const uint8_t> bytes) const {
265 if(bytes.size() != m_order_bytes) {
266 return nullptr;
267 }
268
269 if(m_pcurve) {
270 if(auto s = m_pcurve->deserialize_scalar(bytes)) {
271 return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), *s);
272 } else {
273 return nullptr;
274 }
275 } else {
276#if defined(BOTAN_HAS_LEGACY_EC_POINT)
277 BigInt r(bytes);
278
279 if(r.is_zero() || r >= m_order) {
280 return nullptr;
281 }
282
283 return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), std::move(r));
284#else
285 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
286#endif
287 }
288}
289
290std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_deserialize(std::span<const uint8_t> bytes) const {
291 // The deprecated "hybrid" point format
292 // TODO(Botan4) remove this
293 if(bytes.size() >= 1 + 2 * 4 && (bytes[0] == 0x06 || bytes[0] == 0x07)) {
294 bool hdr_y_is_even = bytes[0] == 0x06;
295 bool y_is_even = (bytes.back() & 0x01) == 0;
296
297 if(hdr_y_is_even == y_is_even) {
298 std::vector<uint8_t> sec1(bytes.begin(), bytes.end());
299 sec1[0] = 0x04;
300 return this->point_deserialize(sec1);
301 }
302 }
303
304 try {
305 if(m_pcurve) {
306 if(auto pt = m_pcurve->deserialize_point(bytes)) {
307 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(*pt));
308 } else {
309 return {};
310 }
311 } else {
312#if defined(BOTAN_HAS_LEGACY_EC_POINT)
313 auto pt = Botan::OS2ECP(bytes, m_curve);
314 return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
315#else
316 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
317#endif
318 }
319 } catch(...) {
320 return {};
321 }
322}
323
324namespace {
325
326std::function<void(std::span<uint8_t>)> h2c_expand_message(std::string_view hash_fn,
327 std::span<const uint8_t> input,
328 std::span<const uint8_t> domain_sep) {
329 /*
330 * This could be extended to support expand_message_xof or a MHF like Argon2
331 */
332
333 if(hash_fn.starts_with("SHAKE")) {
334 throw Not_Implemented("Hash to curve currently does not support expand_message_xof");
335 }
336
337 return [=](std::span<uint8_t> uniform_bytes) {
338#if defined(BOTAN_HAS_XMD)
339 expand_message_xmd(hash_fn, uniform_bytes, input, domain_sep);
340#else
341 BOTAN_UNUSED(hash_fn, uniform_bytes, input, domain_sep);
342 throw Not_Implemented("Hash to curve is not implemented due to XMD being disabled");
343#endif
344 };
345}
346
347} // namespace
348
349std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_hash_to_curve_ro(std::string_view hash_fn,
350 std::span<const uint8_t> input,
351 std::span<const uint8_t> domain_sep) const {
352 if(m_pcurve) {
353 auto pt = m_pcurve->hash_to_curve_ro(h2c_expand_message(hash_fn, input, domain_sep));
354 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));
355 } else {
356 throw Not_Implemented("Hash to curve is not implemented for this curve");
357 }
358}
359
360std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_hash_to_curve_nu(std::string_view hash_fn,
361 std::span<const uint8_t> input,
362 std::span<const uint8_t> domain_sep) const {
363 if(m_pcurve) {
364 auto pt = m_pcurve->hash_to_curve_nu(h2c_expand_message(hash_fn, input, domain_sep));
365 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));
366 } else {
367 throw Not_Implemented("Hash to curve is not implemented for this curve");
368 }
369}
370
371std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_g_mul(const EC_Scalar_Data& scalar,
372 RandomNumberGenerator& rng) const {
373 if(m_pcurve) {
374 const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);
375 auto pt = m_pcurve->point_to_affine(m_pcurve->mul_by_g(k.value(), rng));
376 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));
377 } else {
378#if defined(BOTAN_HAS_LEGACY_EC_POINT)
379 const auto& group = scalar.group();
380 const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);
381
382 BOTAN_STATE_CHECK(group->m_base_mult != nullptr);
383 std::vector<BigInt> ws;
384 auto pt = group->m_base_mult->mul(bn.value(), rng, m_order, ws);
385 return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
386#else
387 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
388#endif
389 }
390}
391
392std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::mul_px_qy(const EC_AffinePoint_Data& p,
393 const EC_Scalar_Data& x,
394 const EC_AffinePoint_Data& q,
395 const EC_Scalar_Data& y,
396 RandomNumberGenerator& rng) const {
397 if(m_pcurve) {
398 auto pt = m_pcurve->mul_px_qy(EC_AffinePoint_Data_PC::checked_ref(p).value(),
402 rng);
403
404 if(pt) {
405 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(*pt));
406 } else {
407 return nullptr;
408 }
409 } else {
410#if defined(BOTAN_HAS_LEGACY_EC_POINT)
411 std::vector<BigInt> ws;
412 const auto& group = p.group();
413
414 // TODO this could be better!
415 EC_Point_Var_Point_Precompute p_mul(p.to_legacy_point(), rng, ws);
416 EC_Point_Var_Point_Precompute q_mul(q.to_legacy_point(), rng, ws);
417
418 const auto order = group->order() * group->cofactor(); // See #3800
419
420 auto px = p_mul.mul(EC_Scalar_Data_BN::checked_ref(x).value(), rng, order, ws);
421 auto qy = q_mul.mul(EC_Scalar_Data_BN::checked_ref(y).value(), rng, order, ws);
422
423 auto px_qy = px + qy;
424
425 if(!px_qy.is_zero()) {
426 px_qy.force_affine();
427 return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(px_qy));
428 } else {
429 return nullptr;
430 }
431#else
432 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
433#endif
434 }
435}
436
437std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_add(const EC_AffinePoint_Data& p,
438 const EC_AffinePoint_Data& q) const {
439 if(m_pcurve) {
440 auto pt = m_pcurve->point_add(EC_AffinePoint_Data_PC::checked_ref(p).value(),
442
443 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));
444 } else {
445#if defined(BOTAN_HAS_LEGACY_EC_POINT)
446 auto pt = p.to_legacy_point() + q.to_legacy_point();
447 return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
448#else
449 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
450#endif
451 }
452}
453
454std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_neg(const EC_AffinePoint_Data& p) const {
455 if(m_pcurve) {
456 auto pt = m_pcurve->point_negate(EC_AffinePoint_Data_PC::checked_ref(p).value());
457 return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), pt);
458 } else {
459#if defined(BOTAN_HAS_LEGACY_EC_POINT)
460 auto pt = p.to_legacy_point();
461 pt.negate(); // negates in place
462 return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
463#else
464 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
465#endif
466 }
467}
468
469std::unique_ptr<EC_Mul2Table_Data> EC_Group_Data::make_mul2_table(const EC_AffinePoint_Data& h) const {
470 if(m_pcurve) {
471 return std::make_unique<EC_Mul2Table_Data_PC>(h);
472 } else {
473#if defined(BOTAN_HAS_LEGACY_EC_POINT)
474 EC_AffinePoint_Data_BN g(shared_from_this(), this->base_point());
475 return std::make_unique<EC_Mul2Table_Data_BN>(g, h);
476#else
477 throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
478#endif
479 }
480}
481
482} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:144
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static BigInt zero()
Definition bigint.h:49
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43
static BigInt one()
Definition bigint.h:54
bool is_zero() const
Definition bigint.h:457
T serialize(size_t len) const
Definition bigint.h:711
DER_Encoder & encode(bool b)
Definition der_enc.cpp:252
static const EC_AffinePoint_Data_PC & checked_ref(const EC_AffinePoint_Data &data)
std::unique_ptr< EC_Scalar_Data > gk_x_mod_order(const EC_Scalar_Data &scalar, RandomNumberGenerator &rng) const
const BigInt & p() const
const BigInt & g_x() const
std::unique_ptr< EC_AffinePoint_Data > affine_neg(const EC_AffinePoint_Data &p) const
const BigInt & a() const
std::unique_ptr< EC_Scalar_Data > scalar_from_bytes_mod_order(std::span< const uint8_t > bytes) const
std::unique_ptr< EC_AffinePoint_Data > point_deserialize(std::span< const uint8_t > bytes) const
std::unique_ptr< EC_Scalar_Data > scalar_random(RandomNumberGenerator &rng) const
std::unique_ptr< EC_Scalar_Data > scalar_deserialize(std::span< const uint8_t > bytes) const
bool params_match(const BigInt &p, const BigInt &a, const BigInt &b, const BigInt &g_x, const BigInt &g_y, const BigInt &order, const BigInt &cofactor) 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)
std::unique_ptr< EC_AffinePoint_Data > affine_add(const EC_AffinePoint_Data &p, const EC_AffinePoint_Data &q) const
std::unique_ptr< EC_Scalar_Data > scalar_from_bytes_with_trunc(std::span< const uint8_t > bytes) const
std::unique_ptr< EC_Mul2Table_Data > make_mul2_table(const EC_AffinePoint_Data &pt) const
std::unique_ptr< EC_AffinePoint_Data > mul_px_qy(const EC_AffinePoint_Data &p, const EC_Scalar_Data &x, const EC_AffinePoint_Data &q, const EC_Scalar_Data &y, RandomNumberGenerator &rng) const
std::unique_ptr< EC_Scalar_Data > scalar_one() const
const OID & oid() const
std::unique_ptr< EC_AffinePoint_Data > point_g_mul(const EC_Scalar_Data &scalar, RandomNumberGenerator &rng) const
size_t order_bits() const
const BigInt & cofactor() const
EC_Group_Data(const EC_Group_Data &other)=delete
EC_Group_Source source() const
void set_oid(const OID &oid)
const BigInt & g_y() const
size_t order_bytes() const
std::unique_ptr< EC_Scalar_Data > scalar_from_bigint(const BigInt &bn) const
std::unique_ptr< EC_AffinePoint_Data > point_hash_to_curve_ro(std::string_view hash_fn, std::span< const uint8_t > input, std::span< const uint8_t > domain_sep) const
const BigInt & b() const
std::unique_ptr< EC_AffinePoint_Data > point_hash_to_curve_nu(std::string_view hash_fn, std::span< const uint8_t > input, std::span< const uint8_t > domain_sep) const
const BigInt & order() const
EC_Point mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
static const EC_Scalar_Data_BN & checked_ref(const EC_Scalar_Data &data)
static const EC_Scalar_Data_PC & checked_ref(const EC_Scalar_Data &data)
virtual const std::shared_ptr< const EC_Group_Data > & group() const =0
static std::shared_ptr< const PrimeOrderCurve > from_params(const BigInt &p, const BigInt &a, const BigInt &b, const BigInt &base_x, const BigInt &base_y, const BigInt &order)
Definition pcurves.cpp:15
#define BOTAN_HAS_LEGACY_EC_POINT
Definition build.h:230
@ Generic
A generic implementation that handles many curves in one implementation.
Definition ec_group.h:70
void carry(int64_t &h0, int64_t &h1)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
EC_Group_Source
Definition ec_group.h:56
EC_Point OS2ECP(std::span< const uint8_t > data, const CurveGFp &curve)
Definition ec_point.cpp:855