Diffie-Hellmann Key Exchange

Introduction
Flavour
Simple cryptographic use case
Discrete Logarithm Problem
Group
Flaws
Further

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

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 $A 1 = g^{a} m o d p = 5^{13} m o d 23 = 21$
B chooses secret integer $b = 9$ and computes $B 1 = g^{b} m o d p = 5^{9} m o d 23 = 11$
A and B exchange A1 and B1
C intercepts $A 1 = 21$ and $B 1 = 11$
*MAGIC*
A performs ${B 1}^{a} m o d 23 = 11^{13} m o d 23 = 17$
B performs ${A 1}^{b} m o d 23 = 21^{9} m o d 23 = 17$
Thus A and B could now use this an their encryption key.

This is because

(g^{a})^{b} m o d p = (g^{b})^{a} m o d p

i.e.

(g^{a} m o d p)^{b} m o d p = (g^{b} m o d p)^{a} m o d 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

g^{x} m o d p =

A1

But is this secure enough?

Discrete Logarithm Problem

Given

p

g

g^{x} m o d 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) m o d 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} m o d 5) = 1$ for any $i$
2 : $2 [i] = (2^{i} m o d 5) = 2, 4, 3, 1$ for $i = 1, 2, 3, 4$ respectively = G
3 : $3 [i] = (3^{i} m o d 5) = 3, 4, 2, 1$ for $i = 1, 2, 3, 4$ respectively = G
4 : $4 [i] = (4^{i} m o d 5) = 4, 1$ for $i = 1, 2, \dots$

Since, we can generate

G

from 2 and 3, they are the generators of group (G,dot) .

Generators have a property that

g^{i} m o d p

generate a group of numbers between

1

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) m o d n

). Since our

p

is prime, the generated group includes all numbers from

1

p - 1

.

This way, the encryption key could take any value between

1

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^{a b} m o d p

always lies between

1

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