diff options
| -rw-r--r-- | doc/examples/Makefile | 4 | ||||
| -rw-r--r-- | doc/examples/ecdsa.cpp | 16 | ||||
| -rw-r--r-- | doc/license.txt | 3 | ||||
| -rw-r--r-- | include/bigint.h | 3 | ||||
| -rw-r--r-- | include/curve_gfp.h | 165 | ||||
| -rw-r--r-- | include/ec.h | 376 | ||||
| -rw-r--r-- | include/ec_dompar.h | 115 | ||||
| -rw-r--r-- | include/ecdsa.h | 100 | ||||
| -rw-r--r-- | include/engine.h | 17 | ||||
| -rw-r--r-- | include/gfp_element.h | 308 | ||||
| -rw-r--r-- | include/gfp_modulus.h | 124 | ||||
| -rw-r--r-- | include/pk_core.h | 53 | ||||
| -rw-r--r-- | include/pk_ops.h | 32 | ||||
| -rw-r--r-- | include/point_gfp.h | 307 | ||||
| -rw-r--r-- | include/rsa.h | 1 | ||||
| -rw-r--r-- | src/curve_gfp.cpp | 157 | ||||
| -rw-r--r-- | src/ec.cpp | 533 | ||||
| -rw-r--r-- | src/ec_dompar.cpp | 288 | ||||
| -rw-r--r-- | src/ecdsa.cpp | 72 | ||||
| -rw-r--r-- | src/eng_base.cpp | 20 | ||||
| -rw-r--r-- | src/engine.cpp | 38 | ||||
| -rw-r--r-- | src/gfp_element.cpp | 674 | ||||
| -rw-r--r-- | src/pk_core.cpp | 78 | ||||
| -rw-r--r-- | src/point_gfp.cpp | 1157 |
24 files changed, 4639 insertions, 2 deletions
diff --git a/doc/examples/Makefile b/doc/examples/Makefile index 6706aaaf6..a25782f89 100644 --- a/doc/examples/Makefile +++ b/doc/examples/Makefile @@ -65,6 +65,10 @@ encrypt: encrypt.cpp $(CXX) $(FLAGS) $? $(LIBS) -o $@ @$(STRIP) $@ +ecdsa: ecdsa.cpp + $(CXX) $(FLAGS) $? $(LIBS) -o $@ + @$(STRIP) $@ + factor: factor.cpp $(CXX) $(FLAGS) $? $(LIBS) -o $@ @$(STRIP) $@ diff --git a/doc/examples/ecdsa.cpp b/doc/examples/ecdsa.cpp new file mode 100644 index 000000000..6b6bb65e5 --- /dev/null +++ b/doc/examples/ecdsa.cpp @@ -0,0 +1,16 @@ +#include <botan/botan.h> +#include <botan/ec.h> + +#include <memory> + +using namespace Botan; + +int main() + { + std::auto_ptr<RandomNumberGenerator> rng(RandomNumberGenerator::make_rng()); + + EC_Domain_Params params = get_EC_Dom_Pars_by_oid("1.3.132.8"); + + ECDSA_PrivateKey ecdsa(rng, params); + + } diff --git a/doc/license.txt b/doc/license.txt index c0fb58c10..1b36b84c7 100644 --- a/doc/license.txt +++ b/doc/license.txt @@ -7,6 +7,9 @@ Copyright (C) 1999-2008 Jack Lloyd 2007 Yves Jerschow 2007-2008 FlexSecure GmbH 2007-2008 Falko Strenzke + 2007 Martin Doering + 2007 Manuel Hartl + 2007 Christoph Ludwig Redistribution and use in source and binary forms, for any use, with or without modification, is permitted provided that the following conditions are met: diff --git a/include/bigint.h b/include/bigint.h index c1dbc7171..194516518 100644 --- a/include/bigint.h +++ b/include/bigint.h @@ -77,7 +77,9 @@ class BOTAN_DLL BigInt const word* data() const { return reg.begin(); } SecureVector<word>& get_reg() { return reg; } + void grow_reg(u32bit) const; + void grow_to(u32bit) const; word& operator[](u32bit); word operator[](u32bit) const; @@ -107,7 +109,6 @@ class BOTAN_DLL BigInt BigInt(Sign, u32bit); BigInt(NumberType, u32bit); private: - void grow_to(u32bit) const; SecureVector<word> reg; Sign signedness; }; diff --git a/include/curve_gfp.h b/include/curve_gfp.h new file mode 100644 index 000000000..49688b5dc --- /dev/null +++ b/include/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/include/ec.h b/include/ec.h new file mode 100644 index 000000000..5515d641f --- /dev/null +++ b/include/ec.h @@ -0,0 +1,376 @@ +/************************************************* +* 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 + // until dom pars are provided + std::auto_ptr<EC_Domain_Params> mp_dom_pars; + std::auto_ptr<Botan::PointGFp> mp_public_point; + mutable 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 + */ + 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 + void X509_load_hook(); + + 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: + 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, + 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_ecdsa_core = ECDSA_Core(*mp_dom_pars, m_private_value, *mp_public_point); + } + 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) 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/include/ec_dompar.h b/include/ec_dompar.h new file mode 100644 index 000000000..8f9cc77d9 --- /dev/null +++ b/include/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/include/ecdsa.h b/include/ecdsa.h new file mode 100644 index 000000000..2f8392a3f --- /dev/null +++ b/include/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/include/engine.h b/include/engine.h index 13007e662..74449c959 100644 --- a/include/engine.h +++ b/include/engine.h @@ -8,6 +8,7 @@ #include <botan/base.h> #include <botan/mutex.h> +#include <botan/ec_dompar.h> #include <botan/pk_ops.h> #include <botan/pow_mod.h> #include <botan/basefilt.h> @@ -43,6 +44,14 @@ class BOTAN_DLL Engine const BigInt&) const; virtual DH_Operation* dh_op(const DL_Group&, const BigInt&) const; + virtual ECDSA_Operation* ecdsa_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key) const; + + virtual ECKAEG_Operation* eckaeg_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key) const; + virtual Modular_Exponentiator* mod_exp(const BigInt&, Power_Mod::Usage_Hints) const; @@ -116,6 +125,14 @@ ELG_Operation* elg_op(const DL_Group&, const BigInt&, const BigInt&); DH_Operation* dh_op(const DL_Group&, const BigInt&); +ECDSA_Operation* ecdsa_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key); + +ECKAEG_Operation* eckaeg_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key); + } } diff --git a/include/gfp_element.h b/include/gfp_element.h new file mode 100644 index 000000000..e9850df30 --- /dev/null +++ b/include/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/include/gfp_modulus.h b/include/gfp_modulus.h new file mode 100644 index 000000000..5edf44ba0 --- /dev/null +++ b/include/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/include/pk_core.h b/include/pk_core.h index 585c12ee4..66b1d43f9 100644 --- a/include/pk_core.h +++ b/include/pk_core.h @@ -8,6 +8,7 @@ #include <botan/bigint.h> #include <botan/dl_group.h> +#include <botan/ec_dompar.h> #include <botan/blinding.h> #include <botan/pk_ops.h> @@ -123,6 +124,58 @@ class BOTAN_DLL DH_Core Blinder blinder; }; +/************************************************* +* ECDSA Core * +*************************************************/ +class ECDSA_Core + { + public: + bool verify(const byte signature[], u32bit sig_len, + const byte message[], u32bit mess_len) const; + + SecureVector<byte> sign(const byte message[], u32bit mess_len) const; + + ECDSA_Core& operator=(const ECDSA_Core&); + + ECDSA_Core() { op = 0; } + + ECDSA_Core(const ECDSA_Core&); + + ECDSA_Core(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key); + + ~ECDSA_Core() { delete op; } + private: + ECDSA_Operation* op; + }; + +/************************************************* +* ECKAEG Core * +*************************************************/ +class ECKAEG_Core + { + public: + SecureVector<byte> agree(const PointGFp&) const; + + ECKAEG_Core& operator=(const ECKAEG_Core&); + + ECKAEG_Core() { op = 0; } + + ECKAEG_Core(const ECKAEG_Core&); + + ECKAEG_Core(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + PointGFp const& pub_key); + + ~ECKAEG_Core() { delete op; } + private: + ECKAEG_Operation* op; + Blinder blinder; + }; + + + } #endif diff --git a/include/pk_ops.h b/include/pk_ops.h index fad87b573..7a0cbccf7 100644 --- a/include/pk_ops.h +++ b/include/pk_ops.h @@ -1,6 +1,6 @@ /************************************************* * Public Key Operations Header File * -* (C) 1999-2007 Jack Lloyd * +* (C) 1999-2008 Jack Lloyd * *************************************************/ #ifndef BOTAN_PK_OPS_H__ @@ -8,6 +8,8 @@ #include <botan/bigint.h> #include <botan/dl_group.h> +#include <botan/point_gfp.h> +#include <botan/ecdsa.h> namespace Botan { @@ -74,6 +76,34 @@ class BOTAN_DLL DH_Operation virtual ~DH_Operation() {} }; +/************************************************* +* ECDSA Operation * +*************************************************/ +class BOTAN_DLL ECDSA_Operation + { + public: + virtual bool verify(const byte sig[], u32bit sig_len, + const byte msg[], u32bit msg_len) const = 0; + + virtual SecureVector<byte> sign(const byte message[], + u32bit mess_len) const = 0; + + virtual ECDSA_Operation* clone() const = 0; + + virtual ~ECDSA_Operation() {} + }; + +/************************************************* +* ECKAEG Operation * +*************************************************/ +class BOTAN_DLL ECKAEG_Operation + { + public: + virtual SecureVector<byte> agree(const PointGFp&) const = 0; + virtual ECKAEG_Operation* clone() const = 0; + virtual ~ECKAEG_Operation() {} + }; + } #endif diff --git a/include/point_gfp.h b/include/point_gfp.h new file mode 100644 index 000000000..7e5aec379 --- /dev/null +++ b/include/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 diff --git a/include/rsa.h b/include/rsa.h index 445902a6f..64aa748ad 100644 --- a/include/rsa.h +++ b/include/rsa.h @@ -1,3 +1,4 @@ + /************************************************* * RSA Header File * * (C) 1999-2008 Jack Lloyd * diff --git a/src/curve_gfp.cpp b/src/curve_gfp.cpp new file mode 100644 index 000000000..89fa74c49 --- /dev/null +++ b/src/curve_gfp.cpp @@ -0,0 +1,157 @@ +/****************************************************** + * Elliptic curves over GF(p) (source file) * + * * + * (C) 2007 Martin Doering * + * [email protected] * + * Christoph Ludwig * + * [email protected] * + * Falko Strenzke * + * [email protected] * + ******************************************************/ + +#include <botan/curve_gfp.h> + +namespace Botan { + +CurveGFp::CurveGFp(GFpElement const& a, GFpElement const& b, + const BigInt& p) : + mA(a), mB(b) + { + if(p != mA.get_p() || p != mB.get_p()) + throw Invalid_Argument("could not construct curve: moduli of arguments differ"); + + std::tr1::shared_ptr<GFpModulus> p_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(p)); + // the above is the creation of the GFpModuls object which will be shared point-wide + // (in the context of a point of course) + set_shrd_mod(p_mod); + } + +// copy constructor +CurveGFp::CurveGFp(CurveGFp const& other) + : mA(other.get_a()), + mB(other.get_b()) + { + mp_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(*other.mp_mod)); + //assert(mp_mod->p_equal_to(mA.get_p())); + //assert(mp_mod->p_equal_to(mB.get_p())); + set_shrd_mod(mp_mod); + if(other.mp_mres_a.get()) + { + mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); + } + if(other.mp_mres_b.get()) + { + mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); + } + if(other.mp_mres_one.get()) + { + mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_one)); + } + + } + +// assignment operator +CurveGFp const& CurveGFp::operator=(CurveGFp const& other) + { + // for exception safety... + GFpElement a_tmp = other.mA; + GFpElement b_tmp = other.mB; + mA.swap(a_tmp); + mB.swap(b_tmp); + + std::tr1::shared_ptr<GFpModulus> p_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(*other.mp_mod)); + set_shrd_mod(p_mod); + + // exception safety note: no problem if we have a throw from here on... + if(other.mp_mres_a.get()) + { + mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); + } + if(other.mp_mres_b.get()) + { + mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); + } + if(other.mp_mres_one.get()) + { + mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_one)); + } + return *this; + } + +// getters +GFpElement const CurveGFp::get_a() const + { + return mA; + } +GFpElement const CurveGFp::get_b() const + { + return mB; + } + +BigInt const CurveGFp::get_p() const + { + //assert(mp_mod.get() != 0); + return mp_mod->get_p(); + } + +// swaps the states of *this and other, does not throw +void CurveGFp::swap(CurveGFp& other) + { + mA.swap(other.mA); + mB.swap(other.mB); + mp_mod.swap(other.mp_mod); + std::swap(mp_mres_a, other.mp_mres_a); + std::swap(mp_mres_b, other.mp_mres_b); + std::swap(mp_mres_one, other.mp_mres_one); + } + +void CurveGFp::set_shrd_mod(std::tr1::shared_ptr<GFpModulus> const mod) + { + mp_mod = mod; + mA.turn_off_sp_red_mul();// m.m. is not needed, must be trf. back + mB.turn_off_sp_red_mul();// m.m. is not needed, must be trf. back + //ok, above we destroy any evantually computated montg. mult. values, + // but that won't influence performance in usual applications + mA.set_shrd_mod(mod); + mB.set_shrd_mod(mod); + } + +GFpElement const CurveGFp::get_mres_a() const + { + if(mp_mres_a.get() == 0) + { + mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(mA)); + mp_mres_a->turn_on_sp_red_mul(); + mp_mres_a->get_mres(); + } + return GFpElement(*mp_mres_a); + } + +GFpElement const CurveGFp::get_mres_b() const + { + if(mp_mres_b.get() == 0) + { + mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(mB)); + mp_mres_b->turn_on_sp_red_mul(); + mp_mres_b->get_mres(); + } + return GFpElement(*mp_mres_b); + } + +std::tr1::shared_ptr<GFpElement const> const CurveGFp::get_mres_one() const + { + if(mp_mres_one.get() == 0) + { + mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(mp_mod->get_p(), 1)); + mp_mres_one->turn_on_sp_red_mul(); + mp_mres_one->get_mres(); + } + return mp_mres_one; + } + +bool operator==(CurveGFp const& lhs, CurveGFp const& rhs) + { + return (lhs.get_p() == rhs.get_p() && lhs.get_a() == rhs.get_a() && lhs.get_b() == rhs.get_b()); + } + +} diff --git a/src/ec.cpp b/src/ec.cpp new file mode 100644 index 000000000..7384f8082 --- /dev/null +++ b/src/ec.cpp @@ -0,0 +1,533 @@ +/************************************************* +* ECC Key implemenation * +* (C) 2007 Manuel Hartl / FlexSecure GmbH * +* * +* Falko Strenzke * +* [email protected] * +*************************************************/ + +#include <botan/ec.h> +#include <botan/numthry.h> +#include <botan/util.h> +#include <botan/der_enc.h> +#include <botan/ber_dec.h> +#include <botan/secmem.h> +#include <botan/point_gfp.h> + +namespace Botan { + +/************************************************* +* EC_PublicKey * +*************************************************/ +void EC_PublicKey::affirm_init() const // virtual + { + if ((mp_dom_pars.get() == 0) || (mp_public_point.get() == 0)) + { + throw Invalid_State("cannot use uninitialized EC_Key"); + } + } +EC_Domain_Params const EC_PublicKey::get_domain_parameters() const + { + if(!mp_dom_pars.get()) + { + throw Invalid_State("EC_PublicKey::get_domain_parameters(): ec domain parameters are not yet set"); + } + return *mp_dom_pars; + } +bool EC_PublicKey::domain_parameters_set() + { + if (mp_dom_pars.get()) + { + return true; + } + return false; + } +void EC_PublicKey::X509_load_hook() + { + try + { + // the base point is checked to be on curve already when decoding it + affirm_init(); + mp_public_point->check_invariants(); + } + catch ( Illegal_Point exc ) + { + throw Decoding_Error ( "decoded public point was found not to lie on curve" ); + } + } + + +X509_Encoder* EC_PublicKey::x509_encoder() const + { + class EC_Key_Encoder : public X509_Encoder + { + public: + AlgorithmIdentifier alg_id() const + { + key->affirm_init(); + SecureVector<byte> params = encode_der_ec_dompar ( * ( key->mp_dom_pars ), key->m_param_enc ); + return AlgorithmIdentifier ( key->get_oid(), + params ); + } + + MemoryVector<byte> key_bits() const + { + key->affirm_init(); + return EC2OSP ( * ( key->mp_public_point ), PointGFp::COMPRESSED ); + + } + + EC_Key_Encoder ( const EC_PublicKey* k ) : key ( k ) + {} + private: + const EC_PublicKey* key; + }; + + return new EC_Key_Encoder(this); + } + +X509_Decoder* EC_PublicKey::x509_decoder() + { + class EC_Key_Decoder : public X509_Decoder + { + public: + void alg_id ( const AlgorithmIdentifier& alg_id ) + { + key->mp_dom_pars.reset ( new EC_Domain_Params ( decode_ber_ec_dompar ( alg_id.parameters ) ) ); + } + + void key_bits ( const MemoryRegion<byte>& bits ) + { + key->mp_public_point.reset ( new PointGFp ( OS2ECP ( bits, key->mp_dom_pars->get_curve() ) ) ); + key->X509_load_hook(); + } + + EC_Key_Decoder ( EC_PublicKey* k ) : key ( k ) + {} + private: + EC_PublicKey* key; + }; + + return new EC_Key_Decoder(this); + } + +void EC_PublicKey::set_parameter_encoding ( EC_dompar_enc type ) + { + if ( ( type != ENC_EXPLICIT ) && ( type != ENC_IMPLICITCA ) && ( type != ENC_OID ) ) + { + throw Invalid_Argument ( "invalid encoding type for EC-key object specified" ); + } + affirm_init(); + if ( ( mp_dom_pars->get_oid() == "" ) && ( type == ENC_OID ) ) + { + throw Invalid_Argument ( "invalid encoding type ENC_OID specified for EC-key object whose corresponding domain parameters are without oid" ); + } + m_param_enc = type; + } + +/******************************** +* EC_PrivateKey * +********************************/ +void EC_PrivateKey::affirm_init() const // virtual + { + EC_PublicKey::affirm_init(); + if (m_private_value == 0) + { + throw Invalid_State("cannot use EC_PrivateKey when private key is uninitialized"); + } + } + +/** +* EC_PrivateKey generator +**/ +void EC_PrivateKey::generate_private_key(RandomNumberGenerator& rng) + { + if (mp_dom_pars.get() == 0) + { + throw Invalid_State("cannot generate private key when domain parameters are not set"); + } + BigInt tmp_private_value(0); + tmp_private_value = random_integer (rng, 1, mp_dom_pars->get_order() ); + + mp_public_point = std::auto_ptr<PointGFp>( new PointGFp (mp_dom_pars->get_base_point())); + mp_public_point->mult_this_secure(tmp_private_value, mp_dom_pars->get_order(), mp_dom_pars->get_order()-1); + //assert(mp_public_point.get() != 0); + tmp_private_value.swap(m_private_value); + } + +/** +* Return the PKCS #8 public key encoder +**/ +PKCS8_Encoder* EC_PrivateKey::pkcs8_encoder() const + { + class EC_Key_Encoder : public PKCS8_Encoder + { + public: + AlgorithmIdentifier alg_id() const + { + key->affirm_init(); + SecureVector<byte> params = encode_der_ec_dompar ( * ( key->mp_dom_pars ), ENC_EXPLICIT ); + return AlgorithmIdentifier ( key->get_oid(), + params ); + } + + MemoryVector<byte> key_bits() const + { + key->affirm_init(); + SecureVector<byte> octstr_secret = BigInt::encode_1363 ( key->m_private_value, key->m_private_value.bytes() ); + + return DER_Encoder() + .start_cons ( SEQUENCE ) + .encode ( BigInt ( 1 ) ) + .encode ( octstr_secret, OCTET_STRING ) + .end_cons() + .get_contents(); + } + + EC_Key_Encoder ( const EC_PrivateKey* k ) : key ( k ) + {} + private: + const EC_PrivateKey* key; + }; + + return new EC_Key_Encoder(this); + } + +/** +* Return the PKCS #8 public key decoder +*/ +PKCS8_Decoder* EC_PrivateKey::pkcs8_decoder(RandomNumberGenerator&) + { + class EC_Key_Decoder : public PKCS8_Decoder + { + public: + void alg_id ( const AlgorithmIdentifier& alg_id ) + { + key->mp_dom_pars.reset ( new EC_Domain_Params ( decode_ber_ec_dompar ( alg_id.parameters ) ) ); + } + + void key_bits ( const MemoryRegion<byte>& bits ) + { + u32bit version; + SecureVector<byte> octstr_secret; + BER_Decoder ( bits ) + .start_cons ( SEQUENCE ) + .decode ( version ) + .decode ( octstr_secret, OCTET_STRING ) + .verify_end() + .end_cons(); + key->m_private_value = BigInt::decode ( octstr_secret, octstr_secret.size() ); + if ( version != 1 ) + throw Decoding_Error ( "Wrong PKCS #1 key format version for EC key" ); + key->PKCS8_load_hook(); + } + + EC_Key_Decoder ( EC_PrivateKey* k ) : key ( k ) + {} + private: + EC_PrivateKey* key; + }; + + return new EC_Key_Decoder(this); + } + + +void EC_PrivateKey::PKCS8_load_hook ( bool ) + { + // we cannot use affirm_init() here because mp_public_point might still be null + if (mp_dom_pars.get() == 0 ) + { + throw Invalid_State("attempt to set public point for an uninitialized key"); + } + mp_public_point.reset ( new PointGFp ( m_private_value * mp_dom_pars->get_base_point() ) ); + mp_public_point->check_invariants(); + + } + + + + +/************************************************* +* ECDSA_PublicKey * +*************************************************/ +void ECDSA_PublicKey::affirm_init() const // virtual + { + EC_PublicKey::affirm_init(); + } +void ECDSA_PublicKey::set_domain_parameters(EC_Domain_Params const& dom_pars) + { + if (mp_dom_pars.get()) + { + // they are already set, we must ensure that they are equal to the arg + if (dom_pars != *mp_dom_pars.get()) + { + throw Invalid_Argument("EC_PublicKey::set_domain_parameters(): domain parameters are already set, and they are different from the argument"); + } + else + { + // they are equal, so nothing to do + return; + } + } + // set them ... + if (m_enc_public_point.size() == 0) + { + throw Invalid_State("EC_PublicKey::set_domain_parameters(): encoded public point isn´t set"); + } + + // now try to decode the public key ... + PointGFp tmp_pp(OS2ECP(m_enc_public_point, dom_pars.get_curve())); + try + { + tmp_pp.check_invariants(); + } + catch(Illegal_Point e) + { + throw Invalid_State("EC_PublicKey::set_domain_parameters(): point does not lie on provided curve"); + } + std::auto_ptr<EC_Domain_Params> p_tmp_pars(new EC_Domain_Params(dom_pars)); + ECDSA_Core tmp_ecdsa_core( *p_tmp_pars, BigInt ( 0 ), tmp_pp ); + mp_public_point.reset(new PointGFp(tmp_pp)); + m_ecdsa_core = tmp_ecdsa_core; + mp_dom_pars = p_tmp_pars; + } + +void ECDSA_PublicKey::set_all_values ( ECDSA_PublicKey const& other ) + { + m_param_enc = other.m_param_enc; + m_ecdsa_core = other.m_ecdsa_core; + m_enc_public_point = other.m_enc_public_point; + if ( other.mp_dom_pars.get() ) + { + mp_dom_pars.reset ( new EC_Domain_Params ( * ( other.mp_dom_pars ) ) ); + } + if ( other.mp_public_point.get() ) + { + mp_public_point.reset ( new PointGFp ( * ( other.mp_public_point ) ) ); + } + } +ECDSA_PublicKey::ECDSA_PublicKey ( ECDSA_PublicKey const& other ) + : Public_Key(), + EC_PublicKey(), + PK_Verifying_wo_MR_Key() + { + set_all_values ( other ); + } +ECDSA_PublicKey const& ECDSA_PublicKey::operator= ( ECDSA_PublicKey const& rhs ) + { + set_all_values ( rhs ); + return *this; + } +bool ECDSA_PublicKey::verify ( const byte message[], u32bit mess_len, const byte signature [], u32bit sig_len ) const + { + affirm_init(); + ECDSA_Signature sig; + std::auto_ptr<ECDSA_Signature_Decoder> dec(sig.x509_decoder()); + SecureVector<byte> sv_sig; + sv_sig.set ( signature, sig_len ); + dec->signature_bits ( sv_sig ); + SecureVector<byte> sv_plain_sig = sig.get_concatenation(); + return m_ecdsa_core.verify ( sv_plain_sig, sv_plain_sig.size(), message, mess_len ); + } +ECDSA_PublicKey::ECDSA_PublicKey ( EC_Domain_Params const& dom_par, PointGFp const& public_point ) + { + mp_dom_pars = std::auto_ptr<EC_Domain_Params> ( new EC_Domain_Params ( dom_par ) ); + mp_public_point = std::auto_ptr<PointGFp> ( new PointGFp ( public_point ) ); + m_param_enc = ENC_EXPLICIT; + m_ecdsa_core = ECDSA_Core ( *mp_dom_pars, BigInt ( 0 ), *mp_public_point ); + } +void ECDSA_PublicKey::X509_load_hook() + { + EC_PublicKey::X509_load_hook(); + EC_PublicKey::affirm_init(); + m_ecdsa_core = ECDSA_Core ( *mp_dom_pars, BigInt ( 0 ), *mp_public_point ); + } +u32bit ECDSA_PublicKey::max_input_bits() const + { + if(!mp_dom_pars.get()) + { + throw Invalid_State("ECDSA_PublicKey::max_input_bits(): domain parameters not set"); + } + return mp_dom_pars->get_order().bits(); + } + + +/************************* +* ECDSA_PrivateKey * +*************************/ + +void ECDSA_PrivateKey::affirm_init() const // virtual + { + EC_PrivateKey::affirm_init(); + } + +void ECDSA_PrivateKey::PKCS8_load_hook ( bool generated ) + { + EC_PrivateKey::PKCS8_load_hook ( generated ); + EC_PrivateKey::affirm_init(); + m_ecdsa_core = ECDSA_Core ( *mp_dom_pars, m_private_value, *mp_public_point ); + } + + +void ECDSA_PrivateKey::set_all_values ( ECDSA_PrivateKey const& other ) + { + m_private_value = other.m_private_value; + m_param_enc = other.m_param_enc; + m_ecdsa_core = other.m_ecdsa_core; + m_enc_public_point = other.m_enc_public_point; + if ( other.mp_dom_pars.get() ) + { + mp_dom_pars.reset ( new EC_Domain_Params ( * ( other.mp_dom_pars ) ) ); + } + if ( other.mp_public_point.get() ) + { + mp_public_point.reset ( new PointGFp ( * ( other.mp_public_point ) ) ); + } + } + +ECDSA_PrivateKey::ECDSA_PrivateKey(ECDSA_PrivateKey const& other) + : Public_Key(), + EC_PublicKey(), + Private_Key(), + ECDSA_PublicKey(), + EC_PrivateKey(), + PK_Signing_Key() + { + set_all_values(other); + } +ECDSA_PrivateKey const& ECDSA_PrivateKey::operator= (ECDSA_PrivateKey const& rhs) + { + set_all_values(rhs); + return *this; + } +SecureVector<byte> ECDSA_PrivateKey::sign ( const byte message [], u32bit mess_len ) const + { + affirm_init(); + SecureVector<byte> sv_sig = m_ecdsa_core.sign ( message, mess_len ); + //code which der encodes the signature returned + ECDSA_Signature sig = decode_concatenation( sv_sig ); + std::auto_ptr<ECDSA_Signature_Encoder> enc(sig.x509_encoder()); + return enc->signature_bits(); + + } + + + +/********************************* +* ECKAEG_PublicKey * +*********************************/ + +void ECKAEG_PublicKey::affirm_init() const // virtual + { + EC_PublicKey::affirm_init(); + } + +void ECKAEG_PublicKey::set_all_values ( ECKAEG_PublicKey const& other ) + { + m_param_enc = other.m_param_enc; + m_eckaeg_core = other.m_eckaeg_core; + m_enc_public_point = other.m_enc_public_point; + if ( other.mp_dom_pars.get() ) + { + mp_dom_pars.reset ( new EC_Domain_Params ( * ( other.mp_dom_pars ) ) ); + } + if ( other.mp_public_point.get() ) + { + mp_public_point.reset ( new PointGFp ( * ( other.mp_public_point ) ) ); + } + } +ECKAEG_PublicKey::ECKAEG_PublicKey ( ECKAEG_PublicKey const& other ) + : Public_Key(), + EC_PublicKey() + { + set_all_values ( other ); + } +ECKAEG_PublicKey const& ECKAEG_PublicKey::operator= ( ECKAEG_PublicKey const& rhs ) + { + set_all_values ( rhs ); + return *this; + } + +void ECKAEG_PublicKey::X509_load_hook() + { + EC_PublicKey::X509_load_hook(); + EC_PublicKey::affirm_init(); + m_eckaeg_core = ECKAEG_Core ( *mp_dom_pars, BigInt ( 0 ), *mp_public_point ); + } +ECKAEG_PublicKey::ECKAEG_PublicKey ( EC_Domain_Params const& dom_par, PointGFp const& public_point ) + { + + mp_dom_pars = std::auto_ptr<EC_Domain_Params> ( new EC_Domain_Params ( dom_par ) ); + mp_public_point = std::auto_ptr<PointGFp> ( new PointGFp ( public_point ) ); + if(mp_public_point->get_curve() != mp_dom_pars->get_curve()) + { + throw Invalid_Argument("ECKAEG_PublicKey(): curve of arg. point and curve of arg. domain parameters are different"); + } + EC_PublicKey::affirm_init(); + m_eckaeg_core = ECKAEG_Core ( *mp_dom_pars, BigInt ( 0 ), *mp_public_point ); + } + + +/********************************* +* ECKAEG_PrivateKey * +*********************************/ +void ECKAEG_PrivateKey::affirm_init() const // virtual + { + EC_PrivateKey::affirm_init(); + } +void ECKAEG_PrivateKey::PKCS8_load_hook ( bool generated ) + { + EC_PrivateKey::PKCS8_load_hook ( generated ); + EC_PrivateKey::affirm_init(); + m_eckaeg_core = ECKAEG_Core ( *mp_dom_pars, m_private_value, *mp_public_point ); + } +void ECKAEG_PrivateKey::set_all_values ( ECKAEG_PrivateKey const& other ) + { + m_private_value = other.m_private_value; + m_param_enc = other.m_param_enc; + m_eckaeg_core = other.m_eckaeg_core; + m_enc_public_point = other.m_enc_public_point; + if ( other.mp_dom_pars.get() ) + { + mp_dom_pars.reset ( new EC_Domain_Params ( * ( other.mp_dom_pars ) ) ); + } + if ( other.mp_public_point.get() ) + { + mp_public_point.reset ( new PointGFp ( * ( other.mp_public_point ) ) ); + } + } + +ECKAEG_PrivateKey::ECKAEG_PrivateKey(ECKAEG_PrivateKey const& other) + : Public_Key(), + EC_PublicKey(), + Private_Key(), + ECKAEG_PublicKey(), + EC_PrivateKey(), + PK_Key_Agreement_Key() + + { + set_all_values(other); + } +ECKAEG_PrivateKey const& ECKAEG_PrivateKey::operator= (ECKAEG_PrivateKey const& rhs) + { + set_all_values(rhs); + return *this; + } + +/** +* Derive a key +*/ +SecureVector<byte> ECKAEG_PrivateKey::derive_key(const Public_Key& key) const + { + affirm_init(); + + const EC_PublicKey * p_ec_pk = dynamic_cast<const EC_PublicKey*>(&key); + if(!p_ec_pk) + { + throw Invalid_Argument("ECKAEG_PrivateKey::derive_key(): argument must be an EC_PublicKey"); + } + p_ec_pk->affirm_init(); + return m_eckaeg_core.agree ( p_ec_pk->get_public_point() ); + } + +} diff --git a/src/ec_dompar.cpp b/src/ec_dompar.cpp new file mode 100644 index 000000000..232233669 --- /dev/null +++ b/src/ec_dompar.cpp @@ -0,0 +1,288 @@ +#include <botan/ec_dompar.h> +#include <botan/ec.h> +#include <botan/enums.h> +#include <botan/parsing.h> +#include <botan/libstate.h> +#include <botan/hex.h> + +namespace Botan { + +namespace { + +std::vector<std::string> get_standard_domain_parameter(const std::string& oid) + { + /* + GEC 2: Test Vectors for SEC 1 + Certicom Research + Working Draft + September, 1999 + Version 0.3; + section 2.1.2 + */ + if(oid == "1.3.132.8") // InSiTo had '08' + { + std::vector<std::string> dom_par; + dom_par.push_back("0xffffffffffffffffffffffffffffffff7fffffff"); //p + dom_par.push_back("0xffffffffffffffffffffffffffffffff7ffffffc"); // a + dom_par.push_back("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); // b + dom_par.push_back("024a96b5688ef573284664698968c38bb913cbfc82"); // G + dom_par.push_back("0x0100000000000000000001f4c8f927aed3ca752257"); // order + dom_par.push_back("1"); // cofactor + return dom_par; + } + + if(oid == "1.2.840.10045.3.1.1") // prime192v1 Flexiprovider + { + std::vector<std::string> dom_par; + dom_par.push_back("0xfffffffffffffffffffffffffffffffeffffffffffffffff"); //p + dom_par.push_back("0xfffffffffffffffffffffffffffffffefffffffffffffffc"); // a + dom_par.push_back("0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"); // b + dom_par.push_back("03188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"); // G + dom_par.push_back("0xffffffffffffffffffffffff99def836146bc9b1b4d22831"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime192v2; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.2") + { + std::vector<std::string> dom_par; + dom_par.push_back("0xfffffffffffffffffffffffffffffffeffffffffffffffff"); //p + dom_par.push_back("0xffffffffffffffffffffffffffffffFeffffffffffffffFC"); // a + dom_par.push_back("0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953"); // b + dom_par.push_back("03eea2bae7e1497842f2de7769cfe9c989c072ad696f48034a"); // G + dom_par.push_back("0xfffffffffffffffffffffffe5fb1a724dc80418648d8dd31"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime192v3; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.3") + { + std::vector<std::string> dom_par; + dom_par.push_back("0xfffffffffffffffffffffffffffffffeffffffffffffffff"); //p + dom_par.push_back("0xfffffffffffffffffffffffffffffffefffffffffffffffc"); // a + dom_par.push_back("0x22123dc2395a05caa7423daeccc94760a7d462256bd56916"); // b + dom_par.push_back("027d29778100c65a1da1783716588dce2b8b4aee8e228f1896"); // G + dom_par.push_back("0xffffffffffffffffffffffff7a62d031c83f4294f640ec13"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime239v1; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.4") + { + std::vector<std::string> dom_par; + dom_par.push_back("0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff"); //p + dom_par.push_back("0x7ffFffffffffffffffffffff7fffffffffff8000000000007ffffffffffc"); // a + dom_par.push_back("0x6B016C3BDCF18941D0D654921475CA71A9DB2FB27D1D37796185C2942C0A"); // b + dom_par.push_back("020ffA963CDCA8816CCC33B8642BEDF905C3D358573D3F27FBBD3B3CB9AAAF"); // G + dom_par.push_back("0x7fffffffffffffffffffffff7fffff9e5e9a9f5d9071fbd1522688909d0b"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime239v2; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.5") + { + std::vector<std::string> dom_par; + dom_par.push_back("0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff"); //p + dom_par.push_back("0x7ffFffffffffffffffffffff7ffFffffffff8000000000007ffFffffffFC"); // a + dom_par.push_back("0x617FAB6832576CBBFED50D99F0249C3FEE58B94BA0038C7AE84C8C832F2C"); // b + dom_par.push_back("0238AF09D98727705120C921BB5E9E26296A3CDCF2F35757A0EAFD87B830E7"); // G + dom_par.push_back("0x7fffffffffffffffffffffff800000CFA7E8594377D414C03821BC582063"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime239v3; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.6") + { + std::vector<std::string> dom_par; + dom_par.push_back("0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff"); //p + dom_par.push_back("0x7ffFffffffffffffffffffff7ffFffffffff8000000000007ffFffffffFC"); // a + dom_par.push_back("0x255705FA2A306654B1F4CB03D6A750A30C250102D4988717D9BA15AB6D3E"); // b + dom_par.push_back("036768AE8E18BB92CFCF005C949AA2C6D94853D0E660BBF854B1C9505FE95A"); // G + dom_par.push_back("0x7fffffffffffffffffffffff7fffff975DEB41B3A6057C3C432146526551"); // order + dom_par.push_back("1"); // cofactor + } + + /* prime256v1; source: Flexiprovider */ + if(oid == "1.2.840.10045.3.1.7") + { + std::vector<std::string> dom_par; + dom_par.push_back("0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff"); //p + dom_par.push_back("0xffffffff00000001000000000000000000000000ffffffffffffffffffffffFC"); // a + dom_par.push_back("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B"); // b + dom_par.push_back("036B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296"); // G + dom_par.push_back("0xffffffff00000000ffffffffffffffffBCE6FAADA7179E84F3B9CAC2FC632551"); // order + dom_par.push_back("1"); // cofactor + } + + throw Invalid_Argument("No such ECC curve " + oid); + + // Todo, add SEC2, Brainpool, NIST curves + } + +EC_Domain_Params get_ec_dompar(const std::string& oid) + { + std::vector<std::string> dom_par = get_standard_domain_parameter(oid); + + BigInt p(dom_par[0]); // give as 0x... + GFpElement a(p, BigInt(dom_par[1])); + GFpElement b(p, BigInt(dom_par[2])); + + Pipe pipe(new Hex_Decoder); + pipe.process_msg(dom_par[3]); + SecureVector<byte> sv_g = pipe.read_all(); + + CurveGFp curve(a, b, p); + PointGFp G = OS2ECP ( sv_g, curve ); + G.check_invariants(); + BigInt order(dom_par[4]); + BigInt cofactor(dom_par[5]); + EC_Domain_Params result(curve, G, order, cofactor); + return result; + } + +} + +EC_Domain_Params get_EC_Dom_Pars_by_oid(std::string oid) + { + EC_Domain_Params result = get_ec_dompar(oid); + result.m_oid = oid; + return result; + } + +EC_Domain_Params::EC_Domain_Params(const CurveGFp& curve, const PointGFp& base_point, + const BigInt& order, const BigInt& cofactor) + : m_curve(curve), + m_base_point(base_point), + m_order(order), + m_cofactor(cofactor), + m_oid("") + { } + +namespace { + +SecureVector<byte> encode_der_ec_dompar_explicit(EC_Domain_Params const& dom_pars) + { + u32bit ecpVers1 = 1; + OID curve_type_oid("1.2.840.10045.1.1"); + + DER_Encoder der; + + der.start_cons(SEQUENCE) + .encode(ecpVers1) + .start_cons(SEQUENCE) + .encode(curve_type_oid) + .encode(dom_pars.get_curve().get_p()) + .end_cons() + .start_cons(SEQUENCE) + .encode(FE2OSP ( dom_pars.get_curve().get_a() ), OCTET_STRING) + .encode(FE2OSP ( dom_pars.get_curve().get_b() ), OCTET_STRING) + .end_cons() + .encode(EC2OSP ( dom_pars.get_base_point(), PointGFp::UNCOMPRESSED), OCTET_STRING) + .encode(dom_pars.get_order()) + .encode(dom_pars.get_cofactor()) + .end_cons(); + + return der.get_contents(); + } + +EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded) + { + BigInt ecpVers1(1); + OID curve_type_oid; + SecureVector<byte> sv_a; + SecureVector<byte> sv_b; + BigInt p; + SecureVector<byte> sv_base_point; + BigInt order; + BigInt cofactor; + BER_Decoder dec(encoded); + dec + .start_cons(SEQUENCE) + .decode(ecpVers1) + .start_cons(SEQUENCE) + .decode(curve_type_oid) + .decode(p) + .end_cons() + .start_cons(SEQUENCE) + .decode(sv_a, OCTET_STRING) + .decode(sv_b, OCTET_STRING) + .end_cons() + .decode(sv_base_point, OCTET_STRING) + .decode(order) + .decode(cofactor) + .verify_end() + .end_cons(); + if(ecpVers1 != 1) + { + throw Decoding_Error("wrong ecpVers"); + } + // Set the domain parameters + if(curve_type_oid.as_string() != "1.2.840.10045.1.1") // NOTE: hardcoded: prime field type + { + throw Decoding_Error("wrong curve type oid where prime field was expected"); + } + GFpElement a(p,BigInt::decode(sv_a, sv_a.size())); + GFpElement b(p,BigInt::decode(sv_b, sv_b.size())); + CurveGFp curve(a,b,p); + PointGFp G = OS2ECP ( sv_base_point, curve ); + G.check_invariants(); + return EC_Domain_Params(curve, G, order, cofactor); + } + +} // end anonymous namespace + +SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, EC_dompar_enc enc_type) + { + SecureVector<byte> result; + + if(enc_type == ENC_EXPLICIT) + { + result = encode_der_ec_dompar_explicit(dom_pars); + } + else if(enc_type == ENC_OID) + { + OID dom_par_oid(dom_pars.get_oid()); + result = DER_Encoder().encode(dom_par_oid).get_contents(); + } + else if(enc_type == ENC_IMPLICITCA) + { + result = DER_Encoder().encode_null().get_contents(); + } + else + { + throw Internal_Error("encountered illegal value for ec parameter encoding type"); + } + return result; + } + +EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded) + { + BER_Decoder dec(encoded); + BER_Object obj = dec.get_next_object(); + ASN1_Tag tag = obj.type_tag; + std::auto_ptr<EC_Domain_Params> p_result; + + if(tag == OBJECT_ID) + { + OID dom_par_oid; + BER_Decoder(encoded).decode(dom_par_oid); + return EC_Domain_Params(get_ec_dompar(dom_par_oid.as_string())); + } + else if(tag == SEQUENCE) + return EC_Domain_Params(decode_ber_ec_dompar_explicit(encoded)); + else if(tag == NULL_TAG) + throw Decoding_Error("cannot decode ECDSA parameters that are ImplicitCA"); + + throw Decoding_Error("encountered unexpected when trying to decode domain parameters"); + } + +bool operator==(EC_Domain_Params const& lhs, EC_Domain_Params const& rhs) + { + return ((lhs.get_curve() == rhs.get_curve()) && + (lhs.get_base_point() == rhs.get_base_point()) && + (lhs.get_order() == rhs.get_order()) && + (lhs.get_cofactor() == rhs.get_cofactor())); + } + +} + diff --git a/src/ecdsa.cpp b/src/ecdsa.cpp new file mode 100644 index 000000000..04dc1e529 --- /dev/null +++ b/src/ecdsa.cpp @@ -0,0 +1,72 @@ +#include <botan/bigint.h> +#include <botan/ecdsa.h> +#include <memory> + +namespace Botan { + +ECDSA_Signature::ECDSA_Signature(const BigInt& r, const BigInt& s) + : m_r(r), + m_s(s) + {} + +ECDSA_Signature::ECDSA_Signature(ECDSA_Signature const& other) + : m_r(other.m_r), + m_s(other.m_s) + {} + +ECDSA_Signature const& ECDSA_Signature::operator=(ECDSA_Signature const& other) + { + m_r = other.m_r; + m_s = other.m_s; + return *this; + } + +bool operator== ( ECDSA_Signature const& lhs, ECDSA_Signature const& rhs ) + { + return (lhs.get_r() == rhs.get_r() && lhs.get_s() == rhs.get_s()); + } + +ECDSA_Signature_Decoder* ECDSA_Signature::x509_decoder() + { + return new ECDSA_Signature_Decoder(this); + } + +ECDSA_Signature_Encoder* ECDSA_Signature::x509_encoder() const + { + return new ECDSA_Signature_Encoder(this); + } +SecureVector<byte> const ECDSA_Signature::get_concatenation() const + { + u32bit enc_len = m_r > m_s ? m_r.bytes() : m_s.bytes(); // use the larger + SecureVector<byte> sv_r = BigInt::encode_1363 ( m_r, enc_len ); + SecureVector<byte> sv_s = BigInt::encode_1363 ( m_s, enc_len ); + SecureVector<byte> result(sv_r); + result.append(sv_s); + return result; + } + +ECDSA_Signature const decode_seq(MemoryRegion<byte> const& seq) + { + ECDSA_Signature sig; + std::auto_ptr<ECDSA_Signature_Decoder> dec(sig.x509_decoder()); + dec->signature_bits(seq); + return sig; + } + +ECDSA_Signature const decode_concatenation(MemoryRegion<byte> const& concatenation) + { + if(concatenation.size() % 2 != 0) + { + throw Invalid_Argument("Erroneous length of signature"); + } + u32bit rs_len = concatenation.size()/2; + SecureVector<byte> sv_r; + SecureVector<byte> sv_s; + sv_r.set(concatenation.begin(), rs_len); + sv_s.set(&concatenation[rs_len], rs_len); + BigInt r = BigInt::decode ( sv_r, sv_r.size()); + BigInt s = BigInt::decode (sv_s, sv_s.size()); + return ECDSA_Signature(r, s); + } + +} diff --git a/src/eng_base.cpp b/src/eng_base.cpp index 38234d462..bd6b53447 100644 --- a/src/eng_base.cpp +++ b/src/eng_base.cpp @@ -111,6 +111,26 @@ DH_Operation* Engine::dh_op(const DL_Group&, const BigInt&) const /************************************************* * Basic No-Op Engine Implementation * *************************************************/ +ECDSA_Operation* Engine::ecdsa_op(const EC_Domain_Params&, + const BigInt&, + const PointGFp&) const + { + return 0; + } + +/************************************************* +* Basic No-Op Engine Implementation * +*************************************************/ +ECKAEG_Operation* Engine::eckaeg_op(const EC_Domain_Params&, + const BigInt&, + const PointGFp&) const + { + return 0; + } + +/************************************************* +* Basic No-Op Engine Implementation * +*************************************************/ Modular_Exponentiator* Engine::mod_exp(const BigInt&, Power_Mod::Usage_Hints) const { diff --git a/src/engine.cpp b/src/engine.cpp index 0a4bb48ee..bfa02ed5d 100644 --- a/src/engine.cpp +++ b/src/engine.cpp @@ -101,6 +101,44 @@ DH_Operation* dh_op(const DL_Group& group, const BigInt& x) } /************************************************* +* Acquire an ECDSA op * +*************************************************/ +ECDSA_Operation* ecdsa_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key) + { + Library_State::Engine_Iterator i(global_state()); + + while(const Engine* engine = i.next()) + { + ECDSA_Operation* op = engine->ecdsa_op(dom_pars, priv_key, pub_key); + if(op) + return op; + } + + throw Lookup_Error("Engine_Core::ecdsa_op: Unable to find a working engine"); + } + +/************************************************* +* Acquire a ECKAEG op * +*************************************************/ +ECKAEG_Operation* eckaeg_op(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key) + { + Library_State::Engine_Iterator i(global_state()); + + while(const Engine* engine = i.next()) + { + ECKAEG_Operation* op = engine->eckaeg_op(dom_pars, priv_key, pub_key); + if(op) + return op; + } + + throw Lookup_Error("Engine_Core::eckaeg_op: Unable to find a working engine"); + } + +/************************************************* * Acquire a modular exponentiator * *************************************************/ Modular_Exponentiator* mod_exp(const BigInt& n, Power_Mod::Usage_Hints hints) diff --git a/src/gfp_element.cpp b/src/gfp_element.cpp new file mode 100644 index 000000000..686cc338b --- /dev/null +++ b/src/gfp_element.cpp @@ -0,0 +1,674 @@ +/****************************************************** + * Arithmetic for prime fields GF(p) (source file) * + * * + * (C) 2007 Martin Doering * + * [email protected] * + * Christoph Ludwig * + * [email protected] * + * Falko Strenzke * + * [email protected] * + ******************************************************/ + +#include <botan/gfp_element.h> +#include <botan/numthry.h> +#include <botan/def_powm.h> +#include <botan/mp_asm.h> +#include <botan/mp_asmi.h> +#include <botan/mp_core.h> + +namespace Botan { + +namespace { + +/** +*calculates R=b^n (here b=2) with R>m (and R beeing as small as possible) for an odd modulus m. +* no check for oddity is performed! +*/ +BigInt montgm_calc_r_oddmod(const BigInt& prime) + { + u32bit n = prime.sig_words(); + BigInt result(1); + result <<= n*BOTAN_MP_WORD_BITS; + return result; + + } + +/** +*calculates m' with r*r^-1 - m*m' = 1 +* where r^-1 is the multiplicative inverse of r to the modulus m +*/ +BigInt montgm_calc_m_dash(const BigInt& r, const BigInt& m, const BigInt& r_inv ) + { + BigInt result = ((r * r_inv) - BigInt(1))/m; + return result; + } +BigInt montg_trf_to_mres(const BigInt& ord_res, const BigInt& r, const BigInt& m) + { + BigInt result(ord_res); + result *= r; + result %= m; + return result; + } +BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r_inv) + { + BigInt result(m_res); + result *= r_inv; + result %= m; + return result; + } + +void inner_montg_mult_sos(word result[], const word* a_bar, + const word* b_bar, const word* n, + const word* n_dash, u32bit s) + { + SecureVector<word> t; + t.grow_to(2*s+1); + + for (u32bit i=0; i<s; i++) + { + word C = 0; + word S = 0; + for (u32bit j=0; j<s; j++) + { + S = word_madd3(a_bar[j], b_bar[i], t[i+j], &C); + t[i+j] = S; + } + t[i+s] = C; + } + + + for (u32bit i=0; i<s; i++) + { + // word word_madd2(word a, word b, word c, word* carry) + // returns a * b + c, resets the carry + + word C = 0; + word m = word_madd2(t[i], n_dash[0], &C); + // C = 0; ??? + + for (u32bit j=0; j<s; j++) + { + word S = word_madd3(m, n[j], t[i+j], &C); + t[i+j] = S; + } + + //// mp_mulop.cpp: + ////word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y) + u32bit cnt = 0; + while (C > 0) + { + // we need not worry here about C > 1, because the other operand is zero + word tmp = word_add(t[i+s+cnt], 0, &C); + t[i+s+cnt] = tmp; + cnt++; + } + } + SecureVector<word> u; + u.grow_to(s+1); + for (u32bit j=0; j<s+1; j++) + { + u[j] = t[j+s]; + } + + word B = 0; + word D = 0; + for (u32bit i=0; i<s; i++) + { + D = word_sub(u[i], n[i], &B); + t[i] = D; + } + D = word_sub(u[s], 0, &B); + t[s] = D; + if (B == 0) + { + for (u32bit i=0; i<s; i++) + { + result[i] = t[i]; + } + } + else + { + for (u32bit i=0; i<s; i++) + { + result[i] = u[i]; + } + } + } + +void montg_mult(BigInt& result, BigInt& a_bar, BigInt& b_bar, const BigInt& m, const BigInt& m_dash, const BigInt ) + { + if (m.is_zero() || m_dash.is_zero()) + { + throw Invalid_Argument("montg_mult(): neither modulus nor m_dash may be zero (and one of them was)"); + } + if (a_bar.is_zero() || b_bar.is_zero()) + { + result = 0; + } + u32bit s = m.sig_words(); + a_bar.grow_to(s); + b_bar.grow_to(s); + + result.grow_to(s); + + inner_montg_mult_sos(result.get_reg(), a_bar.data(), b_bar.data(), m.data(), m_dash.data(), s); + + } + + +} + +GFpElement::GFpElement ( const BigInt& p, const BigInt& value, bool use_montgm) + : mp_mod(), + m_value(value %p), + m_use_montgm(use_montgm), + m_is_trf(false) + { + //assert(mp_mod.get() == 0); + mp_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(p)); + //assert(mp_mod->m_p_dash == 0); + if (m_use_montgm) + { + ensure_montgm_precomp(); + + } + + } + +GFpElement::GFpElement(std::tr1::shared_ptr<GFpModulus> const mod, const BigInt& value, bool use_montgm) + : mp_mod(), + m_value(value % mod->m_p), + m_use_montgm(use_montgm), + m_is_trf(false) + { + //assert(mp_mod.get() == 0); + mp_mod = mod; + } + +GFpElement::GFpElement ( GFpElement const& other ) + : m_value ( other.m_value ), + m_use_montgm(other.m_use_montgm), + m_is_trf(other.m_is_trf) + + { + //creates an independent copy + //assert((other.m_is_trf && other.m_use_montgm) || !other.m_is_trf); + mp_mod.reset(new GFpModulus(*other.mp_mod)); // copy-ctor of GFpModulus + } + +void GFpElement::turn_on_sp_red_mul() const + { + ensure_montgm_precomp(); + m_use_montgm = true; + } +void GFpElement::turn_off_sp_red_mul() const + { + if (m_is_trf) + { + trf_to_ordres(); + // will happen soon anyway, so we can do it here already + // (this is not lazy but way more secure concerning our internal logic here) + } + m_use_montgm = false; + } +void GFpElement::ensure_montgm_precomp() const + { + if ((!mp_mod->m_r.is_zero()) && (!mp_mod->m_r_inv.is_zero()) && (!mp_mod->m_p_dash.is_zero())) + { + // values are already set, nothing more to do + } + else + { + BigInt tmp_r(montgm_calc_r_oddmod(mp_mod->m_p)); + + BigInt tmp_r_inv(inverse_mod(tmp_r, mp_mod->m_p)); + + BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, mp_mod->m_p, tmp_r_inv)); + + mp_mod->m_r.grow_reg(tmp_r.size()); + mp_mod->m_r_inv.grow_reg(tmp_r_inv.size()); + mp_mod->m_p_dash.grow_reg(tmp_p_dash.size()); + + mp_mod->m_r = tmp_r; + mp_mod->m_r_inv = tmp_r_inv; + mp_mod->m_p_dash = tmp_p_dash; + + //assert(!mp_mod->m_r.is_zero()); + //assert(!mp_mod->m_r_inv.is_zero()); + //assert(!mp_mod->m_p_dash.is_zero()); + } + + } + +void GFpElement::set_shrd_mod(std::tr1::shared_ptr<GFpModulus> const p_mod) + { + mp_mod = p_mod; + } +void GFpElement::trf_to_mres() const + { + if (!m_use_montgm) + { + throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); + } + //assert(m_is_trf == false); + //assert(!mp_mod->m_r_inv.is_zero()); + //assert(!mp_mod->m_p_dash.is_zero()); + m_value = montg_trf_to_mres(m_value, mp_mod->m_r, mp_mod->m_p); + m_is_trf = true; + } +void GFpElement::trf_to_ordres() const + { + //assert(m_is_trf == true); + m_value = montg_trf_to_ordres(m_value, mp_mod->m_p, mp_mod->m_r_inv); + m_is_trf = false; + } +bool GFpElement::align_operands_res(GFpElement const& lhs, GFpElement const& rhs) //static + { + //assert(lhs.mp_mod->m_p == rhs.mp_mod->m_p); + if (lhs.m_use_montgm && rhs.m_use_montgm) + { + + //assert(rhs.mp_mod->m_p_dash == lhs.mp_mod->m_p_dash); + //assert(rhs.mp_mod->m_r == lhs.mp_mod->m_r); + //assert(rhs.mp_mod->m_r_inv == lhs.mp_mod->m_r_inv); + if (!lhs.m_is_trf && !rhs.m_is_trf) + { + return false; + } + else if (lhs.m_is_trf && rhs.m_is_trf) + { + return true; + } + else // one is transf., the other not + { + if (!lhs.m_is_trf) + { + lhs.trf_to_mres(); + //assert(rhs.m_is_trf==true); + return true; + } + //assert(rhs.m_is_trf==false); + //assert(lhs.m_is_trf==true); + rhs.trf_to_mres(); // the only possibility left... + return true; + } + } + else // at least one of them does not use mm + // (so it is impossible that both use it) + { + if (lhs.m_is_trf) + { + lhs.trf_to_ordres(); + //assert(rhs.m_is_trf == false); + return false; + } + if (rhs.m_is_trf) + { + rhs.trf_to_ordres(); + //assert(lhs.m_is_trf == false); + return false; + } + return false; + } + //assert(false); + + } +bool GFpElement::is_trf_to_mres() const + { + return m_is_trf; + + } +BigInt const GFpElement::get_p() const + { + return (mp_mod->m_p); + } +BigInt const GFpElement::get_value() const + { + + if (m_is_trf) + { + //assert(m_use_montgm); + trf_to_ordres(); + } + return m_value; + } +BigInt const GFpElement::get_mres() const + { + if (!m_use_montgm) + { + // does the following exception really make sense? + // wouldn´t it be better to simply turn on montg.mult. when + // this explicit request is made? + throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); + } + if (!m_is_trf) + { + + trf_to_mres(); + + } + return m_value; + } +GFpElement const& GFpElement::operator= ( GFpElement const& other ) + { + m_value.grow_reg(other.m_value.size()); // grow first for exception safety + + //m_value = other.m_value; + + // m_use_montgm = other.m_use_montgm; + // m_is_trf = other.m_is_trf; + // we want to keep the member pointers, which might be part of a "sharing group" + // but we may not simply overwrite the BigInt values with those of the argument!! + // if ours already contains precomputations, it would be hazardous to + // set them back to zero. + // thus we first check for equality of the moduli, + // then whether either of the two objects already contains + // precomputed values. + + // we also deal with the case were the pointers themsevles are equal: + if (mp_mod.get() == other.mp_mod.get()) + { + // everything ok, we are in the same sharing group anyway, nothing to do + m_value = other.m_value; // cannot throw + m_use_montgm = other.m_use_montgm; + m_is_trf = other.m_is_trf; + return *this; + } + if (mp_mod->m_p != other.mp_mod->m_p) + { + // the moduli are different, this is a special case + // which will not occur in usual applications, + // so we don´t hesitate to simply create new objects + // (we do want to create an independent copy) + mp_mod.reset(new GFpModulus(*other.mp_mod)); // this could throw, + // and because of this + // we haven't modified + // anything so far + m_value = other.m_value; // can't throw + m_use_montgm = other.m_use_montgm; + m_is_trf = other.m_is_trf; + return *this; + } + // exception safety note: from now on we are on the safe + // side with respect to the modulus, + // so we can assign the value now: + m_value = other.m_value; + m_use_montgm = other.m_use_montgm; + m_is_trf = other.m_is_trf; + // the moduli are equal, but we deal with different sharing groups. + // we will NOT fuse the sharing goups + // and we will NOT reset already precomputed values + if (mp_mod->has_precomputations()) + { + // our own sharing group already has precomputed values, + // so nothing to do. + return *this; + } + else + { + // let´s see whether the argument has something for us... + if (other.mp_mod->has_precomputations()) + { + // fetch them for our sharing group + // exc. safety note: grow first + mp_mod->m_p_dash.grow_reg(other.mp_mod->m_p_dash.size()); + mp_mod->m_r.grow_reg(other.mp_mod->m_r.size()); + mp_mod->m_r_inv.grow_reg(other.mp_mod->m_r_inv.size()); + + mp_mod->m_p_dash = other.mp_mod->m_p_dash; + mp_mod->m_r = other.mp_mod->m_r; + mp_mod->m_r_inv = other.mp_mod->m_r_inv; + return *this; + } + } + // our precomputations aren´t set, the arguments neither, + // so we let them alone + return *this; + + + } +void GFpElement::share_assign(GFpElement const& other) + { + //assert((other.m_is_trf && other.m_use_montgm) || !other.m_is_trf); + + // use grow_to to make it exc safe + m_value.grow_reg(other.m_value.size()); + m_value = other.m_value; + + m_use_montgm = other.m_use_montgm; + m_is_trf = other.m_is_trf; + mp_mod = other.mp_mod; // cannot throw + + } +GFpElement& GFpElement::operator+= ( GFpElement const& rhs ) + { + GFpElement::align_operands_res(*this, rhs); + + workspace = m_value; + workspace += rhs.m_value; + if (workspace >= mp_mod->m_p) + { + workspace -= mp_mod->m_p; + } + + m_value = workspace; + //assert(m_value < mp_mod->m_p); + //assert(m_value >= 0); + + return *this; + } +GFpElement& GFpElement::operator-= ( GFpElement const& rhs ) + { + GFpElement::align_operands_res(*this, rhs); + + workspace = m_value; + + workspace -= rhs.m_value; + + if (workspace.is_negative()) + { + workspace += mp_mod->m_p; + } + + m_value = workspace; + //assert(m_value < mp_mod->m_p); + //assert(m_value >= 0); + return *this; + + } +GFpElement& GFpElement::operator*= (u32bit rhs) + { + workspace = m_value; + workspace *= rhs; + workspace %= mp_mod->m_p; + m_value = workspace; + return *this; + } +GFpElement& GFpElement::operator*= ( GFpElement const& rhs ) + { + //assert(rhs.mp_mod->m_p == mp_mod->m_p); + // here, we do not use align_operands_res() for one simple reason: + // we want to enforce the transformation to an m-residue, otherwise it would + // never happen + if (m_use_montgm && rhs.m_use_montgm) + { + //assert(rhs.mp_mod->m_p == mp_mod->m_p); // is montgm. mult is on, then precomps must be there + //assert(rhs.mp_mod->m_p_dash == mp_mod->m_p_dash); + //assert(rhs.mp_mod->m_r == mp_mod->m_r); + if (!m_is_trf) + { + trf_to_mres(); + } + if (!rhs.m_is_trf) + { + rhs.trf_to_mres(); + } + workspace = m_value; + montg_mult(m_value, workspace, rhs.m_value, mp_mod->m_p, mp_mod->m_p_dash, mp_mod->m_r); + } + else // ordinary multiplication + { + if (m_is_trf) + { + //assert(m_use_montgm); + trf_to_ordres(); + } + if (rhs.m_is_trf) + { + //assert(rhs.m_use_montgm); + rhs.trf_to_ordres(); + } + workspace = m_value; + workspace *= rhs.m_value; + workspace %= mp_mod->m_p; + m_value = workspace; + } + return *this; + } +GFpElement& GFpElement::operator/= ( GFpElement const& rhs ) + { + bool use_mres = GFpElement::align_operands_res(*this, rhs); + //assert((this->m_is_trf && rhs.m_is_trf) || !(this->m_is_trf && rhs.m_is_trf) ); + // (internal note: see C86) + if (use_mres) + { + //assert(m_use_montgm && rhs.m_use_montgm); + GFpElement rhs_ordres(rhs); + rhs_ordres.trf_to_ordres(); + rhs_ordres.inverse_in_place(); + workspace = m_value; + workspace *= rhs_ordres.get_value(); + workspace %= mp_mod->m_p; + m_value = workspace; + + } + else + { + GFpElement inv_rhs(rhs); + inv_rhs.inverse_in_place(); + *this *= inv_rhs; + } + return *this; + } +bool GFpElement::is_zero() + { + return (m_value.is_zero()); + // this is correct because x_bar = x * r = x = 0 for x = 0 + } +GFpElement& GFpElement::inverse_in_place() + { + m_value = inverse_mod(m_value, mp_mod->m_p); + if (m_is_trf) + { + //assert(m_use_montgm); + + m_value *= mp_mod->m_r; + m_value *= mp_mod->m_r; + m_value %= mp_mod->m_p; + } + //assert(m_value <= mp_mod->m_p); + return *this; + + } +GFpElement& GFpElement::negate() + { + m_value = mp_mod->m_p - m_value; + //assert(m_value <= mp_mod->m_p); + return *this; + } +void GFpElement::swap ( GFpElement& other ) + { + m_value.swap ( other.m_value ); + mp_mod.swap(other.mp_mod); + std::swap<bool>(m_use_montgm,other.m_use_montgm); + std::swap<bool>(m_is_trf,other.m_is_trf); + } + +bool operator== ( GFpElement const& lhs, GFpElement const& rhs ) + { + // for effeciency reasons we firstly check whether + //the modulus pointers are different in the first place: + if (lhs.get_ptr_mod() != rhs.get_ptr_mod()) + { + if (lhs.get_p() != rhs.get_p()) + { + return false; + } + } + // so the modulus is equal, now check the values + bool use_mres = GFpElement::align_operands_res(lhs, rhs); + + if (use_mres) + { + return (lhs.get_mres() == rhs.get_mres()); + } + else + { + return(lhs.get_value() == rhs.get_value()); + } + } + +GFpElement operator+ ( GFpElement const& lhs, GFpElement const& rhs ) + { + // consider the case that lhs and rhs both use montgm: + // then += returns an element which uses montgm. + // thus the return value of op+ here will be an element + // using montgm in this case + // NOTE: the rhs might be transformed when using op+, the lhs never + GFpElement result ( lhs ); + result += rhs; + return result; + } +GFpElement operator- ( GFpElement const& lhs, GFpElement const& rhs ) + { + GFpElement result ( lhs ); + result -= rhs; + return result; + // NOTE: the rhs might be transformed when using op-, the lhs never + } +GFpElement operator- ( GFpElement const& lhs ) + { + return ( GFpElement ( lhs ) ).negate(); + } +GFpElement operator* ( GFpElement const& lhs, GFpElement const& rhs ) + { + // consider the case that lhs and rhs both use montgm: + // then *= returns an element which uses montgm. + // thus the return value of op* here will be an element + // using montgm in this case + GFpElement result ( lhs ); + result *= rhs; + return result; + } +GFpElement operator*(GFpElement const& lhs, u32bit rhs) + { + GFpElement result(lhs); + result *= rhs; + return result; + + } +GFpElement operator*(u32bit lhs, GFpElement const& rhs ) + { + return rhs*lhs; + } +GFpElement operator/ ( GFpElement const& lhs, GFpElement const& rhs ) + { + GFpElement result (lhs); + result /= rhs; + return result; + } +SecureVector<byte> FE2OSP ( GFpElement const& elem ) + { + return BigInt::encode_1363 ( elem.get_value(), elem.get_p().bytes() ); + } +GFpElement OS2FEP ( MemoryRegion<byte> const& os, BigInt p ) + { + + return GFpElement ( p, BigInt::decode ( os.begin(), os.size() ) ); + } +GFpElement inverse ( GFpElement const& elem ) + { + return GFpElement ( elem ).inverse_in_place(); + } + +} // namespace Botan diff --git a/src/pk_core.cpp b/src/pk_core.cpp index 82fe4c217..63a1141a0 100644 --- a/src/pk_core.cpp +++ b/src/pk_core.cpp @@ -297,4 +297,82 @@ BigInt DH_Core::agree(const BigInt& i) const return blinder.unblind(op->agree(blinder.blind(i))); } +/************************************************* +* ECKAEG_Core Constructor * +*************************************************/ +ECKAEG_Core::ECKAEG_Core(const EC_Domain_Params& dom_pars, + const BigInt& priv_key, + const PointGFp& pub_key) + { + op = Engine_Core::eckaeg_op(dom_pars, priv_key, pub_key); + } + +/************************************************* +* ECKAEG_Core Copy Constructor * +*************************************************/ +ECKAEG_Core::ECKAEG_Core(const ECKAEG_Core& core) + { + op = 0; + if(core.op) + op = core.op->clone(); + blinder = core.blinder; + } + +/************************************************* +* ECKAEG_Core Assignment Operator * +*************************************************/ +ECKAEG_Core& ECKAEG_Core::operator=(const ECKAEG_Core& core) + { + delete op; + if(core.op) + op = core.op->clone(); + blinder = core.blinder; + return (*this); + } + +/************************************************* +* ECKAEG Operation * +*************************************************/ +SecureVector<byte> ECKAEG_Core::agree(const PointGFp& otherKey) const + { + //assert(op.get()); + return op->agree(otherKey); + } + +/************************************************* +* ECDSA Operation * +*************************************************/ +bool ECDSA_Core::verify(const byte signature[], u32bit sig_len, + const byte message[], u32bit mess_len) const + { + //assert(op.get()); + return op->verify(signature, sig_len, message, mess_len); + } + +SecureVector<byte> ECDSA_Core::sign(const byte message[], u32bit mess_len) const + { + //assert(op.get()); + return op->sign(message, mess_len); + } + +ECDSA_Core& ECDSA_Core::operator=(const ECDSA_Core& core) + { + delete op; + if(core.op) + op = core.op->clone(); + return (*this); + } + +ECDSA_Core::ECDSA_Core(const ECDSA_Core& core) + { + op = 0; + if(core.op) + op = core.op->clone(); + } + +ECDSA_Core::ECDSA_Core(EC_Domain_Params const& dom_pars, const BigInt& priv_key, PointGFp const& pub_key) + { + op = Engine_Core::ecdsa_op(dom_pars, priv_key, pub_key); + } + } diff --git a/src/point_gfp.cpp b/src/point_gfp.cpp new file mode 100644 index 000000000..23b6d4518 --- /dev/null +++ b/src/point_gfp.cpp @@ -0,0 +1,1157 @@ +/****************************************************** + * Arithmetic for point groups of elliptic curves * + * over GF(p) (source file) * + * * + * (C) 2007 Martin Döring * + * [email protected] * + * Christoph Ludwig * + * [email protected] * + * Falko Strenzke * + * [email protected] * + ******************************************************/ + +#include <botan/point_gfp.h> +#include <botan/numthry.h> + +namespace Botan { + +// construct the point at infinity or a random point +PointGFp::PointGFp(CurveGFp const& curve) + : mC(curve), + mX(curve.get_p(), 0), + mY(curve.get_p(), 1), + mZ(curve.get_p(), 0), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) + { + // first set the point wide pointer + + set_shrd_mod(mC.get_ptr_mod()); + + } + + +// construct a point given its jacobian projective coordinates +PointGFp::PointGFp(CurveGFp const& curve, GFpElement const& x, + GFpElement const& y, GFpElement const& z) + : mC(curve), + mX(x), + mY(y), + mZ(z), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) + { + set_shrd_mod(mC.get_ptr_mod()); + } +PointGFp::PointGFp ( CurveGFp const& curve, GFpElement const& x, + GFpElement const& y ) + :mC(curve), + mX(x), + mY(y), + mZ(curve.get_p(),1), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) + { + set_shrd_mod(mC.get_ptr_mod()); + } + +// copy constructor +PointGFp::PointGFp(PointGFp const& other) + : mC(other.mC), + mX(other.mX), + mY(other.mY), + mZ(other.mZ), + mZpow2(other.mZpow2), + mZpow3(other.mZpow3), + mAZpow4(other.mAZpow4), + mZpow2_set(other.mZpow2_set), + mZpow3_set(other.mZpow3_set), + mAZpow4_set(other.mAZpow4_set) + { + set_shrd_mod(mC.get_ptr_mod()); + } + +// assignment operator +PointGFp const& PointGFp::operator=(PointGFp const& other) + { + mC = other.get_curve(); + mX = other.get_jac_proj_x(); + mY = other.get_jac_proj_y(); + mZ = other.get_jac_proj_z(); + mZpow2 = GFpElement(other.mZpow2); + mZpow3 = GFpElement(other.mZpow3); + mAZpow4 = GFpElement(other.mAZpow4); + mZpow2_set = other.mZpow2_set; + mZpow3_set = other.mZpow3_set; + mAZpow4_set = other.mAZpow4_set; + set_shrd_mod(mC.get_ptr_mod()); + return *this; + } + +PointGFp const& PointGFp::assign_within_same_curve(PointGFp const& other) + { + mX = other.get_jac_proj_x(); + mY = other.get_jac_proj_y(); + mZ = other.get_jac_proj_z(); + mZpow2_set = false; + mZpow3_set = false; + mAZpow4_set = false; + // the rest stays! + return *this; + } + +void PointGFp::set_shrd_mod(std::tr1::shared_ptr<GFpModulus> p_mod) + { + mX.set_shrd_mod(p_mod); + mY.set_shrd_mod(p_mod); + mZ.set_shrd_mod(p_mod); + mZpow2.set_shrd_mod(p_mod); + mZpow3.set_shrd_mod(p_mod); + mAZpow4.set_shrd_mod(p_mod); + } + +void PointGFp::ensure_worksp() const + { + if (mp_worksp_gfp_el.get() != 0) + { + if ((*mp_worksp_gfp_el).size() == GFPEL_WKSP_SIZE) + { + return; + } + else + { + throw Invalid_State("encountered incorrect size for PointGFp´s GFpElement workspace"); + } + } + + mp_worksp_gfp_el = std::tr1::shared_ptr<std::vector<GFpElement> >(new std::vector<GFpElement>); + mp_worksp_gfp_el->reserve(9); + for (u32bit i=0; i<GFPEL_WKSP_SIZE; i++) + { + mp_worksp_gfp_el->push_back(GFpElement(1,0)); + + } + } + +// arithmetic operators +PointGFp& PointGFp::operator+=(PointGFp const& rhs) + { + if (is_zero()) + { + *this = rhs; + return *this; + } + if (rhs.is_zero()) + { + return *this; + } + ensure_worksp(); + + if (rhs.mZ == *(mC.get_mres_one())) + { + //U1 = mX; + (*mp_worksp_gfp_el)[0].share_assign(mX); + + //S1 = mY; + (*mp_worksp_gfp_el)[2].share_assign(mY); + } + else + { + if ((!rhs.mZpow2_set) || (!rhs.mZpow3_set)) + { + rhs.mZpow2 = rhs.mZ; + rhs.mZpow2 *= rhs.mZ; + rhs.mZpow3 = rhs.mZpow2; + rhs.mZpow3 *= rhs.mZ; + + rhs.mZpow2_set = true; + rhs.mZpow3_set = true; + } + //U1 = mX * rhs.mZpow2; + (*mp_worksp_gfp_el)[0].share_assign(mX); + (*mp_worksp_gfp_el)[0] *= rhs.mZpow2; + + //S1 = mY * rhs.mZpow3; + (*mp_worksp_gfp_el)[2].share_assign(mY); + (*mp_worksp_gfp_el)[2] *= rhs.mZpow3; + + } + if (mZ == *(mC.get_mres_one())) + { + //U2 = rhs.mX; + (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); + + //S2 = rhs.mY; + (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); + } + else + { + if ((!mZpow2_set) || (!mZpow3_set)) + { + // precomputation can´t be used, because *this changes anyway + mZpow2 = mZ; + mZpow2 *= mZ; + + mZpow3 = mZpow2; + mZpow3 *= mZ; + } + //U2 = rhs.mX * mZpow2; + (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); + (*mp_worksp_gfp_el)[1] *= mZpow2; + + //S2 = rhs.mY * mZpow3; + (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); + (*mp_worksp_gfp_el)[3] *= mZpow3; + + } + //GFpElement H(U2 - U1); + + (*mp_worksp_gfp_el)[4].share_assign((*mp_worksp_gfp_el)[1]); + (*mp_worksp_gfp_el)[4] -= (*mp_worksp_gfp_el)[0]; + + //GFpElement r(S2 - S1); + (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[3]); + (*mp_worksp_gfp_el)[5] -= (*mp_worksp_gfp_el)[2]; + + //if(H.is_zero()) + if ((*mp_worksp_gfp_el)[4].is_zero()) + + { + if ((*mp_worksp_gfp_el)[5].is_zero()) + + { + mult2_in_place(); + return *this; + } + *this = PointGFp(mC); // setting myself to zero + return *this; + } + + //U2 = H * H; + (*mp_worksp_gfp_el)[1].share_assign((*mp_worksp_gfp_el)[4]); + (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[4]; + + //S2 = U2 * H; + (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[1]); + (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[4]; + + //U2 *= U1; + (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[0]; + + //GFpElement x(r*r - S2 - (U2+U2)); + (*mp_worksp_gfp_el)[6].share_assign((*mp_worksp_gfp_el)[5]); + (*mp_worksp_gfp_el)[6] *= (*mp_worksp_gfp_el)[5]; + (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[3]; + (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[1]; + (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[1]; + + //GFpElement z(S1 * S2); + (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[2]); + (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[3]; + + //GFpElement y(r * (U2-x) - z); + (*mp_worksp_gfp_el)[7].share_assign((*mp_worksp_gfp_el)[1]); + (*mp_worksp_gfp_el)[7] -= (*mp_worksp_gfp_el)[6]; + (*mp_worksp_gfp_el)[7] *= (*mp_worksp_gfp_el)[5]; + (*mp_worksp_gfp_el)[7] -= (*mp_worksp_gfp_el)[8]; + + if (mZ == *(mC.get_mres_one())) + { + if (rhs.mZ != *(mC.get_mres_one())) + { + //z = rhs.mZ * H; + (*mp_worksp_gfp_el)[8].share_assign(rhs.mZ); + (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; + } + else + { + //z = H; + (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[4]); + } + } + else if (rhs.mZ != *(mC.get_mres_one())) + { + //U1 = mZ * rhs.mZ; + (*mp_worksp_gfp_el)[0].share_assign(mZ); + (*mp_worksp_gfp_el)[0] *= rhs.mZ; + + //z = U1 * H; + (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[0]); + (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; + + } + else + { + //z = mZ * H; + (*mp_worksp_gfp_el)[8].share_assign(mZ); + (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; + + } + mZpow2_set = false; + mZpow3_set = false; + mAZpow4_set = false; + + mX = (*mp_worksp_gfp_el)[6]; + mY = (*mp_worksp_gfp_el)[7]; + mZ = (*mp_worksp_gfp_el)[8]; + + return *this; + + } +PointGFp& PointGFp::operator-=(PointGFp const& rhs) + { + PointGFp minus_rhs = PointGFp(rhs).negate(); + + if (is_zero()) + { + *this = minus_rhs; + } + else + { + *this += minus_rhs; + } + return *this; + } + +PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, + const BigInt& /*point_order*/, + const BigInt& /*max_secr*/) + { + // NOTE: FS: so far this is code duplication of op*=. + // we have to see how we deal with this. + // fact is that we will probably modify this function + // while evaluating the countermeasures + // whereas we probably will not start modifying the + // function operator*=. + // however, in the end both should be merged. + + // use montgomery mult. in this operation + this->turn_on_sp_red_mul(); + + std::tr1::shared_ptr<PointGFp> H(new PointGFp(this->mC)); + std::tr1::shared_ptr<PointGFp> tmp; // used for AADA + + PointGFp P(*this); + BigInt m(scalar); + + if (m < BigInt(0)) + { + m = -m; + P.negate(); + } + if (P.is_zero() || (m == BigInt(0))) + { + *this = *H; + return *this; + } + if (m == BigInt(1)) + { + return *this; + } + // +#ifdef CM_AADA +#ifndef CM_RAND_EXP + int max_secr_bits = max_secr.bits(); +#endif +#endif + + int mul_bits = m.bits(); // this is used for a determined number of loop runs in + // the mult_loop where leading zero´s are padded if necessary. + // Here we assign the value that will be used when no countermeasures are specified +#ifdef CM_RAND_EXP + u32bit rand_r_bit_len = 20; // Coron(99) proposes 20 bit for r + +#ifdef CM_AADA + + BigInt r_max(1); + +#endif // CM_AADA + + // use randomized exponent +#ifdef TA_COLL_T + static BigInt r_randexp; + if (new_rand) + { + r_randexp = random_integer(rand_r_bit_len); + } + //assert(!r_randexp.is_zero()); +#else + BigInt r_randexp(random_integer(rand_r_bit_len)); +#endif + + m += r_randexp * point_order; + // determine mul_bits... +#ifdef CM_AADA + // AADA with rand. Exp. + //assert(rand_r_bit_len > 0); + r_max <<= rand_r_bit_len; + r_max -= 1; + //assert(r_max.bits() == rand_r_bit_len); + mul_bits = (max_secr + point_order * r_max).bits(); +#else + // rand. Exp. without AADA + mul_bits = m.bits(); +#endif // CM_AADA + + +#endif // CM_RAND_EXP + + // determine mul_bits... +#if (CM_AADA == 1 && CM_RAND_EXP != 1) + + mul_bits = max_secr_bits; +#endif // CM_AADA without CM_RAND_EXP + + //assert(mul_bits != 0); + + + H = mult_loop(mul_bits-1, m, H, tmp, P); + + if (!H->is_zero()) // cannot convert if H == O + { + *this = H->get_z_to_one(); + }else + { + *this = *H; + } + mX.turn_off_sp_red_mul(); + mY.turn_off_sp_red_mul(); + mZ.turn_off_sp_red_mul(); + return *this; + } +PointGFp& PointGFp::operator*=(const BigInt& scalar) + { + // use montgomery mult. in this operation + + this->turn_on_sp_red_mul(); + + PointGFp H(this->mC); // create as zero + H.turn_on_sp_red_mul(); + PointGFp P(*this); + P.turn_on_sp_red_mul(); + BigInt m(scalar); + if (m < BigInt(0)) + { + m = -m; + P.negate(); + } + if (P.is_zero() || (m == BigInt(0))) + { + *this = H; + return *this; + } + if (m == BigInt(1)) + { + //*this == P already + return *this; + } + + const int l = m.bits() - 1; + for (int i=l; i >=0; i--) + { + + H.mult2_in_place(); + if (m.get_bit(i)) + { + H += P; + } + } + + if (!H.is_zero()) // cannot convert if H == O + { + *this = H.get_z_to_one(); + }else + { + *this = H; + } + return *this; + } + +inline std::tr1::shared_ptr<PointGFp> PointGFp::mult_loop( + int l, + const BigInt& m, + std::tr1::shared_ptr<PointGFp> H, + std::tr1::shared_ptr<PointGFp> tmp, + PointGFp const& P) + { + + //assert(l >= (int)m.bits()- 1); + tmp = H; + std::tr1::shared_ptr<PointGFp> to_add(new PointGFp(P)); // we just need some point + // so that we can use op= + // inside the loop + for (int i=l; i >=0; i--) + { + H->mult2_in_place(); + +#ifndef CM_AADA + + if (m.get_bit(i)) + { + *H += P; + } +#else // (CM_AADA is in) + + if (H.get() == to_add.get()) + { + to_add = tmp; // otherwise all pointers might point to the same object + // and we always need two objects to be able to switch around + } + to_add->assign_within_same_curve(*H); + tmp = H; + *tmp += P; // tmp already points to H + + if (m.get_bit(i)) + { + H = tmp; // NOTE: assign the pointer, not the value! + // (so that the operation is fast and thus as difficult + // to detect as possible) + } + else + { + H = to_add; // NOTE: this is necessary, because the assignment + // "*tmp = ..." already changed what H pointed to + + + } +#endif // CM_AADA + + } + return H; + } +PointGFp& PointGFp::negate() + { + if (!is_zero()) + { + mY.negate(); + } + return *this; + } +// *this *= 2 +PointGFp& PointGFp::mult2_in_place() + { + if (is_zero()) + { + return *this; + } + if (mY.is_zero()) + { + + *this = PointGFp(mC); // setting myself to zero + return *this; + } + ensure_worksp(); + + (*mp_worksp_gfp_el)[0].share_assign(mY); + (*mp_worksp_gfp_el)[0] *= mY; + + //GFpElement S(mX * z); + (*mp_worksp_gfp_el)[1].share_assign(mX); + (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[0]; + + //GFpElement x(S + S); + (*mp_worksp_gfp_el)[2].share_assign((*mp_worksp_gfp_el)[1]); + (*mp_worksp_gfp_el)[2] += (*mp_worksp_gfp_el)[1]; + + //S = x + x; + (*mp_worksp_gfp_el)[1].share_assign((*mp_worksp_gfp_el)[2]); + (*mp_worksp_gfp_el)[1] += (*mp_worksp_gfp_el)[2]; + + if (!mAZpow4_set) + { + if (mZ == *(mC.get_mres_one())) + { + mAZpow4 = mC.get_mres_a(); + mAZpow4_set = true; + } + else + { + if (!mZpow2_set) + { + mZpow2 = mZ; + mZpow2 *= mZ; + + mZpow2_set = true; + } + //x = mZpow2 * mZpow2; + (*mp_worksp_gfp_el)[2].share_assign(mZpow2); + (*mp_worksp_gfp_el)[2] *= mZpow2; + + //mAZpow4 = mC.get_mres_a() * x; + mAZpow4 = mC.get_mres_a(); + mAZpow4 *= (*mp_worksp_gfp_el)[2]; + + } + + } + + //GFpElement y(mX * mX); + (*mp_worksp_gfp_el)[3].share_assign(mX); + (*mp_worksp_gfp_el)[3] *= mX; + + //GFpElement M(y + y + y + mAZpow4); + (*mp_worksp_gfp_el)[4].share_assign((*mp_worksp_gfp_el)[3]); + (*mp_worksp_gfp_el)[4] += (*mp_worksp_gfp_el)[3]; + (*mp_worksp_gfp_el)[4] += (*mp_worksp_gfp_el)[3]; + (*mp_worksp_gfp_el)[4] += mAZpow4; + + //x = M * M - (S+S); + (*mp_worksp_gfp_el)[2].share_assign((*mp_worksp_gfp_el)[4]); + (*mp_worksp_gfp_el)[2] *= (*mp_worksp_gfp_el)[4]; + (*mp_worksp_gfp_el)[2] -= (*mp_worksp_gfp_el)[1]; + (*mp_worksp_gfp_el)[2] -= (*mp_worksp_gfp_el)[1]; + + //y = z * z; + (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[0]); + (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[0]; + + //GFpElement U(y + y); + (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[3]); + (*mp_worksp_gfp_el)[5] += (*mp_worksp_gfp_el)[3]; + + //z = U + U; + (*mp_worksp_gfp_el)[0].share_assign((*mp_worksp_gfp_el)[5]); + (*mp_worksp_gfp_el)[0] += (*mp_worksp_gfp_el)[5]; + + //U = z + z; + (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[0]); + (*mp_worksp_gfp_el)[5] += (*mp_worksp_gfp_el)[0]; + + //y = M * (S - x) - U; + (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[1]); + (*mp_worksp_gfp_el)[3] -= (*mp_worksp_gfp_el)[2]; + (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[4]; + (*mp_worksp_gfp_el)[3] -= (*mp_worksp_gfp_el)[5]; + + if (mZ != *(mC.get_mres_one())) + { + //z = mY * mZ; + (*mp_worksp_gfp_el)[0].share_assign(mY); + (*mp_worksp_gfp_el)[0] *= mZ; + + } + else + { + //z = mY; + (*mp_worksp_gfp_el)[0].share_assign(mY); + + } + //z = z + z; + (*mp_worksp_gfp_el)[6].share_assign((*mp_worksp_gfp_el)[0]); + (*mp_worksp_gfp_el)[0] += (*mp_worksp_gfp_el)[6]; + + //mX = x; + //mY = y; + //mZ = z; + mX = (*mp_worksp_gfp_el)[2]; + mY = (*mp_worksp_gfp_el)[3]; + mZ = (*mp_worksp_gfp_el)[0]; + + mZpow2_set = false; + mZpow3_set = false; + mAZpow4_set = false; + return *this; + + } +void PointGFp::turn_on_sp_red_mul() const + { + mX.turn_on_sp_red_mul(); + mY.turn_on_sp_red_mul(); + mZ.turn_on_sp_red_mul(); + + // also pretransform, otherwise + // we might have bad results with respect to + // performance because + // additions/subtractions in mult2_in_place() + // and op+= spread untransformed GFpElements + mX.get_mres(); + mY.get_mres(); + mZ.get_mres(); + + mZpow2.turn_on_sp_red_mul(); + mZpow3.turn_on_sp_red_mul(); + mAZpow4.turn_on_sp_red_mul(); + } +// getters + +/** +* returns a point equivalent to *this but were +* Z has value one, i.e. x and y correspond to +* their values in affine coordinates +*/ +PointGFp const PointGFp::get_z_to_one() const + { + return PointGFp(*this).set_z_to_one(); + } +/** +* changes the representation of *this so that +* Z has value one, i.e. x and y correspond to +* their values in affine coordinates. +* returns *this. +*/ +PointGFp const& PointGFp::set_z_to_one() const + { + if (!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) + { + GFpElement z = inverse(mZ); + GFpElement z2 = z * z; + z *= z2; + GFpElement x = mX * z2; + GFpElement y = mY * z; + mZ = GFpElement(mC.get_p(), BigInt(1)); + mX = x; + mY = y; + } + else + { + if (mZ.get_value() == BigInt(0)) + { + throw Illegal_Transformation("cannot convert Z to one"); + } + } + return *this; // mZ = 1 already + } +CurveGFp const PointGFp::get_curve() const + { + return mC; + } +GFpElement const PointGFp::get_affine_x() const + { + + if (is_zero()) + { + throw Illegal_Transformation("cannot convert to affine"); + + } + /*if(!mZpow2_set) + {*/ + mZpow2 = mZ * mZ; + mZpow2_set = true; + //} + //assert(mZpow2 == mZ*mZ); + GFpElement z2 = mZpow2; + return mX * z2.inverse_in_place(); + } + +GFpElement const PointGFp::get_affine_y() const + { + + if (is_zero()) + { + throw Illegal_Transformation("cannot convert to affine"); + + } + /*if(!mZpow3_set ) + {*/ + mZpow3 = mZ * mZ * mZ; + mZpow3_set = true; + //} + //assert(mZpow3 == mZ * mZ *mZ); + GFpElement z3 = mZpow3; + return mY * z3.inverse_in_place(); + } +GFpElement const PointGFp::get_jac_proj_x() const + { + return GFpElement(mX); + } +GFpElement const PointGFp::get_jac_proj_y() const + { + return GFpElement(mY); + } +GFpElement const PointGFp::get_jac_proj_z() const + { + return GFpElement(mZ); + } + +// Is this the point at infinity? +bool PointGFp::is_zero() const + { + return(mX.is_zero() && mZ.is_zero()); + //NOTE: the calls to GFpElement::is_zero() instead of getting the value and + // and comparing it are import because they do not provoke backtransformations + // to the ordinary residue. + } + +// Is the point still on the curve?? +// (If everything is correct, the point is always on its curve; then the +// function will return silently. If Oskar managed to corrupt this object's state, +// then it will throw an exception.) +void PointGFp::check_invariants() const + { + if (is_zero()) + { + return; + } + const GFpElement y2 = mY * mY; + const GFpElement x3 = mX * mX * mX; + + if (mZ.get_value() == BigInt(1)) + { + GFpElement ax = mC.get_a() * mX; + if (y2 != (x3 + ax + mC.get_b())) + { + throw Illegal_Point(); + } + + } + /*if (!mZpow2_set) + {*/ + mZpow2 = mZ * mZ; + mZpow2_set = true; + /*} + if (!mZpow3_set) + {*/ + mZpow3 = mZpow2 * mZ; + mZpow3_set = true; + /*} + if(!mAZpow4_set) + {*/ + mAZpow4 = mZpow3 * mZ * mC.get_a(); + mAZpow4_set = true; + //} + const GFpElement aXZ4 = mAZpow4 * mX; + const GFpElement bZ6 = mC.get_b() * mZpow3 * mZpow3; + + if (y2 != (x3 + aXZ4 + bZ6)) + { + throw Illegal_Point(); + } + + } +// swaps the states of *this and other, does not throw! +void PointGFp::swap(PointGFp& other) + { + mC.swap(other.mC); + mX.swap(other.mX); + mY.swap(other.mY); + mZ.swap(other.mZ); + mZpow2.swap(other.mZpow2); + mZpow3.swap(other.mZpow3); + mAZpow4.swap(other.mAZpow4); + std::swap<bool>(mZpow2_set, other.mZpow2_set); + std::swap<bool>(mZpow3_set, other.mZpow3_set); + std::swap<bool>(mAZpow4_set, other.mAZpow4_set); + } + +PointGFp const mult2(PointGFp const& point) + { + return (PointGFp(point)).mult2_in_place(); + } + + +bool operator==(PointGFp const& lhs, PointGFp const& rhs) + { + if (lhs.is_zero() && rhs.is_zero()) + { + return true; + } + if ((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) + { + return false; + } + // neither operand is zero, so we can call get_z_to_one() + //assert(!lhs.is_zero()); + //assert(!rhs.is_zero()); + PointGFp aff_lhs = lhs.get_z_to_one(); + PointGFp aff_rhs = rhs.get_z_to_one(); + return (aff_lhs.get_curve() == aff_rhs.get_curve() && + aff_lhs.get_jac_proj_x() == aff_rhs.get_jac_proj_x() && + aff_lhs.get_jac_proj_y() == aff_rhs.get_jac_proj_y()); + } + +// arithmetic operators +PointGFp operator+(PointGFp const& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp += rhs; + } + +PointGFp operator-(PointGFp const& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp -= rhs; + } + +PointGFp operator-(PointGFp const& lhs) + { + return PointGFp(lhs).negate(); + } + +PointGFp operator*(const BigInt& scalar, PointGFp const& point) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp operator*(PointGFp const& point, const BigInt& scalar) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp mult_point_secure(PointGFp const& point, const BigInt& scalar, const BigInt& point_order, const BigInt& max_secret) + { + PointGFp result(point); + result.mult_this_secure(scalar, point_order, max_secret); + return result; + } + +// encoding and decoding +SecureVector<byte> EC2OSP(PointGFp const& point, byte format) + { + SecureVector<byte> result; + if (format == PointGFp::UNCOMPRESSED) + { + result = encode_uncompressed(point); + } + else if (format == PointGFp::COMPRESSED) + { + result = encode_compressed(point); + + } + else if (format == PointGFp::HYBRID) + { + result = encode_hybrid(point); + } + else + { + throw Format_Error("illegal point encoding format specification"); + } + return result; + } +SecureVector<byte> encode_compressed(PointGFp const& point) + { + + + if (point.is_zero()) + { + SecureVector<byte> result (1); + result[0] = 0; + return result; + + } + u32bit l = point.get_curve().get_p().bits(); + int dummy = l & 7; + if (dummy != 0) + { + l += 8 - dummy; + } + l /= 8; + SecureVector<byte> result (l+1); + result[0] = 2; + BigInt x = point.get_affine_x().get_value(); + SecureVector<byte> bX = BigInt::encode_1363(x, l); + result.copy(1, bX.begin(), bX.size()); + BigInt y = point.get_affine_y().get_value(); + if (y.get_bit(0)) + { + result[0] |= 1; + } + return result; + } + + +SecureVector<byte> encode_uncompressed(PointGFp const& point) + { + if (point.is_zero()) + { + SecureVector<byte> result (1); + result[0] = 0; + return result; + } + u32bit l = point.get_curve().get_p().bits(); + int dummy = l & 7; + if (dummy != 0) + { + l += 8 - dummy; + } + l /= 8; + SecureVector<byte> result (2*l+1); + result[0] = 4; + BigInt x = point.get_affine_x().get_value(); + BigInt y = point.get_affine_y().get_value(); + SecureVector<byte> bX = BigInt::encode_1363(x, l); + SecureVector<byte> bY = BigInt::encode_1363(y, l); + result.copy(1, bX.begin(), l); + result.copy(l+1, bY.begin(), l); + return result; + + } + +SecureVector<byte> encode_hybrid(PointGFp const& point) + { + if (point.is_zero()) + { + SecureVector<byte> result (1); + result[0] = 0; + return result; + } + u32bit l = point.get_curve().get_p().bits(); + int dummy = l & 7; + if (dummy != 0) + { + l += 8 - dummy; + } + l /= 8; + SecureVector<byte> result (2*l+1); + result[0] = 6; + BigInt x = point.get_affine_x().get_value(); + BigInt y = point.get_affine_y().get_value(); + SecureVector<byte> bX = BigInt::encode_1363(x, l); + SecureVector<byte> bY = BigInt::encode_1363(y, l); + result.copy(1, bX.begin(), bX.size()); + result.copy(l+1, bY.begin(), bY.size()); + if (y.get_bit(0)) + { + result[0] |= 1; + } + return result; + } + +PointGFp OS2ECP(MemoryRegion<byte> const& os, CurveGFp const& curve) + { + if (os.size() == 1 && os[0] == 0) + { + return PointGFp(curve); // return zero + } + SecureVector<byte> bX; + SecureVector<byte> bY; + + GFpElement x(1,0); + GFpElement y(1,0); + GFpElement z(1,0); + + const byte pc = os[0]; + BigInt bi_dec_x; + BigInt bi_dec_y; + switch (pc) + { + case 2: + case 3: + //compressed form + bX = SecureVector<byte>(os.size() - 1); + bX.copy(os.begin()+1, os.size()-1); + + /* Problem wäre, wenn decode() das erste bit als Vorzeichen interpretiert. + *--------------------- + * AW(FS): decode() interpretiert das erste Bit nicht als Vorzeichen + */ + bi_dec_x = BigInt::decode(bX, bX.size()); + x = GFpElement(curve.get_p(), bi_dec_x); + bool yMod2; + yMod2 = (pc & 1) == 1; + y = PointGFp::decompress(yMod2, x, curve); + break; + case 4: + // uncompressed form + int l; + l = (os.size() -1)/2; + bX = SecureVector<byte>(l); + bY = SecureVector<byte>(l); + bX.copy(os.begin()+1, l); + bY.copy(os.begin()+1+l, l); + bi_dec_x = BigInt::decode(bX.begin(), bX.size()); + + bi_dec_y = BigInt::decode(bY.begin(),bY.size()); + x = GFpElement(curve.get_p(), bi_dec_x); + y = GFpElement(curve.get_p(), bi_dec_y); + break; + + case 6: + case 7: + //hybrid form + l = (os.size() - 1)/2; + bX = SecureVector<byte>(l); + bY = SecureVector<byte>(l); + bX.copy(os.begin() + 1, l); + bY.copy(os.begin()+1+l, l); + yMod2 = (pc & 0x01) == 1; + if (!(PointGFp::decompress(yMod2, x, curve) == y)) + { + throw Illegal_Point("error during decoding hybrid format"); + } + break; + default: + throw Format_Error("encountered illegal format specification while decoding point"); + } + z = GFpElement(curve.get_p(), BigInt(1)); + //assert((x.is_trf_to_mres() && x.is_use_montgm()) || !x.is_trf_to_mres()); + //assert((y.is_trf_to_mres() && y.is_use_montgm()) || !y.is_trf_to_mres()); + //assert((z.is_trf_to_mres() && z.is_use_montgm()) || !z.is_trf_to_mres()); + PointGFp result(curve, x, y, z); + result.check_invariants(); + //assert((result.get_jac_proj_x().is_trf_to_mres() && result.get_jac_proj_x().is_use_montgm()) || !result.get_jac_proj_x().is_trf_to_mres()); + //assert((result.get_jac_proj_y().is_trf_to_mres() && result.get_jac_proj_y().is_use_montgm()) || !result.get_jac_proj_y().is_trf_to_mres()); + //assert((result.get_jac_proj_z().is_trf_to_mres() && result.get_jac_proj_z().is_use_montgm()) || !result.get_jac_proj_z().is_trf_to_mres()); + return result; + } + +GFpElement PointGFp::decompress(bool yMod2, GFpElement const& x, + CurveGFp const& curve) + { + BigInt xVal = x.get_value(); + BigInt xpow3 = xVal * xVal * xVal; + BigInt g = curve.get_a().get_value() * xVal; + g += xpow3; + g += curve.get_b().get_value(); + g = g%curve.get_p(); + BigInt z = ressol(g, curve.get_p()); + + if(z < 0) + throw Illegal_Point("error during decompression"); + + bool zMod2 = z.get_bit(0); + if ((zMod2 && ! yMod2) || (!zMod2 && yMod2)) + { + z = curve.get_p() - z; + } + return GFpElement(curve.get_p(),z); + } + +PointGFp const create_random_point(RandomNumberGenerator& rng, + CurveGFp const& curve) + { + + // create a random point + GFpElement mX(1,1); + GFpElement mY(1,1); + GFpElement mZ(1,1); + GFpElement minusOne(curve.get_p(), BigInt(BigInt::Negative,1)); + mY = minusOne; + GFpElement y2(1,1); + GFpElement x(1,1); + + while (mY == minusOne) + { + BigInt value(rng, curve.get_p().bits()); + mX = GFpElement(curve.get_p(),value); + y2 = curve.get_a() * mX; + x = mX * mX; + x *= mX; + y2 += (x + curve.get_b()); + + value = ressol(y2.get_value(), curve.get_p()); + + if(value < 0) + mY = minusOne; + else + mY = GFpElement(curve.get_p(), value); + } + mZ = GFpElement(curve.get_p(), BigInt(1)); + + return PointGFp(curve, mX, mY, mZ); + } + +} // namespace Botan |