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.

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);

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. 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.

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.