Botan 3.14.1
Crypto and TLS for C&
pcurves_wrap.h
Go to the documentation of this file.
1/*
2* (C) 2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_PCURVES_WRAP_H_
8#define BOTAN_PCURVES_WRAP_H_
9
10#include <botan/exceptn.h>
11#include <botan/internal/pcurves.h>
12#include <botan/internal/pcurves_impl.h>
13
14namespace Botan::PCurve {
15
16template <typename C>
17concept curve_supports_scalar_invert = requires(const typename C::Scalar& s) {
18 { C::scalar_invert(s) } -> std::same_as<typename C::Scalar>;
19};
20
21/**
22* This class provides a bridge between the "public" (actually still
23* internal) PrimeOrderCurve type, and the inner templates which are
24* subclasses of EllipticCurve from pcurves_impl.h
25*/
26template <typename C>
28 public:
29 static_assert(C::OrderBits <= PrimeOrderCurve::MaximumBitLength);
30 static_assert(C::PrimeFieldBits <= PrimeOrderCurve::MaximumBitLength);
31
32 size_t order_bits() const override { return C::OrderBits; }
33
34 size_t scalar_bytes() const override { return C::Scalar::BYTES; }
35
36 size_t field_element_bytes() const override { return C::FieldElement::BYTES; }
37
38 ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const override {
39 return stash(m_mul_by_g.mul(from_stash(scalar), rng));
40 }
41
42 ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const override {
43 return stash(varpoint_mul<C, VarPointWindowBits>(from_stash(pt), from_stash(scalar), rng));
44 }
45
47 const Scalar& scalar,
48 RandomNumberGenerator& rng) const override {
49 const auto result = varpoint_mul<C, VarPointWindowBits>(from_stash(pt), from_stash(scalar), rng);
50 BOTAN_STATE_CHECK(!result.is_identity().as_bool());
51 const auto pt_x = to_affine_x<C>(result);
52 secure_vector<uint8_t> x_bytes(C::FieldElement::BYTES);
53 pt_x.serialize_to(std::span<uint8_t, C::FieldElement::BYTES>{x_bytes});
54 return x_bytes;
55 }
56
58 public:
59 const auto& table() const { return m_table; }
60
61 explicit PrecomputedMul2TableC(const typename C::AffinePoint& q) : m_table(q) {}
62
63 private:
65 };
66
67 std::unique_ptr<const PrecomputedMul2Table> mul2_setup_g(const AffinePoint& q) const override {
68 return std::make_unique<PrecomputedMul2TableC>(from_stash(q));
69 }
70
71 std::optional<ProjectivePoint> mul2_vartime(const PrecomputedMul2Table& tableb,
72 const Scalar& x,
73 const Scalar& y) const override {
74 try {
75 const auto& table = dynamic_cast<const PrecomputedMul2TableC&>(tableb);
76 const auto pt = table.table().mul2_vartime(m_mul_by_g, from_stash(x), from_stash(y));
77 if(pt.is_identity().as_bool()) {
78 return {};
79 } else {
80 return stash(pt);
81 }
82 } catch(std::bad_cast&) {
83 throw Invalid_Argument("Curve mismatch");
84 }
85 }
86
87 std::optional<ProjectivePoint> mul_px_qy(const AffinePoint& p,
88 const Scalar& x,
89 const AffinePoint& q,
90 const Scalar& y,
91 RandomNumberGenerator& rng) const override {
92 const auto pt =
93 varpoint_mul2<C, Mul2WindowBits>(from_stash(p), from_stash(x), from_stash(q), from_stash(y), rng);
94 if(pt.is_identity().as_bool()) {
95 return {};
96 } else {
97 return stash(pt);
98 }
99 }
100
102 const Scalar& v,
103 const Scalar& x,
104 const Scalar& y) const override {
105 try {
106 const auto& table = dynamic_cast<const PrecomputedMul2TableC&>(tableb);
107 const auto pt = table.table().mul2_vartime(m_mul_by_g, from_stash(x), from_stash(y));
108 // Variable time here, so the early return is fine
109 if(pt.is_identity().as_bool()) {
110 return false;
111 }
112
113 /*
114 * Avoid the inversion by instead projecting v.
115 *
116 * Given (x*z2) and v we want to know if x % n == v
117 *
118 * Inverting z2 to extract x is expensive. Instead compute (v*z2) and
119 * compare it with (x*z2).
120 *
121 * With overwhelming probability, this conversion is correct. The
122 * only time it is not is in the extremely unlikely case where the
123 * signer actually reduced the x coordinate modulo the group order.
124 * That is handled separately in a second step.
125 */
126 const auto z2 = pt.z().square();
127
128 std::array<uint8_t, C::Scalar::BYTES> v_bytes{};
129 from_stash(v).serialize_to(v_bytes);
130
131 if(const auto fe_v = C::FieldElement::deserialize(v_bytes)) {
132 if((*fe_v * z2 == pt.x()).as_bool()) {
133 return true;
134 }
135
136 /*
137 * Possibly (if cryptographically unlikely) the signer
138 * reduced the value modulo the group order.
139 *
140 * If so we must check v + n similarly as before. However here
141 * we must be careful to not overflow since otherwise that
142 * would lead to us accepting an incorrect signature.
143 *
144 * If the order is > p then the reduction modulo p would not have
145 * had any effect and we don't need to consider the possibility
146 */
147 if constexpr(C::OrderIsLessThanField) {
148 /*
149 * We have to be careful to avoid overflow since this would
150 * lead to a forgery
151 *
152 * v < (p)-n => v + n < p
153 *
154 * The values n and neg_n could be precomputed but they are
155 * fast to compute and this codepath will ~never be taken
156 * unless when verifying an invalid signature. In any case
157 * it is many times cheaper than performing the modular inversion
158 * which this approach avoids.
159 */
160
161 // Create the group order as a field element, safe because n < p
162 const auto n = C::FieldElement::from_words(C::NW);
163 const auto neg_n = n.negate().to_words();
164
165 const auto vw = fe_v->to_words();
166 if(bigint_ct_is_lt(vw.data(), vw.size(), neg_n.data(), neg_n.size()).as_bool()) {
167 return (((*fe_v + n) * z2) == pt.x()).as_bool();
168 }
169 }
170 }
171
172 return false;
173 } catch(std::bad_cast&) {
174 throw Invalid_Argument("Curve mismatch");
175 }
176 }
177
178 Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const override {
179 const auto pt = m_mul_by_g.mul(from_stash(scalar), rng);
180 BOTAN_STATE_CHECK(!pt.is_identity().as_bool());
181 std::array<uint8_t, C::FieldElement::BYTES> x_bytes{};
182 to_affine_x<C>(pt).serialize_to(std::span{x_bytes});
183 // Reduction might be required (if unlikely)
184 return stash(C::Scalar::from_wide_bytes(std::span<const uint8_t, C::FieldElement::BYTES>{x_bytes}));
185 }
186
187 AffinePoint generator() const override { return stash(C::G); }
188
189 AffinePoint point_to_affine(const ProjectivePoint& pt) const override {
190 const auto affine = to_affine<C>(from_stash(pt));
191
192 const auto y2 = affine.y().square();
193 const auto x3_ax_b = C::x3_ax_b(affine.x());
194 const auto valid_point = affine.is_identity() || (y2 == x3_ax_b);
195
196 BOTAN_ASSERT(valid_point.as_bool(), "Computed point is on the curve");
197
198 return stash(affine);
199 }
200
201 ProjectivePoint point_add(const AffinePoint& a, const AffinePoint& b) const override {
202 return stash(C::ProjectivePoint::from_affine(from_stash(a)) + from_stash(b));
203 }
204
205 AffinePoint point_negate(const AffinePoint& pt) const override { return stash(from_stash(pt).negate()); }
206
207 bool affine_point_is_identity(const AffinePoint& pt) const override {
208 return from_stash(pt).is_identity().as_bool();
209 }
210
211 void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const override {
212 BOTAN_ARG_CHECK(bytes.size() == C::AffinePoint::BYTES, "Invalid length for serialize_point");
213 from_stash(pt).serialize_to(bytes.subspan<0, C::AffinePoint::BYTES>());
214 }
215
216 void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const override {
217 BOTAN_ARG_CHECK(bytes.size() == C::Scalar::BYTES, "Invalid length to serialize_scalar");
218 return from_stash(scalar).serialize_to(bytes.subspan<0, C::Scalar::BYTES>());
219 }
220
221 std::optional<Scalar> deserialize_scalar(std::span<const uint8_t> bytes) const override {
222 if(auto scalar = C::Scalar::deserialize(bytes)) {
223 if(!scalar->is_zero().as_bool()) {
224 return stash(*scalar);
225 }
226 }
227
228 return {};
229 }
230
231 std::optional<Scalar> scalar_from_wide_bytes(std::span<const uint8_t> bytes) const override {
232 if(auto s = C::Scalar::from_wide_bytes_varlen(bytes)) {
233 return stash(*s);
234 } else {
235 return {};
236 }
237 }
238
239 AffinePoint point_identity() const override { return stash(C::AffinePoint::identity()); }
240
241 std::optional<AffinePoint> deserialize_point_uncompressed(std::span<const uint8_t> bytes) const override {
242 constexpr size_t FieldElementBytes = C::FieldElement::BYTES;
243 constexpr size_t UncompressedBytes = 2 * C::FieldElement::BYTES + 1;
244
245 if(bytes.size() == UncompressedBytes && bytes[0] == 0x04) {
246 const auto encoded_point = bytes.subspan(1);
247 auto x = C::FieldElement::deserialize(encoded_point.first(FieldElementBytes));
248 auto y = C::FieldElement::deserialize(encoded_point.last(FieldElementBytes));
249
250 if(x && y) {
251 // Check that y^2 = x^3 + ax + b
252 const auto lhs = (*y).square();
253 const auto rhs = C::x3_ax_b(*x);
254 const auto valid = (lhs == rhs);
255 if(valid.as_bool()) {
256 return stash(typename C::AffinePoint(*x, *y));
257 }
258 }
259 }
260
261 return {};
262 }
263
264 std::optional<AffinePoint> deserialize_point_compressed(std::span<const uint8_t> bytes) const override {
265 constexpr size_t FieldElementBytes = C::FieldElement::BYTES;
266 constexpr size_t CompressedBytes = C::FieldElement::BYTES + 1;
267
268 if(bytes.size() == CompressedBytes && (bytes[0] == 0x02 || bytes[0] == 0x03)) {
269 const CT::Choice y_is_even = CT::Mask<uint8_t>::is_equal(bytes[0], 0x02).as_choice();
270
271 if(auto x = C::FieldElement::deserialize(bytes.subspan(1, FieldElementBytes))) {
272 if(auto y = sqrt_field_element<C>(C::x3_ax_b(*x)).as_optional_vartime()) {
273 return stash(typename C::AffinePoint(*x, y->correct_sign(y_is_even)));
274 }
275 }
276 }
277
278 return {};
279 }
280
281 bool supports_hash_to_curve() const override { return C::ValidForSswuHash; }
282
283 AffinePoint hash_to_curve_nu(std::function<void(std::span<uint8_t>)> expand_message) const override {
284 if constexpr(C::ValidForSswuHash) {
285 return stash(hash_to_curve_sswu<C, false>(expand_message));
286 } else {
287 throw Not_Implemented("Hash to curve is not implemented for this curve");
288 }
289 }
290
291 ProjectivePoint hash_to_curve_ro(std::function<void(std::span<uint8_t>)> expand_message) const override {
292 if constexpr(C::ValidForSswuHash) {
293 return stash(hash_to_curve_sswu<C, true>(expand_message));
294 } else {
295 throw Not_Implemented("Hash to curve is not implemented for this curve");
296 }
297 }
298
299 Scalar scalar_add(const Scalar& a, const Scalar& b) const override {
300 return stash(from_stash(a) + from_stash(b));
301 }
302
303 Scalar scalar_sub(const Scalar& a, const Scalar& b) const override {
304 return stash(from_stash(a) - from_stash(b));
305 }
306
307 Scalar scalar_mul(const Scalar& a, const Scalar& b) const override {
308 return stash(from_stash(a) * from_stash(b));
309 }
310
311 Scalar scalar_square(const Scalar& s) const override { return stash(from_stash(s).square()); }
312
313 Scalar scalar_invert(const Scalar& ss) const override {
314 const auto s = from_stash(ss);
315 if constexpr(curve_supports_scalar_invert<C>) {
316 return stash(C::scalar_invert(s));
317 } else {
318 return stash(s.invert());
319 }
320 }
321
322 Scalar scalar_invert_vartime(const Scalar& ss) const override {
323 const auto s = from_stash(ss);
324 return stash(s.invert_vartime());
325 }
326
327 Scalar scalar_negate(const Scalar& s) const override { return stash(from_stash(s).negate()); }
328
329 bool scalar_is_zero(const Scalar& s) const override { return from_stash(s).is_zero().as_bool(); }
330
331 bool scalar_equal(const Scalar& a, const Scalar& b) const override {
332 return (from_stash(a) == from_stash(b)).as_bool();
333 }
334
335 Scalar scalar_one() const override { return stash(C::Scalar::one()); }
336
337 Scalar random_scalar(RandomNumberGenerator& rng) const override { return stash(C::Scalar::random(rng)); }
338
339 PrimeOrderCurveImpl() : m_mul_by_g(C::G) {}
340
341 static std::shared_ptr<const PrimeOrderCurve> instance() {
342 static const auto g_curve = std::make_shared<const PrimeOrderCurveImpl<C>>();
343 return g_curve;
344 }
345
346 private:
347 static Scalar stash(const typename C::Scalar& s) {
348 return Scalar::_create(instance(), s.template stash_value<StorageWords>());
349 }
350
351 static typename C::Scalar from_stash(const Scalar& s) {
352 if(s._curve() != instance()) {
353 throw Invalid_Argument("Curve mismatch");
354 }
355 return C::Scalar::from_stash(s._value());
356 }
357
358 static AffinePoint stash(const typename C::AffinePoint& pt) {
359 const auto x_w = pt.x().template stash_value<StorageWords>();
360 const auto y_w = pt.y().template stash_value<StorageWords>();
361 return AffinePoint::_create(instance(), x_w, y_w);
362 }
363
364 static typename C::AffinePoint from_stash(const AffinePoint& pt) {
365 if(pt._curve() != instance()) {
366 throw Invalid_Argument("Curve mismatch");
367 }
368 const auto x = C::FieldElement::from_stash(pt._x());
369 const auto y = C::FieldElement::from_stash(pt._y());
370 return typename C::AffinePoint(x, y);
371 }
372
373 static ProjectivePoint stash(const typename C::ProjectivePoint& pt) {
374 const auto x_w = pt.x().template stash_value<StorageWords>();
375 const auto y_w = pt.y().template stash_value<StorageWords>();
376 const auto z_w = pt.z().template stash_value<StorageWords>();
377 return ProjectivePoint::_create(instance(), x_w, y_w, z_w);
378 }
379
380 static typename C::ProjectivePoint from_stash(const ProjectivePoint& pt) {
381 if(pt._curve() != instance()) {
382 throw Invalid_Argument("Curve mismatch");
383 }
384 const auto x = C::FieldElement::from_stash(pt._x());
385 const auto y = C::FieldElement::from_stash(pt._y());
386 const auto z = C::FieldElement::from_stash(pt._z());
387 return typename C::ProjectivePoint(x, y, z);
388 }
389
390 private:
391 const PrecomputedBaseMulTable<C, BasePointWindowBits> m_mul_by_g;
392};
393
394} // namespace Botan::PCurve
395
396#endif
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
PrecomputedMul2TableC(const typename C::AffinePoint &q)
AffinePoint point_negate(const AffinePoint &pt) const override
Scalar scalar_invert(const Scalar &ss) const override
Scalar inversion.
size_t field_element_bytes() const override
std::unique_ptr< const PrecomputedMul2Table > mul2_setup_g(const AffinePoint &q) const override
Setup a table for 2-ary multiplication where the first point is the generator.
bool scalar_equal(const Scalar &a, const Scalar &b) const override
Test if two scalars are equal.
void serialize_scalar(std::span< uint8_t > bytes, const Scalar &scalar) const override
bool affine_point_is_identity(const AffinePoint &pt) const override
Scalar scalar_sub(const Scalar &a, const Scalar &b) const override
Scalar subtraction.
size_t order_bits() const override
Return the bit length of the group order.
AffinePoint generator() const override
Return the standard generator.
bool supports_hash_to_curve() const override
ProjectivePoint mul_by_g(const Scalar &scalar, RandomNumberGenerator &rng) const override
size_t scalar_bytes() const override
Return the byte length of the scalar element.
AffinePoint hash_to_curve_nu(std::function< void(std::span< uint8_t >)> expand_message) const override
bool scalar_is_zero(const Scalar &s) const override
Test if scalar is zero.
std::optional< AffinePoint > deserialize_point_compressed(std::span< const uint8_t > bytes) const override
Scalar scalar_one() const override
static std::shared_ptr< const PrimeOrderCurve > instance()
std::optional< Scalar > scalar_from_wide_bytes(std::span< const uint8_t > bytes) const override
ProjectivePoint hash_to_curve_ro(std::function< void(std::span< uint8_t >)> expand_message) const override
Scalar base_point_mul_x_mod_order(const Scalar &scalar, RandomNumberGenerator &rng) const override
std::optional< Scalar > deserialize_scalar(std::span< const uint8_t > bytes) const override
Scalar scalar_add(const Scalar &a, const Scalar &b) const override
Scalar addition.
Scalar scalar_negate(const Scalar &s) const override
Scalar negation.
AffinePoint point_identity() const override
Return the identity element (aka the point at infinity).
Scalar scalar_invert_vartime(const Scalar &ss) const override
Scalar inversion (variable time).
bool mul2_vartime_x_mod_order_eq(const PrecomputedMul2Table &tableb, const Scalar &v, const Scalar &x, const Scalar &y) const override
ProjectivePoint point_add(const AffinePoint &a, const AffinePoint &b) const override
Scalar random_scalar(RandomNumberGenerator &rng) const override
void serialize_point(std::span< uint8_t > bytes, const AffinePoint &pt) const override
Scalar scalar_square(const Scalar &s) const override
Scalar squaring.
secure_vector< uint8_t > mul_x_only(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const override
Scalar scalar_mul(const Scalar &a, const Scalar &b) const override
Scalar multiplication.
std::optional< AffinePoint > deserialize_point_uncompressed(std::span< const uint8_t > bytes) const override
AffinePoint point_to_affine(const ProjectivePoint &pt) const override
std::optional< ProjectivePoint > mul2_vartime(const PrecomputedMul2Table &tableb, const Scalar &x, const Scalar &y) const override
ProjectivePoint mul(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const override
std::optional< ProjectivePoint > mul_px_qy(const AffinePoint &p, const Scalar &x, const AffinePoint &q, const Scalar &y, RandomNumberGenerator &rng) const override
static constexpr size_t MaximumBitLength
Definition pcurves.h:37
auto to_affine_x(const typename C::ProjectivePoint &pt)
constexpr CT::Option< typename C::FieldElement > sqrt_field_element(const typename C::FieldElement &fe)
C::ProjectivePoint varpoint_mul(const typename C::AffinePoint &p, const typename C::Scalar &s, RandomNumberGenerator &rng)
BigInt square(const BigInt &x)
Definition numthry.cpp:184
constexpr auto to_affine(const typename C::ProjectivePoint &pt)
auto hash_to_curve_sswu(const ExpandMsg &expand_message) -> std::conditional_t< RO, typename C::ProjectivePoint, typename C::AffinePoint >
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510
C::ProjectivePoint varpoint_mul2(const typename C::AffinePoint &p, const typename C::Scalar &x, const typename C::AffinePoint &q, const typename C::Scalar &y, RandomNumberGenerator &rng)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128