Diffie Hellman (DH) Key Exchange¶

Figure 1: 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:

$$ A = g^{a}\;mod\;p $$ $$ B = g^{b}\;mod\;p $$

$$ A^b\;mod\;p = g^{ab}\;mod\;p = g^{ba}\;mod\;p = B^a\;mod\;p $$

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¶

1. 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
2. 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.
3. 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)
4. The second party (Bob) takes the received number $B$ and calculates $B^a\;mod\;p$
5. The first party (Alice) takes the received number $A$ and calculates $A^b\;mod\;p$

Both parties will get the same result.

$$ (g^a\;mod\;p)^b\;mod\;p = g^{ab}\;mod\;p $$ $$ (g^b\;mod\;p)^a\;mod\;p = g^{ba}\;mod\;p $$

Imports¶

In [23]:

import random

import random

Algorithm¶

In [24]:

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

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¶

In [25]:

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