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