/* * 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 #include namespace Botan { /** * Exception thrown if you try to convert a zero point to an affine * coordinate */ struct BOTAN_DLL Illegal_Transformation : public Exception { Illegal_Transformation(const std::string& err = "Requested transformation is not possible") : Exception(err) {} }; /** * Exception thrown if some form of illegal point is decoded */ struct BOTAN_DLL Illegal_Point : public Exception { Illegal_Point(const std::string& err = "Malformed ECP point detected") : Exception(err) {} }; /** * This class represents one point on a curve of GF(p) */ class BOTAN_DLL PointGFp { public: enum Compression_Type { UNCOMPRESSED = 0, COMPRESSED = 1, HYBRID = 2 }; /** * Construct an uninitialized PointGFp */ PointGFp() {} /** * Construct the zero point * @param curve The base curve */ PointGFp(const CurveGFp& curve); static PointGFp zero_of(const CurveGFp& curve) { return PointGFp(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 * @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); /** * += 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); /** * Multiplication Operator * @param scalar the scalar value * @param point the point value * @return scalar*point on the curve */ friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point); /** * Multiexponentiation * @param p1 a point * @param z1 a scalar * @param p2 a point * @param z2 a scalar * @result (p1 * z1 + p2 * z2) */ friend BOTAN_DLL PointGFp multi_exponentiate( const PointGFp& p1, const BigInt& z1, const PointGFp& p2, const BigInt& z2); /** * Negate this point * @return *this */ PointGFp& negate() { if(!is_zero()) m_coord_y = m_curve.get_p() - m_coord_y; return *this; } /** * Return base curve of this point * @result the curve over GF(p) of this point */ const CurveGFp& get_curve() const { return m_curve; } /** * 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; /** * Is this the point at infinity? * @result true, if this point is at infinity, false otherwise. */ bool is_zero() const { return (m_coord_x.is_zero() && 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); /** * Equality operator */ bool operator==(const PointGFp& other) const; private: friend class Blinded_Point_Multiply; BigInt curve_mult(const BigInt& x, const BigInt& y) const { BigInt z; m_curve.mul(z, x, y, m_monty_ws); return z; } void curve_mult(BigInt& z, const BigInt& x, const BigInt& y) const { m_curve.mul(z, x, y, m_monty_ws); } BigInt curve_sqr(const BigInt& x) const { BigInt z; m_curve.sqr(z, x, m_monty_ws); return z; } void curve_sqr(BigInt& z, const BigInt& x) const { m_curve.sqr(z, x, m_monty_ws); } /** * Point addition * @param workspace temp space, at least 11 elements */ void add(const PointGFp& other, std::vector& workspace); /** * Point doubling * @param workspace temp space, at least 9 elements */ void mult2(std::vector& workspace); CurveGFp m_curve; BigInt m_coord_x, m_coord_y, m_coord_z; mutable secure_vector m_monty_ws; // workspace for Montgomery }; // 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; } // encoding and decoding secure_vector BOTAN_DLL EC2OSP(const PointGFp& point, byte format); PointGFp BOTAN_DLL OS2ECP(const byte data[], size_t data_len, const CurveGFp& curve); template PointGFp OS2ECP(const std::vector& data, const CurveGFp& curve) { return OS2ECP(data.data(), data.size(), curve); } /** */ class BOTAN_DLL Blinded_Point_Multiply { public: Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0); PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng); private: const size_t m_h; const BigInt& m_order; std::vector m_ws; std::vector m_U; }; } namespace std { template<> inline void swap(Botan::PointGFp& x, Botan::PointGFp& y) { x.swap(y); } } #endif