Elliptic Curve Cryptography : discrete log and Diffie-Hellman

Question

Here's my current understanding of how ECC works.

There is a recipient and a sender - Alice and Bob and each has a public and private key - (Alice's private key is denoted by a and public key is denoted by A and likewise for Bob).

They have a publicly available curve and a publicly available starting point P.

Alice then applies point multiplication a times on P and then sends it to Bob and then Bob applies point multiplication b times on P. The process is then reversed, but this time Bob is the first one to apply multiplication.

Thus both parties receive S which is the result of point multiplication applied ab times on P.

My question is: why couldn't a man in the middle of brute force work out what "a" and "b" are? If they repeatedly apply point multiplication they will eventually reach the point which is publicly sent hence could they not reverse engineer what the values are? Furthermore, Alice and Bob would have had to apply point multiplication "a" and "b" times anyway - so surely it's computationally feasible for a third party to do the same.

Answer 1

Consider an Elliptic Curve $E$ over a finite field $K$; $E(K)$ with a generator $G$. We will use standard terminology ; scalar multiplication of a point $G$ with a scalar $t$ is adding a point $G$ it self $t$-times

$$ P =[t]G : = \underbrace{G + G + \cdots + G}_{t-times}$$

why couldn't a man in the middle of brute force work out what "a" and "b" are? If they repeatedly apply point multiplication they will eventually reach the point which is publically sent hence could they not reverse engineer what the values are?

The discrete logarithm ( given $P$ and $G$ find $t$ ) has been long studied; There are various better algorithms than the brute-force and best published algorithms (Pollard's $\rho$) took $\mathcal{O}(\sqrt{n})$ where $n$ is the order of $G$ ( well Shor's period finding algorithm will beat this once build with enough q-bits).

So as long as one takes safe curves like curve25519, Curve448, or any NIST recommendation or Certicom curves, they will be fine from the discrete log.

Furthermore, Alice and Bob would have had to apply point multiplication "a" and "b" times anyway - so surely it's computationally feasible for a third party to do the same.

The Standard Elliptic Curve DHKE in short ECDH

Now, the protocol is as follows;

\begin{array}{lcl} \text{Alice} & \text{Transmit} & \text{Bob}\\ \hline a \stackrel{R}{\leftarrow} K& & b \stackrel{R}{\leftarrow} K\\ \text{calculates } A = [a]G & \xrightarrow{A} & \text{calculates } B = [b]G\\ & \xleftarrow{B} & \text{calculates } S = [a]B = [b]([a]G)= [ba]G \\ \text{calculates } S = [b]A = [a]([b]G) = [ab]G & & \end{array}

Here note that $a$ is the secret of $A$ and $b$ is the secret of $B$. The secret $a$ and $b$ are never transmitted, they publish public points $A=[a]G$ and $B =[b]G$ so that their private key is protected with the Discrete Logarithm problem as long as the Curve order is larger $>2^{200}$ and the Discrete Logarithm problem is hard - not all curves have hard discrete logarithm^*.

• Neither Bob nor the third party sees the $a$ Bob and the third party have the same knowledge about the secret $a$ of Alice
• Neither Alice nor the third party sees the $b$ Alice and the third party have the same knowledge about the secret $n$ of Bob.

So they are on the task of finding the discrete logarithm of $A$ given $G$. i.e. words find the secret $a$ of Alice, similarly for Bob's secret $b$.

why couldn't a man in the middle

1. Well the man in the middle has more to do on unprotected DH and in order to be protected from this one needs a digital signature, certificates, etc.

2. Actually we have well-defined problem; the Computational Diffie-Hellman Problem (DHP)

   Given $A,B, G$ find the $S$, i.e. the common agreement between Alice and Bob.

   If the attacker can solve the discrete problem then they can solve DHP. The reverse is not proven, so the two problems are not the same.

   For a general treatment of this see Q/A

   • What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?

_{^*Smart showed that if the order of the curve and order of the base field ($K$) is the same (i.e. $\#E(\mathbf{F}_q ) = q$) then the discrete logarithm on this curves runs in linear time. Such curves are called anomalous curves.}