/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 | | * This class represents one point on a curve of GF(p) |
21 | | */ |
22 | | class BOTAN_PUBLIC_API(2,0) PointGFp final |
23 | | { |
24 | | public: |
25 | | enum Compression_Type { |
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 | 1.76M | 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 | 1.17M | PointGFp(const PointGFp&) = default; |
48 | | |
49 | | /** |
50 | | * Move Constructor |
51 | | */ |
52 | | PointGFp(PointGFp&& other) |
53 | 13.4k | { |
54 | 13.4k | this->swap(other); |
55 | 13.4k | } |
56 | | |
57 | | /** |
58 | | * Standard Assignment |
59 | | */ |
60 | 832k | PointGFp& operator=(const PointGFp&) = default; |
61 | | |
62 | | /** |
63 | | * Move Assignment |
64 | | */ |
65 | | PointGFp& operator=(PointGFp&& other) |
66 | 1.33M | { |
67 | 1.33M | if(this != &other) |
68 | 1.33M | this->swap(other); |
69 | 1.33M | return (*this); |
70 | 1.33M | } |
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 | | */ |
112 | | PointGFp& negate() |
113 | 0 | { |
114 | 0 | if(!is_zero()) |
115 | 0 | m_coord_y = m_curve.get_p() - m_coord_y; |
116 | 0 | return *this; |
117 | 0 | } |
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 | 2.02M | const BigInt& get_x() const { return m_coord_x; } |
132 | 2.02M | const BigInt& get_y() const { return m_coord_y; } |
133 | 617k | const BigInt& get_z() const { return m_coord_z; } |
134 | | |
135 | | void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) |
136 | 298k | { |
137 | 298k | m_coord_x.swap(new_x); |
138 | 298k | m_coord_y.swap(new_y); |
139 | 298k | m_coord_z.swap(new_z); |
140 | 298k | } |
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, |
151 | | secure_vector<word>& ws); |
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 | 25.2M | 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 | 1.47M | { |
198 | 1.47M | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
199 | | |
200 | 1.47M | const size_t p_words = m_curve.get_p_words(); |
201 | | |
202 | 1.47M | add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
203 | 1.47M | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
204 | 1.47M | other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()), |
205 | 1.47M | workspace); |
206 | 1.47M | } |
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 | 15.8k | { |
231 | 15.8k | BOTAN_ASSERT_NOMSG(m_curve == other.m_curve); |
232 | 15.8k | BOTAN_DEBUG_ASSERT(other.is_affine()); |
233 | | |
234 | 15.8k | const size_t p_words = m_curve.get_p_words(); |
235 | 15.8k | add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()), |
236 | 15.8k | other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()), |
237 | 15.8k | workspace); |
238 | 15.8k | } |
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 | 954k | { |
274 | 954k | PointGFp x = (*this); |
275 | 954k | x.add(other, workspace); |
276 | 954k | return x; |
277 | 954k | } |
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 | 139k | { |
286 | 139k | PointGFp x = (*this); |
287 | 139k | x.mult2(workspace); |
288 | 139k | return x; |
289 | 139k | } |
290 | | |
291 | | /** |
292 | | * Return the zero (aka infinite) point associated with this curve |
293 | | */ |
294 | 70.9k | 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 | 42.7k | 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 | | */ |
315 | | BOTAN_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 | | */ |
325 | | BOTAN_PUBLIC_API(2,0) PointGFp multi_exponentiate( |
326 | | const PointGFp& p1, const BigInt& z1, |
327 | | const PointGFp& p2, const BigInt& z2); |
328 | | |
329 | | // relational operators |
330 | | inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) |
331 | 28.0k | { |
332 | 28.0k | return !(rhs == lhs); |
333 | 28.0k | } |
334 | | |
335 | | // arithmetic operators |
336 | | inline PointGFp operator-(const PointGFp& lhs) |
337 | 0 | { |
338 | 0 | return PointGFp(lhs).negate(); |
339 | 0 | } |
340 | | |
341 | | inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs) |
342 | 21.0k | { |
343 | 21.0k | PointGFp tmp(lhs); |
344 | 21.0k | return tmp += rhs; |
345 | 21.0k | } |
346 | | |
347 | | inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs) |
348 | 0 | { |
349 | 0 | PointGFp tmp(lhs); |
350 | 0 | return tmp -= rhs; |
351 | 0 | } |
352 | | |
353 | | inline PointGFp operator*(const PointGFp& point, const BigInt& scalar) |
354 | 10.8k | { |
355 | 10.8k | return scalar * point; |
356 | 10.8k | } |
357 | | |
358 | | /** |
359 | | * Perform point decoding |
360 | | * Use EC_Group::OS2ECP instead |
361 | | */ |
362 | | PointGFp 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 | | */ |
375 | | std::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 | | |
380 | | template<typename Alloc> |
381 | | PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve) |
382 | | { return OS2ECP(data.data(), data.size(), curve); } |
383 | | |
384 | | class PointGFp_Var_Point_Precompute; |
385 | | |
386 | | } |
387 | | |
388 | | namespace std { |
389 | | |
390 | | template<> |
391 | | inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) |
392 | 0 | { x.swap(y); } |
393 | | |
394 | | } |
395 | | |
396 | | #endif |