Elliptic Curve Diffie-Hellman

Elliptic Curve Diffie-Hellman (ECDH) is a key agreement protocol that allows two parties to estabilish a shared secret key over an insecure channel^{[1] [2]}. This key can then be used to encrypt subsequent communications using a symmetric key cipher. It is a variant of the Diffie-Hellman protocol using elliptic curve cryptography.

Key establishment protocol

Suppose Alice wants to establish a shared key with Bob, but the only channel available for them may be eavesdropped by a third party. Initially, the domain parameters (that is Failed to parse (Missing texvc executable; please see math/README to configure.): (p,a,b,G,n,h)

in the prime case or Failed to parse (Missing texvc executable; please see math/README to configure.): (m,f(x),a,b,G,n,h)
in the binary case) must be agreed upon. Also, each party must have a key pair suitable for elliptic curve cryptography, consisting of a private key Failed to parse (Missing texvc executable; please see math/README to configure.): d
(a randomly selected integer in the interval Failed to parse (Missing texvc executable; please see math/README to configure.): [1, n-1]

) and a public key Failed to parse (Missing texvc executable; please see math/README to configure.): Q

(where Failed to parse (Missing texvc executable; please see math/README to configure.): Q = d G

). Let Alice's key pair be Failed to parse (Missing texvc executable; please see math/README to configure.): (d_A, Q_A)

and Bob's key pair be Failed to parse (Missing texvc executable; please see math/README to configure.): (d_B, Q_B)

. Each party must have the other party's public key.

Alice computes Failed to parse (Missing texvc executable; please see math/README to configure.): (x_k, y_k) = d_A Q_B . Bob computes Failed to parse (Missing texvc executable; please see math/README to configure.): k = d_B Q_A . The shared key is Failed to parse (Missing texvc executable; please see math/README to configure.): x_k

(the x coordinate of the point).

The number calculated by both parties is equal, because Failed to parse (Missing texvc executable; please see math/README to configure.): d_A Q_B = d_A d_B G = d_B d_A G = d_B Q_A .

The protocol is secure because nothing is disclosed (except for the public keys, which are not secret), and no party can derive the private key of the other unless it can solve the Elliptic Curve Discrete Logarithm Problem.

The public keys are either static (and trusted, say via a certificate) or ephemeral. Ephemeral keys are not necessarily authenticated, so if authentication is wanted, it has to be obtained by other means. Static public keys provide neither forward secrecy nor key-compromise impersonation resilience, among other advanced security properties. Holders of static private keys should validate the other public key, and should apply a secure key derivation function to the raw Diffie-Hellman shared secret to avoid leaking information about the static private key. For schemes with more advanced security properties see ECMQV.

References

1. ^ NIST, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, March, 2006.
2. ^ Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography, Version 1.0, September 20, 2000.