Botan 3.0.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 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#include <botan/curve_gfp.h>
14#include <botan/exceptn.h>
15#include <vector>
16
17namespace Botan {
18
19enum class EC_Point_Format {
20 Uncompressed = 0,
21 Compressed = 1,
22 Hybrid = 2,
23
24 UNCOMPRESSED BOTAN_DEPRECATED("Use EC_Point_Format::Uncompressed") = Uncompressed,
25 COMPRESSED BOTAN_DEPRECATED("Use EC_Point_Format::Compressed") = Compressed,
26 HYBRID BOTAN_DEPRECATED("Use EC_Point_Format::Hybrid") = Hybrid,
27};
28
29/**
30* This class represents one point on a curve of GF(p)
31*/
33 {
34 public:
36 using enum EC_Point_Format;
37
38 enum { WORKSPACE_SIZE = 8 };
39
40 /**
41 * Construct an uninitialized EC_Point
42 */
43 EC_Point() = default;
44
45 /**
46 * Construct the zero point
47 * @param curve The base curve
48 */
49 explicit EC_Point(const CurveGFp& curve);
50
51 /**
52 * Copy constructor
53 */
54 EC_Point(const EC_Point&) = default;
55
56 /**
57 * Move Constructor
58 */
60 {
61 this->swap(other);
62 }
63
64 /**
65 * Standard Assignment
66 */
67 EC_Point& operator=(const EC_Point&) = default;
68
69 /**
70 * Move Assignment
71 */
73 {
74 if(this != &other)
75 this->swap(other);
76 return (*this);
77 }
78
79 /**
80 * Construct a point from its affine coordinates
81 * Prefer EC_Group::point(x,y) for this operation.
82 * @param curve the base curve
83 * @param x affine x coordinate
84 * @param y affine y coordinate
85 */
86 EC_Point(const CurveGFp& curve, const BigInt& x, const BigInt& y);
87
88 /**
89 * EC2OSP - elliptic curve to octet string primitive
90 * @param format which format to encode using
91 */
92 std::vector<uint8_t> encode(EC_Point_Format format) const;
93
94 /**
95 * += Operator
96 * @param rhs the EC_Point to add to the local value
97 * @result resulting EC_Point
98 */
99 EC_Point& operator+=(const EC_Point& rhs);
100
101 /**
102 * -= Operator
103 * @param rhs the EC_Point to subtract from the local value
104 * @result resulting EC_Point
105 */
106 EC_Point& operator-=(const EC_Point& rhs);
107
108 /**
109 * *= Operator
110 * @param scalar the EC_Point to multiply with *this
111 * @result resulting EC_Point
112 */
113 EC_Point& operator*=(const BigInt& scalar);
114
115 /**
116 * Negate this point
117 * @return *this
118 */
120 {
121 if(!is_zero())
122 m_coord_y = m_curve.get_p() - m_coord_y;
123 return *this;
124 }
125
126 /**
127 * get affine x coordinate
128 * @result affine x coordinate
129 */
130 BigInt get_affine_x() const;
131
132 /**
133 * get affine y coordinate
134 * @result affine y coordinate
135 */
136 BigInt get_affine_y() const;
137
138 /**
139 * Return the internal x coordinate
140 *
141 * Note this may be in Montgomery form
142 */
143 const BigInt& get_x() const { return m_coord_x; }
144
145 /**
146 * Return the internal y coordinate
147 *
148 * Note this may be in Montgomery form
149 */
150 const BigInt& get_y() const { return m_coord_y; }
151
152 /**
153 * Return the internal z coordinate
154 *
155 * Note this may be in Montgomery form
156 */
157 const BigInt& get_z() const { return m_coord_z; }
158
159 void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
160 {
161 m_coord_x.swap(new_x);
162 m_coord_y.swap(new_y);
163 m_coord_z.swap(new_z);
164 }
165
166 /**
167 * Force this point to affine coordinates
168 */
169 void force_affine();
170
171 /**
172 * Force all points on the list to affine coordinates
173 */
174 static void force_all_affine(std::vector<EC_Point>& points,
176
177 bool is_affine() const;
178
179 /**
180 * Is this the point at infinity?
181 * @result true, if this point is at infinity, false otherwise.
182 */
183 bool is_zero() const { return m_coord_z.is_zero(); }
184
185 /**
186 * Checks whether the point is to be found on the underlying
187 * curve; used to prevent fault attacks.
188 * @return if the point is on the curve
189 */
190 bool on_the_curve() const;
191
192 /**
193 * swaps the states of *this and other, does not throw!
194 * @param other the object to swap values with
195 */
196 void swap(EC_Point& other);
197
198 /**
199 * Randomize the point representation
200 * The actual value (get_affine_x, get_affine_y) does not change
201 */
202 void randomize_repr(RandomNumberGenerator& rng);
203
204 /**
205 * Randomize the point representation
206 * The actual value (get_affine_x, get_affine_y) does not change
207 */
208 void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws);
209
210 /**
211 * Equality operator
212 */
213 bool operator==(const EC_Point& other) const;
214
215 /**
216 * Point addition
217 * @param other the point to add to *this
218 * @param workspace temp space, at least WORKSPACE_SIZE elements
219 */
220 void add(const EC_Point& other, std::vector<BigInt>& workspace)
221 {
222 BOTAN_ARG_CHECK(m_curve == other.m_curve, "cannot add points on different curves");
223
224 const size_t p_words = m_curve.get_p_words();
225
226 add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
227 other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
228 other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()),
229 workspace);
230 }
231
232 /**
233 * Point addition. Array version.
234 *
235 * @param x_words the words of the x coordinate of the other point
236 * @param x_size size of x_words
237 * @param y_words the words of the y coordinate of the other point
238 * @param y_size size of y_words
239 * @param z_words the words of the z coordinate of the other point
240 * @param z_size size of z_words
241 * @param workspace temp space, at least WORKSPACE_SIZE elements
242 */
243 void add(const word x_words[], size_t x_size,
244 const word y_words[], size_t y_size,
245 const word z_words[], size_t z_size,
246 std::vector<BigInt>& workspace);
247
248 /**
249 * Point addition - mixed J+A
250 * @param other affine point to add - assumed to be affine!
251 * @param workspace temp space, at least WORKSPACE_SIZE elements
252 */
253 void add_affine(const EC_Point& other, std::vector<BigInt>& workspace)
254 {
255 BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
257
258 const size_t p_words = m_curve.get_p_words();
259 add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
260 other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
261 workspace);
262 }
263
264 /**
265 * Point addition - mixed J+A. Array version.
266 *
267 * @param x_words the words of the x coordinate of the other point
268 * @param x_size size of x_words
269 * @param y_words the words of the y coordinate of the other point
270 * @param y_size size of y_words
271 * @param workspace temp space, at least WORKSPACE_SIZE elements
272 */
273 void add_affine(const word x_words[], size_t x_size,
274 const word y_words[], size_t y_size,
275 std::vector<BigInt>& workspace);
276
277 /**
278 * Point doubling
279 * @param workspace temp space, at least WORKSPACE_SIZE elements
280 */
281 void mult2(std::vector<BigInt>& workspace);
282
283 /**
284 * Repeated point doubling
285 * @param i number of doublings to perform
286 * @param workspace temp space, at least WORKSPACE_SIZE elements
287 */
288 void mult2i(size_t i, std::vector<BigInt>& workspace);
289
290 /**
291 * Point addition
292 * @param other the point to add to *this
293 * @param workspace temp space, at least WORKSPACE_SIZE elements
294 * @return other plus *this
295 */
296 EC_Point plus(const EC_Point& other, std::vector<BigInt>& workspace) const
297 {
298 EC_Point x = (*this);
299 x.add(other, workspace);
300 return x;
301 }
302
303 /**
304 * Point doubling
305 * @param workspace temp space, at least WORKSPACE_SIZE elements
306 * @return *this doubled
307 */
308 EC_Point double_of(std::vector<BigInt>& workspace) const
309 {
310 EC_Point x = (*this);
311 x.mult2(workspace);
312 return x;
313 }
314
315 /**
316 * Return the zero (aka infinite) point associated with this curve
317 */
318 EC_Point zero() const { return EC_Point(m_curve); }
319
320 /**
321 * Return base curve of this point
322 * @result the curve over GF(p) of this point
323 *
324 * You should not need to use this
325 */
326 const CurveGFp& get_curve() const { return m_curve; }
327
328 private:
329 CurveGFp m_curve;
330 BigInt m_coord_x, m_coord_y, m_coord_z;
331 };
332
333/**
334* Point multiplication operator
335* @param scalar the scalar value
336* @param point the point value
337* @return scalar*point on the curve
338*/
339BOTAN_PUBLIC_API(2,0) EC_Point operator*(const BigInt& scalar, const EC_Point& point);
340
341/**
342* ECC point multiexponentiation - not constant time!
343* @param p1 a point
344* @param z1 a scalar
345* @param p2 a point
346* @param z2 a scalar
347* @result (p1 * z1 + p2 * z2)
348*/
350 const EC_Point& p1, const BigInt& z1,
351 const EC_Point& p2, const BigInt& z2);
352
353// relational operators
354inline bool operator!=(const EC_Point& lhs, const EC_Point& rhs)
355 {
356 return !(rhs == lhs);
357 }
358
359// arithmetic operators
360inline EC_Point operator-(const EC_Point& lhs)
361 {
362 return EC_Point(lhs).negate();
363 }
364
365inline EC_Point operator+(const EC_Point& lhs, const EC_Point& rhs)
366 {
367 EC_Point tmp(lhs);
368 return tmp += rhs;
369 }
370
371inline EC_Point operator-(const EC_Point& lhs, const EC_Point& rhs)
372 {
373 EC_Point tmp(lhs);
374 return tmp -= rhs;
375 }
376
377inline EC_Point operator*(const EC_Point& point, const BigInt& scalar)
378 {
379 return scalar * point;
380 }
381
382/**
383* Perform point decoding
384* Use EC_Group::OS2ECP instead
385*/
386EC_Point BOTAN_PUBLIC_API(2,0) OS2ECP(const uint8_t data[], size_t data_len,
387 const CurveGFp& curve);
388
389/**
390* Perform point decoding
391* Use EC_Group::OS2ECP instead
392*
393* @param data the encoded point
394* @param data_len length of data in bytes
395* @param curve_p the curve equation prime
396* @param curve_a the curve equation a parameter
397* @param curve_b the curve equation b parameter
398*/
399std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API OS2ECP(const uint8_t data[], size_t data_len,
400 const BigInt& curve_p,
401 const BigInt& curve_a,
402 const BigInt& curve_b);
403
404template<typename Alloc>
405EC_Point OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
406 { return OS2ECP(data.data(), data.size(), curve); }
407
408class EC_Point_Var_Point_Precompute;
409
410// The name used for this type in older versions
412
413}
414
415namespace std {
416
417template<>
419 { x.swap(y); }
420
421}
422
423#endif
static SIMD_4x64 y
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:67
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:36
size_t size() const
Definition: bigint.h:609
const word * data() const
Definition: bigint.h:649
EC_Point & negate()
Definition: ec_point.h:119
EC_Point & operator=(EC_Point &&other)
Definition: ec_point.h:72
EC_Point plus(const EC_Point &other, std::vector< BigInt > &workspace) const
Definition: ec_point.h:296
void swap(EC_Point &other)
Definition: ec_point.cpp:578
void add(const EC_Point &other, std::vector< BigInt > &workspace)
Definition: ec_point.h:220
EC_Point(EC_Point &&other)
Definition: ec_point.h:59
void add_affine(const EC_Point &other, std::vector< BigInt > &workspace)
Definition: ec_point.h:253
void mult2(std::vector< BigInt > &workspace)
Definition: ec_point.cpp:278
EC_Point double_of(std::vector< BigInt > &workspace) const
Definition: ec_point.h:308
const BigInt & get_y() const
Definition: ec_point.h:150
bool is_zero() const
Definition: ec_point.h:183
const BigInt & get_z() const
Definition: ec_point.h:157
void swap_coords(BigInt &new_x, BigInt &new_y, BigInt &new_z)
Definition: ec_point.h:159
EC_Point zero() const
Definition: ec_point.h:318
bool is_affine() const
Definition: ec_point.cpp:499
EC_Point(const EC_Point &)=default
const CurveGFp & get_curve() const
Definition: ec_point.h:326
EC_Point & operator=(const EC_Point &)=default
const BigInt & get_x() const
Definition: ec_point.h:143
EC_Point()=default
EC_Point_Format Compression_Type
Definition: ec_point.h:35
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
#define BOTAN_UNSTABLE_API
Definition: compiler.h:44
Definition: alg_id.cpp:12
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:48
EC_Point PointGFp
Definition: ec_point.h:411
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition: symkey.cpp:104
EC_Point multi_exponentiate(const EC_Point &p1, const BigInt &z1, const EC_Point &p2, const BigInt &z2)
Definition: point_mul.cpp:24
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1034
EC_Point_Format
Definition: ec_point.h:19
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:64
EC_Point OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: ec_point.cpp:666
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:84
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:64
Definition: bigint.h:1092
void swap< Botan::EC_Point >(Botan::EC_Point &x, Botan::EC_Point &y)
Definition: ec_point.h:418