Botan 3.14.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/secmem.h>
11#include <botan/types.h>
12#include <botan/internal/ct_utils.h>
13#include <array>
14#include <functional>
15#include <memory>
16#include <optional>
17#include <span>
18#include <string_view>
19
20namespace Botan {
21
22class BigInt;
24
25} // namespace Botan
26
27namespace Botan::PCurve {
28
29/**
30* An elliptic curve without cofactor in Weierstrass form
31*/
32class PrimeOrderCurve /* NOLINT(*-special-member-functions) */ {
33 public:
34 /// Somewhat arbitrary maximum size for a field or scalar
35 ///
36 /// Sized to fit at least P-521
37 static constexpr size_t MaximumBitLength = 521;
38
39 static constexpr size_t MaximumByteLength = (MaximumBitLength + 7) / 8;
40
41 /// Number of words used to store MaximumByteLength
42 static constexpr size_t StorageWords = (MaximumByteLength + sizeof(word) - 1) / sizeof(word);
43
44 /// @returns nullptr if the curve specified is not available
45 static std::shared_ptr<const PrimeOrderCurve> for_named_curve(std::string_view name);
46
47 /// @returns nullptr if the parameters seem unsuitable for pcurves
48 /// for example if the prime is too large
49 ///
50 /// This function *should* accept the same subset of curves as
51 /// the EC_Group constructor that accepts BigInts.
52 static std::shared_ptr<const PrimeOrderCurve> from_params(const BigInt& p,
53 const BigInt& a,
54 const BigInt& b,
55 const BigInt& base_x,
56 const BigInt& base_y,
57 const BigInt& order);
58
59 typedef std::array<word, StorageWords> StorageUnit;
60 typedef std::shared_ptr<const PrimeOrderCurve> CurvePtr;
61
62 /// Elliptic curve scalar
63 ///
64 /// This refers to the set of integers modulo the (prime) group order
65 /// of the elliptic curve.
66 class Scalar final {
67 public:
68 Scalar(const Scalar& other) = default;
69 Scalar(Scalar&& other) = default;
70 Scalar& operator=(const Scalar& other) = default;
71 Scalar& operator=(Scalar&& other) = default;
72
73 // Scalars are commonly secret values so wipe on destruction
75
76 void _zeroize();
77
78 const auto& _curve() const { return m_curve; }
79
80 const auto& _value() const { return m_value; }
81
82 static Scalar _create(CurvePtr curve, StorageUnit v) { return Scalar(std::move(curve), v); }
83
84 void _const_time_poison() const { CT::poison(m_value); }
85
86 void _const_time_unpoison() const { CT::unpoison(m_value); }
87
88 private:
89 Scalar(CurvePtr curve, StorageUnit v) : m_curve(std::move(curve)), m_value(v) {}
90
91 CurvePtr m_curve;
92 StorageUnit m_value;
93 };
94
95 /**
96 * A point on the elliptic curve in affine form
97 *
98 * These points can be serialized, or converted to projective form for computation
99 */
100 class AffinePoint final {
101 public:
102 AffinePoint(const AffinePoint& other) = default;
103 AffinePoint(AffinePoint&& other) = default;
104 AffinePoint& operator=(const AffinePoint& other) = default;
105 AffinePoint& operator=(AffinePoint&& other) = default;
106 ~AffinePoint() = default;
107
108 static AffinePoint generator(const CurvePtr& curve) { return curve->generator(); }
109
110 const auto& _curve() const { return m_curve; }
111
112 const auto& _x() const { return m_x; }
113
114 const auto& _y() const { return m_y; }
115
117 return AffinePoint(std::move(curve), x, y);
118 }
119
120 void _const_time_poison() const { CT::poison_all(m_x, m_y); }
121
122 void _const_time_unpoison() const { CT::unpoison_all(m_x, m_y); }
123
124 private:
125 AffinePoint(CurvePtr curve, StorageUnit x, StorageUnit y) : m_curve(std::move(curve)), m_x(x), m_y(y) {}
126
127 CurvePtr m_curve;
128 StorageUnit m_x;
129 StorageUnit m_y;
130 };
131
132 /**
133 * A point on the elliptic curve in projective form
134 *
135 * This is a form that is convenient for computation; it must be converted to
136 * affine form for comparisons or serialization.
137 */
138 class ProjectivePoint final {
139 public:
140 ProjectivePoint(const ProjectivePoint& other) = default;
142 ProjectivePoint& operator=(const ProjectivePoint& other) = default;
144 ~ProjectivePoint() = default;
145
146 const auto& _curve() const { return m_curve; }
147
148 const auto& _x() const { return m_x; }
149
150 const auto& _y() const { return m_y; }
151
152 const auto& _z() const { return m_z; }
153
155 return ProjectivePoint(std::move(curve), x, y, z);
156 }
157
158 private:
160 m_curve(std::move(curve)), m_x(x), m_y(y), m_z(z) {}
161
162 CurvePtr m_curve;
163 StorageUnit m_x;
164 StorageUnit m_y;
165 StorageUnit m_z;
166 };
167
168 class PrecomputedMul2Table /* NOLINT(*-special-member-functions) */ {
169 public:
170 virtual ~PrecomputedMul2Table() = default;
171 };
172
173 virtual ~PrimeOrderCurve() = default;
174
175 /// Return the bit length of the group order
176 virtual size_t order_bits() const = 0;
177
178 /// Return the byte length of the scalar element
179 virtual size_t scalar_bytes() const = 0;
180
181 /// Return the byte length of a field element
182 ///
183 /// Each point consists of two field elements
184 virtual size_t field_element_bytes() const = 0;
185
186 /// Base point multiplication
187 ///
188 /// Multiply by the standard generator point g
189 virtual ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
190
191 /// Base point multiplication, returning only the x coordinate modulo the group order
192 ///
193 /// Multiply by the standard generator point g, then extract the x
194 /// coordinate as an integer, then reduce the x coordinate modulo the
195 /// group order
196 virtual Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
197
198 /// Generic point multiplication
199 ///
200 /// Multiply an arbitrary point by a scalar
201 virtual ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
202
203 /// Generic x-only point multiplication
204 ///
205 /// Multiply an arbitrary point by a scalar, returning only the x coordinate
207 const Scalar& scalar,
208 RandomNumberGenerator& rng) const = 0;
209
210 /// Setup a table for 2-ary multiplication where the first point is the generator
211 virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup_g(const AffinePoint& q) const = 0;
212
213 /// Perform 2-ary multiplication (variable time)
214 ///
215 /// Compute p*x + q*y in variable time
216 ///
217 /// Returns nullopt if the produced point is the point at infinity
218 virtual std::optional<ProjectivePoint> mul2_vartime(const PrecomputedMul2Table& table,
219 const Scalar& x,
220 const Scalar& y) const = 0;
221
222 /// Perform 2-ary multiplication (constant time)
223 ///
224 /// Compute p*x + q*y
225 ///
226 /// Returns nullopt if the produced point is the point at infinity
227 virtual std::optional<ProjectivePoint> mul_px_qy(const AffinePoint& p,
228 const Scalar& x,
229 const AffinePoint& q,
230 const Scalar& y,
231 RandomNumberGenerator& rng) const = 0;
232
233 /// Perform 2-ary multiplication (variable time), reducing x modulo order
234 ///
235 /// Compute p*x + q*y in variable time, then extract the x coordinate of
236 /// the result, and reduce x modulo the group order. Compare that value
237 /// with v. If equal, returns true. Otherwise returns false, including if
238 /// the produced point is the point at infinity
240 const Scalar& v,
241 const Scalar& x,
242 const Scalar& y) const = 0;
243
244 /// Return the standard generator
245 virtual AffinePoint generator() const = 0;
246
247 /// Return the identity element (aka the point at infinity)
248 virtual AffinePoint point_identity() const = 0;
249
250 /// Deserialize a point in the SEC1 uncompressed format
251 ///
252 /// The input must be exactly 1 + 2*field_element_bytes long and have a
253 /// header byte of 0x04. All other encodings are rejected, as are inputs
254 /// where (x,y) is not a point on the curve.
255 virtual std::optional<AffinePoint> deserialize_point_uncompressed(std::span<const uint8_t> bytes) const = 0;
256
257 /// Deserialize a point in the SEC1 compressed format
258 ///
259 /// The input must be exactly 1 + field_element_bytes long and have a
260 /// header byte of 0x02 or 0x03. All other encodings are rejected, as are
261 /// inputs where x is not the affine x coordinate of a point on the curve.
262 virtual std::optional<AffinePoint> deserialize_point_compressed(std::span<const uint8_t> bytes) const = 0;
263
264 /// Deserialize a scalar in [1,p)
265 ///
266 /// This function requires the input length be exactly scalar_bytes long;
267 /// it does not accept inputs that are shorter, or with excess leading
268 /// zero padding bytes.
269 ///
270 /// This function also rejects zero as an input, since in normal usage
271 /// scalars are integers in Z_p*
272 virtual std::optional<Scalar> deserialize_scalar(std::span<const uint8_t> bytes) const = 0;
273
274 /// Reduce an integer modulo the group order
275 ///
276 /// The input can be at most twice the bit length of the order; if larger than this
277 /// nullopt is returned
278 virtual std::optional<Scalar> scalar_from_wide_bytes(std::span<const uint8_t> bytes) const = 0;
279
280 virtual AffinePoint point_to_affine(const ProjectivePoint& pt) const = 0;
281
282 virtual bool affine_point_is_identity(const AffinePoint& pt) const = 0;
283
284 virtual AffinePoint point_negate(const AffinePoint& pt) const = 0;
285
286 virtual ProjectivePoint point_add(const AffinePoint& a, const AffinePoint& b) const = 0;
287
288 virtual void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
289
290 virtual void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const = 0;
291
292 /**
293 * Return the scalar one
294 */
295 virtual Scalar scalar_one() const = 0;
296
297 /// Scalar addition
298 virtual Scalar scalar_add(const Scalar& a, const Scalar& b) const = 0;
299
300 /// Scalar subtraction
301 virtual Scalar scalar_sub(const Scalar& a, const Scalar& b) const = 0;
302
303 /// Scalar multiplication
304 virtual Scalar scalar_mul(const Scalar& a, const Scalar& b) const = 0;
305
306 /// Scalar squaring
307 virtual Scalar scalar_square(const Scalar& s) const = 0;
308
309 /// Scalar inversion
310 virtual Scalar scalar_invert(const Scalar& s) const = 0;
311
312 /// Scalar inversion (variable time)
313 virtual Scalar scalar_invert_vartime(const Scalar& s) const = 0;
314
315 /// Scalar negation
316 virtual Scalar scalar_negate(const Scalar& s) const = 0;
317
318 /// Test if scalar is zero
319 virtual bool scalar_is_zero(const Scalar& s) const = 0;
320
321 /// Test if two scalars are equal
322 virtual bool scalar_equal(const Scalar& a, const Scalar& b) const = 0;
323
324 /**
325 * Return a new random scalar
326 */
328
329 /**
330 * Return true if this curve supports RFC 9380 hash to curve
331 *
332 * If this returns false then hash_to_curve_nu and hash_to_curve_ro
333 * will throw Not_Implemented
334 */
335 virtual bool supports_hash_to_curve() const = 0;
336
337 /**
338 * RFC 9380 hash to curve (NU variant)
339 *
340 * This is currently only supported for a few specific curves
341 *
342 * @param expand_message is a callback which must fill the provided output
343 * span with a sequence of uniform bytes, or if this is not possible due to
344 * length limitations or some other issue, throw an exception. It is
345 * invoked to produce the `uniform_bytes` value; see RFC 9380 section 5.2
346 */
347 virtual AffinePoint hash_to_curve_nu(std::function<void(std::span<uint8_t>)> expand_message) const = 0;
348
349 /**
350 * RFC 9380 hash to curve (RO variant)
351 *
352 * This is currently only supported for a few specific curves
353 *
354 * @param expand_message is a callback which must fill the provided output
355 * span with a sequence of uniform bytes, or if this is not possible due to
356 * length limitations or some other issue, throw an exception. It is
357 * invoked to produce the `uniform_bytes` value; see RFC 9380 section 5.2
358 */
359 virtual ProjectivePoint hash_to_curve_ro(std::function<void(std::span<uint8_t>)> expand_message) const = 0;
360};
361
362} // namespace Botan::PCurve
363
364#endif
AffinePoint & operator=(const AffinePoint &other)=default
static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y)
Definition pcurves.h:116
AffinePoint(AffinePoint &&other)=default
AffinePoint & operator=(AffinePoint &&other)=default
static AffinePoint generator(const CurvePtr &curve)
Definition pcurves.h:108
AffinePoint(const AffinePoint &other)=default
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:154
Scalar(const Scalar &other)=default
Scalar & operator=(Scalar &&other)=default
Scalar & operator=(const Scalar &other)=default
static Scalar _create(CurvePtr curve, StorageUnit v)
Definition pcurves.h:82
virtual ~PrimeOrderCurve()=default
virtual Scalar scalar_add(const Scalar &a, const Scalar &b) const =0
Scalar addition.
virtual AffinePoint point_negate(const AffinePoint &pt) const =0
virtual void serialize_point(std::span< uint8_t > bytes, const AffinePoint &pt) 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 ProjectivePoint hash_to_curve_ro(std::function< void(std::span< uint8_t >)> expand_message) const =0
virtual bool supports_hash_to_curve() const =0
virtual size_t field_element_bytes() const =0
static constexpr size_t StorageWords
Number of words used to store MaximumByteLength.
Definition pcurves.h:42
virtual size_t order_bits() const =0
Return the bit length of the group order.
std::shared_ptr< const PrimeOrderCurve > CurvePtr
Definition pcurves.h:60
virtual AffinePoint point_identity() const =0
Return the identity element (aka the point at infinity).
virtual size_t scalar_bytes() const =0
Return the byte length of the scalar element.
virtual ProjectivePoint point_add(const AffinePoint &a, const AffinePoint &b) const =0
std::array< word, StorageWords > StorageUnit
Definition pcurves.h:59
virtual bool scalar_is_zero(const Scalar &s) const =0
Test if scalar is zero.
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
Scalar inversion.
virtual Scalar scalar_mul(const Scalar &a, const Scalar &b) const =0
Scalar multiplication.
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 std::optional< AffinePoint > deserialize_point_compressed(std::span< const uint8_t > bytes) 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
Scalar negation.
static constexpr size_t MaximumByteLength
Definition pcurves.h:39
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 std::optional< AffinePoint > deserialize_point_uncompressed(std::span< const uint8_t > bytes) const =0
virtual ProjectivePoint mul(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const =0
virtual Scalar scalar_invert_vartime(const Scalar &s) const =0
Scalar inversion (variable time).
virtual Scalar scalar_square(const Scalar &s) const =0
Scalar squaring.
virtual bool scalar_equal(const Scalar &a, const Scalar &b) const =0
Test if two scalars are equal.
virtual AffinePoint hash_to_curve_nu(std::function< void(std::span< uint8_t >)> expand_message) 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
static constexpr size_t MaximumBitLength
Definition pcurves.h:37
virtual bool affine_point_is_identity(const AffinePoint &pt) const =0
static std::shared_ptr< const PrimeOrderCurve > from_params(const BigInt &p, const BigInt &a, const BigInt &b, const BigInt &base_x, const BigInt &base_y, const BigInt &order)
Definition pcurves.cpp:21
static std::shared_ptr< const PrimeOrderCurve > for_named_curve(std::string_view name)
Definition pcurves.cpp:32
virtual Scalar base_point_mul_x_mod_order(const Scalar &scalar, RandomNumberGenerator &rng) 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
Scalar subtraction.
const char * name
Definition ffi_tls.h:59
constexpr void poison_all(const Ts &... ts)
Definition ct_utils.h:201
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131