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