Botan  1.11.15
src/lib/math/ec_gfp/point_gfp.h
Go to the documentation of this file.
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