Botan 3.3.0
Crypto and TLS for C&
ec_point.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_EC_POINT_H_
11#define BOTAN_EC_POINT_H_
12
13#include <botan/curve_gfp.h>
14#include <botan/exceptn.h>
15#include <vector>
16
17namespace Botan {
18
19enum class EC_Point_Format {
20 Uncompressed = 0,
21 Compressed = 1,
22 Hybrid = 2,
23
24 UNCOMPRESSED BOTAN_DEPRECATED("Use EC_Point_Format::Uncompressed") = Uncompressed,
25 COMPRESSED BOTAN_DEPRECATED("Use EC_Point_Format::Compressed") = Compressed,
26 HYBRID BOTAN_DEPRECATED("Use EC_Point_Format::Hybrid") = Hybrid,
27};
28
29/**
30* This class represents one point on a curve of GF(p)
31*/
33 public:
35 using enum EC_Point_Format;
36
37 enum { WORKSPACE_SIZE = 8 };
38
39 /**
40 * Construct an uninitialized EC_Point
41 */
42 EC_Point() = default;
43
44 /**
45 * Construct the zero point
46 * @param curve The base curve
47 */
48 explicit EC_Point(const CurveGFp& curve);
49
50 /**
51 * Copy constructor
52 */
53 EC_Point(const EC_Point&) = default;
54
55 /**
56 * Move Constructor
57 */
58 EC_Point(EC_Point&& other) { this->swap(other); }
59
60 /**
61 * Standard Assignment
62 */
63 EC_Point& operator=(const EC_Point&) = default;
64
65 /**
66 * Move Assignment
67 */
69 if(this != &other) {
70 this->swap(other);
71 }
72 return (*this);
73 }
74
75 /**
76 * Construct a point from its affine coordinates
77 * Prefer EC_Group::point(x,y) for this operation.
78 * @param curve the base curve
79 * @param x affine x coordinate
80 * @param y affine y coordinate
81 */
82 EC_Point(const CurveGFp& curve, const BigInt& x, const BigInt& y);
83
84 /**
85 * EC2OSP - elliptic curve to octet string primitive
86 * @param format which format to encode using
87 */
88 std::vector<uint8_t> encode(EC_Point_Format format) const;
89
90 /**
91 * += Operator
92 * @param rhs the EC_Point to add to the local value
93 * @result resulting EC_Point
94 */
95 EC_Point& operator+=(const EC_Point& rhs);
96
97 /**
98 * -= Operator
99 * @param rhs the EC_Point to subtract from the local value
100 * @result resulting EC_Point
101 */
102 EC_Point& operator-=(const EC_Point& rhs);
103
104 /**
105 * *= Operator
106 * @param scalar the EC_Point to multiply with *this
107 * @result resulting EC_Point
108 */
109 EC_Point& operator*=(const BigInt& scalar);
110
111 /**
112 * Negate this point
113 * @return *this
114 */
116 if(!is_zero()) {
117 m_coord_y = m_curve.get_p() - m_coord_y;
118 }
119 return *this;
120 }
121
122 /**
123 * get affine x coordinate
124 * @result affine x coordinate
125 */
126 BigInt get_affine_x() const;
127
128 /**
129 * get affine y coordinate
130 * @result affine y coordinate
131 */
132 BigInt get_affine_y() const;
133
134 /**
135 * Return the internal x coordinate
136 *
137 * Note this may be in Montgomery form
138 */
139 const BigInt& get_x() const { return m_coord_x; }
140
141 /**
142 * Return the internal y coordinate
143 *
144 * Note this may be in Montgomery form
145 */
146 const BigInt& get_y() const { return m_coord_y; }
147
148 /**
149 * Return the internal z coordinate
150 *
151 * Note this may be in Montgomery form
152 */
153 const BigInt& get_z() const { return m_coord_z; }
154
155 void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) {
156 m_coord_x.swap(new_x);
157 m_coord_y.swap(new_y);
158 m_coord_z.swap(new_z);
159 }
160
161 /**
162 * Force this point to affine coordinates
163 */
164 void force_affine();
165
166 /**
167 * Force all points on the list to affine coordinates
168 */
169 static void force_all_affine(std::vector<EC_Point>& points, secure_vector<word>& ws);
170
171 bool is_affine() 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 { return m_coord_z.is_zero(); }
178
179 /**
180 * Checks whether the point is to be found on the underlying
181 * curve; used to prevent fault attacks.
182 * @return if the point is on the curve
183 */
184 bool on_the_curve() const;
185
186 /**
187 * swaps the states of *this and other, does not throw!
188 * @param other the object to swap values with
189 */
190 void swap(EC_Point& other);
191
192 friend void swap(EC_Point& x, EC_Point& y) { x.swap(y); }
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);
199
200 /**
201 * Randomize the point representation
202 * The actual value (get_affine_x, get_affine_y) does not change
203 */
204 void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws);
205
206 /**
207 * Equality operator
208 */
209 bool operator==(const EC_Point& other) const;
210
211 /**
212 * Point addition
213 * @param other the point to add to *this
214 * @param workspace temp space, at least WORKSPACE_SIZE elements
215 */
216 void add(const EC_Point& other, std::vector<BigInt>& workspace) {
217 BOTAN_ARG_CHECK(m_curve == other.m_curve, "cannot add points on different curves");
218
219 const size_t p_words = m_curve.get_p_words();
220
221 add(other.m_coord_x.data(),
222 std::min(p_words, other.m_coord_x.size()),
223 other.m_coord_y.data(),
224 std::min(p_words, other.m_coord_y.size()),
225 other.m_coord_z.data(),
226 std::min(p_words, other.m_coord_z.size()),
227 workspace);
228 }
229
230 /**
231 * Point addition. Array version.
232 *
233 * @param x_words the words of the x coordinate of the other point
234 * @param x_size size of x_words
235 * @param y_words the words of the y coordinate of the other point
236 * @param y_size size of y_words
237 * @param z_words the words of the z coordinate of the other point
238 * @param z_size size of z_words
239 * @param workspace temp space, at least WORKSPACE_SIZE elements
240 */
241 void add(const word x_words[],
242 size_t x_size,
243 const word y_words[],
244 size_t y_size,
245 const word z_words[],
246 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 EC_Point& other, std::vector<BigInt>& workspace) {
255 BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
257
258 const size_t p_words = m_curve.get_p_words();
259 add_affine(other.m_coord_x.data(),
260 std::min(p_words, other.m_coord_x.size()),
261 other.m_coord_y.data(),
262 std::min(p_words, other.m_coord_y.size()),
263 workspace);
264 }
265
266 /**
267 * Point addition - mixed J+A. Array version.
268 *
269 * @param x_words the words of the x coordinate of the other point
270 * @param x_size size of x_words
271 * @param y_words the words of the y coordinate of the other point
272 * @param y_size size of y_words
273 * @param workspace temp space, at least WORKSPACE_SIZE elements
274 */
275 void add_affine(
276 const word x_words[], size_t x_size, const word y_words[], size_t y_size, 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 EC_Point plus(const EC_Point& other, std::vector<BigInt>& workspace) const {
298 EC_Point x = (*this);
299 x.add(other, workspace);
300 return x;
301 }
302
303 /**
304 * Point doubling
305 * @param workspace temp space, at least WORKSPACE_SIZE elements
306 * @return *this doubled
307 */
308 EC_Point double_of(std::vector<BigInt>& workspace) const {
309 EC_Point x = (*this);
310 x.mult2(workspace);
311 return x;
312 }
313
314 /**
315 * Return the zero (aka infinite) point associated with this curve
316 */
317 EC_Point zero() const { return EC_Point(m_curve); }
318
319 /**
320 * Return base curve of this point
321 * @result the curve over GF(p) of this point
322 *
323 * You should not need to use this
324 */
325 const CurveGFp& get_curve() const { return m_curve; }
326
327 private:
328 CurveGFp m_curve;
329 BigInt m_coord_x, m_coord_y, m_coord_z;
330};
331
332/**
333* Point multiplication operator
334* @param scalar the scalar value
335* @param point the point value
336* @return scalar*point on the curve
337*/
338BOTAN_PUBLIC_API(2, 0) EC_Point operator*(const BigInt& scalar, const EC_Point& point);
339
340/**
341* ECC point multiexponentiation - not constant time!
342* @param p1 a point
343* @param z1 a scalar
344* @param p2 a point
345* @param z2 a scalar
346* @result (p1 * z1 + p2 * z2)
347*/
349EC_Point multi_exponentiate(const EC_Point& p1, const BigInt& z1, const EC_Point& p2, const BigInt& z2);
350
351// relational operators
352inline bool operator!=(const EC_Point& lhs, const EC_Point& rhs) {
353 return !(rhs == lhs);
354}
355
356// arithmetic operators
357inline EC_Point operator-(const EC_Point& lhs) {
358 return EC_Point(lhs).negate();
359}
360
361inline EC_Point operator+(const EC_Point& lhs, const EC_Point& rhs) {
362 EC_Point tmp(lhs);
363 return tmp += rhs;
364}
365
366inline EC_Point operator-(const EC_Point& lhs, const EC_Point& rhs) {
367 EC_Point tmp(lhs);
368 return tmp -= rhs;
369}
370
371inline EC_Point operator*(const EC_Point& point, const BigInt& scalar) {
372 return scalar * point;
373}
374
375/**
376* Perform point decoding
377* Use EC_Group::OS2ECP instead
378*/
379EC_Point BOTAN_PUBLIC_API(2, 0) OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp& curve);
380
381/**
382* Perform point decoding
383* Use EC_Group::OS2ECP instead
384*
385* @param data the encoded point
386* @param data_len length of data in bytes
387* @param curve_p the curve equation prime
388* @param curve_a the curve equation a parameter
389* @param curve_b the curve equation b parameter
390*/
391std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API
392OS2ECP(const uint8_t data[], size_t data_len, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b);
393
394template <typename Alloc>
395EC_Point OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve) {
396 return OS2ECP(data.data(), data.size(), curve);
397}
398
399class EC_Point_Var_Point_Precompute;
400
401// The name used for this type in older versions
403
404} // namespace Botan
405
406#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
size_t size() const
Definition bigint.h:578
const word * data() const
Definition bigint.h:615
EC_Point & negate()
Definition ec_point.h:115
EC_Point & operator=(EC_Point &&other)
Definition ec_point.h:68
EC_Point plus(const EC_Point &other, std::vector< BigInt > &workspace) const
Definition ec_point.h:297
void swap(EC_Point &other)
Definition ec_point.cpp:547
void add(const EC_Point &other, std::vector< BigInt > &workspace)
Definition ec_point.h:216
EC_Point(EC_Point &&other)
Definition ec_point.h:58
void add_affine(const EC_Point &other, std::vector< BigInt > &workspace)
Definition ec_point.h:254
void mult2(std::vector< BigInt > &workspace)
Definition ec_point.cpp:256
EC_Point double_of(std::vector< BigInt > &workspace) const
Definition ec_point.h:308
const BigInt & get_y() const
Definition ec_point.h:146
bool is_zero() const
Definition ec_point.h:177
const BigInt & get_z() const
Definition ec_point.h:153
void swap_coords(BigInt &new_x, BigInt &new_y, BigInt &new_z)
Definition ec_point.h:155
EC_Point zero() const
Definition ec_point.h:317
bool is_affine() const
Definition ec_point.cpp:465
EC_Point(const EC_Point &)=default
const CurveGFp & get_curve() const
Definition ec_point.h:325
EC_Point & operator=(const EC_Point &)=default
friend void swap(EC_Point &x, EC_Point &y)
Definition ec_point.h:192
const BigInt & get_x() const
Definition ec_point.h:139
EC_Point()=default
EC_Point_Format Compression_Type
Definition ec_point.h:34
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition compiler.h:31
#define BOTAN_UNSTABLE_API
Definition compiler.h:44
#define BOTAN_DEPRECATED(msg)
Definition compiler.h:125
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:46
EC_Point PointGFp
Definition ec_point.h:402
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
EC_Point multi_exponentiate(const EC_Point &p1, const BigInt &z1, const EC_Point &p2, const BigInt &z2)
Definition point_mul.cpp:24
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:966
EC_Point_Format
Definition ec_point.h:19
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition alg_id.cpp:54
EC_Point OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition ec_point.cpp:627
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition secmem.h:80
constexpr auto operator-=(Strong< T1, Tags... > &a, T2 b)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr auto operator*=(Strong< T1, Tags... > &a, T2 b)