Back to Home

Diffie-Hellman Key Exchange Game

Instructions
  1. Pick a PRIVATE key k that is 1 ≤ k ≤ 11
  2. Calculate P. This is your PUBLIC key. Anyone can see this.
  3. Calculate s, which is the shared key between you and your partner.
  4. You have successfully shared a key. Now you can encrpyt messages without a 3rd party knowing and without actually sharing s.

Variables

(Private Key)

k = ?

(Public Key)

P = ?

(Shared Secret Key)

s = ?

1-2. Generate a public key

P = 6k (mod 13) = ?

k =

3. Generate a shared secret key

s = Pk (mod 13) = ?

(partner's) P =

Plaintext

4. Shift Cipher

Ciphertext

s = 0

Some Mathmetical Principles

Discrete Logarithm Problem

The key principle behind the DHKE is DLP. It is a function that is easy to go one way, but very hard to go the other. You could think of it like trying to determine how much coffee and milk you have in a cup. Before mixing, you can easily measure the ingredients, but after mixing, it is hard to measure the ingredients.

Given,
g - generator
p - prime

Given x, it is easy to compute gx mod p
but difficult to find x given g and p

The reason behind using a generator and a prime, is that for any given input of x, from 1 to p - 1, a generator will produce all values from 1 to p - 1.

An example is the prime 5 and generator 2.
p = 5, g = 2

gx mod p
21 mod 5 2
22 mod 5 4
23 mod 5 3
24 mod 5 1

As we have seen, it generates 2, 4, 3, 1, which are all the values from 1 to p - 1.

This means that the possible x's are equally distributed and to brute force would be O(p). Though this may seem linear, note that the complexity grows with the input size of n bits. So p = 2n, leading to an exponential complexity, O(2n).

Diffie-Hellman Key Exchange

Secret

k - Private key
s - Secret Shared Key

Public

P - Public key
g - generator
p - prime

Each key is denoted as belonging to Alice or Bob in this example. Such as kA or kB

Protocol

  1. Alice and Bob must decide on a prime p and a generator g.
  2. Alice must pick some private key 1 ≤ kA ≤ p - 2.
  3. Next, Bob must pick some private key 1 ≤ kB ≤ p - 2.
  4. Alice then computes her public key. PA = gkA mod p.
  5. Alice then computes her public key. PB = gkB mod p.
  6. Now Alice and Bob publicize their keys.
  7. Alice takes Bob's public key and computes the secret shared key. s = (PB)kA mod p.
  8. Bob takes Alice's public key and computes the secret shared key. s = (PA)kB mod p.
  9. Now it may seem that Alice and Bob have different keys, but they are the same s. By substituting PA and PB, we see the following formulas.
  10. Alice computed (gkB)kA mod p.
  11. Bob computed (gkA)kB mod p.
  12. We see, (gkB)kA = (gkA)kB = gkAkB
  13. And if a hacker were to try and use the public keys, they may do PA × PB = gkA × gkB = gkA+kB

An Example

  1. Alice and Bob agree on g = 2 and p = 5
  2. Alice picks k = 2, and computes P = 22 mod 5 = 4.
  3. Bob picks k = 3, and computes P = 23 mod 5 = 3.
  4. Alice computes s = 32 mod 5 = 9 mod 5 = 4.
  5. Bob computes s = 43 mod 5 = 54 mod 5 = 4.
  6. s = 4