Return to Answer

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 brute force to work out what "a" and "b" are? Since 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 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.}

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

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 brute force to work out what "a" and "b" are? Since 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 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?

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 brute force to work out what "a" and "b" are? Since 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 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.}

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 brute force to work out what "a" and "b" are? Since 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 piblished algrithms 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 form 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 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 has hard discrete logarithm.

• Neither Bob nor the third party sees the $a$ Bob and the third party are the same knowledge about the secret $a$ of Alice
• Neither Alice nor the third party sees the $b$ Alice and the third party are 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 protected from this one needs digital signature, certificates, etc.

2. Actually we have well- defined problem; 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 same.

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 brute force to work out what "a" and "b" are? Since 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 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?