# Diffie Hellman Key exchange using Elliptic Curve Cryptography

Diffie–Hellman key exchange (DH) is a method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as originally conceptualized by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography.

In this post we would first explain how a Diffie Hellman key exchange works. Then we would dive deeper into the details of elliptic curves and its properties. Finally we would show how Elliptic Curves can be used for efficient key exchange.

### Motivation

Alice and Bob possess secret keys with themselves and would like to come up with a new shared secret which is known to both of them but is unknown to anyone else. They can use this shared secret to then encrypt any further communication. The question is how do they do this?

Interestingly, they have at their disposal a globally known information $g$. Alice holds a secret $a$ while Bob holds the secret $b$. Using $g$ Alice and Bob have to come up with a common secret.

### Algorithm

Alice sends Bob $A = g^a$ and Bob sends Alice $B = g^b$.

Once Alice receives $B$ from Bob she calculates $B^a$ and similarly once Bob gets $A$ from Alice he comuptes $A^b$.

To represent this slightly better:

[ \begin{array}{r|l|l} & \text{Alice} & \text{Bob} \\ \hline \text{global} & g & g \\ \text{secret} & a & b \\ \text{sends} & g^a & g^b \\ \text{receives} & g^b & g^a \\ \text{computes} & (g^b)^a & (g^a)^b \\ \hline \text{shared secret} & g^{ab} & g^{ab} \end{array} ]

As you can see, without sending their secret, Alice and Bob are able to come to the same shared secret.

### Problem

However there is Eve listening to this conversation. So when Alice sends Bob $g^a$, Eve too gets this information, and when Bob sends Alice $g^b$, Eve receives this information as well.

Now Eve has both $g^a$ as well as $g^b$. And since $g$ is globally know, Eve now needs to compute $g^{ab}$ and figure out the shared secret between Alice and Bob

The problem Eve now has is: Given $g$, $g^a$ and $g^b$, how to compute $g^{ab}$. This problem is called Diffie–Hellman_problem (DHP)

If $g$, $a$ and $b$ $\in \text{Real } \mathbb{R} \text{ or Integer } \mathbb{Z} \text{ or Complex } \mathbb{C}$ the computation is fairly straight forward.

$a = log_g\left(g^a\right)$

$g^{ab} = \left(g^b\right)^a$

However, in cryptography, for certain algebraic groups,
it is *assumed* that the DHP is hard, and this is often called the
**Diffie–Hellman assumption**. The problem has survived scrutiny for a few
decades and no “easy” solution has yet been publicized.

As of 2006, the most efficient means known to solve the DHP is to solve the
**discrete logarithm problem**
(DLP), which is to find $x$ given $g$ and $g^x$. In fact, significant progress
has been made towards showing that over many groups the DHP is almost as hard
as the DLP. There is no proof to date that either the DHP or the DLP is a hard
problem, except in generic groups

### Requirement

Alice and Bob do not want there shared secret known to Eve, so they need to find some algerbraic group where DLP is hard.

### Elliptic Curve Cryptography

The discrete logarithm problem (DLP) has been extensively studied since the
discovery of public-key cryptography in 1975. The DLP in an additively-written
group $G = \langle P \rangle$ of order $n$ is the problem, given $P$ and $Q$,
of finding the integer $x \in \left[0, n - 1\right]$ such that $Q = xP$. The DLP
is believed to be intractable for certain (*carefully chosen*) groups including
* the multiplicative group of a finite field, and
* the group of points on an elliptic curve defined over a finite field.

Of these groups, we would like to further investigate the second one, which is the group of points on an elliptic curve defined over a finite field.

#### Math refresher

In this section we would like to define certain mathematical structures and definitions, which would be used throughout the document.

##### Set

A set is a collection of similar objects. There is no ordering among the objects in the set, however no object in the set is allowed to be repeated.

**example**:

$S_1 = {x : 0 < x < 10, x \in \mathbb{Z}}$

$S_2 = {(x, y) : y^2 = x^3 + x + 1, x \in \mathbb{Z}, y \in \mathbb{C} }$

##### Group

A group $G$ is a set $S$ along with a binary operation $\bigoplus$ defined on the set, such that it follows the following properties

*Closure*: $a, b \in S \implies a \bigoplus b \in S$*Associative*: $(a \bigoplus b) \bigoplus c = a \bigoplus (b \bigoplus c)$*Identity*: $\exists e \in S : \forall a \in S \space a \bigoplus e = e \bigoplus a = a$*Inverse*: $\forall a \in S \space \exists a^* \in S : a \bigoplus a^* = e$

**example**:

Set of all integers with the addition operation $\langle \mathbb{Z}, +\rangle$ forms a group. The identity element here is $0$.

Set of all rational numbers with the multiplication operation
$\langle \mathbb{Q}, *\rangle$ does **NOT** form a group. The number $1$ may
seem like the identity element here but $\nexists q \in \mathbb{Q} : 0 * q = 1$

##### Abelian Group

An **abelian group** is a group whose elements commute. More formally:

$G \langle S, \bigoplus \rangle$ is abelian iff $\forall a,b \in S \space a \bigoplus b = b \bigoplus a$

##### Field

A field $F$ is a set $S$ with two binary operations $\left(\bigoplus, \bigotimes\right)$ which satisfies the following properties

*Associativity*: $(a \bigoplus b) \bigoplus c = a \bigoplus (b \bigoplus c)$ and $(a \bigotimes b) \bigotimes c = a \bigotimes (b \bigotimes c)$*Commutative*: $a \bigoplus b = b \bigoplus a$ and $a \bigotimes b = b \bigotimes a$*Additive Identity*: $\exists O \in S : \forall a \in S, O \bigoplus a = a$*Multiplicative Identity*: $\exists I \in S : \forall a \in S, I \bigotimes a = a$*Additive Inverse*: $\forall a \in S \exists -a : a \bigoplus (-a) = O$*Multiplicative Inverse*: $\forall a \in S \exists a^{-1} : a \bigotimes a^{-1} = I$*Distributivity*: $a \bigotimes (b \bigoplus c) = (a \bigotimes b) \bigoplus (a \bigotimes c)$

##### Ring

A ring $R$ is a set $S$ with two binary operations $\left(\bigoplus, \bigotimes \right)$ which satisfy the following properties:

$R$ is an abelian group under $\bigoplus$

*Associativity*: $(a \bigoplus b)\bigoplus c = a \bigoplus (b \bigoplus c)$*Commutative*: $a \bigoplus b = b \bigoplus a$*Identity*: $\exists O \in S : \forall a \in S, O \bigoplus a = a \bigoplus O = a$*Inverse*: $\forall a \in S \exists -a : a \bigoplus (-a) = O$

$R$ is monoid under $\bigotimes$

*Associativity*: $(a \bigotimes b) \bigotimes c = a \bigotimes (b \bigotimes c)$*Identity*: $\exists I \in S : \forall a \in S, I \bigotimes a = a \bigotimes I = a$

$\bigotimes$ is distributive with respect to $\bigoplus$

*Right distributive*: $a \bigotimes (b \bigoplus c) = (a \bigotimes b) \bigoplus (a \bigotimes c)$*Left distributive*: $(b \bigoplus c) \bigotimes a = (b \bigotimes a) \bigoplus (c \bigotimes a)$

#### Elliptic curve

Now we bring our discussion back to Elliptic Curve. The general form of an elliptic curve is given as follows:

$$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$

Where $a_1, a_2, a_3, a_4, a_6 \in K$. This form of elliptic curve is called the generalized Weierstrass equation.

However, if the characteristics of $K \ne 2, 3$ then the equation can further be simplified to:

$$y^2 = x^3 + Ax + B$$

#### Additive properties of points on elliptic curve

**Theorem 1**

Let E be an elliptic curve defined by $y^2 = x^3 + Ax + B$. Let $P_1 = \left(x_1, y_1\right)$ and $P_2 = \left(x_2, y_2\right)$ be points of E. Then $P_3\left(x_3, y_3\right) = P_1 + P_2$ is described by the following cases:

**Case 1**: $P_1 \ne P_2$ and $x_1 \ne x_2$
$$x_3 = m^2 - x_1 - x_2$$
$$y_3 = m\left(x_1 - x_3\right) - y_1$$
where $m = \frac{y_2 - y_1}{x_2 - x_1}$

**Case 2**: $P_1 \ne P_2$ but $x_1 = x_2$
$$P_3 = P_1 + P_2 = \mathcal{O}$$

**Case 3**: $P_1 = P_2$ but $y_1 = y_2 \ne 0$
$$x_3 = m^2 - 2x_1$$
$$y_3 = m\left(x_1 - x_3\right) - y_1$$
where $m = \frac{3x_1^2 + A}{2y_1}$

**Case 4**: $P_1 = P_2$ and $y_1 = y_2 = 0$
$$P_3 = P_1 + P_2 = \mathcal{O}$$

**Case 5**: $P_2 = \mathcal{O}$
$$P_3 = P_1 + P_2 = P_1 + \mathcal{O} = P_1$$

**Note** the point $\mathcal{O} \in K$ is the point at infinity where
**all vertical lines converge**

**Theorem 2**

The addition of points on an elliptic curve $E$, which was described in the previous theorem, satisfies the following properties:

**Commutativity**: $P_1 + P_2 = P_2 + P_1 \forall P_1, P_2 \space on \space E$**Identity**: $P + \mathcal{O} = P \space \forall \space P \space on \space E$**Inverse**: $\forall P \in E \space \exists P’ \in E \space | \space P + P’ = \mathcal{O} \text{ P’ will be denoted by -P}$**Associativity**: $(P_1 + P_2) + P_3 = P_1 + (P_2 + P_3) \space \forall P_1, P_2, P_3 \in E$

The points on the curve form an **additive abelian group**, where $\mathcal{O}$
is the identity element.

**Double and Add algorithm**

Based on **Theorem 1**, given any $P \in E$ we can now compute $kP \space
\forall \space k \in \mathbb{Z}$. To do so, we use the **double and add
algorithm** which is as follows:

- Start with $a = k$, $B = \mathcal{O}$ and $C = P$
- If $a$ is even then $a = a / 2$ and let $B = B$, $C = 2C$
- If $a$ is odd then $a = a - 1$ and let $B = B + C$, $C = C$
- If $a \ne 0$ goto step 2
- output $B$

Note that $P$ and $kP$ are both points on the Elliptic curve. The interesting thing is that given $P$ and $kP$ it is very difficult to figure out $k$

### Conlusion

We now go back to Alice and Bob’s problem. They wanted to find a mathematical
structure where given $g$ and $g^x$ it would be difficult to compute $x$. And we
have now shown that the *Group* formed by the *Set* of points of the elliptic
curve under the *Addition* operation as defined by **Theorem 1** has the
required property.