Botan  2.12.1
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  * 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,
176  secure_vector<word>& ws);
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);
257  BOTAN_DEBUG_ASSERT(other.is_affine());
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 */
340 BOTAN_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
355 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
356  {
357  return !(rhs == lhs);
358  }
359 
360 // arithmetic operators
361 inline PointGFp operator-(const PointGFp& lhs)
362  {
363  return PointGFp(lhs).negate();
364  }
365 
366 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
367  {
368  PointGFp tmp(lhs);
369  return tmp += rhs;
370  }
371 
372 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
373  {
374  PointGFp tmp(lhs);
375  return tmp -= rhs;
376  }
377 
378 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
379  {
380  return scalar * point;
381  }
382 
383 // encoding and decoding
384 inline 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 */
395 PointGFp 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 */
408 std::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 
413 template<typename Alloc>
414 PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
415  { return OS2ECP(data.data(), data.size(), curve); }
416 
417 class 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 */
423 class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use alternative APIs") Blinded_Point_Multiply final
424  {
425  public:
426  Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
427 
429 
430  PointGFp 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 
439 namespace std {
440 
441 template<>
442 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
443  { x.swap(y); }
444 
445 }
446 
447 #endif
#define BOTAN_UNSTABLE_API
Definition: compiler.h:38
OID operator+(const OID &oid, uint32_t new_component)
Definition: asn1_oid.cpp:121
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
Definition: bigint.h:1135
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1078
#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:221
PointGFp & operator=(PointGFp &&other)
Definition: point_gfp.h:90
const word * data() const
Definition: bigint.h:618
PointGFp zero() const
Definition: point_gfp.h:319
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:158
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.h:385
const BigInt & get_y() const
Definition: point_gfp.h:157
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:578
PointGFp & negate()
Definition: point_gfp.h:137
Definition: alg_id.cpp:13
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:297
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:309
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:254
Illegal_Point(const std::string &err)
Definition: point_gfp.h:41
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
const BigInt & get_x() const
Definition: point_gfp.h:156
bool is_zero() const
Definition: point_gfp.h:184
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:74
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:160
const CurveGFp & get_curve() const
Definition: point_gfp.h:327
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:21
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:661