13215274653

Committed 08 Feb 2025 11:38AM UTC coverage: 91.655% (-0.009%) from 91.664%

Build # 13215274653

Build Type

Pull #4650

github

Committed by

web-flow

Commit Message

Merge 107f31833 into bc555cd3c

Pull Request Pull Request #4650: Reorganize code and reduce header dependencies

Run Details

94836 of 103471 relevant lines covered (91.65%)

11230958.94 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.55

/src/lib/math/pcurves/pcurves.h

/*
* (C) 2024 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#ifndef BOTAN_PCURVES_H_
#define BOTAN_PCURVES_H_

#include <botan/internal/pcurves_id.h>

#include <botan/concepts.h>
#include <botan/secmem.h>
#include <botan/types.h>
#include <array>
#include <memory>
#include <optional>
#include <span>
#include <string_view>
#include <vector>

namespace Botan {

class RandomNumberGenerator;

}  // namespace Botan

namespace Botan::PCurve {

/**
* An elliptic curve without cofactor in Weierstrass form
*/
class PrimeOrderCurve {
   public:
      /// Somewhat arbitrary maximum size for a field or scalar
      ///
      /// Sized to fit at least P-521
      static const size_t MaximumBitLength = 521;

      static const size_t MaximumByteLength = (MaximumBitLength + 7) / 8;

      /// Number of words used to store MaximumByteLength
      static const size_t StorageWords = (MaximumByteLength + sizeof(word) - 1) / sizeof(word);

      static std::shared_ptr<const PrimeOrderCurve> from_name(std::string_view name) {
         if(auto id = PrimeOrderCurveId::from_string(name)) {
            return PrimeOrderCurve::from_id(id.value());
         } else {
            return {};
         }
      }

      static std::shared_ptr<const PrimeOrderCurve> from_id(PrimeOrderCurveId id);

      typedef std::array<word, StorageWords> StorageUnit;
      typedef std::shared_ptr<const PrimeOrderCurve> CurvePtr;

      /// Elliptic curve scalar
      ///
      /// This refers to the set of integers modulo the (prime) group order
      /// of the elliptic curve.
      class Scalar final {
         public:
            Scalar(const Scalar& other) = default;
            Scalar(Scalar&& other) = default;
            Scalar& operator=(const Scalar& other) = default;
            Scalar& operator=(Scalar&& other) = default;
            ~Scalar() = default;

            const auto& _curve() const { return m_curve; }

            const auto& _value() const { return m_value; }

            static Scalar _create(CurvePtr curve, StorageUnit v) { return Scalar(std::move(curve), v); }

         private:
            Scalar(CurvePtr curve, StorageUnit v) : m_curve(std::move(curve)), m_value(v) {}

            CurvePtr m_curve;
            StorageUnit m_value;
      };

      /**
      * A point on the elliptic curve in affine form
      *
      * These points can be serialized, or converted to projective form for computation
      */
      class AffinePoint final {
         public:
            AffinePoint(const AffinePoint& other) = default;
            AffinePoint(AffinePoint&& other) = default;
            AffinePoint& operator=(const AffinePoint& other) = default;
            AffinePoint& operator=(AffinePoint&& other) = default;
            ~AffinePoint() = default;

            static AffinePoint generator(CurvePtr curve) { return curve->generator(); }

            const auto& _curve() const { return m_curve; }

            const auto& _x() const { return m_x; }

            const auto& _y() const { return m_y; }

            static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y) {
               return AffinePoint(std::move(curve), x, y);
            }

         private:
            AffinePoint(CurvePtr curve, StorageUnit x, StorageUnit y) : m_curve(std::move(curve)), m_x(x), m_y(y) {}

            CurvePtr m_curve;
            StorageUnit m_x;
            StorageUnit m_y;
      };

      /**
      * A point on the elliptic curve in projective form
      *
      * This is a form that is convenient for computation; it must be converted to
      * affine form for comparisons or serialization.
      */
      class ProjectivePoint final {
         public:
            ProjectivePoint(const ProjectivePoint& other) = default;
            ProjectivePoint(ProjectivePoint&& other) = default;
            ProjectivePoint& operator=(const ProjectivePoint& other) = default;
            ProjectivePoint& operator=(ProjectivePoint&& other) = default;
            ~ProjectivePoint() = default;

            const auto& _curve() const { return m_curve; }

            const auto& _x() const { return m_x; }

            const auto& _y() const { return m_y; }

            const auto& _z() const { return m_z; }

            static ProjectivePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y, StorageUnit z) {
               return ProjectivePoint(std::move(curve), x, y, z);
            }

         private:
            ProjectivePoint(CurvePtr curve, StorageUnit x, StorageUnit y, StorageUnit z) :
                  m_curve(std::move(curve)), m_x(x), m_y(y), m_z(z) {}

            CurvePtr m_curve;
            StorageUnit m_x;
            StorageUnit m_y;
            StorageUnit m_z;
      };

      class PrecomputedMul2Table {
         public:
            virtual ~PrecomputedMul2Table() = default;
      };

      virtual ~PrimeOrderCurve() = default;

      /// Return the bit length of the group order
      virtual size_t order_bits() const = 0;

      /// Return the byte length of the scalar element
      virtual size_t scalar_bytes() const = 0;

      /// Return the byte length of a field element
      ///
      /// Each point consists of two field elements
      virtual size_t field_element_bytes() const = 0;

      /// Base point multiplication
      ///
      /// Multiply by the standard generator point g
      virtual ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;

      /// Base point multiplication, returning only the x coordinate modulo the group order
      ///
      /// Multiply by the standard generator point g, then extract the x
      /// coordinate as an integer, then reduce the x coordinate modulo the
      /// group order
      virtual Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;

      /// Generic point multiplication
      ///
      /// Multiply an arbitrary point by a scalar
      virtual ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const = 0;

      /// Generic x-only point multiplication
      ///
      /// Multiply an arbitrary point by a scalar, returning only the x coordinate
      virtual secure_vector<uint8_t> mul_x_only(const AffinePoint& pt,
                                                const Scalar& scalar,
                                                RandomNumberGenerator& rng) const = 0;

      /// Setup a table for 2-ary multiplication
      virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup(const AffinePoint& p,
                                                                     const AffinePoint& pq) const = 0;

      /// Setup a table for 2-ary multiplication where the first point is the generator
      virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup_g(const AffinePoint& q) const = 0;

      /// Perform 2-ary multiplication (variable time)
      ///
      /// Compute p*x + q*y in variable time
      ///
      /// Returns nullopt if the produced point is the point at infinity
      virtual std::optional<ProjectivePoint> mul2_vartime(const PrecomputedMul2Table& table,
                                                          const Scalar& x,
                                                          const Scalar& y) const = 0;

      /// Perform 2-ary multiplication (constant time)
      ///
      /// Compute p*x + q*y
      ///
      /// Returns nullopt if the produced point is the point at infinity
      virtual std::optional<ProjectivePoint> mul_px_qy(const AffinePoint& p,
                                                       const Scalar& x,
                                                       const AffinePoint& q,
                                                       const Scalar& y,
                                                       RandomNumberGenerator& rng) const = 0;

      /// Perform 2-ary multiplication (variable time), reducing x modulo order
      ///
      /// Compute p*x + q*y in variable time, then extract the x coordinate of
      /// the result, and reduce x modulo the group order. Compare that value
      /// with v. If equal, returns true. Otherwise returns false, including if
      /// the produced point is the point at infinity
      virtual bool mul2_vartime_x_mod_order_eq(const PrecomputedMul2Table& table,
                                               const Scalar& v,
                                               const Scalar& x,
                                               const Scalar& y) const = 0;

      /// Return the standard generator
      virtual AffinePoint generator() const = 0;

      /// Deserialize a point
      ///
      /// Both compressed and uncompressed encodings are accepted
      ///
      /// Note that the deprecated "hybrid" encoding is not supported here
      virtual std::optional<AffinePoint> deserialize_point(std::span<const uint8_t> bytes) const = 0;

      /// Deserialize a scalar in [1,p)
      ///
      /// This function requires the input length be exactly scalar_bytes long;
      /// it does not accept inputs that are shorter, or with excess leading
      /// zero padding bytes.
      ///
      /// This function also rejects zero as an input, since in normal usage
      /// scalars are integers in Z_p*
      virtual std::optional<Scalar> deserialize_scalar(std::span<const uint8_t> bytes) const = 0;

      /// Reduce an integer modulo the group order
      ///
      /// The input can be at most twice the bit length of the order; if larger than this
      /// nullopt is returned
      virtual std::optional<Scalar> scalar_from_wide_bytes(std::span<const uint8_t> bytes) const = 0;

      virtual AffinePoint point_to_affine(const ProjectivePoint& pt) const = 0;

      virtual ProjectivePoint point_to_projective(const AffinePoint& pt) const = 0;

      virtual bool affine_point_is_identity(const AffinePoint& pt) const = 0;

      virtual AffinePoint point_negate(const AffinePoint& pt) const = 0;

      virtual ProjectivePoint point_add(const AffinePoint& a, const AffinePoint& b) const = 0;

      virtual void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;

      virtual void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const = 0;

      /**
      * Return the scalar one
      */
      virtual Scalar scalar_one() const = 0;

      /// Scalar addition
      virtual Scalar scalar_add(const Scalar& a, const Scalar& b) const = 0;

      /// Scalar subtraction
      virtual Scalar scalar_sub(const Scalar& a, const Scalar& b) const = 0;

      /// Scalar multiplication
      virtual Scalar scalar_mul(const Scalar& a, const Scalar& b) const = 0;

      /// Scalar squaring
      virtual Scalar scalar_square(const Scalar& s) const = 0;

      /// Scalar inversion
      virtual Scalar scalar_invert(const Scalar& s) const = 0;

      /// Scalar inversion (variable time)
      virtual Scalar scalar_invert_vartime(const Scalar& s) const = 0;

      /// Scalar negation
      virtual Scalar scalar_negate(const Scalar& s) const = 0;

      /// Test if scalar is zero
      virtual bool scalar_is_zero(const Scalar& s) const = 0;

      /// Test if two scalars are equal
      virtual bool scalar_equal(const Scalar& a, const Scalar& b) const = 0;

      /**
      * Return a new random scalar
      */
      virtual Scalar random_scalar(RandomNumberGenerator& rng) const = 0;

      /**
      * RFC 9380 hash to curve (NU variant)
      *
      * This is currently only supported for a few specific curves
      */
      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;

      /**
      * RFC 9380 hash to curve (RO variant)
      *
      * This is currently only supported for a few specific curves
      */
      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;
};

}  // namespace Botan::PCurve

#endif

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 <memory>
17	#include <optional>
18	#include <span>
19	#include <string_view>
20	#include <vector>
21
22	namespace Botan {
23
24	class RandomNumberGenerator;
25
26	} // namespace Botan
27
28	namespace Botan::PCurve {
29
30	/**
31	* An elliptic curve without cofactor in Weierstrass form
32	*/
33	class PrimeOrderCurve {	492✔
34	public:
35	/// Somewhat arbitrary maximum size for a field or scalar
36	///
37	/// Sized to fit at least P-521
38	static const size_t MaximumBitLength = 521;
39
40	static const size_t MaximumByteLength = (MaximumBitLength + 7) / 8;
41
42	/// Number of words used to store MaximumByteLength
43	static const size_t StorageWords = (MaximumByteLength + sizeof(word) - 1) / sizeof(word);
44
45	static std::shared_ptr<const PrimeOrderCurve> from_name(std::string_view name) {
46	if(auto id = PrimeOrderCurveId::from_string(name)) {
47	return PrimeOrderCurve::from_id(id.value());
48	} else {
49	return {};
50	}
51	}
52
53	static std::shared_ptr<const PrimeOrderCurve> from_id(PrimeOrderCurveId id);
54
55	typedef std::array<word, StorageWords> StorageUnit;
56	typedef std::shared_ptr<const PrimeOrderCurve> CurvePtr;
57
58	/// Elliptic curve scalar
59	///
60	/// This refers to the set of integers modulo the (prime) group order
61	/// of the elliptic curve.
62	class Scalar final {
63	public:
64	Scalar(const Scalar& other) = default;	88,331✔
65	Scalar(Scalar&& other) = default;	266,759✔
66	Scalar& operator=(const Scalar& other) = default;	×
67	Scalar& operator=(Scalar&& other) = default;	3,190✔
68	~Scalar() = default;	318,562✔
69
70	const auto& _curve() const { return m_curve; }	361,126✔
71
72	const auto& _value() const { return m_value; }	361,126✔
73
74	static Scalar _create(CurvePtr curve, StorageUnit v) { return Scalar(std::move(curve), v); }	201,684✔
75
76	private:
77	Scalar(CurvePtr curve, StorageUnit v) : m_curve(std::move(curve)), m_value(v) {}	201,684✔
78
79	CurvePtr m_curve;
80	StorageUnit m_value;
81	};
82
83	/**
84	* A point on the elliptic curve in affine form
85	*
86	* These points can be serialized, or converted to projective form for computation
87	*/
88	class AffinePoint final {
89	public:
90	AffinePoint(const AffinePoint& other) = default;	18,012✔
91	AffinePoint(AffinePoint&& other) = default;	152,160✔
92	AffinePoint& operator=(const AffinePoint& other) = default;
93	AffinePoint& operator=(AffinePoint&& other) = default;
94	~AffinePoint() = default;	170,901✔
95
96	static AffinePoint generator(CurvePtr curve) { return curve->generator(); }
97
98	const auto& _curve() const { return m_curve; }	188,501✔
99
100	const auto& _x() const { return m_x; }	188,500✔
101
102	const auto& _y() const { return m_y; }	188,500✔
103
104	static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y) {	59,935✔
105	return AffinePoint(std::move(curve), x, y);	59,935✔
106	}
107
108	private:
109	AffinePoint(CurvePtr curve, StorageUnit x, StorageUnit y) : m_curve(std::move(curve)), m_x(x), m_y(y) {}	59,935✔
110
111	CurvePtr m_curve;
112	StorageUnit m_x;
113	StorageUnit m_y;
114	};
115
116	/**
117	* A point on the elliptic curve in projective form
118	*
119	* This is a form that is convenient for computation; it must be converted to
120	* affine form for comparisons or serialization.
121	*/
122	class ProjectivePoint final {
123	public:
124	ProjectivePoint(const ProjectivePoint& other) = default;
125	ProjectivePoint(ProjectivePoint&& other) = default;	3,620✔
126	ProjectivePoint& operator=(const ProjectivePoint& other) = default;
127	ProjectivePoint& operator=(ProjectivePoint&& other) = default;
128	~ProjectivePoint() = default;	57,084✔
129
130	const auto& _curve() const { return m_curve; }	26,690✔
131
132	const auto& _x() const { return m_x; }	26,690✔
133
134	const auto& _y() const { return m_y; }	26,690✔
135
136	const auto& _z() const { return m_z; }	26,690✔
137
138	static ProjectivePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y, StorageUnit z) {	26,690✔
139	return ProjectivePoint(std::move(curve), x, y, z);	26,690✔
140	}
141
142	private:
143	ProjectivePoint(CurvePtr curve, StorageUnit x, StorageUnit y, StorageUnit z) :	26,690✔
144	m_curve(std::move(curve)), m_x(x), m_y(y), m_z(z) {}	26,690✔
145
146	CurvePtr m_curve;
147	StorageUnit m_x;
148	StorageUnit m_y;
149	StorageUnit m_z;
150	};
151
152	class PrecomputedMul2Table {	11,167✔
153	public:
154	virtual ~PrecomputedMul2Table() = default;	×
155	};
156
157	virtual ~PrimeOrderCurve() = default;
158
159	/// Return the bit length of the group order
160	virtual size_t order_bits() const = 0;
161
162	/// Return the byte length of the scalar element
163	virtual size_t scalar_bytes() const = 0;
164
165	/// Return the byte length of a field element
166	///
167	/// Each point consists of two field elements
168	virtual size_t field_element_bytes() const = 0;
169
170	/// Base point multiplication
171	///
172	/// Multiply by the standard generator point g
173	virtual ProjectivePoint mul_by_g(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
174
175	/// Base point multiplication, returning only the x coordinate modulo the group order
176	///
177	/// Multiply by the standard generator point g, then extract the x
178	/// coordinate as an integer, then reduce the x coordinate modulo the
179	/// group order
180	virtual Scalar base_point_mul_x_mod_order(const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
181
182	/// Generic point multiplication
183	///
184	/// Multiply an arbitrary point by a scalar
185	virtual ProjectivePoint mul(const AffinePoint& pt, const Scalar& scalar, RandomNumberGenerator& rng) const = 0;
186
187	/// Generic x-only point multiplication
188	///
189	/// Multiply an arbitrary point by a scalar, returning only the x coordinate
190	virtual secure_vector<uint8_t> mul_x_only(const AffinePoint& pt,
191	const Scalar& scalar,
192	RandomNumberGenerator& rng) const = 0;
193
194	/// Setup a table for 2-ary multiplication
195	virtual std::unique_ptr<const PrecomputedMul2Table> mul2_setup(const AffinePoint& p,
196	const AffinePoint& pq) 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 px + qy 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 px + qy
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 px + qy 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
227	virtual bool mul2_vartime_x_mod_order_eq(const PrecomputedMul2Table& table,
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 ProjectivePoint point_to_projective(const AffinePoint& pt) const = 0;
261
262	virtual bool affine_point_is_identity(const AffinePoint& pt) const = 0;
263
264	virtual AffinePoint point_negate(const AffinePoint& pt) const = 0;
265
266	virtual ProjectivePoint point_add(const AffinePoint& a, const AffinePoint& b) const = 0;
267
268	virtual void serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const = 0;
269
270	virtual void serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const = 0;
271
272	/**
273	* Return the scalar one
274	*/
275	virtual Scalar scalar_one() const = 0;
276
277	/// Scalar addition
278	virtual Scalar scalar_add(const Scalar& a, const Scalar& b) const = 0;
279
280	/// Scalar subtraction
281	virtual Scalar scalar_sub(const Scalar& a, const Scalar& b) const = 0;
282
283	/// Scalar multiplication
284	virtual Scalar scalar_mul(const Scalar& a, const Scalar& b) const = 0;
285
286	/// Scalar squaring
287	virtual Scalar scalar_square(const Scalar& s) const = 0;
288
289	/// Scalar inversion
290	virtual Scalar scalar_invert(const Scalar& s) const = 0;
291
292	/// Scalar inversion (variable time)
293	virtual Scalar scalar_invert_vartime(const Scalar& s) const = 0;
294
295	/// Scalar negation
296	virtual Scalar scalar_negate(const Scalar& s) const = 0;
297
298	/// Test if scalar is zero
299	virtual bool scalar_is_zero(const Scalar& s) const = 0;
300
301	/// Test if two scalars are equal
302	virtual bool scalar_equal(const Scalar& a, const Scalar& b) const = 0;
303
304	/**
305	* Return a new random scalar
306	*/
307	virtual Scalar random_scalar(RandomNumberGenerator& rng) const = 0;
308
309	/**
310	* RFC 9380 hash to curve (NU variant)
311	*
312	* This is currently only supported for a few specific curves
313	*/
314	virtual AffinePoint hash_to_curve_nu(std::string_view hash,
315	std::span<const uint8_t> input,
316	std::span<const uint8_t> domain_sep) const = 0;
317
318	/**
319	* RFC 9380 hash to curve (RO variant)
320	*
321	* This is currently only supported for a few specific curves
322	*/
323	virtual ProjectivePoint hash_to_curve_ro(std::string_view hash,
324	std::span<const uint8_t> input,
325	std::span<const uint8_t> domain_sep) const = 0;
326	};
327
328	} // namespace Botan::PCurve
329
330	#endif

randombit / botan / 13215274653

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous