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