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