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:

  1. Commutativity: $P_1 + P_2 = P_2 + P_1 \forall P_1, P_2 \space on \space E$
  2. Identity: $P + \mathcal{O} = P \space \forall \space P \space on \space E$
  3. Inverse: $\forall P \in E \space \exists P’ \in E \space | \space P + P’ = \mathcal{O} \text{ P’ will be denoted by -P}$
  4. 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.

groupLaw.png

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:

  1. Start with $a = k$, $B = \mathcal{O}$ and $C = P$
  2. If $a$ is even then $a = a / 2$ and let $B = B$, $C = 2C$
  3. If $a$ is odd then $a = a - 1$ and let $B = B + C$, $C = C$
  4. If $a \ne 0$ goto step 2
  5. 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.

Abhijit Sinha avatar
About Abhijit Sinha, "Abhijit"
Member of blockchain team at Imaginea