/src/botan/build/include/botan/point_gfp.h
Line | Count | Source (jump to first uncovered line) |
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 | 1.31k | 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 | 4.00k | 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 | 1.47M | 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 | 1.01M | PointGFp(const PointGFp&) = default; |
73 | | |
74 | | /** |
75 | | * Move Constructor |
76 | | */ |
77 | | PointGFp(PointGFp&& other) |
78 | 22.8k | { |
79 | 22.8k | this->swap(other); |
80 | 22.8k | } |
81 | | |
82 | | /** |
83 | | * Standard Assignment |
84 | | */ |
85 | 671k | PointGFp& operator=(const PointGFp&) = default; |
86 | | |
87 | | /** |
88 | | * Move Assignment |
89 | | */ |
90 | | PointGFp& operator=(PointGFp&& other) |
91 | 1.12M | { |
92 | 1.12M | if(this != &other) |
93 | 1.12M | this->swap(other); |
94 | 1.12M | return (*this); |
95 | 1.12M | } |
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 | 0 | { |
139 | 0 | if(!is_zero()) |
140 | 0 | m_coord_y = m_curve.get_p() - m_coord_y; |
141 | 0 | return *this; |
142 | 0 | } |
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 | 1.74M | const BigInt& get_x() const { return m_coord_x; } |
157 | 1.74M | const BigInt& get_y() const { return m_coord_y; } |
158 | 603k | const BigInt& get_z() const { return m_coord_z; } |
159 | | |
160 | | void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) |
161 | 292k | { |
162 | 292k | m_coord_x.swap(new_x); |
163 | 292k | m_coord_y.swap(new_y); |
164 | 292k | m_coord_z.swap(new_z); |
165 | 292k | } |
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 | 21.4M | 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 | 1.37M | { |
223 | 1.37M | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
224 | 1.37M | |
225 | 1.37M | const size_t p_words = m_curve.get_p_words(); |
226 | 1.37M | |
227 | 1.37M | add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
228 | 1.37M | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
229 | 1.37M | other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()), |
230 | 1.37M | workspace); |
231 | 1.37M | } |
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 | 58.2k | { |
256 | 58.2k | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
257 | 58.2k | BOTAN_DEBUG_ASSERT(other.is_affine()); |
258 | 58.2k | |
259 | 58.2k | const size_t p_words = m_curve.get_p_words(); |
260 | 58.2k | add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
261 | 58.2k | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
262 | 58.2k | workspace); |
263 | 58.2k | } |
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 | 800k | { |
299 | 800k | PointGFp x = (*this); |
300 | 800k | x.add(other, workspace); |
301 | 800k | return x; |
302 | 800k | } |
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 | 136k | { |
311 | 136k | PointGFp x = (*this); |
312 | 136k | x.mult2(workspace); |
313 | 136k | return x; |
314 | 136k | } |
315 | | |
316 | | /** |
317 | | * Return the zero (aka infinite) point associated with this curve |
318 | | */ |
319 | 61.9k | 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 | 41.3k | 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 | 20.7k | { |
357 | 20.7k | return !(rhs == lhs); |
358 | 20.7k | } |
359 | | |
360 | | // arithmetic operators |
361 | | inline PointGFp operator-(const PointGFp& lhs) |
362 | 0 | { |
363 | 0 | return PointGFp(lhs).negate(); |
364 | 0 | } |
365 | | |
366 | | inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs) |
367 | 15.5k | { |
368 | 15.5k | PointGFp tmp(lhs); |
369 | 15.5k | return tmp += rhs; |
370 | 15.5k | } |
371 | | |
372 | | inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs) |
373 | 0 | { |
374 | 0 | PointGFp tmp(lhs); |
375 | 0 | return tmp -= rhs; |
376 | 0 | } |
377 | | |
378 | | inline PointGFp operator*(const PointGFp& point, const BigInt& scalar) |
379 | 8.11k | { |
380 | 8.11k | return scalar * point; |
381 | 8.11k | } |
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 | 0 | { |
387 | 0 | std::vector<uint8_t> enc = point.encode(static_cast<PointGFp::Compression_Type>(format)); |
388 | 0 | return secure_vector<uint8_t>(enc.begin(), enc.end()); |
389 | 0 | } |
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) 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 | 0 | { x.swap(y); } |
444 | | |
445 | | } |
446 | | |
447 | | #endif |