Diffie-Hellman Key Exchange Explained with Toy Numbers

What is Diffie-Hellman Key Exchange

An asymmetric key-agreement method that lets two parties derive the same shared secret key without ever sending that key over the wire.

The math behind Diffie-Hellman

Alice and Bob both have the following rule to start with:

0 < g < p

g must be less than p. p must be a prime number (divisible only by 1 or itself).

Alice begins by publicly choosing the values of g and p.

g = 7

p = 41

Bob either agrees or disagrees with the chosen two numbers. Let’s suppose he agrees. (In practice, these values are usually standardized or agreed upon ahead of time. For this example, we just assume Bob accepts them.) Now that both are in agreement with the values of g and p, Alice and Bob each choose a value for their secret numbers a and b, respectively. Let’s suppose Alice picks a = 9, and Bob picks b = 25.

Next, Alice and Bob both use the following formula. NOTE: mod is the remainder after division. For example, 4 ÷ 5 = 0 with remainder 4, so ‘4 mod 5 = 4’.

Alice:
A = ga mod p

Bob
B = gb mod p

Remember that both Alice and Bob have the same agreed-to values for g, p, as well as their respective private numbers a and b. Let’s replace the variables in the above formulas with their respective values and obtain the values of A and B.

A = 79 mod 41
Thus, A is 13.

B = 725 mod 41
Thus, B is 3.

13 and 3 are the two public values transferred over the wire:

  • Alice sends her public value A = 13 to Bob.
  • Bob sends his public value B = 3 to Alice.

This step, where Alice and Bob exchange A and B, is the key exchange.

Next, they use the exchanged public values A and B in a third formula to obtain the shared secret:

For Alice
s = Ba mod p
s = 39 mod 41
Thus, s is 3.

For Bob
s = Ab mod p
s = 1325 mod 41
Thus, s is 3.

s being the private shared key. Notice how the private shared key did not have to be transferred over the wire but was generated from within their respective system. For obvious reasons we picked small numbers, but in real-life we would use 2048 bits for the prime number (p), roughly the same for the shared secret s, and for the private exponents (a, b) we would typically use around 224-256 bits (roughly 70-80 decimal digits.)

Written by RON1N01