# Diffie-Hellmann Key Exchange

## Introduction

- Public key exchange protocol
- Group based cryptography

A and B can agree on a secret key while communicating over a public/insecure network!

## 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 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 colors.
- - A's new mix = P+Y+X
- - B's new mix = P+X+Y
- - A and B arrive at the same colour

C could not come up with P , X and Y from P+X and P+Y as they are *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.

This is because (g^a)^b mod p = (g^b)^a mod p

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 really 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).

Now, 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 and so on..

Since, we can generate G from 2 and 3, they are the *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 n*. It is defined as a group of integers coprime to

**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 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 tends to reduce the encryption key size and provide equivalent security.

Last Updated: 3 April 2020