Botan 3.9.0
Crypto and TLS for C&
ec_point.h
Go to the documentation of this file.
1/*
2* Point arithmetic on elliptic curves over GF(p)
3*
4* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5* 2008-2011,2014,2015,2024 Jack Lloyd
6*
7* Botan is released under the Simplified BSD License (see license.txt)
8*/
9
10#ifndef BOTAN_EC_POINT_H_
11#define BOTAN_EC_POINT_H_
12
13// TODO(Botan4) delete this header
14
15#include <botan/curve_gfp.h>
16#include <botan/ec_point_format.h>
17#include <botan/exceptn.h>
18#include <vector>
19
20namespace Botan {
21
22/**
23* Deprecated elliptic curve type
24*
25* Use EC_AffinePoint in new code; this type is no longer used internally at all
26* except to support very unfortunate (and deprecated) curve types, specifically
27* those with a cofactor, or with unreasonable sizes (above 521 bits), which
28* cannot be accomodated by the new faster EC library in math/pcurves. For
29* normal curves EC_AffinePoint will typically be 2 or 3 times faster.
30*
31* This type will be completely removed in Botan4
32*/
33class BOTAN_PUBLIC_API(2, 0) EC_Point final {
34 public:
38
40 using enum EC_Point_Format;
41
42 enum : uint8_t { WORKSPACE_SIZE = 8 };
43
44 /**
45 * Construct an uninitialized EC_Point
46 */
47 EC_Point() = default;
48
49 /**
50 * Construct the zero point
51 * @param curve The base curve
52 */
53 BOTAN_DEPRECATED("Deprecated no replacement") explicit EC_Point(const CurveGFp& curve);
54
55 /**
56 * Copy constructor
57 */
58 EC_Point(const EC_Point&) = default;
59
60 /**
61 * Move Constructor
62 */
63 EC_Point(EC_Point&& other) noexcept { this->swap(other); }
64
65 /**
66 * Standard Assignment
67 */
68 EC_Point& operator=(const EC_Point&) = default;
69
70 /**
71 * Move Assignment
72 */
73 EC_Point& operator=(EC_Point&& other) noexcept {
74 if(this != &other) {
75 this->swap(other);
76 }
77 return (*this);
78 }
79
80 ~EC_Point() = default;
81
82 /**
83 * Point multiplication operator
84 *
85 * Simple unblinded Montgomery ladder
86 *
87 * Warning: prefer the functions on EC_Group such as
88 * blinded_var_point_multiply
89 *
90 * @param scalar the scalar value
91 * @return *this multiplied by the scalar value
92 */
93 EC_Point mul(const BigInt& scalar) const;
94
95 /**
96 * Construct a point from its affine coordinates
97 * @param curve the base curve
98 * @param x affine x coordinate
99 * @param y affine y coordinate
100 */
101 BOTAN_DEPRECATED("Use EC_AffinePoint::from_bigint_xy") EC_Point(const CurveGFp& curve, BigInt x, BigInt y);
102
103 /**
104 * EC2OSP - elliptic curve to octet string primitive
105 * @param format which format to encode using
106 */
107 std::vector<uint8_t> encode(EC_Point_Format format) const;
108
109 /**
110 * += Operator
111 * @param rhs the EC_Point to add to the local value
112 * @result resulting EC_Point
113 */
114 EC_Point& operator+=(const EC_Point& rhs);
115
116 /**
117 * -= Operator
118 * @param rhs the EC_Point to subtract from the local value
119 * @result resulting EC_Point
120 */
121 EC_Point& operator-=(const EC_Point& rhs);
122
123 /**
124 * *= Operator
125 * @param scalar the EC_Point to multiply with *this
126 * @result resulting EC_Point
127 */
128 EC_Point& operator*=(const BigInt& scalar);
129
130 /**
131 * Negate this point
132 * @return *this
133 */
135 if(!is_zero()) {
136 m_y = m_curve.get_p() - m_y;
137 }
138 return *this;
139 }
140
141 /**
142 * Force this point to affine coordinates
143 *
144 * Convert the point to its equivalent affine coordinates. Throws if this
145 * is the point at infinity.
146 */
147 void force_affine();
148
149 /**
150 * Force all points on the list to affine coordinates
151 *
152 * Force several points to be affine at once. Uses Montgomery's trick to
153 * reduce number of inversions required, so this is much faster than
154 * calling ``force_affine`` on each point in sequence.
155 */
156 static void force_all_affine(std::span<EC_Point> points, secure_vector<word>& ws);
157
158 bool is_affine() const;
159
160 /**
161 * Is this the point at infinity?
162 * @result true, if this point is at infinity, false otherwise.
163 */
164 bool is_zero() const { return m_z.is_zero(); }
165
166 /**
167 * Checks whether the point is to be found on the underlying
168 * curve; used to prevent fault attacks.
169 * @return if the point is on the curve
170 */
171 bool on_the_curve() const;
172
173 /**
174 * Return the fixed length big endian encoding of x coordinate
175 */
176 secure_vector<uint8_t> x_bytes() const;
177
178 /**
179 * Return the fixed length big endian encoding of y coordinate
180 */
181 secure_vector<uint8_t> y_bytes() const;
182
183 /**
184 * Return the fixed length concatenation of the x and y coordinates
185 */
186 secure_vector<uint8_t> xy_bytes() const;
187
188 /**
189 * get affine x coordinate
190 * @result affine x coordinate
191 */
192 BigInt get_affine_x() const;
193
194 /**
195 * get affine y coordinate
196 * @result affine y coordinate
197 */
198 BigInt get_affine_y() const;
199
200 /**
201 * Return the zero (aka infinite) point associated with this curve
202 */
203 EC_Point zero() const;
204
205 /**
206 * Randomize the point representation
207 * The actual value (get_affine_x, get_affine_y) does not change
208 */
209 void randomize_repr(RandomNumberGenerator& rng);
210
211 /**
212 * Equality operator
213 */
214 bool operator==(const EC_Point& other) const;
215
216 bool operator!=(const EC_Point& other) const = default;
217
218 /**
219 * swaps the states of *this and other
220 * @param other the object to swap values with
221 */
222 void swap(EC_Point& other) noexcept;
223
224 /**
225 * For internal use only
226 */
227 bool _is_x_eq_to_v_mod_order(const BigInt& v) const;
228
229#if defined(BOTAN_DISABLE_DEPRECATED_FEATURES)
230
231 private:
232#endif
233
234 /**
235 * Return the internal x coordinate
236 *
237 * Note this may be in Montgomery form
238 */
239 BOTAN_DEPRECATED("Use affine coordinates only") const BigInt& get_x() const { return m_x; }
240
241 /**
242 * Return the internal y coordinate
243 *
244 * Note this may be in Montgomery form
245 */
246 BOTAN_DEPRECATED("Use affine coordinates only") const BigInt& get_y() const { return m_y; }
247
248 /**
249 * Return the internal z coordinate
250 *
251 * Note this may be in Montgomery form
252 */
253 BOTAN_DEPRECATED("Use affine coordinates only") const BigInt& get_z() const { return m_z; }
254
255 BOTAN_DEPRECATED("Deprecated no replacement")
256
257 void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) {
258 m_x.swap(new_x);
259 m_y.swap(new_y);
260 m_z.swap(new_z);
261 }
262
263 friend void swap(EC_Point& x, EC_Point& y) noexcept { x.swap(y); }
264
265 /**
266 * Randomize the point representation
267 * The actual value (get_affine_x, get_affine_y) does not change
268 */
269 void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws);
270
271 /**
272 * Point addition
273 * @param other the point to add to *this
274 * @param workspace temp space, at least WORKSPACE_SIZE elements
275 */
276 void add(const EC_Point& other, std::vector<BigInt>& workspace);
277
278 /**
279 * Point addition. Array version.
280 *
281 * @param x_words the words of the x coordinate of the other point
282 * @param x_size size of x_words
283 * @param y_words the words of the y coordinate of the other point
284 * @param y_size size of y_words
285 * @param z_words the words of the z coordinate of the other point
286 * @param z_size size of z_words
287 * @param workspace temp space, at least WORKSPACE_SIZE elements
288 */
289 void add(const word x_words[],
290 size_t x_size,
291 const word y_words[],
292 size_t y_size,
293 const word z_words[],
294 size_t z_size,
295 std::vector<BigInt>& workspace);
296
297 /**
298 * Point addition - mixed J+A
299 *
300 * @warning This function assumes that @p other is affine, if this is not
301 * correct the result will be invalid.
302 *
303 * @param other affine point to add - assumed to be affine!
304 * @param workspace temp space, at least WORKSPACE_SIZE elements
305 */
306 void add_affine(const EC_Point& other, std::vector<BigInt>& workspace);
307
308 /**
309 * Point addition - mixed J+A. Array version.
310 *
311 * @param x_words the words of the x coordinate of the other point
312 * @param x_size size of x_words
313 * @param y_words the words of the y coordinate of the other point
314 * @param y_size size of y_words
315 * @param workspace temp space, at least WORKSPACE_SIZE elements
316 */
317 void add_affine(
318 const word x_words[], size_t x_size, const word y_words[], size_t y_size, std::vector<BigInt>& workspace);
319
320 /**
321 * Point doubling
322 * @param workspace temp space, at least WORKSPACE_SIZE elements
323 */
324 void mult2(std::vector<BigInt>& workspace);
325
326 /**
327 * Repeated point doubling
328 * @param i number of doublings to perform
329 * @param workspace temp space, at least WORKSPACE_SIZE elements
330 */
331 void mult2i(size_t i, std::vector<BigInt>& workspace);
332
333 /**
334 * Point addition
335 * @param other the point to add to *this
336 * @param workspace temp space, at least WORKSPACE_SIZE elements
337 * @return other plus *this
338 */
339 EC_Point plus(const EC_Point& other, std::vector<BigInt>& workspace) const {
340 EC_Point x = (*this);
341 x.add(other, workspace);
342 return x;
343 }
344
345 /**
346 * Point doubling
347 * @param workspace temp space, at least WORKSPACE_SIZE elements
348 * @return *this doubled
349 */
350 EC_Point double_of(std::vector<BigInt>& workspace) const {
351 EC_Point x = (*this);
352 x.mult2(workspace);
353 return x;
354 }
355
356 /**
357 * Return base curve of this point
358 * @result the curve over GF(p) of this point
359 *
360 * You should not need to use this
361 */
362 BOTAN_DEPRECATED("Deprecated no replacement") const CurveGFp& get_curve() const { return m_curve; }
363
364 private:
365 CurveGFp m_curve;
366 BigInt m_x, m_y, m_z;
367};
368
369/**
370* ECC point multiexponentiation - not constant time!
371* @param p1 a point
372* @param z1 a scalar
373* @param p2 a point
374* @param z2 a scalar
375* @result (p1 * z1 + p2 * z2)
376*/
377BOTAN_DEPRECATED("Use EC_AffinePoint::mul_px_qy")
378EC_Point BOTAN_PUBLIC_API(2, 0)
379 multi_exponentiate(const EC_Point& p1, const BigInt& z1, const EC_Point& p2, const BigInt& z2);
380
381// arithmetic operators
382inline EC_Point operator-(const EC_Point& lhs) {
383 return EC_Point(lhs).negate();
384}
385
386inline EC_Point operator+(const EC_Point& lhs, const EC_Point& rhs) {
387 EC_Point tmp(lhs);
388 return tmp += rhs;
389}
390
391inline EC_Point operator-(const EC_Point& lhs, const EC_Point& rhs) {
392 EC_Point tmp(lhs);
393 return tmp -= rhs;
394}
395
396inline EC_Point operator*(const EC_Point& point, const BigInt& scalar) {
397 return point.mul(scalar);
398}
399
400inline EC_Point operator*(const BigInt& scalar, const EC_Point& point) {
401 return point.mul(scalar);
402}
403
404/**
405* Perform point decoding
406* Use EC_Group::OS2ECP instead
407*/
408BOTAN_DEPRECATED("Use EC_AffinePoint::deserialize")
409EC_Point BOTAN_PUBLIC_API(2, 0) OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp& curve);
410
411/**
412* Perform point decoding
413*
414* This is an internal function which was accidentally made public.
415* Do not use it; it will be removed in Botan4.
416*
417* @param data the encoded point
418* @param data_len length of data in bytes
419* @param curve_p the curve equation prime
420* @param curve_a the curve equation a parameter
421* @param curve_b the curve equation b parameter
422*/
423BOTAN_DEPRECATED("Use EC_AffinePoint::deserialize")
424std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API
425 OS2ECP(const uint8_t data[], size_t data_len, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b);
426
427BOTAN_DEPRECATED("Use EC_AffinePoint::deserialize")
428EC_Point BOTAN_UNSTABLE_API OS2ECP(std::span<const uint8_t> data, const CurveGFp& curve);
429
430// The name used for this type in older versions
432
433} // namespace Botan
434
435#endif
#define BOTAN_PUBLIC_API(maj, min)
Definition api.h:21
#define BOTAN_UNSTABLE_API
Definition api.h:34
#define BOTAN_DEPRECATED(msg)
Definition api.h:73
~EC_Point()=default
EC_Point & negate()
Definition ec_point.h:134
void swap(EC_Point &other) noexcept
Definition ec_point.cpp:781
bool operator!=(const EC_Point &other) const =default
EC_Point plus(const EC_Point &other, std::vector< BigInt > &workspace) const
Definition ec_point.h:339
void add(const EC_Point &other, std::vector< BigInt > &workspace)
Definition ec_point.cpp:266
void mult2(std::vector< BigInt > &workspace)
Definition ec_point.cpp:388
EC_Point double_of(std::vector< BigInt > &workspace) const
Definition ec_point.h:350
const BigInt & get_y() const
Definition ec_point.h:246
bool is_zero() const
Definition ec_point.h:164
friend class EC_Point_Var_Point_Precompute
Definition ec_point.h:35
const BigInt & get_z() const
Definition ec_point.h:253
void swap_coords(BigInt &new_x, BigInt &new_y, BigInt &new_z)
Definition ec_point.h:257
EC_Point & operator=(EC_Point &&other) noexcept
Definition ec_point.h:73
friend class EC_Point_Base_Point_Precompute
Definition ec_point.h:37
friend class EC_Point_Multi_Point_Precompute
Definition ec_point.h:36
EC_Point mul(const BigInt &scalar) const
Definition ec_point.cpp:497
friend void swap(EC_Point &x, EC_Point &y) noexcept
Definition ec_point.h:263
const CurveGFp & get_curve() const
Definition ec_point.h:362
EC_Point & operator=(const EC_Point &)=default
const BigInt & get_x() const
Definition ec_point.h:239
EC_Point()=default
EC_Point_Format Compression_Type
Definition ec_point.h:39
std::vector< uint8_t > encode(EC_Point_Format format) const
Definition ec_point.cpp:802
bool _is_x_eq_to_v_mod_order(const BigInt &v) const
Definition ec_point.cpp:714
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:56
EC_Point PointGFp
Definition ec_point.h:431
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
EC_Point multi_exponentiate(const EC_Point &p1, const BigInt &z1, const EC_Point &p2, const BigInt &z2)
Definition point_mul.cpp:35
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1095
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition alg_id.cpp:53
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
EC_Point OS2ECP(std::span< const uint8_t > data, const CurveGFp &curve)
Definition ec_point.cpp:855