1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is about the hardness of the discrete logarithm of the selected algebraic structure, where you are talking about Elliptic curves. This is usually mentioned immediately after introduction of DHKE. Note that the standard terminology is not point multiplication, it is scalar multiplication. Using multiplication can can fuse as the points can form ring, rather they are forming Z-module. $\endgroup$
    – kelalaka
    Oct 21, 2023 at 10:12
  • $\begingroup$ Issues with the question: 1) It's not applied "point multiplication $a$ times on $P$". It's performed one point mutiplication (or equivalently scalar multiplication) of $P$ by scalar $a$. That yields the same result as would adding $a$ copies of $P$ using $a-1$ point additions, only much faster (much like we can multiply by billions without doing billions additions). 2) An attack that brute-forces what $a$ or $b$ are requires only passive eavesdropping, which is not the Man-in-the-Middle attack (where the attacker actively modifies messages). $\endgroup$
    – fgrieu
    Oct 23, 2023 at 9:30

1 Answer 1

0
$\begingroup$

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

*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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.