Botan  1.10.9
point_gfp.h
Go to the documentation of this file.
1 /*
2 * Point arithmetic on elliptic curves over GF(p)
3 *
4 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5 * 2008-2011 Jack Lloyd
6 *
7 * Distributed under the terms of the Botan license
8 */
9 
10 #ifndef BOTAN_POINT_GFP_H__
11 #define BOTAN_POINT_GFP_H__
12 
13 #include <botan/curve_gfp.h>
14 #include <vector>
15 
16 namespace Botan {
17 
18 /**
19 * Exception thrown if you try to convert a zero point to an affine
20 * coordinate
21 */
22 struct BOTAN_DLL Illegal_Transformation : public Exception
23  {
24  Illegal_Transformation(const std::string& err =
25  "Requested transformation is not possible") :
26  Exception(err) {}
27  };
28 
29 /**
30 * Exception thrown if some form of illegal point is decoded
31 */
32 struct BOTAN_DLL Illegal_Point : public Exception
33  {
34  Illegal_Point(const std::string& err = "Malformed ECP point detected") :
35  Exception(err) {}
36  };
37 
38 /**
39 * This class represents one point on a curve of GF(p)
40 */
41 class BOTAN_DLL PointGFp
42  {
43  public:
45  UNCOMPRESSED = 0,
46  COMPRESSED = 1,
47  HYBRID = 2
48  };
49 
50  /**
51  * Construct an uninitialized PointGFp
52  */
53  PointGFp() {}
54 
55  /**
56  * Construct the zero point
57  * @param curve The base curve
58  */
59  PointGFp(const CurveGFp& curve);
60 
61  /**
62  * Construct a point from its affine coordinates
63  * @param curve the base curve
64  * @param x affine x coordinate
65  * @param y affine y coordinate
66  */
67  PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);
68 
69  //PointGFp(const PointGFp& other) = default;
70  //PointGFp& operator=(const PointGFp& other) = default;
71 
72  /**
73  * += Operator
74  * @param rhs the PointGFp to add to the local value
75  * @result resulting PointGFp
76  */
77  PointGFp& operator+=(const PointGFp& rhs);
78 
79  /**
80  * -= Operator
81  * @param rhs the PointGFp to subtract from the local value
82  * @result resulting PointGFp
83  */
84  PointGFp& operator-=(const PointGFp& rhs);
85 
86  /**
87  * *= Operator
88  * @param scalar the PointGFp to multiply with *this
89  * @result resulting PointGFp
90  */
91  PointGFp& operator*=(const BigInt& scalar);
92 
93  /**
94  * Multiplication Operator
95  * @param scalar the scalar value
96  * @param point the point value
97  * @return scalar*point on the curve
98  */
99  friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point);
100 
101  /**
102  * Multiexponentiation
103  * @param p1 a point
104  * @param z1 a scalar
105  * @param p2 a point
106  * @param z2 a scalar
107  * @result (p1 * z1 + p2 * z2)
108  */
109  friend BOTAN_DLL PointGFp multi_exponentiate(
110  const PointGFp& p1, const BigInt& z1,
111  const PointGFp& p2, const BigInt& z2);
112 
113  /**
114  * Negate this point
115  * @return *this
116  */
118  {
119  if(!is_zero())
120  coord_y = curve.get_p() - coord_y;
121  return *this;
122  }
123 
124  /**
125  * Return base curve of this point
126  * @result the curve over GF(p) of this point
127  */
128  const CurveGFp& get_curve() const { return curve; }
129 
130  /**
131  * get affine x coordinate
132  * @result affine x coordinate
133  */
134  BigInt get_affine_x() const;
135 
136  /**
137  * get affine y coordinate
138  * @result affine y coordinate
139  */
140  BigInt get_affine_y() const;
141 
142  /**
143  * Is this the point at infinity?
144  * @result true, if this point is at infinity, false otherwise.
145  */
146  bool is_zero() const
147  { return (coord_x.is_zero() && coord_z.is_zero()); }
148 
149  /**
150  * Checks whether the point is to be found on the underlying
151  * curve; used to prevent fault attacks.
152  * @return if the point is on the curve
153  */
154  bool on_the_curve() const;
155 
156  /**
157  * swaps the states of *this and other, does not throw!
158  * @param other the object to swap values with
159  */
160  void swap(PointGFp& other);
161 
162  /**
163  * Equality operator
164  */
165  bool operator==(const PointGFp& other) const;
166  private:
167 
168  /**
169  * Montgomery multiplication/reduction
170  * @param x first multiplicand
171  * @param y second multiplicand
172  * @param workspace temp space
173  */
174  BigInt monty_mult(const BigInt& x, const BigInt& y) const
175  {
176  BigInt result;
177  monty_mult(result, x, y);
178  return result;
179  }
180 
181  /**
182  * Montgomery multiplication/reduction
183  * @warning z cannot alias x or y
184  * @param z output
185  * @param x first multiplicand
186  * @param y second multiplicand
187  */
188  void monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const;
189 
190  /**
191  * Montgomery squaring/reduction
192  * @param x multiplicand
193  */
194  BigInt monty_sqr(const BigInt& x) const
195  {
196  BigInt result;
197  monty_sqr(result, x);
198  return result;
199  }
200 
201  /**
202  * Montgomery squaring/reduction
203  * @warning z cannot alias x
204  * @param z output
205  * @param x multiplicand
206  */
207  void monty_sqr(BigInt& z, const BigInt& x) const;
208 
209  /**
210  * Point addition
211  * @param workspace temp space, at least 11 elements
212  */
213  void add(const PointGFp& other, std::vector<BigInt>& workspace);
214 
215  /**
216  * Point doubling
217  * @param workspace temp space, at least 9 elements
218  */
219  void mult2(std::vector<BigInt>& workspace);
220 
221  CurveGFp curve;
222  BigInt coord_x, coord_y, coord_z;
223  mutable SecureVector<word> ws; // workspace for Montgomery
224  };
225 
226 // relational operators
227 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
228  {
229  return !(rhs == lhs);
230  }
231 
232 // arithmetic operators
233 inline PointGFp operator-(const PointGFp& lhs)
234  {
235  return PointGFp(lhs).negate();
236  }
237 
238 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs)
239  {
240  PointGFp tmp(lhs);
241  return tmp += rhs;
242  }
243 
244 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs)
245  {
246  PointGFp tmp(lhs);
247  return tmp -= rhs;
248  }
249 
250 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar)
251  {
252  return scalar * point;
253  }
254 
255 // encoding and decoding
256 SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format);
257 
258 PointGFp BOTAN_DLL OS2ECP(const byte data[], size_t data_len,
259  const CurveGFp& curve);
260 
261 inline PointGFp OS2ECP(const MemoryRegion<byte>& data, const CurveGFp& curve)
262  { return OS2ECP(&data[0], data.size(), curve); }
263 
264 }
265 
266 namespace std {
267 
268 template<>
269 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y)
270  { x.swap(y); }
271 
272 }
273 
274 #endif
bool operator!=(const OctetString &s1, const OctetString &s2)
Definition: symkey.cpp:106
PointGFp OS2ECP(const byte data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:554
Illegal_Point(const std::string &err="Malformed ECP point detected")
Definition: point_gfp.h:34
bool operator==(const OctetString &s1, const OctetString &s2)
Definition: symkey.cpp:98
Definition: secmem.h:422
const CurveGFp & get_curve() const
Definition: point_gfp.h:128
unsigned char byte
Definition: types.h:22
SecureVector< byte > EC2OSP(const PointGFp &point, byte format)
Definition: point_gfp.cpp:482
Illegal_Transformation(const std::string &err="Requested transformation is not possible")
Definition: point_gfp.h:24
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition: symkey.cpp:114
PointGFp & negate()
Definition: point_gfp.h:117
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:83
std::runtime_error Exception
Definition: exceptn.h:19
size_t size() const
Definition: secmem.h:29
MemoryRegion< T > & operator+=(MemoryRegion< T > &out, const MemoryRegion< T > &in)
Definition: secmem.h:373
bool is_zero() const
Definition: point_gfp.h:146
void swap(Botan::MemoryRegion< T > &x, Botan::MemoryRegion< T > &y)
Definition: secmem.h:425
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:48
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:257