How does Diffie–Hellman differ from elliptic curve Diffie–Hellman?

Question

I didn't understand how ECDH actually works. Disclaimer: I know very little about elliptic curves.

Here is how DH works:

1. Alice and Bob agree on a prime number $P$ and a generator $G$. (They use one from RFC 3526)
2. Alice generates a long-enough (how long?) secret $S$ and calculates $R = G^S \pmod{P}$ and sends the result $R$ to Bob
3. Bob does the same that Alice did in step 2.
4. Alice and Bob exchange the values of $R$
5. They both calculate $R^S \pmod{P}$ with the value send by the other party, and find the same value $SS$.

$SS$ is the Shared Secret.

How do points 1..4 differ when using elliptic curves?
What are the "equivalent" values of RFC 3526 for EC?

Answer 1

You might want to checkout Wikipedia page of elliptic curves to get a basic overview.

The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime $p$, ECDH uses a multiplicative group of points on an elliptic curve:

1. Alice and Bob agree on an elliptic curve $E$ over a Field $\mathbb{F}_q$ and a base point $P \in E/\mathbb{F}_q$.

2. Alice generates a (random) secret $k_A$ and computes $P_A = k_A P$.

3. Bob generates a (random) secret $k_B$ and computes $P_B = k_B P$.

4. Alice and Bob exchange $P_A$ and $P_B$.

5. Alice and Bob compute $P_{AB} = k_A P_B = k_B P_A$.

   The secret $k_A$ and $k_B$ is a random value $\in \{1, ..., n-1\}$ where $n$ is the order of the group generated by $G$.

The equivalent RFC may be RFC 4753 (not sure, not into RFCs at all).

To agree on a common curve Alice and Bob may either generate a curve them selves or use predefined curves and base points. For this there are a couple of standards defined, see:

• Brainpool
• IEEE P1363
• NIST
• NSA Suite B
• ANSI X9.63
• ...

Depending on application for ECDH you might want to choose different curves since some curves have benefits, for example amount of calculation steps for point multiplications.

Answer 2

It works on the very same way.
The only difference is the group where you do the math. In Elliptic Curve Cryptography the group is given by the point on the curve and the group operation is denoted by +, while in the standard Diffie-Hellman algorithm the group operation is denoted by $ \cdot $.

I would suggest you to read the following link. I think it is very well written and easy to follow. After that Elliptic Curve Cryptography won't have any secrets for you (sort of. It is a quite difficult and complex branch of crypto and maths, but this is very good to understand all the principles).

http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/