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