Diffie Hellman (DH) Key Exchange
Contents
Diffie Hellman (DH) Key Exchange¶
Fig. 30 Diffie Hellman Key Exchange Example¶
Diffie-Hellman Key Exchange (DH) is a very widely used method to exchange cryptographic keys. The private keys are not actually exchanged, they are jointly derived. They were invented and published by Whitfield Diffie and Martin Hellman in 1976.
In an encrypted communication channel an symmetric key is used, this means both parties need the same encryption key for either encrypting or decrypting the messages. DH allows to infer this key without the public exchange of it.
The algorithm is based on Elliptic Curve Cryptography, a method of doing public-key cryptography based on algebra structure of elliptic curves over finite fields.
It is based on the principle that:
The resulting key for the Diffie Hellman Key Exchange can be then used to any data encryption such as AES, Blowfish etc.
Terminology¶
private key - \(a\) and \(b\) secret integer specific for each end between 1 and the prime number \(p\). Also called secret.
public key - \(A\) and \(B\) generated key derived from the private key to be shared
\(g\) or \(b\) - called generator or base. It is a primitive root modulo or a small prime number.
\(p\) - big prime number often between 2048 and 4096 bits long
Algorithm¶
The first party (Alice) picks two numbers, \(g\) a primitive root modulo and \(p\) a big prime number and tells them to the second party
The second party (Bob) picks a secret number \(a\), and then it computes \(A = g^a\;mod\;p\) and sends the result \(A\) back to the first party. The secret number \(a\) has not been sent only the calculation result.
Then the first party (Alice) does the same, it selects a secret number \(b\) and calculates \(B = g^b\;mod\;p\) and sends \(B\) to the second party (Bob)
The second party (Bob) takes the received number \(B\) and calculates \(B^a\;mod\;p\)
The first party (Alice) takes the received number \(A\) and calculates \(A^b\;mod\;p\)
Both parties will get the same result.
Imports¶
import random
Algorithm¶
class Person:
def __init__(self, seed: int = 1234, name: str = "", left: bool = True, verbose: bool = True):
"""Representing a end of the kexy exchange transmission
Args:
seed (int, optional): seed for initialising the random number generators. Defaults to 1234.
name (string, optional): name of the person. Defaults to "".
left (bool, optional): bool indicating if its the left or right party (only used for prints). Defaults to True.
verbose (bool, optional): being verbose or not. Defaults to True.
"""
self._name = name
self._seed = seed
self._rand_gen = random.Random()
self._rand_gen.seed(self._seed)
self._left = left
self._verbose = verbose
if self._left:
self._prefix = ""
else:
self._prefix = " "*40
if self._verbose:
print("{}{} is alive".format(self._prefix, self._name))
def genPrimeNumber(self, x: int, y: int):
"""generates a random prime number between the range x and y, very inefficient method
Args:
x (int): lower range bound
y (int): higher range bound
Returns:
int: random prime number
"""
# generates list of prime numbers
_prime_list = []
for n in range(x, y):
_isPrime = True
for num in range(2, n):
if n % num == 0:
_isPrime = False
if _isPrime:
_prime_list.append(n)
# select a prime number
return self._rand_gen.choice(_prime_list)
def genSecretKey(self):
"""generates a random private key between 1 and prime $p$. Representing self._name[0].lower()"""
self._secret_key = self._rand_gen.randint(1,self.p)
if self._verbose:
print("{}{} generated his secret key {}: {}".format(self._prefix, self._name, self._name[0].lower(), self._secret_key))
def genPublicKey(self):
"""generates the public variables (key) to be shared. Representing self._name[0].upper()
Returns:
int: shared publiuc key self._name.lower()
"""
self.public_key = (self.g**self._secret_key) % self.p
if self._verbose:
print("{}{} generated his public key {}: {}".format(self._prefix, self._name, self._name[0].upper(), self.public_key))
return self.public_key
def getPublicKey(self, public_key: int):
"""get the other party public key
Args:
public_key (int): pubic key from partner
"""
self.other_public_key = public_key
def genGenerator(self):
"""generates the public base $b$ or generator number $g$
Returns:
int: shared number $g$
"""
self.g = self.genPrimeNumber(1,50)
if self._verbose:
print("{}{} generated shared base g: {}".format(self._prefix, self._name, self.g))
return self.g
def setGenerator(self, g: int):
"""sets the base $b$ or generator $g$ number, if the other party has generated it
Args:
g (int): shared generator number
Returns:
int: shared number $g$
"""
self.g = g
return self.g
def genPrime(self):
"""generates a public prime number. This is way too small for reality, commonly 4096 bits
Returns:
int: shared prime number $p$
"""
self.p = self.genPrimeNumber(100, 1000)
if self._verbose:
print("{}{} generated shared prime p: {}".format(self._prefix, self._name, self.p))
return self.p
def setPrime(self, p: int):
"""sets the prime number $p$, if the other party has generated it
Args:
p (int): shared prime number $p$
Returns:
int: shared prime number $p$
"""
self.p = p
return self.p
def genSharedSecret(self):
"""generates the common shared secret key
Returns:
int: shared secret key
"""
self._shared_secret = (self.other_public_key ** self._secret_key) % self.p
if self._verbose:
print("{}{} generated shared secret: {}".format(self._prefix, self._name, self._shared_secret))
Test¶
alice = Person(1234, "Alice", True)
bob = Person(4321, "Bob", False)
# generate variables g and p
g = alice.genGenerator()
p = alice.genPrime()
# share variables g and p
bob.setGenerator(g)
bob.setPrime(p)
# create secrets keys
alice.genSecretKey()
bob.genSecretKey()
# create public keys
alice_pubkey = alice.genPublicKey()
bob_pubkey = bob.genPublicKey()
# Exchange keys
alice.getPublicKey(bob_pubkey)
bob.getPublicKey(alice_pubkey)
# Calculate shared secret which should be both times the same
alice.genSharedSecret()
bob.genSharedSecret()
Alice is alive
Bob is alive
Alice generated shared base g: 43
Alice generated shared prime p: 257
Alice generated his secret key a: 4
Bob generated his secret key b: 131
Alice generated his public key A: 187
Bob generated his public key B: 163
Alice generated shared secret: 95
Bob generated shared secret: 95