/src/botan/build/include/botan/point_gfp.h

Source (jump to first uncovered line)
/*
* Point arithmetic on elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
*     2008-2011,2014,2015 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#ifndef BOTAN_POINT_GFP_H_
#define BOTAN_POINT_GFP_H_

#include <botan/curve_gfp.h>
#include <botan/exceptn.h>
#include <vector>

namespace Botan {

/**
* This class represents one point on a curve of GF(p)
*/
class BOTAN_PUBLIC_API(2,0) PointGFp final
   {
   public:
      enum Compression_Type {
         UNCOMPRESSED = 0,
         COMPRESSED   = 1,
         HYBRID       = 2
      };

      enum { WORKSPACE_SIZE = 8 };

      /**
      * Construct an uninitialized PointGFp
      */
      PointGFp() = default;

      /**
      * Construct the zero point
      * @param curve The base curve
      */
      explicit PointGFp(const CurveGFp& curve);

      /**
      * Copy constructor
      */
      PointGFp(const PointGFp&) = default;

      /**
      * Move Constructor
      */
      PointGFp(PointGFp&& other)
         {
         this->swap(other);
         }

      /**
      * Standard Assignment
      */
      PointGFp& operator=(const PointGFp&) = default;

      /**
      * Move Assignment
      */
      PointGFp& operator=(PointGFp&& other)
         {
         if(this != &other)
            this->swap(other);
         return (*this);
         }

      /**
      * Construct a point from its affine coordinates
      * Prefer EC_Group::point(x,y) for this operation.
      * @param curve the base curve
      * @param x affine x coordinate
      * @param y affine y coordinate
      */
      PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);

      /**
      * EC2OSP - elliptic curve to octet string primitive
      * @param format which format to encode using
      */
      std::vector<uint8_t> encode(PointGFp::Compression_Type format) const;

      /**
      * += Operator
      * @param rhs the PointGFp to add to the local value
      * @result resulting PointGFp
      */
      PointGFp& operator+=(const PointGFp& rhs);

      /**
      * -= Operator
      * @param rhs the PointGFp to subtract from the local value
      * @result resulting PointGFp
      */
      PointGFp& operator-=(const PointGFp& rhs);

      /**
      * *= Operator
      * @param scalar the PointGFp to multiply with *this
      * @result resulting PointGFp
      */
      PointGFp& operator*=(const BigInt& scalar);

      /**
      * Negate this point
      * @return *this
      */
      PointGFp& negate()
         {
         if(!is_zero())
            m_coord_y = m_curve.get_p() - m_coord_y;
         return *this;
         }

      /**
      * get affine x coordinate
      * @result affine x coordinate
      */
      BigInt get_affine_x() const;

      /**
      * get affine y coordinate
      * @result affine y coordinate
      */
      BigInt get_affine_y() const;

      const BigInt& get_x() const { return m_coord_x; }
      const BigInt& get_y() const { return m_coord_y; }
      const BigInt& get_z() const { return m_coord_z; }

      void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
         {
         m_coord_x.swap(new_x);
         m_coord_y.swap(new_y);
         m_coord_z.swap(new_z);
         }

      /**
      * Force this point to affine coordinates
      */
      void force_affine();

      /**
      * Force all points on the list to affine coordinates
      */
      static void force_all_affine(std::vector<PointGFp>& points,
                                   secure_vector<word>& ws);

      bool is_affine() const;

      /**
      * Is this the point at infinity?
      * @result true, if this point is at infinity, false otherwise.
      */
      bool is_zero() const { return m_coord_z.is_zero(); }

      /**
      * Checks whether the point is to be found on the underlying
      * curve; used to prevent fault attacks.
      * @return if the point is on the curve
      */
      bool on_the_curve() const;

      /**
      * swaps the states of *this and other, does not throw!
      * @param other the object to swap values with
      */
      void swap(PointGFp& other);

      /**
      * Randomize the point representation
      * The actual value (get_affine_x, get_affine_y) does not change
      */
      void randomize_repr(RandomNumberGenerator& rng);

      /**
      * Randomize the point representation
      * The actual value (get_affine_x, get_affine_y) does not change
      */
      void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws);

      /**
      * Equality operator
      */
      bool operator==(const PointGFp& other) const;

      /**
      * Point addition
      * @param other the point to add to *this
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void add(const PointGFp& other, std::vector<BigInt>& workspace)
         {
         BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);

         const size_t p_words = m_curve.get_p_words();

         add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
             other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
             other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()),
             workspace);
         }

      /**
      * Point addition. Array version.
      *
      * @param x_words the words of the x coordinate of the other point
      * @param x_size size of x_words
      * @param y_words the words of the y coordinate of the other point
      * @param y_size size of y_words
      * @param z_words the words of the z coordinate of the other point
      * @param z_size size of z_words
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void add(const word x_words[], size_t x_size,
               const word y_words[], size_t y_size,
               const word z_words[], size_t z_size,
               std::vector<BigInt>& workspace);

      /**
      * Point addition - mixed J+A
      * @param other affine point to add - assumed to be affine!
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void add_affine(const PointGFp& other, std::vector<BigInt>& workspace)
         {
         BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
         BOTAN_DEBUG_ASSERT(other.is_affine());

         const size_t p_words = m_curve.get_p_words();
         add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
                    other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
                    workspace);
         }

      /**
      * Point addition - mixed J+A. Array version.
      *
      * @param x_words the words of the x coordinate of the other point
      * @param x_size size of x_words
      * @param y_words the words of the y coordinate of the other point
      * @param y_size size of y_words
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void add_affine(const word x_words[], size_t x_size,
                      const word y_words[], size_t y_size,
                      std::vector<BigInt>& workspace);

      /**
      * Point doubling
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void mult2(std::vector<BigInt>& workspace);

      /**
      * Repeated point doubling
      * @param i number of doublings to perform
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      */
      void mult2i(size_t i, std::vector<BigInt>& workspace);

      /**
      * Point addition
      * @param other the point to add to *this
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      * @return other plus *this
      */
      PointGFp plus(const PointGFp& other, std::vector<BigInt>& workspace) const
         {
         PointGFp x = (*this);
         x.add(other, workspace);
         return x;
         }

      /**
      * Point doubling
      * @param workspace temp space, at least WORKSPACE_SIZE elements
      * @return *this doubled
      */
      PointGFp double_of(std::vector<BigInt>& workspace) const
         {
         PointGFp x = (*this);
         x.mult2(workspace);
         return x;
         }

      /**
      * Return the zero (aka infinite) point associated with this curve
      */
      PointGFp zero() const { return PointGFp(m_curve); }

      /**
      * Return base curve of this point
      * @result the curve over GF(p) of this point
      *
      * You should not need to use this
      */
      const CurveGFp& get_curve() const { return m_curve; }

   private:
      CurveGFp m_curve;
      BigInt m_coord_x, m_coord_y, m_coord_z;
   };

/**
* Point multiplication operator
* @param scalar the scalar value
* @param point the point value
* @return scalar*point on the curve
*/
BOTAN_PUBLIC_API(2,0) PointGFp operator*(const BigInt& scalar, const PointGFp& point);

/**
* ECC point multiexponentiation - not constant time!
* @param p1 a point
* @param z1 a scalar
* @param p2 a point
* @param z2 a scalar
* @result (p1 * z1 + p2 * z2)
*/
BOTAN_PUBLIC_API(2,0) PointGFp multi_exponentiate(
   const PointGFp& p1, const BigInt& z1,
   const PointGFp& p2, const BigInt& z2);

// relational operators
inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
   {
   return !(rhs == lhs);
   }

// arithmetic operators
inline PointGFp operator-(const PointGFp& lhs)
   {
   return PointGFp(lhs).negate();
   }

inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
   {
   PointGFp tmp(lhs);
   return tmp += rhs;
   }

inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
   {
   PointGFp tmp(lhs);
   return tmp -= rhs;
   }

inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
   {
   return scalar * point;
   }

/**
* Perform point decoding
* Use EC_Group::OS2ECP instead
*/
PointGFp BOTAN_PUBLIC_API(2,0) OS2ECP(const uint8_t data[], size_t data_len,
                                      const CurveGFp& curve);

/**
* Perform point decoding
* Use EC_Group::OS2ECP instead
*
* @param data the encoded point
* @param data_len length of data in bytes
* @param curve_p the curve equation prime
* @param curve_a the curve equation a parameter
* @param curve_b the curve equation b parameter
*/
std::pair<BigInt, BigInt> BOTAN_UNSTABLE_API OS2ECP(const uint8_t data[], size_t data_len,
                                                    const BigInt& curve_p,
                                                    const BigInt& curve_a,
                                                    const BigInt& curve_b);

template<typename Alloc>
PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
   { return OS2ECP(data.data(), data.size(), curve); }

class PointGFp_Var_Point_Precompute;

}

namespace std {

template<>
inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
   { x.swap(y); }

}

#endif

Coverage Report

Created: 2022-01-14 08:07

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	2.80M	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.86M	PointGFp(const PointGFp&) = default;
48
49		/**
50		* Move Constructor
51		*/
52		PointGFp(PointGFp&& other)
53	20.8k	{
54	20.8k	this->swap(other);
55	20.8k	}
56
57		/**
58		* Standard Assignment
59		*/
60	1.34M	PointGFp& operator=(const PointGFp&) = default;
61
62		/**
63		* Move Assignment
64		*/
65		PointGFp& operator=(PointGFp&& other)
66	2.10M	{
67	2.10M	if(this != &other)
68	2.10M	this->swap(other);
69	2.10M	return (*this);
70	2.10M	}
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	3.20M	const BigInt& get_x() const { return m_coord_x; }
132	3.20M	const BigInt& get_y() const { return m_coord_y; }
133	909k	const BigInt& get_z() const { return m_coord_z; }
134
135		void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
136	440k	{
137	440k	m_coord_x.swap(new_x);
138	440k	m_coord_y.swap(new_y);
139	440k	m_coord_z.swap(new_z);
140	440k	}
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	34.5M	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	2.93M	{
198	2.93M	BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
199
200	2.93M	const size_t p_words = m_curve.get_p_words();
201
202	2.93M	add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
203	2.93M	other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
204	2.93M	other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()),
205	2.93M	workspace);
206	2.93M	}
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	29.3k	{
231	29.3k	BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
232	29.3k	BOTAN_DEBUG_ASSERT(other.is_affine());
233
234	29.3k	const size_t p_words = m_curve.get_p_words();
235	29.3k	add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
236	29.3k	other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
237	29.3k	workspace);
238	29.3k	}
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	1.53M	{
274	1.53M	PointGFp x = (*this);
275	1.53M	x.add(other, workspace);
276	1.53M	return x;
277	1.53M	}
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	205k	{
286	205k	PointGFp x = (*this);
287	205k	x.mult2(workspace);
288	205k	return x;
289	205k	}
290
291		/**
292		* Return the zero (aka infinite) point associated with this curve
293		*/
294	90.0k	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	63.3k	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	43.8k	{
332	43.8k	return !(rhs == lhs);
333	43.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	32.8k	{
343	32.8k	PointGFp tmp(lhs);
344	32.8k	return tmp += rhs;
345	32.8k	}
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	16.8k	{
355	16.8k	return scalar * point;
356	16.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