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