Botan 3.7.1
Crypto and TLS for C&
pcurves.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_H_
8#define BOTAN_PCURVES_H_
9
10#include <botan/internal/pcurves_id.h>
11
12#include <botan/concepts.h>
13#include <botan/secmem.h>
14#include <botan/types.h>
15#include <array>
16#include <optional>
17#include <span>
18#include <string_view>
19#include <vector>
20
21namespace Botan {
22
23class RandomNumberGenerator;
24
25} // namespace Botan
26
27namespace Botan::PCurve {
28
29/**
30* An elliptic curve without cofactor in Weierstrass form
31*/
33 public:
34 /// Somewhat arbitrary maximum size for a field or scalar
35 ///
36 /// Sized to fit at least P-521
37 static const size_t MaximumBitLength = 521;
38
39 static const size_t MaximumByteLength = (MaximumBitLength + 7) / 8;
40
41 /// Number of words used to store MaximumByteLength
42 static const size_t StorageWords = (MaximumByteLength + sizeof(word) - 1) / sizeof(word);
43
44 static std::shared_ptr<const PrimeOrderCurve> from_name(std::string_view name) {
46 return PrimeOrderCurve::from_id(id.value());
47 } else {
48 return {};
49 }
50 }
51
52 static std::shared_ptr<const PrimeOrderCurve> from_id(PrimeOrderCurveId id);
53
54 typedef std::array<word, StorageWords> StorageUnit;
55 typedef std::shared_ptr<const PrimeOrderCurve> CurvePtr;
56
57 /// Elliptic curve scalar
58 ///
59 /// This refers to the set of integers modulo the (prime) group order
60 /// of the elliptic curve.
61 class Scalar final {
62 public:
63 Scalar(const Scalar& other) = default;
64 Scalar(Scalar&& other) = default;
65 Scalar& operator=(const Scalar& other) = default;
66 Scalar& operator=(Scalar&& other) = default;
67 ~Scalar() = default;
68
69 /**
70 * Return the size of the byte encoding of Scalars
71 */
72 size_t bytes() const { return m_curve->scalar_bytes(); }
73
74 /**
75 * Return the fixed length serialization of this scalar
76 */
77 template <concepts::resizable_byte_buffer T = std::vector<uint8_t>>
78 T serialize() const {
79 T bytes(this->bytes());
80 m_curve->serialize_scalar(bytes, *this);
81 return bytes;
82 }
83
84 /**
85 * Perform integer multiplication modulo the group order
86 */
87 friend Scalar operator*(const Scalar& a, const Scalar& b) { return a.m_curve->scalar_mul(a, b); }
88
89 /**
90 * Perform integer addition modulo the group order
91 */
92 friend Scalar operator+(const Scalar& a, const Scalar& b) { return a.m_curve->scalar_add(a, b); }
93
94 /**
95 * Perform integer subtraction modulo the group order
96 */
97 friend Scalar operator-(const Scalar& a, const Scalar& b) { return a.m_curve->scalar_sub(a, b); }
98
99 /**
100 * Check for equality
101 */
102 friend bool operator==(const Scalar& a, const Scalar& b) { return a.m_curve->scalar_equal(a, b); }
103
104 /**
105 * Negate modulo the group order (ie return p - *this where p is the group order)
106 */
107 Scalar negate() const { return m_curve->scalar_negate(*this); }
108
109 /**
110 * Square modulo the group order
111 */
112 Scalar square() const { return m_curve->scalar_square(*this); }
113
114 /**
115 * Return the modular inverse of *this
116 *
117 * If *this is zero then returns zero.
118 */
119 Scalar invert() const { return m_curve->scalar_invert(*this); }
120
121 /**
122 * Return the modular inverse of *this (variable time)
123 *
124 * If *this is zero then returns zero.
125 */
126 Scalar invert_vartime() const { return m_curve->scalar_invert_vartime(*this); }
127
128 /**
129 * Returns true if this is equal to zero
130 */
131 bool is_zero() const { return m_curve->scalar_is_zero(*this); }
132
133 const auto& _curve() const { return m_curve; }
134
135 const auto& _value() const { return m_value; }
136
137 static Scalar _create(CurvePtr curve, StorageUnit v) { return Scalar(std::move(curve), v); }
138
139 private:
140 Scalar(CurvePtr curve, StorageUnit v) : m_curve(std::move(curve)), m_value(v) {}
141
142 CurvePtr m_curve;
143 StorageUnit m_value;
144 };
145
146 /**
147 * A point on the elliptic curve in affine form
148 *
149 * These points can be serialized, or converted to projective form for computation
150 */
152 public:
153 AffinePoint(const AffinePoint& other) = default;
154 AffinePoint(AffinePoint&& other) = default;
155 AffinePoint& operator=(const AffinePoint& other) = default;
156 AffinePoint& operator=(AffinePoint&& other) = default;
157 ~AffinePoint() = default;
158
159 static AffinePoint generator(CurvePtr curve) { return curve->generator(); }
160
161 /**
162 * Return the size of the uncompressed encoding of points
163 */
164 size_t bytes() const { return 1 + 2 * m_curve->field_element_bytes(); }
165
166 /**
167 * Return the size of the compressed encoding of points
168 */
169 size_t compressed_bytes() const { return 1 + m_curve->field_element_bytes(); }
170
171 /**
172 * Return the serialization of the point in uncompressed form
173 */
174 template <concepts::resizable_byte_buffer T = std::vector<uint8_t>>
175 T serialize() const {
176 T bytes(this->bytes());
177 m_curve->serialize_point(bytes, *this);
178 return bytes;
179 }
180
181 /**
182 * Return the serialization of the point in compressed form
183 */
184 template <concepts::resizable_byte_buffer T = std::vector<uint8_t>>
186 T bytes(this->compressed_bytes());
187 m_curve->serialize_point_compressed(bytes, *this);
188 return bytes;
189 }
190
191 /**
192 * Return the serialization of the x coordinate
193 */
194 template <concepts::resizable_byte_buffer T = secure_vector<uint8_t>>
195 T x_bytes() const {
196 secure_vector<uint8_t> bytes(m_curve->field_element_bytes());
197 m_curve->serialize_point_x(bytes, *this);
198 return bytes;
199 }
200
201 /**
202 * Point negation
203 */
204 AffinePoint negate() const { return m_curve->point_negate(*this); }
205
206 /**
207 * Return true if this is the curve identity element (aka the point at infinity)
208 */
209 bool is_identity() const { return m_curve->affine_point_is_identity(*this); }
210
211 const auto& _curve() const { return m_curve; }
212
213 const auto& _x() const { return m_x; }
214
215 const auto& _y() const { return m_y; }
216
218 return AffinePoint(std::move(curve), x, y);
219 }
220
221 private:
222 AffinePoint(CurvePtr curve, StorageUnit x, StorageUnit y) : m_curve(std::move(curve)), m_x(x), m_y(y) {}
223
224 CurvePtr m_curve;
225 StorageUnit m_x;
226 StorageUnit m_y;
227 };
228
229 /**
230 * A point on the elliptic curve in projective form
231 *
232 * This is a form that is convenient for computation; it must be converted to
233 * affine form for comparisons or serialization.
234 */
236 public:
237 ProjectivePoint(const ProjectivePoint& other) = default;
239 ProjectivePoint& operator=(const ProjectivePoint& other) = default;
241 ~ProjectivePoint() = default;
242
243 /**
244 * Convert a point from affine to projective form
245 */
246 static ProjectivePoint from_affine(const AffinePoint& pt) { return pt._curve()->point_to_projective(pt); }
247
248 /**
249 * Convert a point from projective to affine form
250 *
251 * This operation is expensive; perform it only when required for
252 * serialization
253 */
254 AffinePoint to_affine() const { return m_curve->point_to_affine(*this); }
255
256 ProjectivePoint dbl() const { return m_curve->point_double(*this); }
257
259 return x.m_curve->point_add(x, y);
260 }
261
263 return x.m_curve->point_add_mixed(x, y);
264 }
265
266 const auto& _curve() const { return m_curve; }
267
268 const auto& _x() const { return m_x; }
269
270 const auto& _y() const { return m_y; }
271
272 const auto& _z() const { return m_z; }
273
275 return ProjectivePoint(std::move(curve), x, y, z);
276 }
277
278 private:
280 m_curve(std::move(curve)), m_x(x), m_y(y), m_z(z) {}
281
282 CurvePtr m_curve;
283 StorageUnit m_x;
284 StorageUnit m_y;
285 StorageUnit m_z;
286 };
287
289 public:
290 virtual ~PrecomputedMul2Table() = default;
291 };
292
293 virtual ~PrimeOrderCurve() = default;
294
295 /// Return the bit length of the group order
296 virtual size_t order_bits() const = 0;
297
298 /// Return the byte length of the scalar element
299 virtual size_t scalar_bytes() const = 0;
300
301 /// Return the byte length of a field element
302 ///
303 /// Each point consists of two field elements
304 virtual size_t field_element_bytes() const = 0;
305
306 /// Base point multiplication
307 ///
308 /// Multiply by the standard generator point g
309 virtual ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
310
311 /// Base point multiplication, returning only the x coordinate modulo the group order
312 ///
313 /// Multiply by the standard generator point g, then extract the x
314 /// coordinate as an integer, then reduce the x coordinate modulo the
315 /// group order
316 virtual Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
317
318 /// Generic point multiplication
319 ///
320 /// Multiply an arbitrary point by a scalar
321 virtual ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
322
323 /// Generic x-only point multiplication
324 ///
325 /// Multiply an arbitrary point by a scalar, returning only the x coordinate
327 const Scalar& scalar,
328 RandomNumberGenerator& rng) const = 0;
329
330 /// Setup a table for 2-ary multiplication
331 virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup(const AffinePoint& p,
332 const AffinePoint& pq) const = 0;
333
334 /// Setup a table for 2-ary multiplication where the first point is the generator
335 virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup_g(const AffinePoint& q) const = 0;
336
337 /// Perform 2-ary multiplication (variable time)
338 ///
339 /// Compute p*x + q*y in variable time
340 ///
341 /// Returns nullopt if the produced point is the point at infinity
342 virtual std::optional<ProjectivePoint> mul2_vartime(const PrecomputedMul2Table& table,
343 const Scalar& x,
344 const Scalar& y) const = 0;
345
346 /// Perform 2-ary multiplication (constant time)
347 ///
348 /// Compute p*x + q*y
349 ///
350 /// Returns nullopt if the produced point is the point at infinity
351 virtual std::optional<ProjectivePoint> mul_px_qy(const AffinePoint& p,
352 const Scalar& x,
353 const AffinePoint& q,
354 const Scalar& y,
355 RandomNumberGenerator& rng) const = 0;
356
357 /// Perform 2-ary multiplication (variable time), reducing x modulo order
358 ///
359 /// Compute p*x + q*y in variable time, then extract the x coordinate of
360 /// the result, and reduce x modulo the group order. Compare that value
361 /// with v. If equal, returns true. Otherwise returns false, including if
362 /// the produced point is the point at infinity
364 const Scalar& v,
365 const Scalar& x,
366 const Scalar& y) const = 0;
367
368 /// Return the standard generator
369 virtual AffinePoint generator() const = 0;
370
371 /// Deserialize a point
372 ///
373 /// Both compressed and uncompressed encodings are accepted
374 ///
375 /// Note that the deprecated "hybrid" encoding is not supported here
376 virtual std::optional<AffinePoint> deserialize_point(std::span<const uint8_t> bytes) const = 0;
377
378 /// Deserialize a scalar in [1,p)
379 ///
380 /// This function requires the input length be exactly scalar_bytes long;
381 /// it does not accept inputs that are shorter, or with excess leading
382 /// zero padding bytes.
383 ///
384 /// This function also rejects zero as an input, since in normal usage
385 /// scalars are integers in Z_p*
386 virtual std::optional<Scalar> deserialize_scalar(std::span<const uint8_t> bytes) const = 0;
387
388 /// Reduce an integer modulo the group order
389 ///
390 /// The input can be at most twice the bit length of the order; if larger than this
391 /// nullopt is returned
392 virtual std::optional<Scalar> scalar_from_wide_bytes(std::span<const uint8_t> bytes) const = 0;
393
394 virtual AffinePoint point_to_affine(const ProjectivePoint& pt) const = 0;
395
396 virtual ProjectivePoint point_to_projective(const AffinePoint& pt) const = 0;
397
398 virtual bool affine_point_is_identity(const AffinePoint& pt) const = 0;
399
400 virtual ProjectivePoint point_double(const ProjectivePoint& pt) const = 0;
401
402 virtual AffinePoint point_negate(const AffinePoint& pt) const = 0;
403
404 virtual ProjectivePoint point_add(const ProjectivePoint& a, const ProjectivePoint& b) const = 0;
405
406 virtual ProjectivePoint point_add_mixed(const ProjectivePoint& a, const AffinePoint& b) const = 0;
407
408 virtual void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
409
410 virtual void serialize_point_compressed(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
411
412 virtual void serialize_point_x(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
413
414 virtual void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const = 0;
415
416 /**
417 * Return the scalar zero
418 */
419 virtual Scalar scalar_zero() const = 0;
420
421 /**
422 * Return the scalar one
423 */
424 virtual Scalar scalar_one() const = 0;
425
426 virtual Scalar scalar_add(const Scalar& a, const Scalar& b) const = 0;
427 virtual Scalar scalar_sub(const Scalar& a, const Scalar& b) const = 0;
428 virtual Scalar scalar_mul(const Scalar& a, const Scalar& b) const = 0;
429 virtual Scalar scalar_square(const Scalar& s) const = 0;
430 virtual Scalar scalar_invert(const Scalar& s) const = 0;
431 virtual Scalar scalar_invert_vartime(const Scalar& s) const = 0;
432 virtual Scalar scalar_negate(const Scalar& s) const = 0;
433 virtual bool scalar_is_zero(const Scalar& s) const = 0;
434 virtual bool scalar_equal(const Scalar& a, const Scalar& b) const = 0;
435
436 /**
437 * Return a new random scalar
438 */
440
441 /**
442 * RFC 9380 hash to curve (NU variant)
443 *
444 * This is currently only supported for a few specific curves
445 */
446 virtual AffinePoint hash_to_curve_nu(std::string_view hash,
447 std::span<const uint8_t> input,
448 std::span<const uint8_t> domain_sep) const = 0;
449
450 /**
451 * RFC 9380 hash to curve (RO variant)
452 *
453 * This is currently only supported for a few specific curves
454 */
455 virtual ProjectivePoint hash_to_curve_ro(std::string_view hash,
456 std::span<const uint8_t> input,
457 std::span<const uint8_t> domain_sep) const = 0;
458};
459
460} // namespace Botan::PCurve
461
462#endif
Identifier for a named prime order curve.
Definition pcurves_id.h:27
static std::optional< PrimeOrderCurveId > from_string(std::string_view name)
Map a string to a curve identifier.
Definition pcurves.cpp:163
AffinePoint & operator=(const AffinePoint &other)=default
static AffinePoint generator(CurvePtr curve)
Definition pcurves.h:159
static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y)
Definition pcurves.h:217
AffinePoint(AffinePoint &&other)=default
AffinePoint & operator=(AffinePoint &&other)=default
AffinePoint(const AffinePoint &other)=default
friend ProjectivePoint operator+(const ProjectivePoint &x, const AffinePoint &y)
Definition pcurves.h:262
ProjectivePoint & operator=(const ProjectivePoint &other)=default
ProjectivePoint(const ProjectivePoint &other)=default
ProjectivePoint(ProjectivePoint &&other)=default
ProjectivePoint & operator=(ProjectivePoint &&other)=default
static ProjectivePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y, StorageUnit z)
Definition pcurves.h:274
friend ProjectivePoint operator+(const ProjectivePoint &x, const ProjectivePoint &y)
Definition pcurves.h:258
static ProjectivePoint from_affine(const AffinePoint &pt)
Definition pcurves.h:246
Scalar(const Scalar &other)=default
friend Scalar operator-(const Scalar &a, const Scalar &b)
Definition pcurves.h:97
friend Scalar operator*(const Scalar &a, const Scalar &b)
Definition pcurves.h:87
Scalar & operator=(Scalar &&other)=default
Scalar & operator=(const Scalar &other)=default
friend bool operator==(const Scalar &a, const Scalar &b)
Definition pcurves.h:102
static Scalar _create(CurvePtr curve, StorageUnit v)
Definition pcurves.h:137
friend Scalar operator+(const Scalar &a, const Scalar &b)
Definition pcurves.h:92
virtual ~PrimeOrderCurve()=default
virtual Scalar scalar_add(const Scalar &a, const Scalar &b) const =0
virtual std::unique_ptr< const PrecomputedMul2Table > mul2_setup(const AffinePoint &p, const AffinePoint &pq) const =0
Setup a table for 2-ary multiplication.
static const size_t MaximumByteLength
Definition pcurves.h:39
virtual AffinePoint point_negate(const AffinePoint &pt) const =0
virtual AffinePoint hash_to_curve_nu(std::string_view hash, std::span< const uint8_t > input, std::span< const uint8_t > domain_sep) const =0
virtual void serialize_point(std::span< uint8_t > bytes, const AffinePoint &pt) const =0
virtual std::optional< AffinePoint > deserialize_point(std::span< const uint8_t > bytes) const =0
virtual Scalar scalar_zero() const =0
virtual std::unique_ptr< const PrecomputedMul2Table > mul2_setup_g(const AffinePoint &q) const =0
Setup a table for 2-ary multiplication where the first point is the generator.
virtual size_t field_element_bytes() const =0
virtual size_t order_bits() const =0
Return the bit length of the group order.
virtual size_t scalar_bytes() const =0
Return the byte length of the scalar element.
virtual bool scalar_is_zero(const Scalar &s) const =0
std::array< word, StorageWords > StorageUnit
Definition pcurves.h:54
virtual std::optional< ProjectivePoint > mul2_vartime(const PrecomputedMul2Table &table, const Scalar &x, const Scalar &y) const =0
virtual std::optional< Scalar > deserialize_scalar(std::span< const uint8_t > bytes) const =0
virtual Scalar scalar_invert(const Scalar &s) const =0
virtual Scalar scalar_mul(const Scalar &a, const Scalar &b) const =0
virtual void serialize_point_compressed(std::span< uint8_t > bytes, const AffinePoint &pt) const =0
virtual ProjectivePoint hash_to_curve_ro(std::string_view hash, std::span< const uint8_t > input, std::span< const uint8_t > domain_sep) const =0
virtual Scalar random_scalar(RandomNumberGenerator &rng) const =0
virtual secure_vector< uint8_t > mul_x_only(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const =0
virtual bool mul2_vartime_x_mod_order_eq(const PrecomputedMul2Table &table, const Scalar &v, const Scalar &x, const Scalar &y) const =0
virtual AffinePoint point_to_affine(const ProjectivePoint &pt) const =0
virtual AffinePoint generator() const =0
Return the standard generator.
virtual Scalar scalar_one() const =0
virtual Scalar scalar_negate(const Scalar &s) const =0
static std::shared_ptr< const PrimeOrderCurve > from_id(PrimeOrderCurveId id)
Definition pcurves.cpp:101
virtual void serialize_point_x(std::span< uint8_t > bytes, const AffinePoint &pt) const =0
virtual ProjectivePoint mul_by_g(const Scalar &scalar, RandomNumberGenerator &rng) const =0
virtual std::optional< Scalar > scalar_from_wide_bytes(std::span< const uint8_t > bytes) const =0
virtual ProjectivePoint point_to_projective(const AffinePoint &pt) const =0
static std::shared_ptr< const PrimeOrderCurve > from_name(std::string_view name)
Definition pcurves.h:44
virtual ProjectivePoint mul(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const =0
static const size_t StorageWords
Number of words used to store MaximumByteLength.
Definition pcurves.h:42
virtual Scalar scalar_invert_vartime(const Scalar &s) const =0
virtual Scalar scalar_square(const Scalar &s) const =0
virtual bool scalar_equal(const Scalar &a, const Scalar &b) const =0
virtual std::optional< ProjectivePoint > mul_px_qy(const AffinePoint &p, const Scalar &x, const AffinePoint &q, const Scalar &y, RandomNumberGenerator &rng) const =0
virtual ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b) const =0
virtual bool affine_point_is_identity(const AffinePoint &pt) const =0
std::shared_ptr< const PrimeOrderCurve > CurvePtr
Definition pcurves.h:55
virtual Scalar base_point_mul_x_mod_order(const Scalar &scalar, RandomNumberGenerator &rng) const =0
virtual ProjectivePoint point_add(const ProjectivePoint &a, const ProjectivePoint &b) const =0
virtual void serialize_scalar(std::span< uint8_t > bytes, const Scalar &scalar) const =0
virtual Scalar scalar_sub(const Scalar &a, const Scalar &b) const =0
static const size_t MaximumBitLength
Definition pcurves.h:37
virtual ProjectivePoint point_double(const ProjectivePoint &pt) const =0
std::string name
int(* final)(unsigned char *, CTX *)
FE_25519 T
Definition ge.cpp:34
const SIMD_8x32 & b
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61