Botan  2.11.0
Crypto and TLS for C++11
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 
17 namespace 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  */
77  PointGFp(PointGFp&& other)
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  * @param curve the base curve
100  * @param x affine x coordinate
101  * @param y affine y coordinate
102  */
103  PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);
104 
105  /**
106  * EC2OSP - elliptic curve to octet string primitive
107  * @param format which format to encode using
108  */
109  std::vector<uint8_t> encode(PointGFp::Compression_Type format) const;
110 
111  /**
112  * += Operator
113  * @param rhs the PointGFp to add to the local value
114  * @result resulting PointGFp
115  */
116  PointGFp& operator+=(const PointGFp& rhs);
117 
118  /**
119  * -= Operator
120  * @param rhs the PointGFp to subtract from the local value
121  * @result resulting PointGFp
122  */
123  PointGFp& operator-=(const PointGFp& rhs);
124 
125  /**
126  * *= Operator
127  * @param scalar the PointGFp to multiply with *this
128  * @result resulting PointGFp
129  */
130  PointGFp& operator*=(const BigInt& scalar);
131 
132  /**
133  * Negate this point
134  * @return *this
135  */
137  {
138  if(!is_zero())
139  m_coord_y = m_curve.get_p() - m_coord_y;
140  return *this;
141  }
142 
143  /**
144  * get affine x coordinate
145  * @result affine x coordinate
146  */
147  BigInt get_affine_x() const;
148 
149  /**
150  * get affine y coordinate
151  * @result affine y coordinate
152  */
153  BigInt get_affine_y() const;
154 
155  const BigInt& get_x() const { return m_coord_x; }
156  const BigInt& get_y() const { return m_coord_y; }
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<PointGFp>& points,
175  secure_vector<word>& ws);
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(PointGFp& 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 PointGFp& 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 PointGFp& other, std::vector<BigInt>& workspace)
221  {
222  BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
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 PointGFp& other, std::vector<BigInt>& workspace)
254  {
255  BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
256  BOTAN_DEBUG_ASSERT(other.is_affine());
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  PointGFp plus(const PointGFp& other, std::vector<BigInt>& workspace) const
297  {
298  PointGFp 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  PointGFp double_of(std::vector<BigInt>& workspace) const
309  {
310  PointGFp 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  PointGFp zero() const { return PointGFp(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 */
339 BOTAN_PUBLIC_API(2,0) PointGFp operator*(const BigInt& scalar, const PointGFp& 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 PointGFp& p1, const BigInt& z1,
351  const PointGFp& p2, const BigInt& z2);
352 
353 // relational operators
354 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
355  {
356  return !(rhs == lhs);
357  }
358 
359 // arithmetic operators
360 inline PointGFp operator-(const PointGFp& lhs)
361  {
362  return PointGFp(lhs).negate();
363  }
364 
365 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
366  {
367  PointGFp tmp(lhs);
368  return tmp += rhs;
369  }
370 
371 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
372  {
373  PointGFp tmp(lhs);
374  return tmp -= rhs;
375  }
376 
377 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
378  {
379  return scalar * point;
380  }
381 
382 // encoding and decoding
383 inline secure_vector<uint8_t> BOTAN_DEPRECATED("Use PointGFp::encode")
384  EC2OSP(const PointGFp& point, uint8_t format)
385  {
386  std::vector<uint8_t> enc = point.encode(static_cast<PointGFp::Compression_Type>(format));
387  return secure_vector<uint8_t>(enc.begin(), enc.end());
388  }
389 
390 /**
391 * Perform point decoding
392 * Use EC_Group::OS2ECP instead
393 */
394 PointGFp BOTAN_PUBLIC_API(2,0) OS2ECP(const uint8_t data[], size_t data_len,
395  const CurveGFp& curve);
396 
397 /**
398 * Perform point decoding
399 * Use EC_Group::OS2ECP instead
400 *
401 * @param data the encoded point
402 * @param data_len length of data in bytes
403 * @param curve_p the curve equation prime
404 * @param curve_a the curve equation a parameter
405 * @param curve_b the curve equation b parameter
406 */
407 std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API OS2ECP(const uint8_t data[], size_t data_len,
408  const BigInt& curve_p,
409  const BigInt& curve_a,
410  const BigInt& curve_b);
411 
412 template<typename Alloc>
413 PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
414  { return OS2ECP(data.data(), data.size(), curve); }
415 
416 class PointGFp_Var_Point_Precompute;
417 
418 /**
419 * Deprecated API for point multiplication
420 * Use EC_Group::blinded_base_point_multiply or EC_Group::blinded_var_point_multiply
421 */
422 class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use alternative APIs") Blinded_Point_Multiply final
423  {
424  public:
425  Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
426 
428 
429  PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
430  private:
431  std::vector<BigInt> m_ws;
432  const BigInt& m_order;
433  std::unique_ptr<PointGFp_Var_Point_Precompute> m_point_mul;
434  };
435 
436 }
437 
438 namespace std {
439 
440 template<>
441 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
442  { x.swap(y); }
443 
444 }
445 
446 #endif
#define BOTAN_UNSTABLE_API
Definition: compiler.h:38
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
Definition: bigint.h:1136
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1079
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
bool is_affine() const
Definition: point_gfp.cpp:494
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:220
PointGFp & operator=(PointGFp &&other)
Definition: point_gfp.h:90
const word * data() const
Definition: bigint.h:623
PointGFp zero() const
Definition: point_gfp.h:318
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Illegal_Transformation(const std::string &err)
Definition: point_gfp.h:29
const BigInt & get_z() const
Definition: point_gfp.h:157
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.h:384
const BigInt & get_y() const
Definition: point_gfp.h:156
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:110
size_t size() const
Definition: bigint.h:583
PointGFp & negate()
Definition: point_gfp.h:136
Definition: alg_id.cpp:13
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:296
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:308
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:253
Illegal_Point(const std::string &err)
Definition: point_gfp.h:41
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
const BigInt & get_x() const
Definition: point_gfp.h:155
bool is_zero() const
Definition: point_gfp.h:183
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:75
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
void swap_coords(BigInt &new_x, BigInt &new_y, BigInt &new_z)
Definition: point_gfp.h:159
const CurveGFp & get_curve() const
Definition: point_gfp.h:326
PointGFp(PointGFp &&other)
Definition: point_gfp.h:77
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:15
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:661