Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 *
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:
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:
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 */
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 */
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
156 const BigInt& get_x() const { return m_coord_x; }
157 const BigInt& get_y() const { return m_coord_y; }
158 const BigInt& get_z() const { return m_coord_z; }
159
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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")
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>
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) BOTAN_DEPRECATED("Use alternative APIs") 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 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
BOTAN_UNSTABLE_API
#define BOTAN_UNSTABLE_API
Definition: compiler.h:38
Botan::Illegal_Transformation
Definition: point_gfp.h:26
Botan::operator+
OID operator+(const OID &oid, uint32_t new_component)
Definition: asn1_oid.cpp:121
Botan::BigInt
Definition: bigint.h:24
Botan::PointGFp::is_affine
bool is_affine() const
Definition: point_gfp.cpp:494
Botan::PointGFp
Definition: point_gfp.h:47
Botan::RandomNumberGenerator
Definition: rng.h:24
final
int(* final)(unsigned char *, CTX *)
Definition: commoncrypto_hash.cpp:28
BOTAN_PUBLIC_API
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
Botan::PointGFp::get_y
const BigInt & get_y() const
Definition: point_gfp.h:157
std
Definition: bigint.h:1135
Botan::operator-
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1078
BOTAN_ASSERT_NOMSG
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
Botan::BigInt::size
size_t size() const
Definition: bigint.h:578
Botan::PointGFp::add
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:221
Botan::PointGFp::operator=
PointGFp & operator=(PointGFp &&other)
Definition: point_gfp.h:90
Botan::PointGFp::Compression_Type
Compression_Type
Definition: point_gfp.h:50
Botan::PointGFp::get_curve
const CurveGFp & get_curve() const
Definition: point_gfp.h:327
Botan::Decoding_Error
Definition: exceptn.h:199
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
Botan::PEM_Code::encode
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::Illegal_Transformation::Illegal_Transformation
Illegal_Transformation(const std::string &err)
Definition: point_gfp.h:29
m_ws
std::vector< BigInt > m_ws
Definition: ecdh.cpp:55
Botan::EC2OSP
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.h:385
Botan::operator+=
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:110
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::PointGFp::zero
PointGFp zero() const
Definition: point_gfp.h:319
Botan::PointGFp::negate
PointGFp & negate()
Definition: point_gfp.h:137
Botan::PointGFp::get_z
const BigInt & get_z() const
Definition: point_gfp.h:158
Botan::Illegal_Point
Definition: point_gfp.h:38
Botan
Definition: alg_id.cpp:13
Botan::PointGFp::plus
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:297
Botan::PointGFp::mult2
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
Botan::PointGFp::double_of
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:309
Botan::PointGFp::add_affine
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:254
Botan::Illegal_Point::Illegal_Point
Illegal_Point(const std::string &err)
Definition: point_gfp.h:41
Botan::operator*
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
Botan::Invalid_State
Definition: exceptn.h:215
Botan::Blinded_Point_Multiply
Definition: point_gfp.h:423
Botan::PointGFp::is_zero
bool is_zero() const
Definition: point_gfp.h:184
Botan::operator==
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:74
Botan::PointGFp::swap_coords
void swap_coords(BigInt &new_x, BigInt &new_y, BigInt &new_z)
Definition: point_gfp.h:160
Botan::PointGFp::PointGFp
PointGFp(PointGFp &&other)
Definition: point_gfp.h:77
Botan::PointGFp::get_x
const BigInt & get_x() const
Definition: point_gfp.h:156
Botan::multi_exponentiate
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:21
Botan::OS2ECP
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:661
Botan::CurveGFp
Definition: curve_gfp.h:96