Botan  2.4.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  /**
53  * Construct an uninitialized PointGFp
54  */
55  PointGFp() = default;
56 
57  /**
58  * Construct the zero point
59  * @param curve The base curve
60  */
61  explicit PointGFp(const CurveGFp& curve);
62 
63  static PointGFp zero_of(const CurveGFp& curve)
64  {
65  return PointGFp(curve);
66  }
67 
68  /**
69  * Copy constructor
70  */
71  PointGFp(const PointGFp&) = default;
72 
73  /**
74  * Move Constructor
75  */
76  PointGFp(PointGFp&& other)
77  {
78  this->swap(other);
79  }
80 
81  /**
82  * Standard Assignment
83  */
84  PointGFp& operator=(const PointGFp&) = default;
85 
86  /**
87  * Move Assignment
88  */
90  {
91  if(this != &other)
92  this->swap(other);
93  return (*this);
94  }
95 
96  /**
97  * Construct a point from its affine coordinates
98  * @param curve the base curve
99  * @param x affine x coordinate
100  * @param y affine y coordinate
101  */
102  PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);
103 
104  /**
105  * += Operator
106  * @param rhs the PointGFp to add to the local value
107  * @result resulting PointGFp
108  */
109  PointGFp& operator+=(const PointGFp& rhs);
110 
111  /**
112  * -= Operator
113  * @param rhs the PointGFp to subtract from the local value
114  * @result resulting PointGFp
115  */
116  PointGFp& operator-=(const PointGFp& rhs);
117 
118  /**
119  * *= Operator
120  * @param scalar the PointGFp to multiply with *this
121  * @result resulting PointGFp
122  */
123 
124  PointGFp& operator*=(const BigInt& scalar);
125 
126  /**
127  * Multiplication Operator
128  * @param scalar the scalar value
129  * @param point the point value
130  * @return scalar*point on the curve
131  */
132  friend BOTAN_PUBLIC_API(2,0) PointGFp operator*(const BigInt& scalar, const PointGFp& point);
133 
134  /**
135  * Multiexponentiation
136  * @param p1 a point
137  * @param z1 a scalar
138  * @param p2 a point
139  * @param z2 a scalar
140  * @result (p1 * z1 + p2 * z2)
141  */
143  const PointGFp& p1, const BigInt& z1,
144  const PointGFp& p2, const BigInt& z2);
145 
146  /**
147  * Negate this point
148  * @return *this
149  */
151  {
152  if(!is_zero())
153  m_coord_y = m_curve.get_p() - m_coord_y;
154  return *this;
155  }
156 
157  /**
158  * Return base curve of this point
159  * @result the curve over GF(p) of this point
160  */
161  const CurveGFp& get_curve() const { return m_curve; }
162 
163  /**
164  * get affine x coordinate
165  * @result affine x coordinate
166  */
167  BigInt get_affine_x() const;
168 
169  /**
170  * get affine y coordinate
171  * @result affine y coordinate
172  */
173  BigInt get_affine_y() const;
174 
175  /**
176  * Is this the point at infinity?
177  * @result true, if this point is at infinity, false otherwise.
178  */
179  bool is_zero() const
180  { return (m_coord_x.is_zero() && m_coord_z.is_zero()); }
181 
182  /**
183  * Checks whether the point is to be found on the underlying
184  * curve; used to prevent fault attacks.
185  * @return if the point is on the curve
186  */
187  bool on_the_curve() const;
188 
189  /**
190  * swaps the states of *this and other, does not throw!
191  * @param other the object to swap values with
192  */
193  void swap(PointGFp& other);
194 
195  /**
196  * Randomize the point representation
197  * The actual value (get_affine_x, get_affine_y) does not change
198  */
199  void randomize_repr(RandomNumberGenerator& rng);
200 
201  /**
202  * Equality operator
203  */
204  bool operator==(const PointGFp& other) const;
205  private:
207 
208  BigInt curve_mult(const BigInt& x, const BigInt& y) const
209  {
210  BigInt z;
211  m_curve.mul(z, x, y, m_monty_ws);
212  return z;
213  }
214 
215  void curve_mult(BigInt& z, const BigInt& x, const BigInt& y) const
216  {
217  m_curve.mul(z, x, y, m_monty_ws);
218  }
219 
220  BigInt curve_sqr(const BigInt& x) const
221  {
222  BigInt z;
223  m_curve.sqr(z, x, m_monty_ws);
224  return z;
225  }
226 
227  void curve_sqr(BigInt& z, const BigInt& x) const
228  {
229  m_curve.sqr(z, x, m_monty_ws);
230  }
231 
232  /**
233  * Point addition
234  * @param workspace temp space, at least 11 elements
235  */
236  void add(const PointGFp& other, std::vector<BigInt>& workspace);
237 
238  /**
239  * Point doubling
240  * @param workspace temp space, at least 9 elements
241  */
242  void mult2(std::vector<BigInt>& workspace);
243 
244  CurveGFp m_curve;
245  BigInt m_coord_x, m_coord_y, m_coord_z;
246  mutable secure_vector<word> m_monty_ws; // workspace for Montgomery
247  };
248 
249 // relational operators
250 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
251  {
252  return !(rhs == lhs);
253  }
254 
255 // arithmetic operators
256 inline PointGFp operator-(const PointGFp& lhs)
257  {
258  return PointGFp(lhs).negate();
259  }
260 
261 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
262  {
263  PointGFp tmp(lhs);
264  return tmp += rhs;
265  }
266 
267 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
268  {
269  PointGFp tmp(lhs);
270  return tmp -= rhs;
271  }
272 
273 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
274  {
275  return scalar * point;
276  }
277 
278 // encoding and decoding
279 secure_vector<uint8_t> BOTAN_PUBLIC_API(2,0) EC2OSP(const PointGFp& point, uint8_t format);
280 
281 PointGFp BOTAN_PUBLIC_API(2,0) OS2ECP(const uint8_t data[], size_t data_len,
282  const CurveGFp& curve);
283 
284 template<typename Alloc>
285 PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
286  { return OS2ECP(data.data(), data.size(), curve); }
287 
288 /**
289 
290 */
292  {
293  public:
294  Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
295 
296  PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
297  private:
298  const size_t m_h;
299  const BigInt& m_order;
300  std::vector<BigInt> m_ws;
301  std::vector<PointGFp> m_U;
302  };
303 
304 }
305 
306 namespace std {
307 
308 template<>
309 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
310  { x.swap(y); }
311 
312 }
313 
314 #endif
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:90
static PointGFp zero_of(const CurveGFp &curve)
Definition: point_gfp.h:63
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:27
Definition: bigint.h:635
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:49
PointGFp & operator=(PointGFp &&other)
Definition: point_gfp.h:89
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.cpp:469
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:131
PointGFp & negate()
Definition: point_gfp.h:150
Definition: alg_id.cpp:13
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:84
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
bool is_zero() const
Definition: point_gfp.h:179
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:161
PointGFp(PointGFp &&other)
Definition: point_gfp.h:76
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:247
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:543
Illegal_Transformation(const std::string &err="Requested transformation is not possible")
Definition: point_gfp.h:25