10109696569

Committed 26 Jul 2024 10:20AM UTC coverage: 91.648% (+0.004%) from 91.644%

Build # 10109696569

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4256 from randombit/jack/ec-group-debt

Define some deprecated EC_Group functions in terms of the new APIs

Run Details

87247 of 95198 relevant lines covered (91.65%)

9303720.63 hits per line

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

87.69

/src/lib/pubkey/ec_group/ec_inner_bn.cpp

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

#include <botan/internal/ec_inner_bn.h>

namespace Botan {

const EC_Scalar_Data_BN& EC_Scalar_Data_BN::checked_ref(const EC_Scalar_Data& data) {
   const auto* p = dynamic_cast<const EC_Scalar_Data_BN*>(&data);
   if(!p) {
      throw Invalid_State("Failed conversion to EC_Scalar_Data_BN");
   }
   return *p;
}

const std::shared_ptr<const EC_Group_Data>& EC_Scalar_Data_BN::group() const {
   return m_group;
}

size_t EC_Scalar_Data_BN::bytes() const {
   return this->group()->order_bytes();
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::clone() const {
   return std::make_unique<EC_Scalar_Data_BN>(this->group(), this->value());
}

bool EC_Scalar_Data_BN::is_zero() const {
   return this->value().is_zero();
}

bool EC_Scalar_Data_BN::is_eq(const EC_Scalar_Data& other) const {
   return (value() == checked_ref(other).value());
}

void EC_Scalar_Data_BN::assign(const EC_Scalar_Data& other) {
   m_v = checked_ref(other).value();
}

void EC_Scalar_Data_BN::square_self() {
   m_group->square_mod_order(m_v);
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::negate() const {
   return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(-m_v));
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::invert() const {
   return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->inverse_mod_order(m_v));
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::add(const EC_Scalar_Data& other) const {
   return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(m_v + checked_ref(other).value()));
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::sub(const EC_Scalar_Data& other) const {
   return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(m_v - checked_ref(other).value()));
}

std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::mul(const EC_Scalar_Data& other) const {
   return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->multiply_mod_order(m_v, checked_ref(other).value()));
}

void EC_Scalar_Data_BN::serialize_to(std::span<uint8_t> bytes) const {
   BOTAN_ARG_CHECK(bytes.size() == m_group->order_bytes(), "Invalid output length");
   m_v.serialize_to(bytes);
}

EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group, EC_Point pt) :
      m_group(std::move(group)), m_pt(std::move(pt)) {
   if(!m_pt.is_zero()) {
      m_pt.force_affine();
      m_xy = m_pt.xy_bytes();
   } else {
      m_xy.resize(1 + 2 * this->field_element_bytes());
   }
}

EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group,
                                               std::span<const uint8_t> pt) :
      m_group(std::move(group)) {
   BOTAN_ASSERT_NONNULL(m_group);
   m_pt = Botan::OS2ECP(pt.data(), pt.size(), m_group->curve());
   m_xy = m_pt.xy_bytes();
}

std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::clone() const {
   return std::make_unique<EC_AffinePoint_Data_BN>(m_group, m_pt);
}

const std::shared_ptr<const EC_Group_Data>& EC_AffinePoint_Data_BN::group() const {
   return m_group;
}

std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::mul(const EC_Scalar_Data& scalar,
                                                                 RandomNumberGenerator& rng,
                                                                 std::vector<BigInt>& ws) const {
   BOTAN_ARG_CHECK(scalar.group() == m_group, "Curve mismatch");
   const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);

   EC_Point_Var_Point_Precompute mul(m_pt, rng, ws);

   // We pass order*cofactor here to "correctly" handle the case where the
   // point is on the curve but not in the prime order subgroup. This only
   // matters for groups with cofactor > 1
   // See https://github.com/randombit/botan/issues/3800

   const auto order = m_group->order() * m_group->cofactor();
   auto pt = mul.mul(bn.value(), rng, order, ws);
   return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));
}

size_t EC_AffinePoint_Data_BN::field_element_bytes() const {
   return m_xy.size() / 2;
}

void EC_AffinePoint_Data_BN::serialize_x_to(std::span<uint8_t> bytes) const {
   const size_t fe_bytes = this->field_element_bytes();
   BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");
   copy_mem(bytes, std::span{m_xy}.first(fe_bytes));
}

void EC_AffinePoint_Data_BN::serialize_y_to(std::span<uint8_t> bytes) const {
   const size_t fe_bytes = this->field_element_bytes();
   BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");
   copy_mem(bytes, std::span{m_xy}.last(fe_bytes));
}

void EC_AffinePoint_Data_BN::serialize_xy_to(std::span<uint8_t> bytes) const {
   const size_t fe_bytes = this->field_element_bytes();
   BOTAN_ARG_CHECK(bytes.size() == 2 * fe_bytes, "Invalid output size");
   copy_mem(bytes, m_xy);
}

void EC_AffinePoint_Data_BN::serialize_compressed_to(std::span<uint8_t> bytes) const {
   const size_t fe_bytes = this->field_element_bytes();
   BOTAN_ARG_CHECK(bytes.size() == 1 + fe_bytes, "Invalid output size");
   const bool y_is_odd = (m_xy[m_xy.size() - 1] & 0x01) == 0x01;

   BufferStuffer stuffer(bytes);
   stuffer.append(y_is_odd ? 0x03 : 0x02);
   serialize_x_to(stuffer.next(fe_bytes));
}

void EC_AffinePoint_Data_BN::serialize_uncompressed_to(std::span<uint8_t> bytes) const {
   const size_t fe_bytes = this->field_element_bytes();
   BOTAN_ARG_CHECK(bytes.size() == 1 + 2 * fe_bytes, "Invalid output size");
   BufferStuffer stuffer(bytes);
   stuffer.append(0x04);
   stuffer.append(m_xy);
}

EC_Mul2Table_Data_BN::EC_Mul2Table_Data_BN(const EC_AffinePoint_Data& g, const EC_AffinePoint_Data& h) :
      m_group(g.group()), m_tbl(g.to_legacy_point(), h.to_legacy_point()) {
   BOTAN_ARG_CHECK(h.group() == m_group, "Curve mismatch");
}

std::unique_ptr<EC_AffinePoint_Data> EC_Mul2Table_Data_BN::mul2_vartime(const EC_Scalar_Data& x,
                                                                        const EC_Scalar_Data& y) const {
   BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group, "Curve mismatch");

   const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);
   const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);
   auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());

   if(pt.is_zero()) {
      return nullptr;
   }
   return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));
}

bool EC_Mul2Table_Data_BN::mul2_vartime_x_mod_order_eq(const EC_Scalar_Data& v,
                                                       const EC_Scalar_Data& x,
                                                       const EC_Scalar_Data& y) const {
   BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group && v.group() == m_group, "Curve mismatch");

   const auto& bn_v = EC_Scalar_Data_BN::checked_ref(v);
   const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);
   const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);
   const auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());

   if(pt.is_zero()) {
      return false;
   }

   /*
   * The trick used below doesn't work for curves with cofactors
   */
   if(m_group->has_cofactor()) {
      return m_group->mod_order(pt.get_affine_x()) == bn_v.value();
   }

   /*
   * Note we're working with the projective coordinate directly here!
   * Nominally we're comparing v with the affine x coordinate.
   *
   * return m_group->mod_order(pt.get_affine_x()) == bn_v.value();
   *
   * However by instead projecting r to an identical z as the x
   * coordinate, we can compare without having to perform an
   * expensive inversion in the field.
   *
   * That is, given (x*z2) and r, instead of checking if
   *    (x*z2)*z2^-1 == r,
   * we check if
   *    (x*z2) == (r*z2)
   */
   auto& curve = m_group->curve();

   secure_vector<word> ws;
   BigInt vr = bn_v.value();
   curve.to_rep(vr, ws);
   BigInt z2, v_z2;
   curve.sqr(z2, pt.get_z(), ws);
   curve.mul(v_z2, vr, z2, ws);

   /*
   * Since (typically) the group order is slightly less than the size
   * of the field elements, its possible the signer had to reduce the
   * r component. If they did not reduce r, then this value is correct.
   *
   * Due to the Hasse bound, this case occurs almost always; the
   * probability that a reduction was actually required is
   * approximately 1 in 2^(n/2) where n is the bit length of the curve.
   */
   if(pt.get_x() == v_z2) {
      return true;
   }

   if(m_group->order_is_less_than_p()) {
      vr = bn_v.value() + m_group->order();
      if(vr < m_group->p()) {
         curve.to_rep(vr, ws);
         curve.mul(v_z2, vr, z2, ws);

         if(pt.get_x() == v_z2) {
            return true;
         }
      }
   }

   // Reject:
   return false;
}

}  // 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_bn.h>
8
9	namespace Botan {
10
11	const EC_Scalar_Data_BN& EC_Scalar_Data_BN::checked_ref(const EC_Scalar_Data& data) {	87,769✔
12	const auto* p = dynamic_cast<const EC_Scalar_Data_BN*>(&data);	87,769✔
13	if(!p) {	87,769✔
14	throw Invalid_State("Failed conversion to EC_Scalar_Data_BN");	×
15	}
16	return *p;	87,769✔
17	}
18
19	const std::shared_ptr<const EC_Group_Data>& EC_Scalar_Data_BN::group() const {	88,625✔
20	return m_group;	31,852✔
21	}
22
23	size_t EC_Scalar_Data_BN::bytes() const {	3,603✔
24	return this->group()->order_bytes();	3,603✔
25	}
26
27	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::clone() const {	31,852✔
28	return std::make_unique<EC_Scalar_Data_BN>(this->group(), this->value());	31,852✔
29	}
30
31	bool EC_Scalar_Data_BN::is_zero() const {	32,039✔
32	return this->value().is_zero();	32,039✔
33	}
34
35	bool EC_Scalar_Data_BN::is_eq(const EC_Scalar_Data& other) const {	×
36	return (value() == checked_ref(other).value());	×
37	}
38
39	void EC_Scalar_Data_BN::assign(const EC_Scalar_Data& other) {	×
40	m_v = checked_ref(other).value();	×
41	}	×
42
43	void EC_Scalar_Data_BN::square_self() {	908✔
44	m_group->square_mod_order(m_v);	908✔
45	}	908✔
46
47	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::negate() const {	111✔
48	return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(-m_v));	333✔
49	}
50
51	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::invert() const {	16,100✔
52	return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->inverse_mod_order(m_v));	16,100✔
53	}
54
55	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::add(const EC_Scalar_Data& other) const {	760✔
56	return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(m_v + checked_ref(other).value()));	2,280✔
57	}
58
59	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::sub(const EC_Scalar_Data& other) const {	353✔
60	return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order(m_v - checked_ref(other).value()));	1,059✔
61	}
62
63	std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::mul(const EC_Scalar_Data& other) const {	33,729✔
64	return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->multiply_mod_order(m_v, checked_ref(other).value()));	33,729✔
65	}
66
67	void EC_Scalar_Data_BN::serialize_to(std::span<uint8_t> bytes) const {	4,254✔
68	BOTAN_ARG_CHECK(bytes.size() == m_group->order_bytes(), "Invalid output length");	4,254✔
69	m_v.serialize_to(bytes);	4,254✔
70	}	4,254✔
71
72	EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group, EC_Point pt) :	37,072✔
73	m_group(std::move(group)), m_pt(std::move(pt)) {	37,072✔
74	if(!m_pt.is_zero()) {	46,835✔
75	m_pt.force_affine();	37,037✔
76	m_xy = m_pt.xy_bytes();	37,037✔
77	} else {
78	m_xy.resize(1 + 2 * this->field_element_bytes());	35✔
79	}
80	}	37,072✔
81
82	EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group,	49✔
83	std::span<const uint8_t> pt) :	49✔
84	m_group(std::move(group)) {	49✔
85	BOTAN_ASSERT_NONNULL(m_group);	49✔
86	m_pt = Botan::OS2ECP(pt.data(), pt.size(), m_group->curve());	98✔
87	m_xy = m_pt.xy_bytes();	49✔
88	}	49✔
89
90	std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::clone() const {	6✔
91	return std::make_unique<EC_AffinePoint_Data_BN>(m_group, m_pt);	6✔
92	}
93
94	const std::shared_ptr<const EC_Group_Data>& EC_AffinePoint_Data_BN::group() const {	34,443✔
95	return m_group;	34,443✔
96	}
97
98	std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::mul(const EC_Scalar_Data& scalar,	3,121✔
99	RandomNumberGenerator& rng,
100	std::vector<BigInt>& ws) const {
101	BOTAN_ARG_CHECK(scalar.group() == m_group, "Curve mismatch");	3,121✔
102	const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);	3,121✔
103
104	EC_Point_Var_Point_Precompute mul(m_pt, rng, ws);	3,121✔
105
106	// We pass order*cofactor here to "correctly" handle the case where the
107	// point is on the curve but not in the prime order subgroup. This only
108	// matters for groups with cofactor > 1
109	// See https://github.com/randombit/botan/issues/3800
110
111	const auto order = m_group->order() * m_group->cofactor();	3,121✔
112	auto pt = mul.mul(bn.value(), rng, order, ws);	3,121✔
113	return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));	6,242✔
114	}	6,242✔
115
116	size_t EC_AffinePoint_Data_BN::field_element_bytes() const {	3,943✔
117	return m_xy.size() / 2;	35✔
118	}
119
120	void EC_AffinePoint_Data_BN::serialize_x_to(std::span<uint8_t> bytes) const {	864✔
121	const size_t fe_bytes = this->field_element_bytes();	864✔
122	BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");	864✔
123	copy_mem(bytes, std::span{m_xy}.first(fe_bytes));	864✔
124	}	864✔
125
126	void EC_AffinePoint_Data_BN::serialize_y_to(std::span<uint8_t> bytes) const {	56✔
127	const size_t fe_bytes = this->field_element_bytes();	56✔
128	BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");	56✔
129	copy_mem(bytes, std::span{m_xy}.last(fe_bytes));	56✔
130	}	56✔
131
132	void EC_AffinePoint_Data_BN::serialize_xy_to(std::span<uint8_t> bytes) const {	200✔
133	const size_t fe_bytes = this->field_element_bytes();	200✔
134	BOTAN_ARG_CHECK(bytes.size() == 2 * fe_bytes, "Invalid output size");	200✔
135	copy_mem(bytes, m_xy);	200✔
136	}	200✔
137
138	void EC_AffinePoint_Data_BN::serialize_compressed_to(std::span<uint8_t> bytes) const {	×
139	const size_t fe_bytes = this->field_element_bytes();	×
140	BOTAN_ARG_CHECK(bytes.size() == 1 + fe_bytes, "Invalid output size");	×
141	const bool y_is_odd = (m_xy[m_xy.size() - 1] & 0x01) == 0x01;	×
142
143	BufferStuffer stuffer(bytes);	×
144	stuffer.append(y_is_odd ? 0x03 : 0x02);	×
145	serialize_x_to(stuffer.next(fe_bytes));	×
146	}	×
147
148	void EC_AffinePoint_Data_BN::serialize_uncompressed_to(std::span<uint8_t> bytes) const {	834✔
149	const size_t fe_bytes = this->field_element_bytes();	834✔
150	BOTAN_ARG_CHECK(bytes.size() == 1 + 2 * fe_bytes, "Invalid output size");	834✔
151	BufferStuffer stuffer(bytes);	834✔
152	stuffer.append(0x04);	834✔
153	stuffer.append(m_xy);	834✔
154	}	834✔
155
156	EC_Mul2Table_Data_BN::EC_Mul2Table_Data_BN(const EC_AffinePoint_Data& g, const EC_AffinePoint_Data& h) :	11,481✔
157	m_group(g.group()), m_tbl(g.to_legacy_point(), h.to_legacy_point()) {	11,481✔
158	BOTAN_ARG_CHECK(h.group() == m_group, "Curve mismatch");	11,481✔
159	}	11,481✔
160
161	std::unique_ptr<EC_AffinePoint_Data> EC_Mul2Table_Data_BN::mul2_vartime(const EC_Scalar_Data& x,	320✔
162	const EC_Scalar_Data& y) const {
163	BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group, "Curve mismatch");	320✔
164
165	const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);	320✔
166	const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);	320✔
167	auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());	320✔
168
169	if(pt.is_zero()) {	640✔
170	return nullptr;	×
171	}
172	return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));	320✔
173	}	320✔
174
175	bool EC_Mul2Table_Data_BN::mul2_vartime_x_mod_order_eq(const EC_Scalar_Data& v,	15,283✔
176	const EC_Scalar_Data& x,
177	const EC_Scalar_Data& y) const {
178	BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group && v.group() == m_group, "Curve mismatch");	15,283✔
179
180	const auto& bn_v = EC_Scalar_Data_BN::checked_ref(v);	15,283✔
181	const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);	15,283✔
182	const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);	15,283✔
183	const auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());	15,283✔
184
185	if(pt.is_zero()) {	30,452✔
186	return false;
187	}
188
189	/*
190	* The trick used below doesn't work for curves with cofactors
191	*/
192	if(m_group->has_cofactor()) {	15,173✔
193	return m_group->mod_order(pt.get_affine_x()) == bn_v.value();	×
194	}
195
196	/*
197	* Note we're working with the projective coordinate directly here!
198	* Nominally we're comparing v with the affine x coordinate.
199	*
200	* return m_group->mod_order(pt.get_affine_x()) == bn_v.value();
201	*
202	* However by instead projecting r to an identical z as the x
203	* coordinate, we can compare without having to perform an
204	* expensive inversion in the field.
205	*
206	* That is, given (x*z2) and r, instead of checking if
207	* (xz2)z2^-1 == r,
208	* we check if
209	* (xz2) == (rz2)
210	*/
211	auto& curve = m_group->curve();	15,173✔
212
213	secure_vector<word> ws;	15,173✔
214	BigInt vr = bn_v.value();	15,173✔
215	curve.to_rep(vr, ws);	15,173✔
216	BigInt z2, v_z2;	15,173✔
217	curve.sqr(z2, pt.get_z(), ws);	15,173✔
218	curve.mul(v_z2, vr, z2, ws);	15,173✔
219
220	/*
221	* Since (typically) the group order is slightly less than the size
222	* of the field elements, its possible the signer had to reduce the
223	* r component. If they did not reduce r, then this value is correct.
224	*
225	* Due to the Hasse bound, this case occurs almost always; the
226	* probability that a reduction was actually required is
227	* approximately 1 in 2^(n/2) where n is the bit length of the curve.
228	*/
229	if(pt.get_x() == v_z2) {	15,173✔
230	return true;
231	}
232
233	if(m_group->order_is_less_than_p()) {	8,162✔
234	vr = bn_v.value() + m_group->order();	7,732✔
235	if(vr < m_group->p()) {	7,732✔
236	curve.to_rep(vr, ws);	67✔
237	curve.mul(v_z2, vr, z2, ws);	67✔
238
239	if(pt.get_x() == v_z2) {	67✔
240	return true;
241	}
242	}
243	}
244
245	// Reject:
246	return false;
247	}	60,802✔
248
249	} // namespace Botan

randombit / botan / 10109696569

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