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