Elliptic Curve Integrated Encryption Scheme

From Crypto++ Wiki
Jump to navigation Jump to search

Elliptic Curve Integrated Encryption Scheme, or ECIES, is a hybrid encryption system proposed by Victor Shoup in 2001. ECIES has been standardized in ANSI X9.63, IEEE 1363a, ISO/IEC 18033-2, and SECG SEC-1. Shoup's submission can be found at A Proposal for an ISO Standard for Public Key Encryption (v2.1).

ECIES combines a Key Encapsulation Mechanism (KEM) with a Data Encapsulation Mechanism (DEM). The system independently derives a bulk encryption key and a MAC key from a common secret. Data is first encrypted under a symmetric cipher, and then the cipher text is MAC'd under an authentication scheme. Finally, the common secret is encrypted under the public part of a public/private key pair. The output of the encryption function is the tuple {K,C,T}, where K is the encrypted common secret, C is the ciphertext, and T is the authentication tag. There is some hand waiving around the "common secret" since its actually the result of applying a Key Agreement function, and it uses the static public key and an ephemeral key pair.

Crypto++ originally implemented IEEE P1363's version of ECIES. IEEE's version of ECIES was slightly different algorithm than Shoup recommended. Botan and Bouncy Castle implemented Shoup's version of ECIES, so Crypto++ Botan and Bouncy Castle did not interop. The non-interop was fixed at Crypto++ 6.0. Also see Issue 21, ECIES uses byte count, and not bit count, for label size.

As Martínez, Encinas, and Ávila note in A Survey of the Elliptic Curve Integrated Encryption Scheme, "... it is not possible to implement a software version compatible with all those standards, regarding both the specific operations and the list of allowed functions and algorithms." Many differences are pointed out in the document A Comparison of the Standardized Versions of ECIES.

Shoup's scheme is similar to Discrete Logarithm Integrated Encryption Scheme. ECIES operates over a field of elliptic curves, while DLIES operates over a field of integers.

Ján Jančár showed Crypto++ 8.2 and below leaked timing information in elliptic curve gear. You should upgrade to Crypto++ 8.3 and above. Also see Issue 869, Elliptic Curve timing leaks.

ECIES

ECIES is a template structure in eccrypto.h. The structure's default parameters follow Shoup's recommendations and interop with Botan and Bouncy Castle. You can interop with P1363 by using the parameters specified in P1363 Interop.

template <class EC, class HASH = SHA1,
          class COFACTOR_OPTION = NoCofactorMultiplication,
          bool DHAES_MODE = true, bool LABEL_OCTETS = false>
struct ECIES
	: public DL_ES<
		DL_Keys_EC<EC>,
		DL_KeyAgreementAlgorithm_DH<typename EC::Point, COFACTOR_OPTION>,
		DL_KeyDerivationAlgorithm_P1363<typename EC::Point, DHAES_MODE, P1363_KDF2<HASH> >,
		DL_EncryptionAlgorithm_Xor<HMAC<HASH>, DHAES_MODE, LABEL_OCTETS>,
		ECIES<EC> >
{
	// TODO: fix this after name is standardized
	CRYPTOPP_STATIC_CONSTEXPR const char* CRYPTOPP_API StaticAlgorithmName() {return "ECIES";}
};

The template parameters include COFACTOR_OPTION and DHAES_MODE. Greater efficiency can be achieved by selecting COFACTOR_OPTION = IncompatibleCofactorMultiplication and DHAES_MODE = false.

DHAES_MODE = true provides the best security. The greater security is achieved by including the ephemeralPublicKey in the key derivation function, and the size of the encodingParameters in the authenticator function.

If you want P1363 compatibility, then use the following declarations:

ECIES<ECP,SHA1,NoCofactorMultiplication,false,true>::Decryptor decryptor;
ECIES<ECP,SHA1,NoCofactorMultiplication,false,true>::Encryptor encryptor;

Sample Code

The following generates private and public keys; saves and loads the keys; and encrypts a message under the keys. Key operations are performed using Crypto++'s PrivateKey, PublicKey, DL_PrivateKey_EC<ECP>, and DL_PublicKey_EC<ECP>. A more complete treatment of keys is available at Keys and Formats.

Operations are shown over a prime field (ECP), and similar operations can be performed over binary fields (EC2N).

The sample program is available for download below in ZIP format. The archive includes the entire program, including required header files.

void PrintPrivateKey(const DL_PrivateKey_EC<ECP>& key, ostream& out = cout);
void PrintPublicKey(const DL_PublicKey_EC<ECP>& key, ostream& out = cout);

void SavePrivateKey(const PrivateKey& key, const string& file = "ecies.private.key");
void SavePublicKey(const PublicKey& key, const string& file = "ecies.public.key");

void LoadPrivateKey(PrivateKey& key, const string& file = "ecies.private.key");
void LoadPublicKey(PublicKey& key, const string& file = "ecies.public.key");

static const string message("Now is the time for all good men to come to the aide of their country.");

int main(int argc, char* argv[])
{
    AutoSeededRandomPool prng;
    
    /////////////////////////////////////////////////
    // Part one - generate keys
    
    ECIES<ECP>::Decryptor d0(prng, ASN1::secp256r1());
    PrintPrivateKey(d0.GetKey());

    ECIES<ECP>::Encryptor e0(d0);
    PrintPublicKey(e0.GetKey());
    
    /////////////////////////////////////////////////
    // Part two - save keys
    //   Get* returns a const reference
    
    SavePrivateKey(d0.GetPrivateKey());
    SavePublicKey(e0.GetPublicKey());
    
    /////////////////////////////////////////////////
    // Part three - load keys
    //   Access* returns a non-const reference
    
    ECIES<ECP>::Decryptor d1;
    LoadPrivateKey(d1.AccessPrivateKey());
    d1.GetPrivateKey().ThrowIfInvalid(prng, 3);
    
    ECIES<ECP>::Encryptor e1;
    LoadPublicKey(e1.AccessPublicKey());
    e1.GetPublicKey().ThrowIfInvalid(prng, 3);
    
    /////////////////////////////////////////////////
    // Part four - encrypt/decrypt with e0/d1
    
    string em0; // encrypted message
    StringSource ss1 (message, true, new PK_EncryptorFilter(prng, e0, new StringSink(em0) ) );
    string dm0; // decrypted message
    StringSource ss2 (em0, true, new PK_DecryptorFilter(prng, d1, new StringSink(dm0) ) );
    
    cout << dm0 << endl;
    
    /////////////////////////////////////////////////
    // Part five - encrypt/decrypt with e1/d0
    
    string em1; // encrypted message
    StringSource ss3 (message, true, new PK_EncryptorFilter(prng, e1, new StringSink(em1) ) );
    string dm1; // decrypted message
    StringSource ss4 (em1, true, new PK_DecryptorFilter(prng, d0, new StringSink(dm1) ) );
    
    cout << dm1 << endl;
    
    return 0;
}

void SavePrivateKey(const PrivateKey& key, const string& file)
{
    FileSink sink(file.c_str());
    key.Save(sink);
}

void SavePublicKey(const PublicKey& key, const string& file)
{
    FileSink sink(file.c_str());
    key.Save(sink);
}

void LoadPrivateKey(PrivateKey& key, const string& file)
{
    FileSource source(file.c_str(), true);
    key.Load(source);
}

void LoadPublicKey(PublicKey& key, const string& file)
{
    FileSource source(file.c_str(), true);
    key.Load(source);
}

void PrintPrivateKey(const DL_PrivateKey_EC<ECP>& key, ostream& out)
{
    // Group parameters
    const DL_GroupParameters_EC<ECP>& params = key.GetGroupParameters();
    // Base precomputation (for public key calculation from private key)
    const DL_FixedBasePrecomputation<ECPPoint>& bpc = params.GetBasePrecomputation();
    // Public Key (just do the exponentiation)
    const ECPPoint point = bpc.Exponentiate(params.GetGroupPrecomputation(), key.GetPrivateExponent());
    
    out << "Modulus: " << std::hex << params.GetCurve().GetField().GetModulus() << endl;
    out << "Cofactor: " << std::hex << params.GetCofactor() << endl;
    
    out << "Coefficients" << endl;
    out << "  A: " << std::hex << params.GetCurve().GetA() << endl;
    out << "  B: " << std::hex << params.GetCurve().GetB() << endl;
    
    out << "Base Point" << endl;
    out << "  x: " << std::hex << params.GetSubgroupGenerator().x << endl;
    out << "  y: " << std::hex << params.GetSubgroupGenerator().y << endl;
    
    out << "Public Point" << endl;
    out << "  x: " << std::hex << point.x << endl;
    out << "  y: " << std::hex << point.y << endl;
    
    out << "Private Exponent (multiplicand): " << endl;
    out << "  " << std::hex << key.GetPrivateExponent() << endl;
}

void PrintPublicKey(const DL_PublicKey_EC<ECP>& key, ostream& out)
{
    // Group parameters
    const DL_GroupParameters_EC<ECP>& params = key.GetGroupParameters();
    // Public key
    const ECPPoint& point = key.GetPublicElement();
    
    out << "Modulus: " << std::hex << params.GetCurve().GetField().GetModulus() << endl;
    out << "Cofactor: " << std::hex << params.GetCofactor() << endl;
    
    out << "Coefficients" << endl;
    out << "  A: " << std::hex << params.GetCurve().GetA() << endl;
    out << "  B: " << std::hex << params.GetCurve().GetB() << endl;
    
    out << "Base Point" << endl;
    out << "  x: " << std::hex << params.GetSubgroupGenerator().x << endl;
    out << "  y: " << std::hex << params.GetSubgroupGenerator().y << endl;
    
    out << "Public Point" << endl;
    out << "  x: " << std::hex << point.x << endl;
    out << "  y: " << std::hex << point.y << endl;
}

A typical run of the program is shown below with some additional formatting (white space for readability):

$ ./cryptopp-ecies-test.exe

Modulus: ffffffff00000001000000000000000000000000ffffffffffffffffffffffffh
Cofactor: 1h
Coefficients
  A: ffffffff00000001000000000000000000000000fffffffffffffffffffffffch
  B: 5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bh
Base Point
  x: 6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296h
  y: 4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5h
Public Point
  x: de16a2eed14a76cb75d1a4d2b7ec5d695164566ea46bdee26f7d4ff7e91a3c5bh
  y: c67e3796bd6438378f6e46ed17c9925b18523d760148db59a0f64451113e7200h
Private Exponent (multiplicand): 
  9d0fba48b5ca7c99d1f35e8db4c3513ef5e30b17576e36851e2958c5af9f99e0h

Modulus: ffffffff00000001000000000000000000000000ffffffffffffffffffffffffh
Cofactor: 1h
Coefficients
  A: ffffffff00000001000000000000000000000000fffffffffffffffffffffffch
  B: 5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bh
Base Point
  x: 6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296h
  y: 4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5h
Public Point
  x: de16a2eed14a76cb75d1a4d2b7ec5d695164566ea46bdee26f7d4ff7e91a3c5bh
  y: c67e3796bd6438378f6e46ed17c9925b18523d760148db59a0f64451113e7200h

Now is the time for all good men to come to the aide of their country.
Now is the time for all good men to come to the aide of their country.

If you want to perform two-step construction and initialization of a private key, then perform the following. Note that Initialize takes a RandomNumberGenerator, which causes private key generation. An Initialize that lacks the PRNG does not generate a private key.

// From Wei Dai in a private email
ECIES<ECP>::Decryptor d;
d.AccessKey().GenerateRandom(GlobalRNG(), MakeParameters(Name::GroupOID(), ASN1::secp256r1()));

Alternative, but non-preferred methods include the following.

ECIES<ECP>::Decryptor decryptor;
decryptor.AccessKey().AccessGroupParameters().Initialize(prng, ASN1::secp256r1());

As yet another alternative, you can set the private exponent (multiplicand) directly:

ECIES<ECP>::Decryptor decryptor;
decryptor.AccessKey().AccessGroupParameters().Initialize(ASN1::secp256r1());

Integer x(prng, Integer::One(), decryptor.AccessKey().GetGroupParameters().GetSubgroupOrder()-1);
decryptor.AccessKey().SetPrivateExponent(x);

Android Pay Example

Google uses ECIES for Android Pay tokens, and they provide a complete Java example at Payment Token Cryptography. The wiki page covering the interop is at Android Pay.

Bouncy Castle Interop

Prior to Crypto++ 6.0, the library did not interop with Botan or Bouncy Castle's implementation of ECIES. For the discussion on the mailing list, see Jesse Wilson's Problem with the way gfpcrypt HMAC's the encoding parameters' length in DHAES_MODE. The were three problems with interop. First, the label length L must be MAC'd to preserve semantic authentication. Second, Crypto++ used a 8-byte word for L, while Bouncy Castle uses a 4-byte word for L. (This was a Bouncy Castle bug). Third, Crypto++ wrote a byte count to the while Bouncy Castle wrote a bit count. (This was a Crypto++ bug).

Crypto++ changed its implementation prior to the Crypto++ 6.0 release under Issue 21, ECIES uses byte count, and not bit count, for label size. Bouncy Castle also changed its behavior around that time.

P1363 Interop

Changing Crypto++ to interop with Botan and Bouncy Castle meant we no longer interop'd with IEEE P1363. If you need the former P1363 behavior then use the following declarations:

ECIES<ECP,SHA1,NoCofactorMultiplication,false,true>::Decryptor decryptor;
ECIES<ECP,SHA1,NoCofactorMultiplication,false,true>::Encryptor encryptor;

Crypto++ tests the legacy behavior in validat8.cpp. See the functions ValidateECP_Legacy_Encrypt and ValidateEC2N_Legacy_Encrypt.

GetSymmetricKeyLength

After Crypto++ 5.6.5 was released we changed ECIES to align with Botan and Bouncy Castle to avoid interop problems. Around that time we also cleared up some warnings in DL_SymmetricEncryptionAlgorithm. The warning cleanup introduced a bug due to this change in GetSymmetricKeyLength. Also see Commit c3e2e0fb25fd.

OLD GetSymmetricKeyLength (correct):

size_t GetSymmetricKeyLength(size_t plaintextLength) const
    {return plaintextLength + static_cast<size_t>(MAC::DEFAULT_KEYLENGTH);}
size_t GetSymmetricCiphertextLength(size_t plaintextLength) const
    {return plaintextLength + static_cast<size_t>(MAC::DIGESTSIZE);}

NEW GetSymmetricKeyLength (incorrect):

size_t GetSymmetricKeyLength(size_t plaintextLength) const
    {return plaintextLength + static_cast<size_t>(MAC::DIGESTSIZE);}
size_t GetSymmetricCiphertextLength(size_t plaintextLength) const
    {return plaintextLength + static_cast<size_t>(MAC::DIGESTSIZE);}

MAC::DEFAULT_KEYLENGTH was restored at Crypto++ 8.3 under Issue 856, ECIES and GetSymmetricKeyLength no longer uses MAC::DEFAULT_KEYLENGTH.

Downloads

cryptopp-ecies-test.zip - Generates, saves, loads, and validates keys for ECIES. Additionally, encryption and decryption are exercised using PK_EncryptorFilter and PK_DecryptorFilter.

cryptopp-ecies-bc.zip - Patch to provide compatibility with Bouncy Castle's implementation of ECIES.