Botan 3.8.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/concepts.h>
11#include <botan/secmem.h>
12#include <botan/types.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*/
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 ~Scalar() = default;
73
74 const auto& _curve() const { return m_curve; }
75
76 const auto& _value() const { return m_value; }
77
78 static Scalar _create(CurvePtr curve, StorageUnit v) { return Scalar(std::move(curve), v); }
79
80 private:
81 Scalar(CurvePtr curve, StorageUnit v) : m_curve(std::move(curve)), m_value(v) {}
82
83 CurvePtr m_curve;
84 StorageUnit m_value;
85 };
86
87 /**
88 * A point on the elliptic curve in affine form
89 *
90 * These points can be serialized, or converted to projective form for computation
91 */
92 class AffinePoint final {
93 public:
94 AffinePoint(const AffinePoint& other) = default;
95 AffinePoint(AffinePoint&& other) = default;
96 AffinePoint& operator=(const AffinePoint& other) = default;
97 AffinePoint& operator=(AffinePoint&& other) = default;
98 ~AffinePoint() = default;
99
100 static AffinePoint generator(CurvePtr curve) { return curve->generator(); }
101
102 const auto& _curve() const { return m_curve; }
103
104 const auto& _x() const { return m_x; }
105
106 const auto& _y() const { return m_y; }
107
109 return AffinePoint(std::move(curve), x, y);
110 }
111
112 private:
113 AffinePoint(CurvePtr curve, StorageUnit x, StorageUnit y) : m_curve(std::move(curve)), m_x(x), m_y(y) {}
114
115 CurvePtr m_curve;
116 StorageUnit m_x;
117 StorageUnit m_y;
118 };
119
120 /**
121 * A point on the elliptic curve in projective form
122 *
123 * This is a form that is convenient for computation; it must be converted to
124 * affine form for comparisons or serialization.
125 */
126 class ProjectivePoint final {
127 public:
128 ProjectivePoint(const ProjectivePoint& other) = default;
130 ProjectivePoint& operator=(const ProjectivePoint& other) = default;
132 ~ProjectivePoint() = default;
133
134 const auto& _curve() const { return m_curve; }
135
136 const auto& _x() const { return m_x; }
137
138 const auto& _y() const { return m_y; }
139
140 const auto& _z() const { return m_z; }
141
143 return ProjectivePoint(std::move(curve), x, y, z);
144 }
145
146 private:
148 m_curve(std::move(curve)), m_x(x), m_y(y), m_z(z) {}
149
150 CurvePtr m_curve;
151 StorageUnit m_x;
152 StorageUnit m_y;
153 StorageUnit m_z;
154 };
155
157 public:
158 virtual ~PrecomputedMul2Table() = default;
159 };
160
161 virtual ~PrimeOrderCurve() = default;
162
163 /// Return the bit length of the group order
164 virtual size_t order_bits() const = 0;
165
166 /// Return the byte length of the scalar element
167 virtual size_t scalar_bytes() const = 0;
168
169 /// Return the byte length of a field element
170 ///
171 /// Each point consists of two field elements
172 virtual size_t field_element_bytes() const = 0;
173
174 /// Base point multiplication
175 ///
176 /// Multiply by the standard generator point g
177 virtual ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
178
179 /// Base point multiplication, returning only the x coordinate modulo the group order
180 ///
181 /// Multiply by the standard generator point g, then extract the x
182 /// coordinate as an integer, then reduce the x coordinate modulo the
183 /// group order
184 virtual Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
185
186 /// Generic point multiplication
187 ///
188 /// Multiply an arbitrary point by a scalar
189 virtual ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
190
191 /// Generic x-only point multiplication
192 ///
193 /// Multiply an arbitrary point by a scalar, returning only the x coordinate
195 const Scalar& scalar,
196 RandomNumberGenerator& rng) const = 0;
197
198 /// Setup a table for 2-ary multiplication where the first point is the generator
199 virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup_g(const AffinePoint& q) const = 0;
200
201 /// Perform 2-ary multiplication (variable time)
202 ///
203 /// Compute p*x + q*y in variable time
204 ///
205 /// Returns nullopt if the produced point is the point at infinity
206 virtual std::optional<ProjectivePoint> mul2_vartime(const PrecomputedMul2Table& table,
207 const Scalar& x,
208 const Scalar& y) const = 0;
209
210 /// Perform 2-ary multiplication (constant time)
211 ///
212 /// Compute p*x + q*y
213 ///
214 /// Returns nullopt if the produced point is the point at infinity
215 virtual std::optional<ProjectivePoint> mul_px_qy(const AffinePoint& p,
216 const Scalar& x,
217 const AffinePoint& q,
218 const Scalar& y,
219 RandomNumberGenerator& rng) const = 0;
220
221 /// Perform 2-ary multiplication (variable time), reducing x modulo order
222 ///
223 /// Compute p*x + q*y in variable time, then extract the x coordinate of
224 /// the result, and reduce x modulo the group order. Compare that value
225 /// with v. If equal, returns true. Otherwise returns false, including if
226 /// the produced point is the point at infinity
228 const Scalar& v,
229 const Scalar& x,
230 const Scalar& y) const = 0;
231
232 /// Return the standard generator
233 virtual AffinePoint generator() const = 0;
234
235 /// Deserialize a point
236 ///
237 /// Both compressed and uncompressed encodings are accepted
238 ///
239 /// Note that the deprecated "hybrid" encoding is not supported here
240 virtual std::optional<AffinePoint> deserialize_point(std::span<const uint8_t> bytes) const = 0;
241
242 /// Deserialize a scalar in [1,p)
243 ///
244 /// This function requires the input length be exactly scalar_bytes long;
245 /// it does not accept inputs that are shorter, or with excess leading
246 /// zero padding bytes.
247 ///
248 /// This function also rejects zero as an input, since in normal usage
249 /// scalars are integers in Z_p*
250 virtual std::optional<Scalar> deserialize_scalar(std::span<const uint8_t> bytes) const = 0;
251
252 /// Reduce an integer modulo the group order
253 ///
254 /// The input can be at most twice the bit length of the order; if larger than this
255 /// nullopt is returned
256 virtual std::optional<Scalar> scalar_from_wide_bytes(std::span<const uint8_t> bytes) const = 0;
257
258 virtual AffinePoint point_to_affine(const ProjectivePoint& pt) const = 0;
259
260 virtual bool affine_point_is_identity(const AffinePoint& pt) const = 0;
261
262 virtual AffinePoint point_negate(const AffinePoint& pt) const = 0;
263
264 virtual ProjectivePoint point_add(const AffinePoint& a, const AffinePoint& b) const = 0;
265
266 virtual void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
267
268 virtual void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const = 0;
269
270 /**
271 * Return the scalar one
272 */
273 virtual Scalar scalar_one() const = 0;
274
275 /// Scalar addition
276 virtual Scalar scalar_add(const Scalar& a, const Scalar& b) const = 0;
277
278 /// Scalar subtraction
279 virtual Scalar scalar_sub(const Scalar& a, const Scalar& b) const = 0;
280
281 /// Scalar multiplication
282 virtual Scalar scalar_mul(const Scalar& a, const Scalar& b) const = 0;
283
284 /// Scalar squaring
285 virtual Scalar scalar_square(const Scalar& s) const = 0;
286
287 /// Scalar inversion
288 virtual Scalar scalar_invert(const Scalar& s) const = 0;
289
290 /// Scalar inversion (variable time)
291 virtual Scalar scalar_invert_vartime(const Scalar& s) const = 0;
292
293 /// Scalar negation
294 virtual Scalar scalar_negate(const Scalar& s) const = 0;
295
296 /// Test if scalar is zero
297 virtual bool scalar_is_zero(const Scalar& s) const = 0;
298
299 /// Test if two scalars are equal
300 virtual bool scalar_equal(const Scalar& a, const Scalar& b) const = 0;
301
302 /**
303 * Return a new random scalar
304 */
306
307 /**
308 * RFC 9380 hash to curve (NU variant)
309 *
310 * This is currently only supported for a few specific curves
311 *
312 * @param expand_message is a callback which must fill the provided output
313 * span with a sequence of uniform bytes, or if this is not possible due to
314 * length limitations or some other issue, throw an exception. It is
315 * invoked to produce the `uniform_bytes` value; see RFC 9380 section 5.2
316 */
317 virtual AffinePoint hash_to_curve_nu(std::function<void(std::span<uint8_t>)> expand_message) const = 0;
318
319 /**
320 * RFC 9380 hash to curve (RO variant)
321 *
322 * This is currently only supported for a few specific curves
323 *
324 * @param expand_message is a callback which must fill the provided output
325 * span with a sequence of uniform bytes, or if this is not possible due to
326 * length limitations or some other issue, throw an exception. It is
327 * invoked to produce the `uniform_bytes` value; see RFC 9380 section 5.2
328 */
329 virtual ProjectivePoint hash_to_curve_ro(std::function<void(std::span<uint8_t>)> expand_message) const = 0;
330};
331
332} // namespace Botan::PCurve
333
334#endif
AffinePoint & operator=(const AffinePoint &other)=default
static AffinePoint generator(CurvePtr curve)
Definition pcurves.h:100
static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y)
Definition pcurves.h:108
AffinePoint(AffinePoint &&other)=default
AffinePoint & operator=(AffinePoint &&other)=default
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:142
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:78
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: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 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 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 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: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.
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119