13489630701

Committed 24 Feb 2025 02:31AM UTC coverage: 91.692% (-0.002%) from 91.694%

Build # 13489630701

Build Type

Pull #4712

github

Committed by

web-flow

Commit Message

Merge 9b107f966 into 3db6e2f01

Pull Request Pull Request #4712: Add EC_Group::hash_to_curve_supported

Run Details

95826 of 104509 relevant lines covered (91.69%)

11307776.54 hits per line

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

92.7

/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/ec_inner_pc.h>
#include <botan/internal/fmt.h>
#include <botan/internal/pcurves.h>

#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(Modular_Reducer::for_public_modulus(p)),
      m_mod_order(Modular_Reducer::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_hash_to_curve_supported(false),
      m_order_is_less_than_p(m_order < p),
      m_source(source) {
   // 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(m_pcurve) {
      m_hash_to_curve_supported = m_pcurve->hash_to_curve_supported();
   }

#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 {
   return (this->p() == p && this->a() == a && this->b() == b && this->order() == order &&
           this->cofactor() == cofactor && this->g_x() == g_x && this->g_y() == g_y);
}

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

randombit / botan / 13489630701

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