/****************************************************** * Arithmetic for prime fields GF(p) (header file) * * * * (C) 2007 Martin Döring * * doering@cdc.informatik.tu-darmstadt.de * * Christoph Ludwig * * ludwig@fh-worms.de * * Falko Strenzke * * strenzke@flexsecure.de * ******************************************************/ #ifndef BOTAN_MATH_GF_GFP_ELEMENT_H_GUARD_ #define BOTAN_MATH_GF_GFP_ELEMENT_H_GUARD_ #include #include #include namespace Botan { struct Illegal_Transformation : public Exception { Illegal_Transformation(const std::string& err = "Requested transformation is not possible") : Exception(err) {} }; /** * This class represents one element in GF(p). Enables the convenient, transparent use * of the montgomery multiplication. */ class GFpElement { private: std::tr1::shared_ptr mp_mod; mutable BigInt m_value; // ordinary residue or m-residue respectively mutable BigInt workspace; // ***************************************** // data members for montgomery multiplication mutable bool m_use_montgm; //mutable BigInt m_mres; // this bool tells use whether the m_mres carries // the actual value (in this case mValue doesn´t) mutable bool m_is_trf; void ensure_montgm_precomp() const; void trf_to_mres() const; void trf_to_ordres() const; public: /** construct an element of GF(p) with the given value. * use_montg defaults to false and determines wether Montgomery multiplications * will be use when applying operators '*' , '*='. * @param p the prime number of the field * @param value the element value * @param use_montgm whether this object will use Montgomery multiplication */ explicit GFpElement ( const BigInt& p, const BigInt& value, bool use_montgm = false ); /** construct an element of GF(p) with the given value (defaults to 0). * use_montg defaults to false and determines wether montgomery multiplications * will be use when applying operators '*' , '*='. * Use this constructor for efficient use of Montgomery multiplication in a context with a * fixed a modulus. * Warning: do not use this function unless you know in detail about * the implications of using * the shared GFpModulus objects! * @param mod shared pointer to the GFpModulus to be shared * @param value the element value * @param use_montgm whether this object will use Montgomery multiplication */ explicit GFpElement(std::tr1::shared_ptr const mod, const BigInt& value, bool use_mongm = false); /** * Copy constructor * @param other The element to clone */ GFpElement ( GFpElement const& other ); /** * Assignment operator. * makes *this a totally independent object * (gives *this independent modulus specific values). * * @param other The element to assign to our object */ GFpElement const& operator= ( GFpElement const& other ); /** * Works like the assignment operator, but lets * *this share the modulus dependend value with other. * Warning: do not use this function unless you know in detail about * the implications of using * the shared GFpModulus objects! * @param other The element to assign to our object */ void share_assign(GFpElement const& other); /** * Switch Montgomery multiplcation optimizations ON */ void turn_on_sp_red_mul() const; /** * Switch Montgomery multiplcation optimizations OFF */ void turn_off_sp_red_mul() const; /** * += Operator * @param rhs the GFpElement to add to the local value * @result *this */ GFpElement& operator+= ( GFpElement const& rhs ); /** * -= Operator * @param rhs the GFpElement to subtract from the local value * @result *this */ GFpElement& operator-= ( GFpElement const& rhs ); /** * *= Operator * @param rhs the GFpElement to multiply with the local value * @result *this */ GFpElement& operator*= ( GFpElement const& rhs ); /** * /= Operator * @param rhs the GFpElement to divide the local value by * @result *this */ GFpElement& operator/= ( GFpElement const& rhs ); /** * *= Operator * @param rhs the value to multiply with the local value * @result *this */ GFpElement& operator*= (u32bit rhs); /** * Negate internal value ( *this *= -1 ) * @return *this */ GFpElement& negate(); /** * Assigns the inverse of *this to *this, i.e. * *this = (*this)^(-1) * @result *this */ GFpElement& inverse_in_place(); /** * checks whether the value is zero (without provoking * a backtransformation to the ordinary-residue) * @result true, if the value is zero, false otherwise. */ bool is_zero(); /** * return prime number of GF(p) * @result a prime number */ BigInt const get_p() const; /** * Return the represented value in GF(p) * @result The value in GF(p) */ BigInt const get_value() const; /** * Returns the shared pointer to the GFpModulus of *this. * Warning: do not use this function unless you know in detail about * the implications of using * the shared GFpModulus objects! * @result the shared pointer to the GFpModulus of *this */ inline std::tr1::shared_ptr const get_ptr_mod() const { return mp_mod; } /** * Sets the shared pointer to the GFpModulus of *this. * Warning: do not use this function unless you know in detail about * the implications of using * the shared GFpModulus objects! * @param mod a shared pointer to a GFpModulus that will be held in *this */ void set_shrd_mod(std::tr1::shared_ptr const mod); /** * Tells whether this GFpElement is currently transformed to it´ m-residue, * i.e. in the form x_bar = x * r mod m. * @result true if it is currently transformed to it´s m-residue. */ bool is_trf_to_mres() const; /** * Transforms this to x_bar = x * r mod m * @result return the value x_bar. */ BigInt const get_mres() const; /** * Check, if montgomery multiplication is used. * @result true, if montgomery multiplication is used, false otherwise */ bool is_use_montgm() const { return m_use_montgm; } /** * Transforms the arguments in such way that either both * are in m-residue representation (returns true) or both are * in ordinary residue representation (returns false). * m-residue is prefered in case of ambiguity. * does not toggle m_use_montgm of the arguments. * Don´t be confused about the constness of the arguments: * the transformation between normal residue and m-residue is * considered as leaving the object const. * @param lhs the first operand to be aligned * @param rhs the second operand to be aligned * @result true if both are transformed to their m-residue, * false it both are transformed to their normal residue. */ static bool align_operands_res(GFpElement const& lhs, GFpElement const& rhs); //friend declarations for non-member functions /** * write a GFpElement to an output stream. * @param output the output stream to write to * @param elem the object to write * @result the output stream */ friend class Point_Coords_GFp; /** * swaps the states of *this and other, does not throw! * @param other The value to swap with */ void swap ( GFpElement& other ); }; // relational operators bool operator== ( GFpElement const& lhs, GFpElement const& rhs ); inline bool operator!= ( GFpElement const& lhs, GFpElement const& rhs ) { return !operator== ( lhs, rhs ); } // arithmetic operators GFpElement operator+ ( GFpElement const& lhs, GFpElement const& rhs ); GFpElement operator- ( GFpElement const& lhs, GFpElement const& rhs ); GFpElement operator- ( GFpElement const& lhs ); GFpElement operator* ( GFpElement const& lhs, GFpElement const& rhs ); GFpElement operator/ ( GFpElement const& lhs, GFpElement const& rhs ); GFpElement operator* (GFpElement const& lhs, u32bit rhs); GFpElement operator* (u32bit rhs, GFpElement const& lhs); // return (*this)^(-1) GFpElement inverse ( GFpElement const& elem ); // encoding and decoding SecureVector FE2OSP ( GFpElement const& elem ); GFpElement OS2FEP ( MemoryRegion const& os, BigInt p ); // swaps the states of elem1 and elem2, does not throw! // cf. Meyers, Item 25 inline void swap ( GFpElement& elem1, GFpElement& elem2 ) { elem1.swap ( elem2 ); } } // namespace Botan namespace std { // swaps the states of elem1 and elem2, does not throw! // cf. Meyers, Item 25 template<> inline void swap< Botan::GFpElement>(Botan::GFpElement& elem1, Botan::GFpElement& elem2) { elem1.swap(elem2); } } // namespace std #endif