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 */
26 class BOTAN_PUBLIC_API(2,0) Illegal_Transformation final : public Invalid_State
27 {
28 public:
Illegal_Transformation(const std::string & err)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 */
38 class BOTAN_PUBLIC_API(2,0) Illegal_Point final : public Decoding_Error
39 {
40 public:
Illegal_Point(const std::string & err)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 */
47 class BOTAN_PUBLIC_API(2,0) PointGFp final
48 {
49 public:
50 enum Compression_Type {
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 */
PointGFp(PointGFp && other)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 */
90 PointGFp& operator=(PointGFp&& other)
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 */
negate()137 PointGFp& negate()
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
get_x()156 const BigInt& get_x() const { return m_coord_x; }
get_y()157 const BigInt& get_y() const { return m_coord_y; }
get_z()158 const BigInt& get_z() const { return m_coord_z; }
159
swap_coords(BigInt & new_x,BigInt & new_y,BigInt & new_z)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 */
is_zero()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 */
add(const PointGFp & other,std::vector<BigInt> & workspace)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 */
add_affine(const PointGFp & other,std::vector<BigInt> & workspace)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 */
plus(const PointGFp & other,std::vector<BigInt> & workspace)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 */
double_of(std::vector<BigInt> & workspace)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 */
zero()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 */
get_curve()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 */
350 BOTAN_PUBLIC_API(2,0) PointGFp multi_exponentiate(
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")
EC2OSP(const PointGFp & point,uint8_t format)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>
OS2ECP(const std::vector<uint8_t,Alloc> & data,const CurveGFp & curve)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) Blinded_Point_Multiply final
424 {
425 public:
426 Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
427
428 ~Blinded_Point_Multiply();
429
430 PointGFp BOTAN_DEPRECATED("Use alternative APIs") 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
448