Botan  2.1.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 */
22 struct BOTAN_DLL Illegal_Transformation : public Exception
23  {
24  explicit Illegal_Transformation(const std::string& err =
25  "Requested transformation is not possible") :
26  Exception(err) {}
27  };
28 
29 /**
30 * Exception thrown if some form of illegal point is decoded
31 */
32 struct BOTAN_DLL Illegal_Point : public Exception
33  {
34  explicit Illegal_Point(const std::string& err = "Malformed ECP point detected") :
35  Exception(err) {}
36  };
37 
38 /**
39 * This class represents one point on a curve of GF(p)
40 */
41 class BOTAN_DLL PointGFp
42  {
43  public:
45  UNCOMPRESSED = 0,
46  COMPRESSED = 1,
47  HYBRID = 2
48  };
49 
50  /**
51  * Construct an uninitialized PointGFp
52  */
53  PointGFp() = default;
54 
55  /**
56  * Construct the zero point
57  * @param curve The base curve
58  */
59  explicit PointGFp(const CurveGFp& curve);
60 
61  static PointGFp zero_of(const CurveGFp& curve)
62  {
63  return PointGFp(curve);
64  }
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  * += Operator
104  * @param rhs the PointGFp to add to the local value
105  * @result resulting PointGFp
106  */
107  PointGFp& operator+=(const PointGFp& rhs);
108 
109  /**
110  * -= Operator
111  * @param rhs the PointGFp to subtract from the local value
112  * @result resulting PointGFp
113  */
114  PointGFp& operator-=(const PointGFp& rhs);
115 
116  /**
117  * *= Operator
118  * @param scalar the PointGFp to multiply with *this
119  * @result resulting PointGFp
120  */
121 
122  PointGFp& operator*=(const BigInt& scalar);
123 
124  /**
125  * Multiplication Operator
126  * @param scalar the scalar value
127  * @param point the point value
128  * @return scalar*point on the curve
129  */
130  friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point);
131 
132  /**
133  * Multiexponentiation
134  * @param p1 a point
135  * @param z1 a scalar
136  * @param p2 a point
137  * @param z2 a scalar
138  * @result (p1 * z1 + p2 * z2)
139  */
140  friend BOTAN_DLL PointGFp multi_exponentiate(
141  const PointGFp& p1, const BigInt& z1,
142  const PointGFp& p2, const BigInt& z2);
143 
144  /**
145  * Negate this point
146  * @return *this
147  */
149  {
150  if(!is_zero())
151  m_coord_y = m_curve.get_p() - m_coord_y;
152  return *this;
153  }
154 
155  /**
156  * Return base curve of this point
157  * @result the curve over GF(p) of this point
158  */
159  const CurveGFp& get_curve() const { return m_curve; }
160 
161  /**
162  * get affine x coordinate
163  * @result affine x coordinate
164  */
165  BigInt get_affine_x() const;
166 
167  /**
168  * get affine y coordinate
169  * @result affine y coordinate
170  */
171  BigInt get_affine_y() const;
172 
173  /**
174  * Is this the point at infinity?
175  * @result true, if this point is at infinity, false otherwise.
176  */
177  bool is_zero() const
178  { return (m_coord_x.is_zero() && m_coord_z.is_zero()); }
179 
180  /**
181  * Checks whether the point is to be found on the underlying
182  * curve; used to prevent fault attacks.
183  * @return if the point is on the curve
184  */
185  bool on_the_curve() const;
186 
187  /**
188  * swaps the states of *this and other, does not throw!
189  * @param other the object to swap values with
190  */
191  void swap(PointGFp& other);
192 
193  /**
194  * Randomize the point representation
195  * The actual value (get_affine_x, get_affine_y) does not change
196  */
197  void randomize_repr(RandomNumberGenerator& rng);
198 
199  /**
200  * Equality operator
201  */
202  bool operator==(const PointGFp& other) const;
203  private:
205 
206  BigInt curve_mult(const BigInt& x, const BigInt& y) const
207  {
208  BigInt z;
209  m_curve.mul(z, x, y, m_monty_ws);
210  return z;
211  }
212 
213  void curve_mult(BigInt& z, const BigInt& x, const BigInt& y) const
214  {
215  m_curve.mul(z, x, y, m_monty_ws);
216  }
217 
218  BigInt curve_sqr(const BigInt& x) const
219  {
220  BigInt z;
221  m_curve.sqr(z, x, m_monty_ws);
222  return z;
223  }
224 
225  void curve_sqr(BigInt& z, const BigInt& x) const
226  {
227  m_curve.sqr(z, x, m_monty_ws);
228  }
229 
230  /**
231  * Point addition
232  * @param workspace temp space, at least 11 elements
233  */
234  void add(const PointGFp& other, std::vector<BigInt>& workspace);
235 
236  /**
237  * Point doubling
238  * @param workspace temp space, at least 9 elements
239  */
240  void mult2(std::vector<BigInt>& workspace);
241 
242  CurveGFp m_curve;
243  BigInt m_coord_x, m_coord_y, m_coord_z;
244  mutable secure_vector<word> m_monty_ws; // workspace for Montgomery
245  };
246 
247 // relational operators
248 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
249  {
250  return !(rhs == lhs);
251  }
252 
253 // arithmetic operators
254 inline PointGFp operator-(const PointGFp& lhs)
255  {
256  return PointGFp(lhs).negate();
257  }
258 
259 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
260  {
261  PointGFp tmp(lhs);
262  return tmp += rhs;
263  }
264 
265 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
266  {
267  PointGFp tmp(lhs);
268  return tmp -= rhs;
269  }
270 
271 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
272  {
273  return scalar * point;
274  }
275 
276 // encoding and decoding
277 secure_vector<uint8_t> BOTAN_DLL EC2OSP(const PointGFp& point, uint8_t format);
278 
279 PointGFp BOTAN_DLL OS2ECP(const uint8_t data[], size_t data_len,
280  const CurveGFp& curve);
281 
282 template<typename Alloc>
283 PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
284  { return OS2ECP(data.data(), data.size(), curve); }
285 
286 /**
287 
288 */
289 class BOTAN_DLL Blinded_Point_Multiply
290  {
291  public:
292  Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
293 
294  PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
295  private:
296  const size_t m_h;
297  const BigInt& m_order;
298  std::vector<BigInt> m_ws;
299  std::vector<PointGFp> m_U;
300  };
301 
302 }
303 
304 namespace std {
305 
306 template<>
307 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
308  { x.swap(y); }
309 
310 }
311 
312 #endif
static PointGFp zero_of(const CurveGFp &curve)
Definition: point_gfp.h:61
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.cpp:470
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:82
Illegal_Point(const std::string &err="Malformed ECP point detected")
Definition: point_gfp.h:34
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:67
const CurveGFp & m_curve
Definition: ecdh.cpp:48
Definition: bigint.h:619
PointGFp & operator=(PointGFp &&other)
Definition: point_gfp.h:87
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
const CurveGFp & get_curve() const
Definition: point_gfp.h:159
Illegal_Transformation(const std::string &err="Requested transformation is not possible")
Definition: point_gfp.h:24
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:544
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:161
PointGFp & negate()
Definition: point_gfp.h:148
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:84
Definition: alg_id.cpp:13
const BigInt & m_order
Definition: ecdh.cpp:50
T is_zero(T x)
Definition: ct_utils.h:110
bool is_zero() const
Definition: point_gfp.h:177
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:49
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_gfp.cpp:248