Elliptic Curve Diffie-Hellman

From Crypto++ Wiki
Jump to: navigation, search

Elliptic Curve Diffie-Hellman (ECDH) is key agreement protocol performed using elliptical curves rather than traditional integers (see, for example DH and DH2). The protocol allows parties to create a secure channel for communications.

There are two variants of ECDH - ephemeral-ephemeral and ephemeral-static. ephemeral-ephemeral is anonymous and suffers Man in the Middle (MitM) attacks. ephemeral-static does not suffer the man in the middle, but the initiator (client) is not authenticated. For details on ephemeral-ephemeral and ephemeral-static, see NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography and Suite B Implementers' Guide to NIST SP 800-56A.

For authenticated Diffie-Hellman using elliptic curves (and other security assurances such as key confirmation and forward secrecy), see ECMQV, HMQV and FHMQV.

Finally, this page is concerned with two party key agreement. For group key agreement and multicast scenarios, see Multicast Security: A Taxonomy and Some Efficient Constructions and Provably Authenticated Group Diffie-Hellman Key Exchange.

Crypto++ Validation

Crypto++'s valdat2.cpp test file performs ECDH validation over Fp and F2m. See ValidateECP and ValidateEC2N for details.

Choice of Fields

ECDH is defined over both prime fields (Fp) and binary fields (F2m). To operate over a prime field, use ECP:

ECDH<ECP>::Domain ecdh;

For binary fields, specify EC2N:

ECDH<EC2N>::Domain ecdh;

Ephemeral Key as (x,y) Coordinate

If you have the other's temporary public key as an (X,Y) coordinate, then the following will allow you to use it with ECDH class. You will have to supply the values used for the ECP::Point q(x,y) below.

OID curve = ASN1::secp256r1();
DL_GroupParameters_EC<ECP> params(curve);

size_t size = params.GetEncodedElementSize(true);
vector<byte> otherPublicKey(size);

ECP::Point q(x,y);
params.EncodeElement(true, q, &otherPublicKey[0]);

Later, you can use it as so:

ecdh.Agree(key, myPrivateKey, &otherPublicKey[0]);

The preceding works because internally the ephemeral public and private keys are created in pubkey.h around line 1380. The code for them is below.

void GeneratePrivateKey(RandomNumberGenerator &rng, byte *privateKey)
    Integer x(rng, Integer::One(), GetAbstractGroupParameters().GetMaxExponent());
    x.Encode(privateKey, PrivateKeyLength());

void GeneratePublicKey(RandomNumberGenerator &rng, const byte *privateKey, byte *publicKey)
    const DL_GroupParameters<T> &params = GetAbstractGroupParameters();
    Integer x(privateKey, PrivateKeyLength());
    Element y = params.ExponentiateBase(x);
    params.EncodeElement(true, y, publicKey);

The line of interest above is the params.EncodeElement(true, y, publicKey). More details are available at eccrypto.h around line 70:

void EncodeElement(bool reversible, const Element &element, byte *encoded)
    if (reversible)
        GetCurve().EncodePoint(encoded, element, m_compress);
        element.x.Encode(encoded, GetEncodedElementSize(false));

reversible is true, so params.EncodeElement calls ECP::EncodePoint. The code for ECP::EncodePoint is located in ecp.cpp around line 120. The routine writes a uncompressed point, but blocks x and y on the maximum size of the public element, which should be the field size or the subgroup order.

void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed)
    if (P.identity)
        NullStore().TransferTo(bt, EncodedPointSize(compressed));
    else if (compressed)
        bt.Put(2 + P.y.GetBit(0));
        P.x.Encode(bt, GetField().MaxElementByteLength());
        unsigned int len = GetField().MaxElementByteLength();
        bt.Put(4);      // uncompressed
        P.x.Encode(bt, len);
        P.y.Encode(bt, len);

Key Agreement

The code below performs key agreement using NIST's 256 bit curve over Fp. The agreed upon value is encoded as an Integer because the class overloads the output operator, which makes it easy to print. In practice, the shared secret is usually hashed before use, and then used as a Key Encryption Key (KEK) to transport a random session key; or used as a Content Encryption Key (CEK).

OID CURVE = secp256r1();
AutoSeededRandomPool rng;

ECDH < ECP >::Domain dhA( CURVE ), dhB( CURVE );
SecByteBlock privA(dhA.PrivateKeyLength()), pubA(dhA.PublicKeyLength());
SecByteBlock privB(dhB.PrivateKeyLength()), pubB(dhB.PublicKeyLength());

dhA.GenerateKeyPair(rng, privA, pubA);
dhB.GenerateKeyPair(rng, privB, pubB);

if(dhA.AgreedValueLength() != dhB.AgreedValueLength())
    throw runtime_error("Shared shared size mismatch");

SecByteBlock sharedA(dhA.AgreedValueLength()), sharedB(dhB.AgreedValueLength());

if(!dhA.Agree(sharedA, privA, pubB))
    throw runtime_error("Failed to reach shared secret (A)");

if(!dhB.Agree(sharedB, privB, pubA))
    throw runtime_error("Failed to reach shared secret (B)");

Integer ssa, ssb;

ssa.Decode(sharedA.BytePtr(), sharedA.SizeInBytes());
cout << "(A): " << std::hex << ssa << endl;

ssb.Decode(sharedB.BytePtr(), sharedB.SizeInBytes());
cout << "(B): " << std::hex << ssb << endl;

if(ssa != ssb)
    throw runtime_error("Failed to reach shared secret (C)");

cout << "Agreed to shared secret" << endl;

In production, the test ssa != ssb cannot be performed since the values will be on different hosts. A problem with agreement will not be detected until data starts flowing - the first data packet received with not authenticate.

A typical run is shown below.

$ ./ecdh.exe
(A): 2b21da66d49b8faa85abc71a4cb23298c9b0c035841eef618fded5eaeb551fb6h
(B): 2b21da66d49b8faa85abc71a4cb23298c9b0c035841eef618fded5eaeb551fb6h
Agreed to shared secret


ecdh-agree.zip - Elliptic Curve Diffie-Hellman (ECDH) key agreement (unauthenticated).