Coverage Report

Created: 2019-09-11 14:12

/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