25619874939

Committed 09 May 2026 05:34PM UTC coverage: 89.328% (-0.002%) from 89.33%

Build # 25619874939

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5591 from randombit/jack/gha-cache-cleanup

In GH Actions clean up branch caches after the PRs are merged

Coverage Stats

107641 of 120501 relevant lines covered (89.33%)

11279629.67 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.57

/src/lib/pubkey/ec_group/ec_inner_data.cpp

/*
* (C) 2024 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/ec_inner_data.h>

#include <botan/der_enc.h>
#include <botan/internal/barrett.h>
#include <botan/internal/ec_inner_pc.h>
#include <botan/internal/fmt.h>
#include <botan/internal/pcurves.h>
#include <algorithm>

#if defined(BOTAN_HAS_LEGACY_EC_POINT)
   #include <botan/internal/ec_inner_bn.h>
   #include <botan/internal/point_mul.h>
#endif

#if defined(BOTAN_HAS_XMD)
   #include <botan/internal/xmd.h>
#endif

namespace Botan {

EC_Group_Data::~EC_Group_Data() = default;

// Note this constructor *does not* initialize m_curve, m_base_point or m_base_mult
EC_Group_Data::EC_Group_Data(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) :
      m_p(p),
      m_a(a),
      m_b(b),
      m_g_x(g_x),
      m_g_y(g_y),
      m_order(order),
      m_cofactor(cofactor),
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      m_mod_field(Barrett_Reduction::for_public_modulus(p)),
      m_mod_order(Barrett_Reduction::for_public_modulus(order)),
      m_monty(m_p, m_mod_field),
#endif
      m_oid(oid),
      m_p_words(p.sig_words()),
      m_p_bits(p.bits()),
      m_order_bits(order.bits()),
      m_order_bytes((m_order_bits + 7) / 8),
      m_a_is_minus_3(a == p - 3),
      m_a_is_zero(a.is_zero()),
      m_has_cofactor(m_cofactor != 1),
      m_order_is_less_than_p(m_order < p),
      m_source(source) {
   // Verify the generator (x, y) satisfies y^2 = x^3 + a*x + b (mod p)
   auto mod_p = Barrett_Reduction::for_public_modulus(p);
   const BigInt y2 = mod_p.square(g_y);
   const BigInt x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);
   if(y2 != x3_ax_b) {
      throw Invalid_Argument("EC_Group generator is not on the curve");
   }

   // TODO(Botan4) we can assume/assert the OID is set
   if(!m_oid.empty()) {
      DER_Encoder der(m_der_named_curve);
      der.encode(m_oid);

      const std::string name = m_oid.human_name_or_empty();
      if(!name.empty()) {
         // returns nullptr if unknown or not supported
         m_pcurve = PCurve::PrimeOrderCurve::for_named_curve(name);
      }
      if(m_pcurve) {
         m_engine = EC_Group_Engine::Optimized;
      }
   }

   // Try a generic pcurves instance
   if(!m_pcurve && !m_has_cofactor) {
      m_pcurve = PCurve::PrimeOrderCurve::from_params(p, a, b, g_x, g_y, order);
      if(m_pcurve) {
         m_engine = EC_Group_Engine::Generic;
      }
      // possibly still null here, if parameters unsuitable or if the
      // pcurves_generic module wasn't included in the build
   }

#if defined(BOTAN_HAS_LEGACY_EC_POINT)
   secure_vector<word> ws;
   m_a_r = m_monty.mul(a, m_monty.R2(), ws);
   m_b_r = m_monty.mul(b, m_monty.R2(), ws);
   if(!m_pcurve) {
      m_engine = EC_Group_Engine::Legacy;
   }
#else
   if(!m_pcurve) {
      if(m_oid.empty()) {
         throw Not_Implemented("EC_Group this group is not supported in this build configuration");
      } else {
         throw Not_Implemented(
            fmt("EC_Group the group {} is not supported in this build configuration", oid.to_string()));
      }
   }
#endif
}

std::shared_ptr<EC_Group_Data> 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) {
   auto group = std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source);

#if defined(BOTAN_HAS_LEGACY_EC_POINT)
   group->m_curve = CurveGFp(group.get());
   group->m_base_point = EC_Point(group->m_curve, g_x, g_y);
   if(!group->m_pcurve) {
      group->m_base_mult = std::make_unique<EC_Point_Base_Point_Precompute>(group->m_base_point, group->m_mod_order);
   }
#endif

   return group;
}

bool EC_Group_Data::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 {
   if(p != this->p()) {
      return false;
   }
   if(a != this->a()) {
      return false;
   }
   if(b != this->b()) {
      return false;
   }
   if(order != this->order()) {
      return false;
   }
   if(cofactor != this->cofactor()) {
      return false;
   }
   if(g_x != this->g_x()) {
      return false;
   }
   if(g_y != this->g_y()) {
      return false;
   }

   return true;
}

bool EC_Group_Data::params_match(const BigInt& p,
                                 const BigInt& a,
                                 const BigInt& b,
                                 std::span<const uint8_t> base_pt,
                                 const BigInt& order,
                                 const BigInt& cofactor) const {
   if(p != this->p()) {
      return false;
   }
   if(a != this->a()) {
      return false;
   }
   if(b != this->b()) {
      return false;
   }
   if(order != this->order()) {
      return false;
   }
   if(cofactor != this->cofactor()) {
      return false;
   }

   const size_t field_len = this->p_bytes();

   if(base_pt.size() == 1 + field_len && (base_pt[0] == 0x02 || base_pt[0] == 0x03)) {
      // compressed

      const auto g_x = m_g_x.serialize(field_len);
      const auto g_y = m_g_y.is_odd();

      const auto sec1_x = base_pt.subspan(1, field_len);
      const bool sec1_y = (base_pt[0] == 0x03);

      if(!std::ranges::equal(sec1_x, g_x)) {
         return false;
      }

      if(sec1_y != g_y) {
         return false;
      }

      return true;
   } else if(base_pt.size() == 1 + 2 * field_len && base_pt[0] == 0x04) {
      const auto g_x = m_g_x.serialize(field_len);
      const auto g_y = m_g_y.serialize(field_len);

      const auto sec1_x = base_pt.subspan(1, field_len);
      const auto sec1_y = base_pt.subspan(1 + field_len, field_len);

      if(!std::ranges::equal(sec1_x, g_x)) {
         return false;
      }

      if(!std::ranges::equal(sec1_y, g_y)) {
         return false;
      }

      return true;
   } else {
      throw Decoding_Error("Invalid base point encoding in explicit group");
   }
}

bool EC_Group_Data::params_match(const EC_Group_Data& other) const {
   return params_match(other.p(), other.a(), other.b(), other.g_x(), other.g_y(), other.order(), other.cofactor());
}

void EC_Group_Data::set_oid(const OID& oid) {
   BOTAN_ARG_CHECK(!oid.empty(), "OID should be set");
   BOTAN_STATE_CHECK(m_oid.empty() && m_der_named_curve.empty());
   m_oid = oid;

   DER_Encoder der(m_der_named_curve);
   der.encode(m_oid);
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_with_trunc(std::span<const uint8_t> bytes) const {
   const size_t bit_length = 8 * bytes.size();

   if(bit_length < order_bits()) {
      // No shifting required, but might still need to reduce by modulus
      return this->scalar_from_bytes_mod_order(bytes);
   } else {
      const size_t shift = bit_length - order_bits();

      const size_t new_length = bytes.size() - (shift / 8);
      const size_t bit_shift = shift % 8;

      if(bit_shift == 0) {
         // Easy case just read different bytes
         return this->scalar_from_bytes_mod_order(bytes.first(new_length));
      } else {
         std::vector<uint8_t> sbytes(new_length);

         uint8_t carry = 0;
         for(size_t i = 0; i != new_length; ++i) {
            const uint8_t w = bytes[i];
            sbytes[i] = (w >> bit_shift) | carry;
            carry = w << (8 - bit_shift);
         }

         return this->scalar_from_bytes_mod_order(sbytes);
      }
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_mod_order(std::span<const uint8_t> bytes) const {
   if(bytes.size() > 2 * order_bytes()) {
      return {};
   }

   if(m_pcurve) {
      if(auto s = m_pcurve->scalar_from_wide_bytes(bytes)) {
         return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), std::move(*s));
      } else {
         return {};
      }
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(BigInt(bytes)));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_random(RandomNumberGenerator& rng) const {
   if(m_pcurve) {
      return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->random_scalar(rng));
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(),
                                                 BigInt::random_integer(rng, BigInt::one(), m_order));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_one() const {
   if(m_pcurve) {
      return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->scalar_one());
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::one());
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bigint(const BigInt& bn) const {
   if(bn <= 0 || bn >= m_order) {
      return {};
   }

   if(m_pcurve) {
      return this->scalar_deserialize(bn.serialize(m_order_bytes));
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), bn);
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::gk_x_mod_order(const EC_Scalar_Data& scalar,
                                                              RandomNumberGenerator& rng) const {
   if(m_pcurve) {
      const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);
      auto gk_x_mod_order = m_pcurve->base_point_mul_x_mod_order(k.value(), rng);
      return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), gk_x_mod_order);
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      const auto& k = EC_Scalar_Data_BN::checked_ref(scalar);
      BOTAN_STATE_CHECK(m_base_mult != nullptr);
      std::vector<BigInt> ws;
      const auto pt = m_base_mult->mul(k.value(), rng, m_order, ws);

      if(pt.is_zero()) {
         return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::zero());
      } else {
         return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(pt.get_affine_x()));
      }
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_deserialize(std::span<const uint8_t> bytes) const {
   if(bytes.size() != m_order_bytes) {
      return nullptr;
   }

   if(m_pcurve) {
      if(auto s = m_pcurve->deserialize_scalar(bytes)) {
         return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), *s);
      } else {
         return nullptr;
      }
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      BigInt r(bytes);

      if(r.is_zero() || r >= m_order) {
         return nullptr;
      }

      return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), std::move(r));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_deserialize(std::span<const uint8_t> bytes) const {
   // The deprecated "hybrid" point format
   // TODO(Botan4) remove this
   if(bytes.size() >= 1 + 2 * 4 && (bytes[0] == 0x06 || bytes[0] == 0x07)) {
      const bool hdr_y_is_even = bytes[0] == 0x06;
      const bool y_is_even = (bytes.back() & 0x01) == 0;

      if(hdr_y_is_even == y_is_even) {
         std::vector<uint8_t> sec1(bytes.begin(), bytes.end());
         sec1[0] = 0x04;
         return this->point_deserialize(sec1);
      }
   }

   try {
      if(m_pcurve) {
         if(auto pt = m_pcurve->deserialize_point(bytes)) {
            return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(*pt));
         } else {
            return {};
         }
      } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
         auto pt = Botan::OS2ECP(bytes, m_curve);
         return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
#else
         throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
      }
   } catch(...) {
      return {};
   }
}

namespace {

std::function<void(std::span<uint8_t>)> h2c_expand_message(std::string_view hash_fn,
                                                           std::span<const uint8_t> input,
                                                           std::span<const uint8_t> domain_sep) {
   /*
   * This could be extended to support expand_message_xof or a MHF like Argon2
   */

   if(hash_fn.starts_with("SHAKE")) {
      throw Not_Implemented("Hash to curve currently does not support expand_message_xof");
   }

   return [=](std::span<uint8_t> uniform_bytes) {
#if defined(BOTAN_HAS_XMD)
      expand_message_xmd(hash_fn, uniform_bytes, input, domain_sep);
#else
      BOTAN_UNUSED(hash_fn, uniform_bytes, input, domain_sep);
      throw Not_Implemented("Hash to curve is not implemented due to XMD being disabled");
#endif
   };
}

}  // namespace

std::unique_ptr<EC_AffinePoint_Data> EC_Group_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 {
   if(m_pcurve) {
      auto pt = m_pcurve->hash_to_curve_ro(h2c_expand_message(hash_fn, input, domain_sep));
      return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));
   } else {
      throw Not_Implemented("Hash to curve is not implemented for this curve");
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_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 {
   if(m_pcurve) {
      auto pt = m_pcurve->hash_to_curve_nu(h2c_expand_message(hash_fn, input, domain_sep));
      return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));
   } else {
      throw Not_Implemented("Hash to curve is not implemented for this curve");
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_g_mul(const EC_Scalar_Data& scalar,
                                                                RandomNumberGenerator& rng) const {
   if(m_pcurve) {
      const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);
      auto pt = m_pcurve->point_to_affine(m_pcurve->mul_by_g(k.value(), rng));
      return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      const auto& group = scalar.group();
      const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);

      BOTAN_STATE_CHECK(group->m_base_mult != nullptr);
      std::vector<BigInt> ws;
      auto pt = group->m_base_mult->mul(bn.value(), rng, m_order, ws);
      return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_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 {
   if(m_pcurve) {
      auto pt = m_pcurve->mul_px_qy(EC_AffinePoint_Data_PC::checked_ref(p).value(),
                                    EC_Scalar_Data_PC::checked_ref(x).value(),
                                    EC_AffinePoint_Data_PC::checked_ref(q).value(),
                                    EC_Scalar_Data_PC::checked_ref(y).value(),
                                    rng);

      if(pt) {
         return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(*pt));
      } else {
         return nullptr;
      }
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      std::vector<BigInt> ws;
      const auto& group = p.group();

      // TODO this could be better!
      const EC_Point_Var_Point_Precompute p_mul(p.to_legacy_point(), rng, ws);
      const EC_Point_Var_Point_Precompute q_mul(q.to_legacy_point(), rng, ws);

      const auto order = group->order() * group->cofactor();  // See #3800

      auto px = p_mul.mul(EC_Scalar_Data_BN::checked_ref(x).value(), rng, order, ws);
      auto qy = q_mul.mul(EC_Scalar_Data_BN::checked_ref(y).value(), rng, order, ws);

      auto px_qy = px + qy;

      if(!px_qy.is_zero()) {
         px_qy.force_affine();
         return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(px_qy));
      } else {
         return nullptr;
      }
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_add(const EC_AffinePoint_Data& p,
                                                               const EC_AffinePoint_Data& q) const {
   if(m_pcurve) {
      auto pt = m_pcurve->point_add(EC_AffinePoint_Data_PC::checked_ref(p).value(),
                                    EC_AffinePoint_Data_PC::checked_ref(q).value());

      return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      auto pt = p.to_legacy_point() + q.to_legacy_point();
      return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_neg(const EC_AffinePoint_Data& p) const {
   if(m_pcurve) {
      auto pt = m_pcurve->point_negate(EC_AffinePoint_Data_PC::checked_ref(p).value());
      return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), pt);
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      auto pt = p.to_legacy_point();
      pt.negate();  // negates in place
      return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

std::unique_ptr<EC_Mul2Table_Data> EC_Group_Data::make_mul2_table(const EC_AffinePoint_Data& h) const {
   if(m_pcurve) {
      return std::make_unique<EC_Mul2Table_Data_PC>(h);
   } else {
#if defined(BOTAN_HAS_LEGACY_EC_POINT)
      const EC_AffinePoint_Data_BN g(shared_from_this(), this->base_point());
      return std::make_unique<EC_Mul2Table_Data_BN>(g, h);
#else
      throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
#endif
   }
}

}  // namespace Botan

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/barrett.h>
11	#include <botan/internal/ec_inner_pc.h>
12	#include <botan/internal/fmt.h>
13	#include <botan/internal/pcurves.h>
14	#include <algorithm>
15
16	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
17	#include <botan/internal/ec_inner_bn.h>
18	#include <botan/internal/point_mul.h>
19	#endif
20
21	#if defined(BOTAN_HAS_XMD)
22	#include <botan/internal/xmd.h>
23	#endif
24
25	namespace Botan {
26
27	EC_Group_Data::~EC_Group_Data() = default;	3,863✔
28
29	// Note this constructor does not initialize m_curve, m_base_point or m_base_mult
30	EC_Group_Data::EC_Group_Data(const BigInt& p,	645✔
31	const BigInt& a,
32	const BigInt& b,
33	const BigInt& g_x,
34	const BigInt& g_y,
35	const BigInt& order,
36	const BigInt& cofactor,
37	const OID& oid,
38	EC_Group_Source source) :	645✔
39	m_p(p),	645✔
40	m_a(a),	645✔
41	m_b(b),	645✔
42	m_g_x(g_x),	645✔
43	m_g_y(g_y),	645✔
44	m_order(order),	645✔
45	m_cofactor(cofactor),	645✔
46	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
47	m_mod_field(Barrett_Reduction::for_public_modulus(p)),	645✔
48	m_mod_order(Barrett_Reduction::for_public_modulus(order)),	645✔
49	m_monty(m_p, m_mod_field),	645✔
50	#endif
51	m_oid(oid),	645✔
52	m_p_words(p.sig_words()),	645✔
53	m_p_bits(p.bits()),	645✔
54	m_order_bits(order.bits()),	645✔
55	m_order_bytes((m_order_bits + 7) / 8),	645✔
56	m_a_is_minus_3(a == p - 3),	645✔
57	m_a_is_zero(a.is_zero()),	645✔
58	m_has_cofactor(m_cofactor != 1),	645✔
59	m_order_is_less_than_p(m_order < p),	645✔
60	m_source(source) {	1,935✔
61	// Verify the generator (x, y) satisfies y^2 = x^3 + a*x + b (mod p)
62	auto mod_p = Barrett_Reduction::for_public_modulus(p);	645✔
63	const BigInt y2 = mod_p.square(g_y);	645✔
64	const BigInt x3_ax_b = mod_p.reduce(mod_p.cube(g_x) + mod_p.multiply(a, g_x) + b);	645✔
65	if(y2 != x3_ax_b) {	645✔
66	throw Invalid_Argument("EC_Group generator is not on the curve");	×
67	}
68
69	// TODO(Botan4) we can assume/assert the OID is set
70	if(!m_oid.empty()) {	645✔
71	DER_Encoder der(m_der_named_curve);	638✔
72	der.encode(m_oid);	638✔
73
74	const std::string name = m_oid.human_name_or_empty();	638✔
75	if(!name.empty()) {	638✔
76	// returns nullptr if unknown or not supported
77	m_pcurve = PCurve::PrimeOrderCurve::for_named_curve(name);	633✔
78	}
79	if(m_pcurve) {	638✔
80	m_engine = EC_Group_Engine::Optimized;	587✔
81	}
82	}	638✔
83
84	// Try a generic pcurves instance
85	if(!m_pcurve && !m_has_cofactor) {	645✔
86	m_pcurve = PCurve::PrimeOrderCurve::from_params(p, a, b, g_x, g_y, order);	57✔
87	if(m_pcurve) {	57✔
88	m_engine = EC_Group_Engine::Generic;	47✔
89	}
90	// possibly still null here, if parameters unsuitable or if the
91	// pcurves_generic module wasn't included in the build
92	}
93
94	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
95	secure_vector<word> ws;	645✔
96	m_a_r = m_monty.mul(a, m_monty.R2(), ws);	1,290✔
97	m_b_r = m_monty.mul(b, m_monty.R2(), ws);	1,290✔
98	if(!m_pcurve) {	645✔
99	m_engine = EC_Group_Engine::Legacy;	11✔
100	}
101	#else
102	if(!m_pcurve) {
103	if(m_oid.empty()) {
104	throw Not_Implemented("EC_Group this group is not supported in this build configuration");
105	} else {
106	throw Not_Implemented(
107	fmt("EC_Group the group {} is not supported in this build configuration", oid.to_string()));
108	}
109	}
110	#endif
111	}	1,290✔
112
113	std::shared_ptr<EC_Group_Data> EC_Group_Data::create(const BigInt& p,	645✔
114	const BigInt& a,
115	const BigInt& b,
116	const BigInt& g_x,
117	const BigInt& g_y,
118	const BigInt& order,
119	const BigInt& cofactor,
120	const OID& oid,
121	EC_Group_Source source) {
122	auto group = std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source);	645✔
123
124	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
125	group->m_curve = CurveGFp(group.get());	645✔
126	group->m_base_point = EC_Point(group->m_curve, g_x, g_y);	1,290✔
127	if(!group->m_pcurve) {	645✔
128	group->m_base_mult = std::make_unique<EC_Point_Base_Point_Precompute>(group->m_base_point, group->m_mod_order);	11✔
129	}
130	#endif
131
132	return group;	645✔
133	}	×
134
135	bool EC_Group_Data::params_match(const BigInt& p,	78✔
136	const BigInt& a,
137	const BigInt& b,
138	const BigInt& g_x,
139	const BigInt& g_y,
140	const BigInt& order,
141	const BigInt& cofactor) const {
142	if(p != this->p()) {	78✔
143	return false;
144	}
145	if(a != this->a()) {	34✔
146	return false;
147	}
148	if(b != this->b()) {	34✔
149	return false;
150	}
151	if(order != this->order()) {	34✔
152	return false;
153	}
154	if(cofactor != this->cofactor()) {	34✔
155	return false;
156	}
157	if(g_x != this->g_x()) {	34✔
158	return false;
159	}
160	if(g_y != this->g_y()) {	34✔
161	return false;
162	}
163
164	return true;
165	}
166
167	bool EC_Group_Data::params_match(const BigInt& p,	830✔
168	const BigInt& a,
169	const BigInt& b,
170	std::span<const uint8_t> base_pt,
171	const BigInt& order,
172	const BigInt& cofactor) const {
173	if(p != this->p()) {	830✔
174	return false;
175	}
176	if(a != this->a()) {	76✔
177	return false;
178	}
179	if(b != this->b()) {	71✔
180	return false;
181	}
182	if(order != this->order()) {	64✔
183	return false;
184	}
185	if(cofactor != this->cofactor()) {	63✔
186	return false;
187	}
188
189	const size_t field_len = this->p_bytes();	63✔
190
191	if(base_pt.size() == 1 + field_len && (base_pt[0] == 0x02 \|\| base_pt[0] == 0x03)) {	63✔
192	// compressed
193
194	const auto g_x = m_g_x.serialize(field_len);	×
195	const auto g_y = m_g_y.is_odd();	×
196
197	const auto sec1_x = base_pt.subspan(1, field_len);	×
198	const bool sec1_y = (base_pt[0] == 0x03);	×
199
200	if(!std::ranges::equal(sec1_x, g_x)) {	×
201	return false;
202	}
203
204	if(sec1_y != g_y) {	×
205	return false;
206	}
207
208	return true;	×
209	} else if(base_pt.size() == 1 + 2 * field_len && base_pt[0] == 0x04) {	63✔
210	const auto g_x = m_g_x.serialize(field_len);	62✔
211	const auto g_y = m_g_y.serialize(field_len);	62✔
212
213	const auto sec1_x = base_pt.subspan(1, field_len);	62✔
214	const auto sec1_y = base_pt.subspan(1 + field_len, field_len);	62✔
215
216	if(!std::ranges::equal(sec1_x, g_x)) {	124✔
217	return false;
218	}
219
220	if(!std::ranges::equal(sec1_y, g_y)) {	174✔
221	return false;
222	}
223
224	return true;	56✔
225	} else {	124✔
226	throw Decoding_Error("Invalid base point encoding in explicit group");	1✔
227	}
228	}
229
230	bool EC_Group_Data::params_match(const EC_Group_Data& other) const {	×
231	return params_match(other.p(), other.a(), other.b(), other.g_x(), other.g_y(), other.order(), other.cofactor());	×
232	}
233
234	void EC_Group_Data::set_oid(const OID& oid) {	×
235	BOTAN_ARG_CHECK(!oid.empty(), "OID should be set");	×
236	BOTAN_STATE_CHECK(m_oid.empty() && m_der_named_curve.empty());	×
237	m_oid = oid;	×
238
239	DER_Encoder der(m_der_named_curve);	×
240	der.encode(m_oid);	×
241	}	×
242
243	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_with_trunc(std::span<const uint8_t> bytes) const {	38,983✔
244	const size_t bit_length = 8 * bytes.size();	38,983✔
245
246	if(bit_length < order_bits()) {	38,983✔
247	// No shifting required, but might still need to reduce by modulus
248	return this->scalar_from_bytes_mod_order(bytes);	8,015✔
249	} else {
250	const size_t shift = bit_length - order_bits();	30,968✔
251
252	const size_t new_length = bytes.size() - (shift / 8);	30,968✔
253	const size_t bit_shift = shift % 8;	30,968✔
254
255	if(bit_shift == 0) {	30,968✔
256	// Easy case just read different bytes
257	return this->scalar_from_bytes_mod_order(bytes.first(new_length));	28,004✔
258	} else {
259	std::vector<uint8_t> sbytes(new_length);	2,964✔
260
261	uint8_t carry = 0;	2,964✔
262	for(size_t i = 0; i != new_length; ++i) {	83,920✔
263	const uint8_t w = bytes[i];	80,956✔
264	sbytes[i] = (w >> bit_shift) \| carry;	80,956✔
265	carry = w << (8 - bit_shift);	80,956✔
266	}
267
268	return this->scalar_from_bytes_mod_order(sbytes);	2,964✔
269	}	2,964✔
270	}
271	}
272
273	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bytes_mod_order(std::span<const uint8_t> bytes) const {	49,937✔
274	if(bytes.size() > 2 * order_bytes()) {	49,937✔
275	return {};	×
276	}
277
278	if(m_pcurve) {	49,937✔
279	if(auto s = m_pcurve->scalar_from_wide_bytes(bytes)) {	46,853✔
280	return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), std::move(*s));	46,853✔
281	} else {
282	return {};	×
283	}	46,853✔
284	} else {
285	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
286	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(BigInt(bytes)));	3,084✔
287	#else
288	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
289	#endif
290	}
291	}
292
293	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_random(RandomNumberGenerator& rng) const {	46,573✔
294	if(m_pcurve) {	46,573✔
295	return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->random_scalar(rng));	40,370✔
296	} else {
297	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
298	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(),	12,406✔
299	BigInt::random_integer(rng, BigInt::one(), m_order));	18,609✔
300	#else
301	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
302	#endif
303	}
304	}
305
306	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_one() const {	266✔
307	if(m_pcurve) {	266✔
308	return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), m_pcurve->scalar_one());	250✔
309	} else {
310	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
311	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::one());	16✔
312	#else
313	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
314	#endif
315	}
316	}
317
318	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_from_bigint(const BigInt& bn) const {	4,497✔
319	if(bn <= 0 \|\| bn >= m_order) {	4,497✔
320	return {};	×
321	}
322
323	if(m_pcurve) {	4,497✔
324	return this->scalar_deserialize(bn.serialize(m_order_bytes));	8,172✔
325	} else {
326	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
327	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), bn);	411✔
328	#else
329	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
330	#endif
331	}
332	}
333
334	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::gk_x_mod_order(const EC_Scalar_Data& scalar,	6,270✔
335	RandomNumberGenerator& rng) const {
336	if(m_pcurve) {	6,270✔
337	const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);	5,871✔
338	auto gk_x_mod_order = m_pcurve->base_point_mul_x_mod_order(k.value(), rng);	5,871✔
339	return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), gk_x_mod_order);	5,871✔
340	} else {	5,871✔
341	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
342	const auto& k = EC_Scalar_Data_BN::checked_ref(scalar);	399✔
343	BOTAN_STATE_CHECK(m_base_mult != nullptr);	399✔
344	std::vector<BigInt> ws;	399✔
345	const auto pt = m_base_mult->mul(k.value(), rng, m_order, ws);	399✔
346
347	if(pt.is_zero()) {	798✔
348	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), BigInt::zero());	×
349	} else {
350	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), m_mod_order.reduce(pt.get_affine_x()));	399✔
351	}
352	#else
353	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
354	#endif
355	}	399✔
356	}
357
358	std::unique_ptr<EC_Scalar_Data> EC_Group_Data::scalar_deserialize(std::span<const uint8_t> bytes) const {	94,835✔
359	if(bytes.size() != m_order_bytes) {	94,835✔
360	return nullptr;	7,764✔
361	}
362
363	if(m_pcurve) {	87,071✔
364	if(auto s = m_pcurve->deserialize_scalar(bytes)) {	82,270✔
365	return std::make_unique<EC_Scalar_Data_PC>(shared_from_this(), *s);	79,791✔
366	} else {
367	return nullptr;	2,479✔
368	}	82,270✔
369	} else {
370	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
371	BigInt r(bytes);	4,801✔
372
373	if(r.is_zero() \|\| r >= m_order) {	9,602✔
374	return nullptr;	454✔
375	}
376
377	return std::make_unique<EC_Scalar_Data_BN>(shared_from_this(), std::move(r));	4,347✔
378	#else
379	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
380	#endif
381	}	4,801✔
382	}
383
384	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_deserialize(std::span<const uint8_t> bytes) const {	46,920✔
385	// The deprecated "hybrid" point format
386	// TODO(Botan4) remove this
387	if(bytes.size() >= 1 + 2 * 4 && (bytes[0] == 0x06 \|\| bytes[0] == 0x07)) {	46,920✔
388	const bool hdr_y_is_even = bytes[0] == 0x06;	181✔
389	const bool y_is_even = (bytes.back() & 0x01) == 0;	181✔
390
391	if(hdr_y_is_even == y_is_even) {	181✔
392	std::vector<uint8_t> sec1(bytes.begin(), bytes.end());	141✔
393	sec1[0] = 0x04;	141✔
394	return this->point_deserialize(sec1);	141✔
395	}	141✔
396	}
397
398	try {	46,779✔
399	if(m_pcurve) {	46,779✔
400	if(auto pt = m_pcurve->deserialize_point(bytes)) {	44,052✔
401	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(*pt));	38,104✔
402	} else {
403	return {};	5,948✔
404	}	44,052✔
405	} else {
406	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
407	auto pt = Botan::OS2ECP(bytes, m_curve);	2,727✔
408	return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));	2,719✔
409	#else
410	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
411	#endif
412	}	2,719✔
413	} catch(...) {	8✔
414	return {};	8✔
415	}	8✔
416	}
417
418	namespace {
419
420	std::function<void(std::span<uint8_t>)> h2c_expand_message(std::string_view hash_fn,	77✔
421	std::span<const uint8_t> input,
422	std::span<const uint8_t> domain_sep) {
423	/*
424	* This could be extended to support expand_message_xof or a MHF like Argon2
425	*/
426
427	if(hash_fn.starts_with("SHAKE")) {	77✔
428	throw Not_Implemented("Hash to curve currently does not support expand_message_xof");	×
429	}
430
431	return [=](std::span<uint8_t> uniform_bytes) {	228✔
432	#if defined(BOTAN_HAS_XMD)
433	expand_message_xmd(hash_fn, uniform_bytes, input, domain_sep);	74✔
434	#else
435	BOTAN_UNUSED(hash_fn, uniform_bytes, input, domain_sep);
436	throw Not_Implemented("Hash to curve is not implemented due to XMD being disabled");
437	#endif
438	};	77✔
439	}
440
441	} // namespace
442
443	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_hash_to_curve_ro(std::string_view hash_fn,	34✔
444	std::span<const uint8_t> input,
445	std::span<const uint8_t> domain_sep) const {
446	if(m_pcurve) {	34✔
447	auto pt = m_pcurve->hash_to_curve_ro(h2c_expand_message(hash_fn, input, domain_sep));	34✔
448	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));	34✔
449	} else {	34✔
450	throw Not_Implemented("Hash to curve is not implemented for this curve");	×
451	}
452	}
453
454	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_hash_to_curve_nu(std::string_view hash_fn,	43✔
455	std::span<const uint8_t> input,
456	std::span<const uint8_t> domain_sep) const {
457	if(m_pcurve) {	43✔
458	auto pt = m_pcurve->hash_to_curve_nu(h2c_expand_message(hash_fn, input, domain_sep));	46✔
459	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));	40✔
460	} else {	40✔
461	throw Not_Implemented("Hash to curve is not implemented for this curve");	×
462	}
463	}
464
465	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::point_g_mul(const EC_Scalar_Data& scalar,	17,551✔
466	RandomNumberGenerator& rng) const {
467	if(m_pcurve) {	17,551✔
468	const auto& k = EC_Scalar_Data_PC::checked_ref(scalar);	15,698✔
469	auto pt = m_pcurve->point_to_affine(m_pcurve->mul_by_g(k.value(), rng));	15,698✔
470	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), std::move(pt));	15,698✔
471	} else {	15,698✔
472	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
473	const auto& group = scalar.group();	1,853✔
474	const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);	1,853✔
475
476	BOTAN_STATE_CHECK(group->m_base_mult != nullptr);	1,853✔
477	std::vector<BigInt> ws;	1,853✔
478	auto pt = group->m_base_mult->mul(bn.value(), rng, m_order, ws);	1,853✔
479	return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));	1,853✔
480	#else
481	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
482	#endif
483	}	1,853✔
484	}
485
486	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::mul_px_qy(const EC_AffinePoint_Data& p,	3,488✔
487	const EC_Scalar_Data& x,
488	const EC_AffinePoint_Data& q,
489	const EC_Scalar_Data& y,
490	RandomNumberGenerator& rng) const {
491	if(m_pcurve) {	3,488✔
492	auto pt = m_pcurve->mul_px_qy(EC_AffinePoint_Data_PC::checked_ref(p).value(),	6,416✔
493	EC_Scalar_Data_PC::checked_ref(x).value(),	3,208✔
494	EC_AffinePoint_Data_PC::checked_ref(q).value(),	3,208✔
495	EC_Scalar_Data_PC::checked_ref(y).value(),	3,208✔
496	rng);	3,208✔
497
498	if(pt) {	3,208✔
499	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(*pt));	3,040✔
500	} else {
501	return nullptr;	168✔
502	}
503	} else {	3,208✔
504	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
505	std::vector<BigInt> ws;	280✔
506	const auto& group = p.group();	280✔
507
508	// TODO this could be better!
509	const EC_Point_Var_Point_Precompute p_mul(p.to_legacy_point(), rng, ws);	280✔
510	const EC_Point_Var_Point_Precompute q_mul(q.to_legacy_point(), rng, ws);	280✔
511
512	const auto order = group->order() * group->cofactor(); // See #3800	280✔
513
514	auto px = p_mul.mul(EC_Scalar_Data_BN::checked_ref(x).value(), rng, order, ws);	280✔
515	auto qy = q_mul.mul(EC_Scalar_Data_BN::checked_ref(y).value(), rng, order, ws);	280✔
516
517	auto px_qy = px + qy;	280✔
518
519	if(!px_qy.is_zero()) {	532✔
520	px_qy.force_affine();	252✔
521	return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(px_qy));	252✔
522	} else {
523	return nullptr;	28✔
524	}
525	#else
526	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
527	#endif
528	}	840✔
529	}
530
531	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_add(const EC_AffinePoint_Data& p,	10,208✔
532	const EC_AffinePoint_Data& q) const {
533	if(m_pcurve) {	10,208✔
534	auto pt = m_pcurve->point_add(EC_AffinePoint_Data_PC::checked_ref(p).value(),	9,468✔
535	EC_AffinePoint_Data_PC::checked_ref(q).value());	9,468✔
536
537	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), m_pcurve->point_to_affine(pt));	9,467✔
538	} else {	9,467✔
539	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
540	auto pt = p.to_legacy_point() + q.to_legacy_point();	740✔
541	return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));	740✔
542	#else
543	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
544	#endif
545	}	740✔
546	}
547
548	std::unique_ptr<EC_AffinePoint_Data> EC_Group_Data::affine_neg(const EC_AffinePoint_Data& p) const {	9,628✔
549	if(m_pcurve) {	9,628✔
550	auto pt = m_pcurve->point_negate(EC_AffinePoint_Data_PC::checked_ref(p).value());	8,566✔
551	return std::make_unique<EC_AffinePoint_Data_PC>(shared_from_this(), pt);	8,566✔
552	} else {	8,566✔
553	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
554	auto pt = p.to_legacy_point();	1,062✔
555	pt.negate(); // negates in place	1,062✔
556	return std::make_unique<EC_AffinePoint_Data_BN>(shared_from_this(), std::move(pt));	1,062✔
557	#else
558	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
559	#endif
560	}	1,062✔
561	}
562
563	std::unique_ptr<EC_Mul2Table_Data> EC_Group_Data::make_mul2_table(const EC_AffinePoint_Data& h) const {	13,606✔
564	if(m_pcurve) {	13,606✔
565	return std::make_unique<EC_Mul2Table_Data_PC>(h);	13,302✔
566	} else {
567	#if defined(BOTAN_HAS_LEGACY_EC_POINT)
568	const EC_AffinePoint_Data_BN g(shared_from_this(), this->base_point());	608✔
569	return std::make_unique<EC_Mul2Table_Data_BN>(g, h);	304✔
570	#else
571	throw Not_Implemented("Legacy EC interfaces disabled in this build configuration");
572	#endif
573	}	304✔
574	}
575
576	} // namespace Botan

randombit / botan / 25619874939

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous