diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/pk/ecdsa/curve_gfp.cpp (renamed from src/curve_gfp.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/curve_gfp.h | 165 | ||||
| -rw-r--r-- | src/pk/ecdsa/ec.cpp (renamed from src/ec.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/ec.h | 379 | ||||
| -rw-r--r-- | src/pk/ecdsa/ec_dompar.cpp (renamed from src/ec_dompar.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/ec_dompar.h | 115 | ||||
| -rw-r--r-- | src/pk/ecdsa/ecdsa.cpp (renamed from src/ecdsa.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/ecdsa.h | 100 | ||||
| -rw-r--r-- | src/pk/ecdsa/gfp_element.cpp (renamed from src/gfp_element.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/gfp_element.h | 308 | ||||
| -rw-r--r-- | src/pk/ecdsa/gfp_modulus.h | 124 | ||||
| -rw-r--r-- | src/pk/ecdsa/point_gfp.cpp (renamed from src/point_gfp.cpp) | 0 | ||||
| -rw-r--r-- | src/pk/ecdsa/point_gfp.h | 307 |
13 files changed, 1498 insertions, 0 deletions
diff --git a/src/curve_gfp.cpp b/src/pk/ecdsa/curve_gfp.cpp index 89fa74c49..89fa74c49 100644 --- a/src/curve_gfp.cpp +++ b/src/pk/ecdsa/curve_gfp.cpp diff --git a/src/pk/ecdsa/curve_gfp.h b/src/pk/ecdsa/curve_gfp.h new file mode 100644 index 000000000..49688b5dc --- /dev/null +++ b/src/pk/ecdsa/curve_gfp.h @@ -0,0 +1,165 @@ +/****************************************************** + * Elliptic curves over GF(p) (header file) * + * * + * (C) 2007 Martin Doering * + * [email protected] * + * Christoph Ludwig * + * [email protected] * + * Falko Strenzke * + * [email protected] * + ******************************************************/ + +#ifndef BOTAN_EC_CURVE_GFP_H__ +#define BOTAN_EC_CURVE_GFP_H__ + +#include <botan/gfp_element.h> +#include <botan/bigint.h> +#include <tr1/memory> + +namespace Botan { + +/** +* This class represents an elliptic curve over GF(p) +*/ +class CurveGFp + { + public: + /** + * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) + * @param a first coefficient + * @param b second coefficient + * @param p prime number of the field + */ + CurveGFp(GFpElement const& a, GFpElement const& b, + const BigInt& p); + + /** + * Copy constructor + * @param other The curve to clone + */ + CurveGFp(CurveGFp const& other); + + /** + * Assignment operator + * @param other The curve to use as source for the assignment + */ + CurveGFp const& operator=(CurveGFp const& other); + + /** + * Set the shared GFpModulus object. + * Warning: do not use this function unless you know in detail how + * the sharing of values + * in the various EC related objects works. + * Do NOT spread pointers to a GFpModulus over different threads! + * @param mod a shared pointer to a GFpModulus object suitable for + * *this. + */ + void set_shrd_mod(std::tr1::shared_ptr<Botan::GFpModulus> const mod); + + // getters + + /** + * Get coefficient a + * @result coefficient a + */ + GFpElement const get_a() const; + + /** + * Get coefficient b + * @result coefficient b + */ + GFpElement const get_b() const; + + /** + * Get the GFpElement coefficient a transformed + * to its m-residue. This can be used for efficency reasons: the curve + * stores the transformed version after the first invocation of this + * function. + * @result the coefficient a, transformed to its m-residue + */ + GFpElement const get_mres_a() const; + + /** + * Get the GFpElement coefficient b transformed + * to it´s m-residue. This can be used for efficency reasons: the curve + * stores the transformed version after the first invocation of this + * function. + * @result the coefficient b, transformed to it´s m-residue + */ + GFpElement const get_mres_b() const; + + + /** + * Get the GFpElement 1 transformed + * to it´s m-residue. This can be used for efficency reasons: the curve + * stores the transformed version after the first invocation of this + * function. + * @result the GFpElement 1, transformed to it´s m-residue + */ + std::tr1::shared_ptr<GFpElement const> const get_mres_one() const; + + /** + * Get prime modulus of the field of the curve + * @result prime modulus of the field of the curve + */ + BigInt const get_p() const; + /*inline std::tr1::shared_ptr<BigInt> const get_ptr_p() const + { + return mp_p; + }*/ + + /** + * Retrieve a shared pointer to the curves GFpModulus object for efficient storage + * and computation of montgomery multiplication related data members and functions. + * Warning: do not use this function unless you know in detail how the sharing of values + * in the various EC related objects works. + * Do NOT spread pointers to a GFpModulus over different threads! + * @result a shared pointer to a GFpModulus object + */ + inline std::tr1::shared_ptr<Botan::GFpModulus> const get_ptr_mod() const + { + return mp_mod; + } + + /** + * swaps the states of *this and other, does not throw + * @param other The curve to swap values with + */ + void swap(CurveGFp& other); + + private: + std::tr1::shared_ptr<Botan::GFpModulus> mp_mod; + GFpElement mA; + GFpElement mB; + mutable std::tr1::shared_ptr<GFpElement> mp_mres_a; + mutable std::tr1::shared_ptr<GFpElement> mp_mres_b; + mutable std::tr1::shared_ptr<GFpElement> mp_mres_one; + }; + +// relational operators +bool operator==(CurveGFp const& lhs, CurveGFp const& rhs); +inline bool operator!=(CurveGFp const& lhs, CurveGFp const& rhs) { +return !operator==(lhs, rhs); +} + +// swaps the states of curve1 and curve2, does not throw! +// cf. Meyers, Item 25 +inline +void swap(CurveGFp& curve1, CurveGFp& curve2) { +curve1.swap(curve2); +} + +} + +namespace std { + +template<> inline void swap<Botan::CurveGFp>( + Botan::CurveGFp& curve1, + Botan::CurveGFp& curve2) + { + curve1.swap(curve2); + } + +} + +#endif diff --git a/src/ec.cpp b/src/pk/ecdsa/ec.cpp index 805d02b4b..805d02b4b 100644 --- a/src/ec.cpp +++ b/src/pk/ecdsa/ec.cpp diff --git a/src/pk/ecdsa/ec.h b/src/pk/ecdsa/ec.h new file mode 100644 index 000000000..48460ba0c --- /dev/null +++ b/src/pk/ecdsa/ec.h @@ -0,0 +1,379 @@ +/************************************************* +* ECDSA Header File * +* (C) 2007 Falko Strenzke, FlexSecure GmbH * +* Manuel hartl, FlexSecure GmbH * +*************************************************/ + +#ifndef BOTAN_EC_H__ +#define BOTAN_EC_H__ + +#include <botan/if_algo.h> +#include <botan/bigint.h> +#include <botan/curve_gfp.h> +#include <botan/pk_keys.h> +#include <botan/ec_dompar.h> + +namespace Botan { + +/** +* This class represents abstract EC Public Keys. +* When encoding a key via an encoder that can be accessed via +* the corresponding member functions, the key will decide upon its +* internally stored encoding information whether to encode itself with +* or without domain parameters, or using the domain parameter oid. +* Furthermore, a public key +* without domain parameters can be decoded. In that case, it cannot be used +* for verification until its domain parameters are set by calling the +* corresponding member function. +*/ +class EC_PublicKey : public virtual Public_Key + { + public: + + /** + * Tells whether this key knows his own domain parameters. + * @result true if the domain parameters are set, false otherwise + */ + bool domain_parameters_set(); + + /** + * Get the public point of this key. + * @throw Invalid_State is thrown if the + * domain parameters of this point are not set + * @result the public point of this key + */ + inline Botan::PointGFp get_public_point() const + { + if (!mp_public_point.get()) + { + throw Invalid_State("EC_PublicKey::get_public_point(): public point not set because ec domain parameters are not yet set"); + } + return *mp_public_point; + } + /** + * Get the domain parameters of this key. + * @throw Invalid_State is thrown if the + * domain parameters of this point are not set + * @result the domain parameters of this key + */ + EC_Domain_Params const get_domain_parameters() const; + /** + * Set the domain parameter encoding to be used when encoding this key. + * @param enc the encoding to use + */ + void set_parameter_encoding(EC_dompar_enc enc); + + /** + * Get the domain parameter encoding to be used when encoding this key. + * @result the encoding to use + */ + inline int get_parameter_encoding() const + { + return m_param_enc; + } + //ctors + + EC_PublicKey() + : m_param_enc(ENC_EXPLICIT) + { + //assert(mp_dom_pars.get() == 0); + //assert(mp_public_point.get() == 0); + } + + /** + * Get an x509_encoder that can be used to encode this key. + * @result an x509_encoder for this key + */ + X509_Encoder* x509_encoder() const; + + /** + * Get an x509_decoder that can be used to decode a stored key into + * this key. + * @result an x509_decoder for this key + */ + X509_Decoder* x509_decoder(); + + /** + * Make sure that the public point and domain parameters of this key are set. + * @throw Invalid_State if either of the two data members is not set + */ + virtual void affirm_init() const; + + virtual ~EC_PublicKey() {} + protected: + virtual void X509_load_hook(); + + SecureVector<byte> m_enc_public_point; // stores the public point + + std::auto_ptr<EC_Domain_Params> mp_dom_pars; + std::auto_ptr<Botan::PointGFp> mp_public_point; + EC_dompar_enc m_param_enc; + }; + +/** +* This abstract class represents general EC Private Keys +*/ +class EC_PrivateKey : public virtual EC_PublicKey, public virtual Private_Key + { + public: + + /** + * Get an PKCS#8 encoder that can be used to encoded this key. + * @result an PKCS#8 encoder for this key + */ + PKCS8_Encoder* pkcs8_encoder() const; + /** + * Get an PKCS#8 decoder that can be used to decoded a stored key into + * this key. + * @result an PKCS#8 decoder for this key + */ + PKCS8_Decoder* pkcs8_decoder(RandomNumberGenerator&); + /** + * Get the private key value of this key object. + * @result the private key value of this key object + */ + inline BigInt const get_value() const + { + return m_private_value; + } + /** + * Make sure that the public key parts of this object are set + * (calls EC_PublicKey::affirm_init()) as well as the private key + * value. + * @throw Invalid_State if the above conditions are not satisfied + */ + virtual void affirm_init() const; + virtual ~EC_PrivateKey() + {} + protected: + virtual void PKCS8_load_hook(bool = false); + void generate_private_key(RandomNumberGenerator&); + BigInt m_private_value; + }; + +/** +* This class represents ECDSA Public Keys. +*/ +class ECDSA_PublicKey : public virtual EC_PublicKey, public PK_Verifying_wo_MR_Key + { + public: + + /** + * Get this keys algorithm name. + * @result this keys algorithm name ("ECDSA") + */ + std::string algo_name() const + { + return "ECDSA"; + } + + /** + * Get the maximum number of bits allowed to be fed to this key. + * This is the bitlength of the order of the base point. + * + * @result the maximum number of input bits + */ + u32bit max_input_bits() const; + + /** + * Verify a message with this key. + * @param message the byte array containing the message + * @param mess_len the number of bytes in the message byte array + * @param signature the byte array containing the signature + * @param sig_len the number of bytes in the signature byte array + */ + bool verify(const byte message[], u32bit mess_len, + const byte signature [], u32bit sig_len) const; + + /** + * Default constructor. Use this one if you want to later fill this object with data + * from an encoded key. + */ + ECDSA_PublicKey() {} + + /** + * Construct a public key from a given public point. + * @param dom_par the domain parameters associated with this key + * @param public_point the public point defining this key + */ + ECDSA_PublicKey(EC_Domain_Params const& dom_par, Botan::PointGFp const& public_point); // sets core + + + ECDSA_PublicKey const& operator= (ECDSA_PublicKey const& rhs); + + ECDSA_PublicKey(ECDSA_PublicKey const& other); + + /** + * Set the domain parameters of this key. This function has to be + * used when a key encoded without domain parameters was decoded into + * this key. Otherwise it will not be able to verify a signature. + * @param dom_pars the domain_parameters associated with this key + * @throw Invalid_Argument if the point was found not to be satisfying the + * curve equation of the provided domain parameters + * or if this key already has domain parameters set + * and these are differing from those given as the parameter + */ + void set_domain_parameters(EC_Domain_Params const& dom_pars); + + /** + * Make sure that the public point and domain parameters of this key are set. + * @throw Invalid_State if either of the two data members is not set + */ + virtual void affirm_init() const; + + protected: + void X509_load_hook(); + virtual void set_all_values(ECDSA_PublicKey const& other); + + ECDSA_Core m_ecdsa_core; + }; +/** +* This class represents ECDSA Public Keys. +*/ +class ECDSA_PrivateKey : public ECDSA_PublicKey, public EC_PrivateKey, public PK_Signing_Key + { + public: + //ctors + /** + * Default constructor. Use this one if you want to later fill this object with data + * from an encoded key. + */ + ECDSA_PrivateKey() + {} + /** + * Generate a new private key + * @param the domain parameters to used for this key + */ + ECDSA_PrivateKey(RandomNumberGenerator& rng, + const EC_Domain_Params& domain); + + ECDSA_PrivateKey(ECDSA_PrivateKey const& other); + ECDSA_PrivateKey const& operator= (ECDSA_PrivateKey const& rhs); + + /** + * Sign a message with this key. + * @param message the byte array representing the message to be signed + * @param mess_len the length of the message byte array + * @result the signature + */ + SecureVector<byte> sign(const byte message[], u32bit mess_len, RandomNumberGenerator& rng) const; + /** + * Make sure that the public key parts of this object are set + * (calls EC_PublicKey::affirm_init()) as well as the private key + * value. + * @throw Invalid_State if the above conditions are not satisfied + */ + virtual void affirm_init() const; + protected: + virtual void set_all_values ( ECDSA_PrivateKey const& other ); + private: + void PKCS8_load_hook(bool = false); + }; + +/** +* This class represents ECKAEG Public Keys. +*/ +class ECKAEG_PublicKey : public virtual EC_PublicKey + { + public: + /** + * Default constructor. Use this one if you want to later fill this object with data + * from an encoded key. + */ + ECKAEG_PublicKey() + {}; + /** + * Construct a public key from a given public point. + * @param dom_par the domain parameters associated with this key + * @param public_point the public point defining this key + */ + ECKAEG_PublicKey(EC_Domain_Params const& dom_par, Botan::PointGFp const& public_point); + + /** + * Get this keys algorithm name. + * @result this keys algorithm name + */ + std::string algo_name() const + { + return "ECKAEG"; + } + /** + * Get the maximum number of bits allowed to be fed to this key. + * This is the bitlength of the order of the base point. + * + * @result the maximum number of input bits + */ + u32bit max_input_bits() const + { + if (!mp_dom_pars.get()) + { + throw Invalid_State("ECKAEG_PublicKey::max_input_bits(): domain parameters not set"); + } + return mp_dom_pars->get_order().bits(); + } + ECKAEG_PublicKey(ECKAEG_PublicKey const& other); + ECKAEG_PublicKey const& operator= (ECKAEG_PublicKey const& rhs); + + + /** + * Make sure that the public point and domain parameters of this key are set. + * @throw Invalid_State if either of the two data members is not set + */ + virtual void affirm_init() const; + protected: + void X509_load_hook(); + virtual void set_all_values ( ECKAEG_PublicKey const& other ); + + ECKAEG_Core m_eckaeg_core; + }; + +/** +* This class represents ECKAEG Private Keys. +*/ +class ECKAEG_PrivateKey : public ECKAEG_PublicKey, public EC_PrivateKey, public PK_Key_Agreement_Key + { + public: + /** + * Generate a new private key + * @param the domain parameters to used for this key + */ + ECKAEG_PrivateKey(RandomNumberGenerator& rng, + EC_Domain_Params const& dom_pars) + { + mp_dom_pars = std::auto_ptr<EC_Domain_Params>(new EC_Domain_Params(dom_pars)); + generate_private_key(rng); + mp_public_point->check_invariants(); + m_eckaeg_core = ECKAEG_Core(*mp_dom_pars, m_private_value, *mp_public_point); + } + /** + * Default constructor. Use this one if you want to later fill this object with data + * from an encoded key. + */ + ECKAEG_PrivateKey() + {} + ECKAEG_PrivateKey(ECKAEG_PrivateKey const& other); + ECKAEG_PrivateKey const& operator= (ECKAEG_PrivateKey const& rhs); + + void PKCS8_load_hook(bool = false); + + /** + * Derive a shared key with the other partys public key. + * @param pub_key the other partys public key + */ + SecureVector<byte> derive_key(const Public_Key& pub_key) const; + + /** + * Make sure that the public key parts of this object are set + * (calls EC_PublicKey::affirm_init()) as well as the private key + * value. + * @throw Invalid_State if the above conditions are not satisfied + */ + virtual void affirm_init() const; + + protected: + virtual void set_all_values ( ECKAEG_PrivateKey const& other ); + }; + +} + +#endif diff --git a/src/ec_dompar.cpp b/src/pk/ecdsa/ec_dompar.cpp index 232233669..232233669 100644 --- a/src/ec_dompar.cpp +++ b/src/pk/ecdsa/ec_dompar.cpp diff --git a/src/pk/ecdsa/ec_dompar.h b/src/pk/ecdsa/ec_dompar.h new file mode 100644 index 000000000..8f9cc77d9 --- /dev/null +++ b/src/pk/ecdsa/ec_dompar.h @@ -0,0 +1,115 @@ +/************************************************* +* ECDSA Domain Parameters Header File * +* (C) 2007 Falko Strenzke, FlexSecure GmbH * +*************************************************/ + +#ifndef EC_DOMPAR_H__ +#define EC_DOMPAR_H__ + +#include <botan/point_gfp.h> +#include <botan/gfp_element.h> +#include <botan/curve_gfp.h> +#include <botan/bigint.h> +#include <botan/der_enc.h> +#include <botan/ber_dec.h> +#include <botan/alg_id.h> +#include <botan/enums.h> + +namespace Botan { + +/** +* This class represents elliptic curce domain parameters +*/ +class EC_Domain_Params + { + public: + + /** + * Construct Domain paramers from specified parameters + * @param curve elliptic curve + * @param base_point a base point + * @param order the order of the base point + * @param cofactor the cofactor + */ + EC_Domain_Params(CurveGFp const& curve, PointGFp const& base_point, + const BigInt& order, const BigInt& cofactor); + + /** + * Return domain parameter curve + * @result domain parameter curve + */ + const CurveGFp& get_curve() const + { + return m_curve; + } + + /** + * Return domain parameter curve + * @result domain parameter curve + */ + const PointGFp& get_base_point() const + { + return m_base_point; + } + + /** + * Return the order of the base point + * @result order of the base point + */ + const BigInt& get_order() const + { + return m_order; + } + + /** + * Return the cofactor + * @result the cofactor + */ + const BigInt& get_cofactor() const + { + return m_cofactor; + } + + /** + * Return the OID of these domain parameters + * @result the OID + */ + std::string get_oid() const { return m_oid; } + + private: + friend EC_Domain_Params get_EC_Dom_Pars_by_oid(std::string oid); + + CurveGFp m_curve; + PointGFp m_base_point; + BigInt m_order; + BigInt m_cofactor; + std::string m_oid; + }; + +bool operator==(EC_Domain_Params const& lhs, EC_Domain_Params const& rhs); + +inline bool operator!=(const EC_Domain_Params& lhs, + const EC_Domain_Params& rhs) + { + return !(lhs == rhs); + } + +enum EC_dompar_enc { ENC_EXPLICIT = 0, ENC_IMPLICITCA = 1, ENC_OID = 2 }; + +SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, + EC_dompar_enc enc_type); + +EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded); + +/** +* Factory function, the only way to obtain EC domain parameters with an OID. +* The demanded OID has to be registered in the InSiTo configuration. Consult the file +* policy.cpp for the default configuration. +* @param the oid of the demanded EC domain parameters +* @result the EC domain parameters associated with the OID +*/ +EC_Domain_Params get_EC_Dom_Pars_by_oid(std::string oid); + +} + +#endif diff --git a/src/ecdsa.cpp b/src/pk/ecdsa/ecdsa.cpp index 04dc1e529..04dc1e529 100644 --- a/src/ecdsa.cpp +++ b/src/pk/ecdsa/ecdsa.cpp diff --git a/src/pk/ecdsa/ecdsa.h b/src/pk/ecdsa/ecdsa.h new file mode 100644 index 000000000..2f8392a3f --- /dev/null +++ b/src/pk/ecdsa/ecdsa.h @@ -0,0 +1,100 @@ +/************************************************* +* ECDSA Header File * +* (C) 2007 Falko Strenzke, FlexSecure GmbH * +* Defines classes ECDSA_Signature and * +* ECDSA_Signature_De/Encoder, * +*************************************************/ + +#ifndef BOTAN_ECDSA_H__ +#define BOTAN_ECDSA_H__ + +#include <botan/bigint.h> +#include <botan/der_enc.h> +#include <botan/ber_dec.h> + +namespace Botan { + +class ECDSA_Signature_Decoder; +class ECDSA_Signature_Encoder; + +class ECDSA_Signature + { + friend class ECDSA_Signature_Decoder; + friend class ECDSA_Signature_Encoder; + public: + ECDSA_Signature(const BigInt& r, const BigInt& s); + ECDSA_Signature() + {} + ; + ECDSA_Signature(ECDSA_Signature const& other); + ECDSA_Signature const& operator=(ECDSA_Signature const& other); + + BigInt const get_r() const + { + return m_r; + } + BigInt const get_s() const + { + return m_s; + } + /** + * return the r||s + */ + SecureVector<byte> const get_concatenation() const; + + + ECDSA_Signature_Encoder* x509_encoder() const; + ECDSA_Signature_Decoder* x509_decoder(); + private: + BigInt m_r; + BigInt m_s; + }; + +bool operator== ( ECDSA_Signature const& lhs, ECDSA_Signature const& rhs ); +inline bool operator!= ( ECDSA_Signature const& lhs, ECDSA_Signature const& rhs ) + { + return !operator== ( lhs, rhs ); + } + +class ECDSA_Signature_Decoder + { + public: + void signature_bits(const MemoryRegion<byte>& bits) + { + BER_Decoder(bits) + .start_cons(SEQUENCE) + .decode(m_signature->m_r) + .decode(m_signature->m_s) + .verify_end() + .end_cons(); + } + ECDSA_Signature_Decoder(ECDSA_Signature* signature) : m_signature(signature) + {} + private: + ECDSA_Signature* m_signature; + }; + +class ECDSA_Signature_Encoder + { + public: + MemoryVector<byte> signature_bits() const + { + return DER_Encoder() + .start_cons(SEQUENCE) + .encode(m_signature->m_r) + .encode(m_signature->m_s) + .end_cons() + .get_contents(); + } + ECDSA_Signature_Encoder(const ECDSA_Signature* signature) : m_signature(signature) + {} + private: + const ECDSA_Signature* m_signature; + }; + +ECDSA_Signature const decode_seq(MemoryRegion<byte> const& seq); +ECDSA_Signature const decode_concatenation(MemoryRegion<byte> const& concatenation); + +} + +#endif diff --git a/src/gfp_element.cpp b/src/pk/ecdsa/gfp_element.cpp index 686cc338b..686cc338b 100644 --- a/src/gfp_element.cpp +++ b/src/pk/ecdsa/gfp_element.cpp diff --git a/src/pk/ecdsa/gfp_element.h b/src/pk/ecdsa/gfp_element.h new file mode 100644 index 000000000..e9850df30 --- /dev/null +++ b/src/pk/ecdsa/gfp_element.h @@ -0,0 +1,308 @@ +/****************************************************** + * Arithmetic for prime fields GF(p) (header file) * + * * + * (C) 2007 Martin Döring * +* [email protected] * +* Christoph Ludwig * +* [email protected] * +* Falko Strenzke * +* [email protected] * +******************************************************/ + +#ifndef BOTAN_MATH_GF_GFP_ELEMENT_H_GUARD_ +#define BOTAN_MATH_GF_GFP_ELEMENT_H_GUARD_ + +#include <botan/gfp_modulus.h> +#include <botan/bigint.h> +#include <tr1/memory> + +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<GFpModulus> 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<GFpModulus> 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<GFpModulus> 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<GFpModulus> 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<byte> FE2OSP ( GFpElement const& elem ); +GFpElement OS2FEP ( MemoryRegion<byte> 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 diff --git a/src/pk/ecdsa/gfp_modulus.h b/src/pk/ecdsa/gfp_modulus.h new file mode 100644 index 000000000..5edf44ba0 --- /dev/null +++ b/src/pk/ecdsa/gfp_modulus.h @@ -0,0 +1,124 @@ +/****************************************************** + * Modulus and related data for a specific * + * implementation of GF(p) (header file) * + * * + * (C) 2008 Martin Döring * + * [email protected] * + * Christoph Ludwig * + * [email protected] * + * Falko Strenzke * + * [email protected] * + ******************************************************/ + +#ifndef BOTAN_MATH_GF_GFP_MODULUS_H_GUARD_ +#define BOTAN_MATH_GF_GFP_MODULUS_H_GUARD_ + +#include <botan/bigint.h> + +namespace Botan +{ + +class GFpElement; +/** +* This class represents a GFpElement modulus including the modulus related +* values necessary for the montgomery multiplication. +*/ +class GFpModulus + { + friend class GFpElement; + private: + BigInt m_p; // the modulus itself + mutable BigInt m_p_dash; + mutable BigInt m_r; + mutable BigInt m_r_inv; + public: + + /** + * Construct a GF(P)-Modulus from a BigInt + */ + GFpModulus(BigInt p) + : m_p(p), + m_p_dash(), + m_r(), + m_r_inv() + {} + + /** + * Tells whether the precomputations necessary for the use of the montgomery + * multiplication have yet been established. + * @result true if the precomputated value are already available. + */ + inline bool has_precomputations() const + { + return(!m_p_dash.is_zero() && !m_r.is_zero() && !m_r_inv.is_zero()); + } + + /** + * Swaps this with another GFpModulus, does not throw. + * @param other the GFpModulus to swap *this with. + */ + inline void swap(GFpModulus& other) + { + m_p.swap(other.m_p); + m_p_dash.swap(other.m_p_dash); + m_r.swap(other.m_r); + m_r_inv.swap(other.m_r_inv); + } + + /** + * Tells whether the modulus of *this is equal to the argument. + * @param mod the modulus to compare this with + * @result true if the modulus of *this and the argument are equal. + */ + inline bool p_equal_to(const BigInt& mod) const + { + return (m_p == mod); + } + + /** + * Return the modulus of this GFpModulus. + * @result the modulus of *this. + */ + inline const BigInt get_p() const + { + return m_p; + } + + /** + * returns the montgomery multiplication related value r. + * Warning: will be zero if precomputations have not yet been + * performed! + * @result r + */ + inline const BigInt get_r() const + { + return m_r; + } + + /** + * returns the montgomery multiplication related value r^{-1}. + * Warning: will be zero if precomputations have not yet been + * performed! + * @result r^{-1} + */ + inline const BigInt get_r_inv() const + { + return m_r_inv; + } + + /** + * returns the montgomery multiplication related value p'. + * Warning: will be zero if precomputations have not yet been + * performed! + * @result p' + */ + inline const BigInt get_p_dash() const + { + return m_p_dash; + } + // default cp-ctor, op= are fine + }; + +} + +#endif diff --git a/src/point_gfp.cpp b/src/pk/ecdsa/point_gfp.cpp index 23b6d4518..23b6d4518 100644 --- a/src/point_gfp.cpp +++ b/src/pk/ecdsa/point_gfp.cpp diff --git a/src/pk/ecdsa/point_gfp.h b/src/pk/ecdsa/point_gfp.h new file mode 100644 index 000000000..7e5aec379 --- /dev/null +++ b/src/pk/ecdsa/point_gfp.h @@ -0,0 +1,307 @@ +/************************************************* +* Arithmetic over GF(p) * +* * +* (C) 2007 Martin Doering * +* Christoph Ludwig * +* Falko Strenzke * +* (C) 2008 Jack Lloyd * +*************************************************/ + +#ifndef BOTAN_POINT_GFP_H__ +#define BOTAN_POINT_GFP_H__ + +#include <botan/curve_gfp.h> +#include <botan/gfp_element.h> +#include <botan/bigint.h> +#include <botan/exceptn.h> +#include <vector> + +namespace Botan { + +struct Illegal_Point : public Exception + { + Illegal_Point(const std::string& err = "") : Exception(err) {} + }; + +/** +* This class represents one point on a curve of GF(p). +*/ +class PointGFp + { + public: + /** + * uncompressed encoding byte value + */ + static const int UNCOMPRESSED = 0; + + /** + * compressed encoding byte value + */ + static const int COMPRESSED = 1; + + /** + * hybrid encoding byte value + */ + static const int HYBRID = 2; + + /** + * Construct the point O + * @param curve The base curve + */ + explicit PointGFp(CurveGFp const& curve); + + /** + * Construct a point given its affine coordinates + * @param curve the base curve + * @param x affine x coordinate + * @param y affine y coordinate + */ + explicit PointGFp(CurveGFp const& curve, GFpElement const& x, + GFpElement const& y ); + + /** + * Construct a point given its jacobian projective coordinates + * @param curve the base curve + * @param x jacobian projective x coordinate + * @param y jacobian projective y coordinate + * @param z jacobian projective y coordinate + */ + explicit PointGFp(CurveGFp const& curve, GFpElement const& x, + GFpElement const& y, GFpElement const& z ); + + /** + * copy constructor + * @param other the value to clone + */ + PointGFp(PointGFp const& other ); + + /** + * assignment operator + * @param other The point to use as source for the assignment + */ + PointGFp const& operator=(PointGFp const& other ); + + /** + * assign another point which is on the same curve as *this + * @param other The point to use as source for the assignment + */ + PointGFp const& assign_within_same_curve(PointGFp const& other); + + + + /** + * += Operator + * @param rhs the PointGFp to add to the local value + * @result resulting PointGFp + */ + PointGFp& operator+=(PointGFp const& rhs ); + + /** + * -= Operator + * @param rhs the PointGFp to subtract from the local value + * @result resulting PointGFp + */ + PointGFp& operator-=(PointGFp const& rhs ); + + /** + * *= Operator + * This function turns on the the special reduction multiplication + * itself for fast computation, turns it off again when finished. + * @param scalar the PointGFp to multiply with *this + * @result resulting PointGFp + */ + PointGFp& operator*=(const BigInt& scalar ); + + /** + * the equivalent to operator*= with countermeasures against + * sidechannel attacks, using the randomized exponent + * and add-and-double-always + * countermeasures (suitable for ECDSA and ECKAEG) + * @param scalar the scalar to multiply the point with + * @param point_order a multiple of the order of the point + *(= n * k in the general case; k is the cofactor) + * @param max_secr the maximal size of the scalar + * (will usually be n-1 ) + * @result resulting PointGFp + */ + PointGFp& mult_this_secure(const BigInt& scalar, + const BigInt& point_order, + const BigInt& max_secr + ); + + /** + * Negate internal value(*this *= -1 ) + * @return *this + */ + PointGFp& negate(); + + /** + * Multiply the point by two(*this *= 2 ) + * @return *this + */ + PointGFp& mult2_in_place(); + + /** + * Set z coordinate to one. + * @return *this + */ + PointGFp const& set_z_to_one() const; + + /** + * Turn on the special reduction multiplication (i.e. the + * Montgomery multiplication in the current implementation) for + * the coordinates. This enables fast execution of mult2_in_place() + * and operator+=(). + */ + void turn_on_sp_red_mul() const; + + /** + * Return a point + * where the coordinates are transformed + * so that z equals one, + * thus x and y have just the affine values. + * @result *this + */ + PointGFp const get_z_to_one() const; + + /** + * Return base curve of this point + * @result the curve over GF(p) of this point + */ + CurveGFp const get_curve() const; + + /** + * get affine x coordinate + * @result affine x coordinate + */ + GFpElement const get_affine_x() const; + + /** + * get affine y coordinate + * @result affine y coordinate + */ + GFpElement const get_affine_y() const; + + /** + * get the jacobian projective x coordinate + * @result jacobian projective x coordinate + */ + GFpElement const get_jac_proj_x() const; + + /** + * get the jacobian projective y coordinate + * @result jacobian projective y coordinate + */ + GFpElement const get_jac_proj_y() const; + + /** + * get the jacobian projective z coordinate + * @result jacobian projective z coordinate + */ + GFpElement const get_jac_proj_z() const; + + /** + * Is this the point at infinity? + * @result true, if this point is at infinity, false otherwise. + */ + bool is_zero() const; + + /** + * Checks whether the point is to be found on the underlying curve. + * Throws an Invalid_Point exception in case of detecting that the point + * does not satisfy the curve equation. + * To be used to ensure against fault attacks. + */ + void check_invariants() const; + + + /** + * swaps the states of *this and other, does not throw! + * @param other the object to swap values with + */ + void swap(PointGFp& other ); + + /** + * Sets the shared pointer to the GFpModulus that will be + * held in *this, specifically the various members of *this. + * Warning: do not use this function unless you know in detail about + * the implications of using + * the shared GFpModulus objects! + * Do NOT spread a shared pointer to GFpModulus over different + * threads! + * @param mod a shared pointer to a GFpModulus that will + * be held in the members *this + */ + void set_shrd_mod(std::tr1::shared_ptr<Botan::GFpModulus> p_mod); + + static GFpElement decompress(bool yMod2, GFpElement const& x, CurveGFp const& curve ); + + private: + static const u32bit GFPEL_WKSP_SIZE = 9; + void ensure_worksp() const; + + inline std::tr1::shared_ptr<PointGFp> mult_loop(int l, const BigInt& m, std::tr1::shared_ptr<PointGFp> H, std::tr1::shared_ptr<PointGFp> tmp, PointGFp const& P); + + CurveGFp mC; + mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) + mutable GFpElement mY; + mutable GFpElement mZ; + mutable GFpElement mZpow2; // mZ^2 + mutable GFpElement mZpow3; // mZ^3 + mutable GFpElement mAZpow4; // mA*mZ^4 + mutable bool mZpow2_set; + mutable bool mZpow3_set; + mutable bool mAZpow4_set; + mutable std::tr1::shared_ptr<std::vector<GFpElement> > mp_worksp_gfp_el; + + }; + +// relational operators +bool operator==(PointGFp const& lhs, PointGFp const& rhs ); +inline bool operator!=(PointGFp const& lhs, PointGFp const& rhs ) + { + return !operator==(lhs, rhs ); + } + +// arithmetic operators +PointGFp operator+(PointGFp const& lhs, PointGFp const& rhs ); +PointGFp operator-(PointGFp const& lhs, PointGFp const& rhs ); +PointGFp operator-(PointGFp const& lhs ); + +PointGFp operator*(const BigInt& scalar, PointGFp const& point ); +PointGFp operator*(PointGFp const& point, const BigInt& scalar ); +PointGFp mult_point_secure(PointGFp const& point, const BigInt& scalar, const BigInt& point_order, const BigInt& max_secret); + +PointGFp const mult2 (PointGFp const& point); + +PointGFp const create_random_point(RandomNumberGenerator& rng, + CurveGFp const& curve); + +// encoding and decoding +SecureVector<byte> EC2OSP(PointGFp const& point, byte format ); +PointGFp OS2ECP(MemoryRegion<byte> const& os, CurveGFp const& curve ); + +SecureVector<byte> encode_uncompressed(PointGFp const& point ); // maybe make private +SecureVector<byte> encode_hybrid(PointGFp const& point ); // maybe make private +SecureVector<byte> encode_compressed(PointGFp const& point ); // maybe make private + +// swaps the states of point1 and point2, does not throw! +// cf. Meyers, Item 25 +inline +void swap(PointGFp& point1, PointGFp& point2 ) + { + point1.swap(point2 ); + } + +} // namespace Botan + +namespace std { + +// swaps the states of point1 and point2, does not throw! +// cf. Meyers, Item 25 +template<> inline void +swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) { x.swap(y); } + +} // namespace std + +#endif |