ECDH: key exchange on an elliptic curve

The first use of elliptic curves takes up the founding idea of public keys: agreeing on a shared secret without ever having exchanged it. It is the elliptic version of Diffie-Hellman, called ECDH (Elliptic Curve Diffie-Hellman).

The public parameters

Everyone agrees beforehand on:

• a specific elliptic curve (its parameters a, b, and the finite field over which you work);
• a generator point G, fixed and public, located on the curve.

These elements are not secret: they are published in standards, known to everyone, including the eavesdropper.

How the exchange unfolds

Alice and Bob want to share a secret. Each chooses a secret scalar and publishes its multiplication by G:

1. Alice chooses a secret integer a, computes A = a·G and sends A to Bob.
2. Bob chooses a secret integer b, computes B = b·G and sends B to Alice.
3. Alice computes a·B. Bob computes b·A.

Now these two points are identical:

a·B = a·(b·G) = (a·b)·G = b·(a·G) = b·A

They have thus obtained the same secret point S = (a·b)·G, without ever having transmitted it. A symmetric key is then derived from it (by hashing the coordinates of S).

   ALICE                    public channel                  BOB
   secret a                                                 secret b
     |                                                          |
     |  A = a·G   ───────────────────────────────►             |
     |             ◄───────────────────────────────   B = b·G  |
     |                                                          |
   computes a·B                                         computes b·A
     |                                                          |
     └──────────►  shared secret  S = a·b·G  ◄─────────────────┘

Why the eavesdropper fails

An eavesdropper listening on the line sees everything that is public go by: the curve, the generator G, as well as A = a·G and B = b·G. To reconstruct S, they would need to know a (from A and G) or b (from B and G).

But recovering a from A = a·G is exactly solving the ECDLP — infeasible. The eavesdropper is stuck:

   What the eavesdropper sees:  G,  A = a·G,  B = b·G
   What they want:              S = a·b·G
   What stops them:             finding a or b requires breaking the ECDLP

Simply adding A + B would give (a + b)·G, which is not the secret a·b·G. There is no known shortcut to « multiply » two points together in the right way without knowing one of the scalars.

An ephemeral secret

In practice, a and b are often regenerated for each session (ephemeral ECDH, written ECDHE). Hence a valuable property, forward secrecy (forward secrecy): even if a server's long-term key is one day compromised, past communications, encrypted with ephemeral secrets long since destroyed, remain unreadable. This is the default exchange mode of TLS 1.3, and thus of your browser's HTTPS.

In summary

• ECDH is the elliptic version of Diffie-Hellman.
• The public parameters are a curve and a generator point G.
• Alice publishes a·G, Bob publishes b·G; the shared secret is a·b·G = a·(b·G) = b·(a·G).
• The eavesdropper sees a·G and b·G but cannot obtain a·b·G without breaking the ECDLP.
• In ephemeral mode (ECDHE), the exchange offers forward secrecy.