Elliptic curve integrated encryption scheme

From Crypto++ Wiki
Jump to: navigation, 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 http://www.shoup.net/papers/iso-2_1.pdf.

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.

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." In fact, Crypto++ and Bouncy Castle enjoy this inter-non-operability. Fortunately, there's a patch available to fix it thanks to Jesse Wilson and Daniele Perito. See the Bouncy Castle Patch below.

If you are trying to inter-operate and Crypto++ lacks a patch for you, then please visit A Comparison of the Standardized Versions of ECIES. It describes the differences between many of the standardized integrated encryption schemes. Martínez, Alvarez, Encinas, and Ávila do a good job at describing them in an easy to digest format.

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.

ECIES

ECIES is typedef'd as a templated structure in eccrypto.h:

template <class EC, class COFACTOR_OPTION = NoCofactorMultiplication, bool DHAES_MODE = 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<SHA1> >,
        DL_EncryptionAlgorithm_Xor<HMAC<SHA1>, DHAES_MODE>,
        ECIES<EC> >
{
    static std::string 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.

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. To load the private key named MERCHANT_PRIVATE_KEY_PKCS8_BASE64, perform the following:

string encoded =
    "MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgCPSuFr4iSIaQprjj"
    "chHPyDu2NXFe0vDBoTpPkYaK9dehRANCAATnaFz/vQKuO90pxsINyVNWojabHfbx"
    "9qIJ6uD7Q7ZSxmtyo/Ez3/o2kDT8g0pIdyVIYktCsq65VoQIDWSh2Bdm";

int main(int argc, char* argv[])
{
    try
    {
        string decoded;
        StringSource ss(encoded.c_str(), true, new Base64Decoder(new StringSink(decoded)));        

        ECIES<ECP>::Decryptor decryptor;
        decryptor.AccessKey().Load(StringStore((const byte*)decoded.data(), decoded.size()).Ref());

        AutoSeededRandomPool prng;
        decryptor.GetKey().ThrowIfInvalid(prng, 3);
        
        cout << "Private key appears to be valid" << endl;
    }
    catch(Exception& ex)
    {
        cerr << ex.what() << endl;
        return 1;
    }
    
    return 0;
}

The Android Pay KDF using HKDF would look similar to the following:

template <class H>
class AndroidPay_KDF
{
public:
    static void CRYPTOPP_API DeriveKey(byte *output, size_t outputLength, const byte *input, size_t inputLength,
            const byte *derivationParams, size_t derivationParamsLength)
    {
        CRYPTOPP_UNUSED(derivationParams), CRYPTOPP_UNUSED(derivationParamsLength);

        static const byte INFO[] = "Android";
        static const size_t INFO_SIZE = 7;
		
        HKDF<H> hkdf;
        hkdf.DeriveKey(output, outputLength, input, inputLength, NULL, 0, INFO, INFO_SIZE);
    }
};

Bouncy Castle Patch

Crypto++ does not interop with 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 essence of the problem is the label L length must be MAC'd to preserve semantic authentication. But Crypto++ uses a 8-byte word for L, while Bouncy Castle uses a 4-byte word for L. In addition, Crypto++ wrote a byte count to the label while Bouncy Castle wrote a bit count. Obviously, mac.Update(L, 8) and mac.Update(L, 4) will produce different results.

Jesse and Daniele Perito offer a patch to unconditionally patch Crypto++ to use Bouncy Castle's encoding method. If you want to retain Crypto++ behavior but interop with Bouncy Castle, then apply the patch cryptopp-ecies-bc.zip and use ECIES_BC rather than ECIES. It incorporates Jesse and Daniel's changes while retaining Crypto++ default behavior.

5.6.3 and 6.0 Changes

The current ECIES implementation was marked as deprecated at 5.6.3. When compiling Crypto++ 5.6.3, you will encounter warnings similar to below. Its safe to ignore them at the moment because it is intended to warn of an impending change to the implementation, which will occur at Crypto++ 6.0. At 6.0, the old class will be available under a different name.

clang++ -DNDEBUG -g2 -O2 -fPIC -march=native -DCRYPTOPP_DISABLE_ASM -pipe -c validat2.cpp
bench2.cpp:293:3: warning: 'ECIES' is deprecated: ECIES will be changing in the
      near future due to (1) an implementation bug and (2) an interop issue.
      [-Wdeprecated-declarations]
                ECIES<ECP>::Encryptor cpub(cpriv);
                ^
eccrypto.h:245:8: note: 'ECIES' declared here
struct ECIES
       ^

And:

g++ -DNDEBUG -g2 -O2 -pipe -c validat2.cpp
validat2.cpp: In function ‘bool ValidateECP()’:
validat2.cpp:548:2: warning: ‘template<class EC, class COFACTOR_OPTION, bool DHAES_MODE> struct CryptoPP::ECIES’ is deprecated [-Wdeprecated-declarations]
  ECIES<ECP>::Decryptor cpriv(GlobalRNG(), ASN1::secp192r1());
  ^
In file included from validat2.cpp:22:0:
eccrypto.h:245:8: note: declared here
 struct ECIES
        ^
validat2.cpp:549:2: warning: ‘template<class EC, class COFACTOR_OPTION, bool DHAES_MODE> struct CryptoPP::ECIES’ is deprecated [-Wdeprecated-declarations]
  ECIES<ECP>::Encryptor cpub(cpriv);
  ^
In file included from validat2.cpp:22:0:
eccrypto.h:245:8: note: declared here
 struct ECIES
        ^
validat2.cpp: In function ‘bool ValidateEC2N()’:
validat2.cpp:597:2: warning: ‘template<class EC, class COFACTOR_OPTION, bool DHAES_MODE> struct CryptoPP::ECIES’ is deprecated [-Wdeprecated-declarations]
  ECIES<EC2N>::Decryptor cpriv(GlobalRNG(), ASN1::sect193r1());
  ^
In file included from validat2.cpp:22:0:
eccrypto.h:245:8: note: declared here
 struct ECIES
        ^
validat2.cpp:598:2: warning: ‘template<class EC, class COFACTOR_OPTION, bool DHAES_MODE> struct CryptoPP::ECIES’ is deprecated [-Wdeprecated-declarations]
  ECIES<EC2N>::Encryptor cpub(cpriv);
  ^
In file included from validat2.cpp:22:0:
eccrypto.h:245:8: note: declared here
 struct ECIES
        ^

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.