Diffie Hellman Example with Python
Introduction
Diffie Hellman key exchange is a method of constructing a shared secret between two parties. A shared secret is something that can be used as a key to conduct symmetric encryption, such as AES. The Diffie Hellman key exchange depends on the difficulty of the discrete log problem, which is generally believed to be hard in this current day and age. Understanding this usually requires some understanding of mathematical groups.
Discrete Log Problem
This discrete log problem is the issue of finding the exponent needed to raise some number \(b\) to yield some other number \(a\), within some group \(G\). For this post, we will assume the group to be the integers modulus \(p\), or \(\mathbb{Z}_p\), and the group operation to be multiplication modulo \(p\). \(p\) should be a prime number to ensure the generator \(g\) cycles over the entire domain of \(\mathbb{Z}_p\).
This is finding \(k\) in the following equation, \(a=b^k\), where \(a\) and \(b\) are given, and \(\mod p\) is implied.
Diffie Hellman Key Exchange
Let there be a public generator \(g=2\) of some group \(G=\mathbb{Z}_{41}\), with associated \(p=41\).
>>> g = 2
>>> p = 41
>>> a = 6
>>> pow(g,a,p)
23Alice generates some secret value \(a=6\), computes \(g^a=23\), and sends this to Bob. Notice because the discrete log problem is hard (\(a\) and \(p\) are sufficiently large to prevent a brute force attack), some eavesdropper is unable to find \(a\) given \(g^a\).
>>> g = 2
>>> p = 41
>>> b = 5
>>> pow(g,a,p)
32Bob does the same for secret value \(b=5\), sending \(g^b=32\) to Alice. Notice an eavesdropper cannot compute \(b\) from the public value \(g^b\).
Alice and Bob can then generate shared secret \(g^{ab}\).
# Alice computing g^(ab)
>>> g_b = 32
>>> a = 6
>>> pow(g_b, a, p)
40# Bob computing g^(ab)
>>> g_a = 23
>>> b = 5
>>> pow(g_a, b, p)
40\(g^{ab}=40\), which is now a shared secret. This shared secret could be used as a key, or as a seed for a pseudo random number generator to generate many keys for transmitting data with a stream cipher.