/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 | 991 | 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.57k | 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.29M | 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 | 891k | PointGFp(const PointGFp&) = default; |
73 | | |
74 | | /** |
75 | | * Move Constructor |
76 | | */ |
77 | | PointGFp(PointGFp&& other) |
78 | 28.8k | { |
79 | 28.8k | this->swap(other); |
80 | 28.8k | } |
81 | | |
82 | | /** |
83 | | * Standard Assignment |
84 | | */ |
85 | 600k | PointGFp& operator=(const PointGFp&) = default; |
86 | | |
87 | | /** |
88 | | * Move Assignment |
89 | | */ |
90 | | PointGFp& operator=(PointGFp&& other) |
91 | 984k | { |
92 | 984k | if(this != &other) |
93 | 984k | this->swap(other); |
94 | 984k | return (*this); |
95 | 984k | } |
96 | | |
97 | | /** |
98 | | * Construct a point from its affine coordinates |
99 | | * @param curve the base curve |
100 | | * @param x affine x coordinate |
101 | | * @param y affine y coordinate |
102 | | */ |
103 | | PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y); |
104 | | |
105 | | /** |
106 | | * EC2OSP - elliptic curve to octet string primitive |
107 | | * @param format which format to encode using |
108 | | */ |
109 | | std::vector<uint8_t> encode(PointGFp::Compression_Type format) const; |
110 | | |
111 | | /** |
112 | | * += Operator |
113 | | * @param rhs the PointGFp to add to the local value |
114 | | * @result resulting PointGFp |
115 | | */ |
116 | | PointGFp& operator+=(const PointGFp& rhs); |
117 | | |
118 | | /** |
119 | | * -= Operator |
120 | | * @param rhs the PointGFp to subtract from the local value |
121 | | * @result resulting PointGFp |
122 | | */ |
123 | | PointGFp& operator-=(const PointGFp& rhs); |
124 | | |
125 | | /** |
126 | | * *= Operator |
127 | | * @param scalar the PointGFp to multiply with *this |
128 | | * @result resulting PointGFp |
129 | | */ |
130 | | PointGFp& operator*=(const BigInt& scalar); |
131 | | |
132 | | /** |
133 | | * Negate this point |
134 | | * @return *this |
135 | | */ |
136 | | PointGFp& negate() |
137 | 0 | { |
138 | 0 | if(!is_zero()) |
139 | 0 | m_coord_y = m_curve.get_p() - m_coord_y; |
140 | 0 | return *this; |
141 | 0 | } |
142 | | |
143 | | /** |
144 | | * get affine x coordinate |
145 | | * @result affine x coordinate |
146 | | */ |
147 | | BigInt get_affine_x() const; |
148 | | |
149 | | /** |
150 | | * get affine y coordinate |
151 | | * @result affine y coordinate |
152 | | */ |
153 | | BigInt get_affine_y() const; |
154 | | |
155 | 1.51M | const BigInt& get_x() const { return m_coord_x; } |
156 | 1.51M | const BigInt& get_y() const { return m_coord_y; } |
157 | 488k | const BigInt& get_z() const { return m_coord_z; } |
158 | | |
159 | | void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) |
160 | 236k | { |
161 | 236k | m_coord_x.swap(new_x); |
162 | 236k | m_coord_y.swap(new_y); |
163 | 236k | m_coord_z.swap(new_z); |
164 | 236k | } |
165 | | |
166 | | /** |
167 | | * Force this point to affine coordinates |
168 | | */ |
169 | | void force_affine(); |
170 | | |
171 | | /** |
172 | | * Force all points on the list to affine coordinates |
173 | | */ |
174 | | static void force_all_affine(std::vector<PointGFp>& points, |
175 | | secure_vector<word>& ws); |
176 | | |
177 | | bool is_affine() const; |
178 | | |
179 | | /** |
180 | | * Is this the point at infinity? |
181 | | * @result true, if this point is at infinity, false otherwise. |
182 | | */ |
183 | 14.3M | bool is_zero() const { return m_coord_z.is_zero(); } |
184 | | |
185 | | /** |
186 | | * Checks whether the point is to be found on the underlying |
187 | | * curve; used to prevent fault attacks. |
188 | | * @return if the point is on the curve |
189 | | */ |
190 | | bool on_the_curve() const; |
191 | | |
192 | | /** |
193 | | * swaps the states of *this and other, does not throw! |
194 | | * @param other the object to swap values with |
195 | | */ |
196 | | void swap(PointGFp& other); |
197 | | |
198 | | /** |
199 | | * Randomize the point representation |
200 | | * The actual value (get_affine_x, get_affine_y) does not change |
201 | | */ |
202 | | void randomize_repr(RandomNumberGenerator& rng); |
203 | | |
204 | | /** |
205 | | * Randomize the point representation |
206 | | * The actual value (get_affine_x, get_affine_y) does not change |
207 | | */ |
208 | | void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws); |
209 | | |
210 | | /** |
211 | | * Equality operator |
212 | | */ |
213 | | bool operator==(const PointGFp& other) const; |
214 | | |
215 | | /** |
216 | | * Point addition |
217 | | * @param other the point to add to *this |
218 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
219 | | */ |
220 | | void add(const PointGFp& other, std::vector<BigInt>& workspace) |
221 | 985k | { |
222 | 985k | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
223 | 985k | |
224 | 985k | const size_t p_words = m_curve.get_p_words(); |
225 | 985k | |
226 | 985k | add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
227 | 985k | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
228 | 985k | other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()), |
229 | 985k | workspace); |
230 | 985k | } |
231 | | |
232 | | /** |
233 | | * Point addition. Array version. |
234 | | * |
235 | | * @param x_words the words of the x coordinate of the other point |
236 | | * @param x_size size of x_words |
237 | | * @param y_words the words of the y coordinate of the other point |
238 | | * @param y_size size of y_words |
239 | | * @param z_words the words of the z coordinate of the other point |
240 | | * @param z_size size of z_words |
241 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
242 | | */ |
243 | | void add(const word x_words[], size_t x_size, |
244 | | const word y_words[], size_t y_size, |
245 | | const word z_words[], size_t z_size, |
246 | | std::vector<BigInt>& workspace); |
247 | | |
248 | | /** |
249 | | * Point addition - mixed J+A |
250 | | * @param other affine point to add - assumed to be affine! |
251 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
252 | | */ |
253 | | void add_affine(const PointGFp& other, std::vector<BigInt>& workspace) |
254 | 78.0k | { |
255 | 78.0k | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
256 | 78.0k | BOTAN_DEBUG_ASSERT(other.is_affine()); |
257 | 78.0k | |
258 | 78.0k | const size_t p_words = m_curve.get_p_words(); |
259 | 78.0k | add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
260 | 78.0k | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
261 | 78.0k | workspace); |
262 | 78.0k | } |
263 | | |
264 | | /** |
265 | | * Point addition - mixed J+A. Array version. |
266 | | * |
267 | | * @param x_words the words of the x coordinate of the other point |
268 | | * @param x_size size of x_words |
269 | | * @param y_words the words of the y coordinate of the other point |
270 | | * @param y_size size of y_words |
271 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
272 | | */ |
273 | | void add_affine(const word x_words[], size_t x_size, |
274 | | const word y_words[], size_t y_size, |
275 | | std::vector<BigInt>& workspace); |
276 | | |
277 | | /** |
278 | | * Point doubling |
279 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
280 | | */ |
281 | | void mult2(std::vector<BigInt>& workspace); |
282 | | |
283 | | /** |
284 | | * Repeated point doubling |
285 | | * @param i number of doublings to perform |
286 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
287 | | */ |
288 | | void mult2i(size_t i, std::vector<BigInt>& workspace); |
289 | | |
290 | | /** |
291 | | * Point addition |
292 | | * @param other the point to add to *this |
293 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
294 | | * @return other plus *this |
295 | | */ |
296 | | PointGFp plus(const PointGFp& other, std::vector<BigInt>& workspace) const |
297 | 712k | { |
298 | 712k | PointGFp x = (*this); |
299 | 712k | x.add(other, workspace); |
300 | 712k | return x; |
301 | 712k | } |
302 | | |
303 | | /** |
304 | | * Point doubling |
305 | | * @param workspace temp space, at least WORKSPACE_SIZE elements |
306 | | * @return *this doubled |
307 | | */ |
308 | | PointGFp double_of(std::vector<BigInt>& workspace) const |
309 | 110k | { |
310 | 110k | PointGFp x = (*this); |
311 | 110k | x.mult2(workspace); |
312 | 110k | return x; |
313 | 110k | } |
314 | | |
315 | | /** |
316 | | * Return the zero (aka infinite) point associated with this curve |
317 | | */ |
318 | 51.4k | PointGFp zero() const { return PointGFp(m_curve); } |
319 | | |
320 | | /** |
321 | | * Return base curve of this point |
322 | | * @result the curve over GF(p) of this point |
323 | | * |
324 | | * You should not need to use this |
325 | | */ |
326 | 35.1k | const CurveGFp& get_curve() const { return m_curve; } |
327 | | |
328 | | private: |
329 | | CurveGFp m_curve; |
330 | | BigInt m_coord_x, m_coord_y, m_coord_z; |
331 | | }; |
332 | | |
333 | | /** |
334 | | * Point multiplication operator |
335 | | * @param scalar the scalar value |
336 | | * @param point the point value |
337 | | * @return scalar*point on the curve |
338 | | */ |
339 | | BOTAN_PUBLIC_API(2,0) PointGFp operator*(const BigInt& scalar, const PointGFp& point); |
340 | | |
341 | | /** |
342 | | * ECC point multiexponentiation - not constant time! |
343 | | * @param p1 a point |
344 | | * @param z1 a scalar |
345 | | * @param p2 a point |
346 | | * @param z2 a scalar |
347 | | * @result (p1 * z1 + p2 * z2) |
348 | | */ |
349 | | BOTAN_PUBLIC_API(2,0) PointGFp multi_exponentiate( |
350 | | const PointGFp& p1, const BigInt& z1, |
351 | | const PointGFp& p2, const BigInt& z2); |
352 | | |
353 | | // relational operators |
354 | | inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) |
355 | 14.7k | { |
356 | 14.7k | return !(rhs == lhs); |
357 | 14.7k | } |
358 | | |
359 | | // arithmetic operators |
360 | | inline PointGFp operator-(const PointGFp& lhs) |
361 | 0 | { |
362 | 0 | return PointGFp(lhs).negate(); |
363 | 0 | } |
364 | | |
365 | | inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs) |
366 | 11.0k | { |
367 | 11.0k | PointGFp tmp(lhs); |
368 | 11.0k | return tmp += rhs; |
369 | 11.0k | } |
370 | | |
371 | | inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs) |
372 | 0 | { |
373 | 0 | PointGFp tmp(lhs); |
374 | 0 | return tmp -= rhs; |
375 | 0 | } |
376 | | |
377 | | inline PointGFp operator*(const PointGFp& point, const BigInt& scalar) |
378 | 5.83k | { |
379 | 5.83k | return scalar * point; |
380 | 5.83k | } |
381 | | |
382 | | // encoding and decoding |
383 | | inline secure_vector<uint8_t> BOTAN_DEPRECATED("Use PointGFp::encode") |
384 | | EC2OSP(const PointGFp& point, uint8_t format) |
385 | 0 | { |
386 | 0 | std::vector<uint8_t> enc = point.encode(static_cast<PointGFp::Compression_Type>(format)); |
387 | 0 | return secure_vector<uint8_t>(enc.begin(), enc.end()); |
388 | 0 | } |
389 | | |
390 | | /** |
391 | | * Perform point decoding |
392 | | * Use EC_Group::OS2ECP instead |
393 | | */ |
394 | | PointGFp BOTAN_PUBLIC_API(2,0) OS2ECP(const uint8_t data[], size_t data_len, |
395 | | const CurveGFp& curve); |
396 | | |
397 | | /** |
398 | | * Perform point decoding |
399 | | * Use EC_Group::OS2ECP instead |
400 | | * |
401 | | * @param data the encoded point |
402 | | * @param data_len length of data in bytes |
403 | | * @param curve_p the curve equation prime |
404 | | * @param curve_a the curve equation a parameter |
405 | | * @param curve_b the curve equation b parameter |
406 | | */ |
407 | | std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API OS2ECP(const uint8_t data[], size_t data_len, |
408 | | const BigInt& curve_p, |
409 | | const BigInt& curve_a, |
410 | | const BigInt& curve_b); |
411 | | |
412 | | template<typename Alloc> |
413 | | PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve) |
414 | | { return OS2ECP(data.data(), data.size(), curve); } |
415 | | |
416 | | class PointGFp_Var_Point_Precompute; |
417 | | |
418 | | /** |
419 | | * Deprecated API for point multiplication |
420 | | * Use EC_Group::blinded_base_point_multiply or EC_Group::blinded_var_point_multiply |
421 | | */ |
422 | | class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use alternative APIs") Blinded_Point_Multiply final |
423 | | { |
424 | | public: |
425 | | Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0); |
426 | | |
427 | | ~Blinded_Point_Multiply(); |
428 | | |
429 | | PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng); |
430 | | private: |
431 | | std::vector<BigInt> m_ws; |
432 | | const BigInt& m_order; |
433 | | std::unique_ptr<PointGFp_Var_Point_Precompute> m_point_mul; |
434 | | }; |
435 | | |
436 | | } |
437 | | |
438 | | namespace std { |
439 | | |
440 | | template<> |
441 | | inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) |
442 | 0 | { x.swap(y); } |
443 | | |
444 | | } |
445 | | |
446 | | #endif |