# Diffie-Hellmann Key Exchange

## Introduction

- Public key exchange protocol
- Group based cryptography

## Flavour

Given:**A**and

**B**want to agree upon a secret colour. Eavesdropper

**C**who is able to intercept their messages.

**Assumption:**Color seperation is expensive.

- A and B
*publically*agree on a common colour P. - A and B choose some secret
*colour*X and Y respectively. - A mixes P+X and sends it to B
- B mixes P+Y and sends to A
- C intercepts P+x and P+Y
- A and B then mix their personal secret colours to the received colours.
- A's new mix = P+Y+X
- B's new mix = P+X+Y
- A and B arrive at the same colour

*almost*inseperable. C is unable to make P+X+Y and thus P+X+Y is now the secure private key for A and B.

*Source:Wikipedia*

## Simple cryptographic use case

A and B publicly agree on a prime number $p$ (say 23). A and B then agree on a generator $g$ (say 5) belonging to ${1, ... , p-1}$. (More on this below)- A chooses secret integer $a=11$ and computes $A1 = g^a\ mod\ p = 5^{13}\ mod\ 23 = 21$
- B chooses secret integer $b=9$ and computes $B1 = g^b\ mod\ p = 5^9\ mod\ 23 = 11$
- A and B exchange A1 and B1
- C intercepts $A1=21$ and $B1=11$
- *MAGIC*
- A performs ${B1}^a\ mod\ 23 = 11^{13}\ mod\ 23 = 17$
- B performs ${A1}^b\ mod\ 23 = 21^9\ mod\ 23 = 17$
- Thus A and B could now use this an their encryption key.

i.e. $(g^a\ mod\ p)^b\ mod\ p = (g^b\ mod\ p)^a\ mod\ p$

Even though C is aware of prime number $p$, generator $G$, A's message A1 and B's message B1; C is unable to generate the new secret key as it is computationally intractable to find secret keys from A1 and B1, i.e. It is hard to figure out $x$ in $g^x\ mod\ p =$ A1

But is this secure enough?

## Discrete Logarithm Problem

Given $p$ , $g$ , $g^x\ mod\ p$ , find $x$. This problem gets hard for very large prime values of $p$. Finding the solution in polynomial time is still an unsolved problem in computer science. Thus, the strength of the Diffie-Hellman key exchange is the Discrete Logarithm Problem.Why generators? What do they generate?

## Group

A group is a set with operation under :*closure , existence of inverse element , associativity, existence of identity element*. For instance, (Z,+) is integer group under addition.

Groups which can be generated by a single element are called

**cyclic**groups. These special elements are called

**generators**.

Example: Consider a dot operation defined as $a . b = (a*b) mod n$ over a simple group $G : {1,2,3,4}$ for $n = 5$

Also consider the notation that $a[i]$ = ((a . a ). a) ... (i times).

A number $g$ from $G$ will be called a generator if it performs the operation on itself to generate the whole group.

- 1 : $1[i] = ( 1^i\ mod\ 5 ) = {1}$ for any $i$
- 2 : $2[i] = ( 2^i\ mod\ 5 ) = {2,4,3,1}$ for $i=1,2,3,4$ respectively = G
- 3 : $3[i] = ( 3^i\ mod\ 5 ) = {3,4,2,1}$ for $i=1,2,3,4$ respectively = G
- 4 : $4[i] = ( 4^i\ mod\ 5 ) = {4,1}$ for $i=1,2, \cdots$

*generators of group (G,dot)*.

Generators have a property that $g^i mod p$ generate a group of numbers between $1$ to $p-1$ and that every number is equally likely to be generated. This group is called

*multiplicative group of integers modulo*. It is defined as a group of integers coprime to

**n****$n$**from the set ${0,1,...n-1}$ under

*multiplication modulo*$n$. ($a . b = (a*b)\ mod\ n$). Since our $p$ is prime, the generated group includes all numbers from $1$ to $p-1$.

This way, the encryption key could take any value between $1$ to $p-1$ equally likely and thus it is harder to guess for larger values of $p$.

Such cyclic groups modulo $p$, a large prime number, and a corresponding generator (primitive root modulo p ) $g$ are used to create a secure public-key transfer protocol given that discreet logarithm problem is hard to solve.

## Flaws

Impersonation issues. Any information passed to the insecure channel could be intercepted by an impersonator who could act like the actual receiver.## Further

We realise that since we use a

*large*prime $p$, the encryption key becomes

**huge**as well, as $g^{ab}\ mod\ p$ always lies between $1$ to $p-1$. This proves to be memory extensive.

An interesting area is Elliptic curve cryptography, which reduces the encryption key size and provides equivalent security.

Last Updated: 3 Apr 2020