How does ECDH arrive on a shared secret?

Question

I read a brilliant, three part article on Elliptic Curve cryptography (one, two, three). It was able to explain Elliptic Curves to me in a way that didn't require a math degree to understand. The crux of the article is in page two, namely, when it discussed the "dot" operation:

In the brilliant animation above (all credit goes to the original author, Nick Sullivan), the author explained that the heart of EC Crypto is that if you take any two points on the curve, A and B, and draw a line from A to B, and then continue the line you end intersecting one, and only one, other point on the curve. You then go to the x-axis opposite (up or down) to find a third point, point C.

This is expressed in the article as:

A dot B = C

This can continue, using the initial point and the newly acquired point as necessary:

A dot C = D
A dot D = E

We can continue this process an arbitrary number of times, but we'll stop after, for the sake of an example, 25 steps and end up at a point Z. Now we know that if we started at A and applied the process above, it would take 25 total "dot" operations to get to Z. But supposedly, this is a number that is very difficult to determine from someone if they just knew where we started (point A) and where we ended (point Z):

It turns out that if you have two points, an initial point "dotted" with itself n times to arrive at a final point, finding out n when you only know the final point and the first point is hard. To continue our bizarro billiards metaphor, imagine that one person plays our game alone in a room for a random period of time. It is easy for him to hit the ball over and over following the rules described above. If someone walks into the room later and sees where the ball has ended up, even if they know all the rules of the game and where the ball started, they cannot determine the number of times the ball was struck to get there without running through the whole game again until the ball gets to the same point. Easy to do, hard to undo. This is the basis for a very good trapdoor function.

Now, here is my question: How do two parties use EC and the 'dot' operation to determine a shared secret over an unsecured medium? Effectively, how do they use A, B, Z, or 25 from the examples above to arrive at a shared secret?

For the purpose of this question, I am not concerned with how the curve is determined, I'm content with the fact that there are pre-existing curves that both parties choose to use.

Also, I am not concerned with Ephemeral variants of DH or not, at this point, knowing the basic concepts described in the article above, I just want to know what values each party start with, and what they do with those values, and what (if anything) is shared across the wire.

Answer 1

Let's assume that everyone agreed on some elliptic curve and a public base point $g$ somewhere on the curve. When two parties Alice and Bob want to agree on a shared secret, they proceed as follows:

• Alice chooses some random number $a$ and applies the curve operation to $g$, the public base point, $a$ times. She obtains some result $A=g^a=\underbrace{g\cdot g\cdots g}_{\text{$a$ times}}$ and shares this point across the wire with Bob.
• Likewise, Bob chooses a random number $b$ and publishes $B=g^b$.
• Alice takes Bob's point $B$ and applies the curve operation $a$ times to it to obtain a point $S$. That is, $S=B^a=\underbrace{B\cdot B\cdots B}_{\text{$a$ times}}$.
• Bob takes Alice's point $A$ and proceeds accordingly to obtain $S'=A^b$.

At this point, the important thing to notice is that applying some operation $a$ times $b$ times is the same thing as applying some operation $b$ times $a$ times. To keep abusing the billiards metaphor: Hitting a ball $3$ times and repeating this process $5$ times is exactly the same thing as hitting a ball $5$ times and repeating this process $3$ times. In both cases, the ball gets hit $15$ times. Therefore, $S=S'$ is a shared secret!

We have yet to make plausible why $S$ is secret: An attacker only sees $A$ and $B$ and wants to find out what point would result in "mixing" the operations performed by Alice and Bob. Mathematically speaking (this is known as the Diffie-Hellman problem): Given $g^a$ and $g^b$, what is $g^{ab}$? The obvious (but perhaps not the only) way to solve this problem is to compute $a$ and $b$ and simply evaluate the desired expression (remember, hitting the ball is easy!). But computing $a$ or $b$ (solving the discrete logarithm problem) is hopefully — this is in fact an open problem — hard when they are sufficiently large, as described in the text you cited. Therefore, an attacker has (for all we know) a very hard time obtaining the shared secret $S$, and Alice and Bob can live their lives happily ever after.

---

As to the ephemeral "variants": There are none. The difference lies exclusively in the way the above procedure is used: "ephemeral" simply means that the private keys $a$ and $b$ are generated only for one single session and thrown away afterwards, providing forward secrecy.

---

Edit. As Stephen pointed out in the comments, it is actually not that easy: If Alice just naïvely applied the curve operation $a$ times, an attacker might obviously also have the computing power to conduct a brute-force search for $a$. In fact, the repeated application of the operation is performed using exponentiation by squaring, effectively obtaining the result in time $\mathcal O(\log a)$ instead of $\mathcal O(a)$. It is based on the observation that, when $a=2a_h+a_\ell$ with $a_\ell\in\{0,1\}$, then $$g^a = (g^2)^{a_h}\cdot g^{a_\ell}\text.$$ Recursively applying this identity to compute $(g^2)^{a_h}$ until $a_h$ is zero requires a number of steps proportional to the bit length of $a$. When $a=\sum_{i=0}^ra_i2^i$ with all $a_i\in\{0,1\}$ is the binary representation of $a$, this yields the formula $$g^a=g^{\sum_{i=0}^ra_i2^i}=\prod_{i=0}^rg^{a_i2^i}\text.$$ (Without using formulae, this means: For each $i$ where the $i$th least significant bit of $a$ is set, take $g$ and square it $i$ times. That is, set $t:=g$ and repeat the assignment $t:=t^2$, i.e. apply the curve operation to $t$ and $t$ and call the result $t$ again, $i$ times. Do this for all $i$ and combine the resulting $t$s using the curve operation.)