Diffie Hellman Key Exchange, Step-by-step

Introduction

Cryptography is means to securely communicate in the presence of adversary.
- anonymous -

In WW2, a machine called Enigma is created with sole purpose of securing communication between the army. It worked well, in fact really well that even using today computer it's still really difficult to break the encryption. That being said, it has some weakness. One of them is how to distribute encryption key across wide area.
The machine use symmetric key which means the party communicating use the same key to encrypt and decrypt message. So it's like chicken egg problem, in order to secure message transmission, a key is needed. But how to securely exchange the key?

To tackle this, Diffie-Hellman algorithm use an ingenious and simple technique. It exploits commutative property of power operation. Key is generated in several stteps, in which some parts are available to public. In this article, we will take closer look at how awesome this technique is.

Overview

The key of DF key exchange is exploiting commutative property of power operation. That is:

(x ^ a) ^ b = (x ^ b) ^ a

We will see how this is working in a moment.

Diffie-Hellman algorithm consists of several steps:

• Decide on common value. We need g as base value and p for power factor and modulus.
• Each party generate their respective private key (pk).
• Each party also generate public key (pb) and send them to each other.
• From p, pk and pb a new secret key (s) is created. This key is identical for both party.

Here's the full code. We'll break it down step-by-step.

import random


def new_pair(p, g):
    pk = private_key(p)
    pb = public_key(pk, p, g)
    return pk, pb


def private_key(p):
    k = 0
    while k <= 1:
        g = random.randint(2, 50000)
        k = (g ** p) % p
    return k


def public_key(pk, p, g):
    return (g ** pk) % p


def secret_key(pk, pb_r, p):
    return (pb_r ** pk) % p


def my_test():
    g = 2
    p = 19
    pk1, pb1 = new_pair(p, g)
    pk2, pb2 = new_pair(p, g)
    print("keypair 1:", pk1, pb1)
    print("keypair 2:", pk2, pb2)
    s1 = secret_key(pk1, pb2, p)
    s2 = secret_key(pk2, pb1, p)
    print("s", s1, s2)

Alright.. Let's get started:

Step 1: Decide on common key

In the first step, both party need to decide on common key. Normally this key is a very large prime number. But in this article a small prime number is sufficient.
We create a helper class to hold our test value.

class DFTest:
    def __init__(self, g, p, pk1, pk2, pb1, pb2, s):
        # Generator
        self.g = g
        # common pb_ry, modulus
        self.p = p
        # private keys
        self.pk1 = pk1
        self.pk2 = pk2
        # public keys
        self.pb1 = pb1
        self.pb2 = pb2
        # Secret key
        self.s = s

Evaluate above code and then we create our test variable:

>>> tc = DFTest(5, 23, 6, 15, 8, 19, 2)
>>>

Step 2: Generate private key

This private key is only known and kept by one of the party. We will use this key later to generate the final secret key.

def private_key(p):
    k = 0
    while k <= 1:
        g = random.randint(2, 50000)
        k = (g ** p) % p
    return k

OK, what happened here? Well, we take a random value g, power it by factor of p and calculate it 's modulus by p. The g value is randomly generated to make it harder for attacker to predict.
We also do not want value 0 or 1 because you want some value that can be multiplied into larger ones.

Let's test in the console:

>>> private_key(tc.p)
15
>>> private_key(tc.p)
6
>>> private_key(tc.p)
8
>>> 

Private key value is changing everytime it's called to make life harder for attacker.

Step 3: Generate public key

We will now generate public key which will be send to other party.

def public_key(pk, p, g):
    return (g ** pk) % p

Let's test this in the console

>>> public_key(tc.pk1, tc.p, tc.g)
8
>>> 

Step 4: Generate secret key

We now already have all the required keys to generate the final key, the secret key.

def secret_key(pk, pb_r, p):
    return (pb_r ** pk) % p

And test this:

>>> s1 = secret_key(tc.pk1, tc.pb2, tc.p)
>>> s2=secret_key(tc.pk2, tc.pb1, tc.p)
>>> print(s1,s2)
2 2
>>> 

Putting it all together

Combining all of the above together, let's run my_test() several times:

>>> my_test()
keypair 1: 17 10
keypair 2: 3 8
s 12 12
>>> my_test()
keypair 1: 17 10
keypair 2: 8 9
s 17 17

As you can see, even with constant value of g and p, we get different private key and public key and identical secret key. This way, although some of the keys are in public area, the secret key is very well hidden.
But how is this possible? If we look closer and remove the modulus operator for a moment, we arrive at:

(g ^ pk1) ^ pb2 = (g ^ pk2) ^ pb1

And the modulus part has role to make things harder to guess. If we have:

x % 7 = 1

We have a almost infinite amount of possibilities for x.

Summary

The beauty of DF key exchange is that it is able to generate secure secret key by exploiting simple mathematical concept. With DF, we can securely exchange keys and solve our initial problem.