Coverage Report

Created: 2020-11-21 08:34

/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.78M
      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.23M
      PointGFp(const PointGFp&) = default;
48
49
      /**
50
      * Move Constructor
51
      */
52
      PointGFp(PointGFp&& other)
53
25.5k
         {
54
25.5k
         this->swap(other);
55
25.5k
         }
56
57
      /**
58
      * Standard Assignment
59
      */
60
819k
      PointGFp& operator=(const PointGFp&) = default;
61
62
      /**
63
      * Move Assignment
64
      */
65
      PointGFp& operator=(PointGFp&& other)
66
1.36M
         {
67
1.36M
         if(this != &other)
68
1.36M
            this->swap(other);
69
1.36M
         return (*this);
70
1.36M
         }
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.09M
      const BigInt& get_x() const { return m_coord_x; }
132
2.09M
      const BigInt& get_y() const { return m_coord_y; }
133
724k
      const BigInt& get_z() const { return m_coord_z; }
134
135
      void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
136
350k
         {
137
350k
         m_coord_x.swap(new_x);
138
350k
         m_coord_y.swap(new_y);
139
350k
         m_coord_z.swap(new_z);
140
350k
         }
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
27.3M
      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.60M
         {
198
1.60M
         BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
199
200
1.60M
         const size_t p_words = m_curve.get_p_words();
201
202
1.60M
         add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
203
1.60M
             other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
204
1.60M
             other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()),
205
1.60M
             workspace);
206
1.60M
         }
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
32.9k
         {
231
32.9k
         BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
232
32.9k
         BOTAN_DEBUG_ASSERT(other.is_affine());
233
234
32.9k
         const size_t p_words = m_curve.get_p_words();
235
32.9k
         add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
236
32.9k
                    other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
237
32.9k
                    workspace);
238
32.9k
         }
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
971k
         {
274
971k
         PointGFp x = (*this);
275
971k
         x.add(other, workspace);
276
971k
         return x;
277
971k
         }
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
163k
         {
286
163k
         PointGFp x = (*this);
287
163k
         x.mult2(workspace);
288
163k
         return x;
289
163k
         }
290
291
      /**
292
      * Return the zero (aka infinite) point associated with this curve
293
      */
294
74.1k
      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
49.5k
      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
26.8k
   {
332
26.8k
   return !(rhs == lhs);
333
26.8k
   }
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
20.1k
   {
343
20.1k
   PointGFp tmp(lhs);
344
20.1k
   return tmp += rhs;
345
20.1k
   }
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.4k
   {
355
10.4k
   return scalar * point;
356
10.4k
   }
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