Coverage Report

Created: 2020-05-23 13:54

/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