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