Botan
1.11.15
|
00001 /* 00002 * Point arithmetic on elliptic curves over GF(p) 00003 * 00004 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke 00005 * 2008-2011,2014 Jack Lloyd 00006 * 00007 * Botan is released under the Simplified BSD License (see license.txt) 00008 */ 00009 00010 #ifndef BOTAN_POINT_GFP_H__ 00011 #define BOTAN_POINT_GFP_H__ 00012 00013 #include <botan/curve_gfp.h> 00014 #include <vector> 00015 00016 namespace Botan { 00017 00018 /** 00019 * Exception thrown if you try to convert a zero point to an affine 00020 * coordinate 00021 */ 00022 struct BOTAN_DLL Illegal_Transformation : public Exception 00023 { 00024 Illegal_Transformation(const std::string& err = 00025 "Requested transformation is not possible") : 00026 Exception(err) {} 00027 }; 00028 00029 /** 00030 * Exception thrown if some form of illegal point is decoded 00031 */ 00032 struct BOTAN_DLL Illegal_Point : public Exception 00033 { 00034 Illegal_Point(const std::string& err = "Malformed ECP point detected") : 00035 Exception(err) {} 00036 }; 00037 00038 /** 00039 * This class represents one point on a curve of GF(p) 00040 */ 00041 class BOTAN_DLL PointGFp 00042 { 00043 public: 00044 enum Compression_Type { 00045 UNCOMPRESSED = 0, 00046 COMPRESSED = 1, 00047 HYBRID = 2 00048 }; 00049 00050 /** 00051 * Construct an uninitialized PointGFp 00052 */ 00053 PointGFp() {} 00054 00055 /** 00056 * Construct the zero point 00057 * @param curve The base curve 00058 */ 00059 PointGFp(const CurveGFp& curve); 00060 00061 /** 00062 * Copy constructor 00063 */ 00064 PointGFp(const PointGFp&) = default; 00065 00066 /** 00067 * Move Constructor 00068 */ 00069 PointGFp(PointGFp&& other) 00070 { 00071 this->swap(other); 00072 } 00073 00074 /** 00075 * Standard Assignment 00076 */ 00077 PointGFp& operator=(const PointGFp&) = default; 00078 00079 /** 00080 * Move Assignment 00081 */ 00082 PointGFp& operator=(PointGFp&& other) 00083 { 00084 if(this != &other) 00085 this->swap(other); 00086 return (*this); 00087 } 00088 00089 /** 00090 * Construct a point from its affine coordinates 00091 * @param curve the base curve 00092 * @param x affine x coordinate 00093 * @param y affine y coordinate 00094 */ 00095 PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y); 00096 00097 /** 00098 * += Operator 00099 * @param rhs the PointGFp to add to the local value 00100 * @result resulting PointGFp 00101 */ 00102 PointGFp& operator+=(const PointGFp& rhs); 00103 00104 /** 00105 * -= Operator 00106 * @param rhs the PointGFp to subtract from the local value 00107 * @result resulting PointGFp 00108 */ 00109 PointGFp& operator-=(const PointGFp& rhs); 00110 00111 /** 00112 * *= Operator 00113 * @param scalar the PointGFp to multiply with *this 00114 * @result resulting PointGFp 00115 */ 00116 PointGFp& operator*=(const BigInt& scalar); 00117 00118 /** 00119 * Multiplication Operator 00120 * @param scalar the scalar value 00121 * @param point the point value 00122 * @return scalar*point on the curve 00123 */ 00124 friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point); 00125 00126 /** 00127 * Multiexponentiation 00128 * @param p1 a point 00129 * @param z1 a scalar 00130 * @param p2 a point 00131 * @param z2 a scalar 00132 * @result (p1 * z1 + p2 * z2) 00133 */ 00134 friend BOTAN_DLL PointGFp multi_exponentiate( 00135 const PointGFp& p1, const BigInt& z1, 00136 const PointGFp& p2, const BigInt& z2); 00137 00138 /** 00139 * Negate this point 00140 * @return *this 00141 */ 00142 PointGFp& negate() 00143 { 00144 if(!is_zero()) 00145 coord_y = curve.get_p() - coord_y; 00146 return *this; 00147 } 00148 00149 /** 00150 * Return base curve of this point 00151 * @result the curve over GF(p) of this point 00152 */ 00153 const CurveGFp& get_curve() const { return curve; } 00154 00155 /** 00156 * get affine x coordinate 00157 * @result affine x coordinate 00158 */ 00159 BigInt get_affine_x() const; 00160 00161 /** 00162 * get affine y coordinate 00163 * @result affine y coordinate 00164 */ 00165 BigInt get_affine_y() const; 00166 00167 /** 00168 * Is this the point at infinity? 00169 * @result true, if this point is at infinity, false otherwise. 00170 */ 00171 bool is_zero() const 00172 { return (coord_x.is_zero() && coord_z.is_zero()); } 00173 00174 /** 00175 * Checks whether the point is to be found on the underlying 00176 * curve; used to prevent fault attacks. 00177 * @return if the point is on the curve 00178 */ 00179 bool on_the_curve() const; 00180 00181 /** 00182 * swaps the states of *this and other, does not throw! 00183 * @param other the object to swap values with 00184 */ 00185 void swap(PointGFp& other); 00186 00187 /** 00188 * Equality operator 00189 */ 00190 bool operator==(const PointGFp& other) const; 00191 private: 00192 00193 BigInt curve_mult(const BigInt& x, const BigInt& y) const 00194 { 00195 BigInt z; 00196 curve.mul(z, x, y, ws); 00197 return z; 00198 } 00199 00200 void curve_mult(BigInt& z, const BigInt& x, const BigInt& y) const 00201 { 00202 curve.mul(z, x, y, ws); 00203 } 00204 00205 BigInt curve_sqr(const BigInt& x) const 00206 { 00207 BigInt z; 00208 curve.sqr(z, x, ws); 00209 return z; 00210 } 00211 00212 void curve_sqr(BigInt& z, const BigInt& x) const 00213 { 00214 curve.sqr(z, x, ws); 00215 } 00216 00217 /** 00218 * Point addition 00219 * @param workspace temp space, at least 11 elements 00220 */ 00221 void add(const PointGFp& other, std::vector<BigInt>& workspace); 00222 00223 /** 00224 * Point doubling 00225 * @param workspace temp space, at least 9 elements 00226 */ 00227 void mult2(std::vector<BigInt>& workspace); 00228 00229 CurveGFp curve; 00230 BigInt coord_x, coord_y, coord_z; 00231 mutable secure_vector<word> ws; // workspace for Montgomery 00232 }; 00233 00234 // relational operators 00235 inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) 00236 { 00237 return !(rhs == lhs); 00238 } 00239 00240 // arithmetic operators 00241 inline PointGFp operator-(const PointGFp& lhs) 00242 { 00243 return PointGFp(lhs).negate(); 00244 } 00245 00246 inline PointGFp operator+(const PointGFp& lhs, const PointGFp& rhs) 00247 { 00248 PointGFp tmp(lhs); 00249 return tmp += rhs; 00250 } 00251 00252 inline PointGFp operator-(const PointGFp& lhs, const PointGFp& rhs) 00253 { 00254 PointGFp tmp(lhs); 00255 return tmp -= rhs; 00256 } 00257 00258 inline PointGFp operator*(const PointGFp& point, const BigInt& scalar) 00259 { 00260 return scalar * point; 00261 } 00262 00263 // encoding and decoding 00264 secure_vector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); 00265 00266 PointGFp BOTAN_DLL OS2ECP(const byte data[], size_t data_len, 00267 const CurveGFp& curve); 00268 00269 template<typename Alloc> 00270 PointGFp OS2ECP(const std::vector<byte, Alloc>& data, const CurveGFp& curve) 00271 { return OS2ECP(&data[0], data.size(), curve); } 00272 00273 } 00274 00275 namespace std { 00276 00277 template<> 00278 inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) 00279 { x.swap(y); } 00280 00281 } 00282 00283 #endif