A simple guide to Diffie-Hellman Key Exchange including the what, the how and the why

Question

I'm tired of going online looking for a simple explanation of how the Diffie-Hellman Key Exchange works. Many guides I've found attempt to explain it using anything from "paint" to massive holes in the explanation such as "g is usually 2" which infuriates me. If you can't explain it simply, you don't understand it well enough. I get that encryption is not often a simple subject but come on now; Paint? Are you kidding me?

Below is a guide I have created which attempts to explain the what, the how and the why. I really don't believe you need to be a mathematician to understand all that is required.

All I need to know is if I got it correctly with your feedback.

For example:

Why is g = 2 in RFC 3526?

• Answer: Because having a generator that produces a distinct group ensures that the shared secret space is as large as possible, maximizing the pool of shared secrets to choose from.
• Not Answer: Because it is usually 2.

The Guide

The Safe Prime (p = 11)

A safe prime is used as the modulus for modular arithmetic in the Diffie-Hellman Key Exchange.
It is a prime number of the form 2·p+1, where p is also a prime. Safe primes ensure a subgroup of a prime order, enhancing the security of the exchange.

The Finite Field & Euler's Totient Function

Euler's totient function, denoted as ϕ(n), counts the positive integers up to n that are relatively prime to n. For a safe prime number p, ϕ(p) = p−1, as all integers from 1 to p−1 are relatively prime to p.

The Primitive Root (Generator, g = 2)

A primitive root modulo p is an integer g such that every number coprime to p is congruent to a power of g modulo p. Using g = 2 as a generator produces a distinct group (where each member of the group can be generated by raising the generator to an exponent modulo p) ensuring that the shared secret space is as large as possible, thus maximizing security.

2 ^ 1   mod 11 = 2
2 ^ 2   mod 11 = 4
2 ^ 3   mod 11 = 8
2 ^ 4   mod 11 = 5
2 ^ 5   mod 11 = 10
2 ^ 6   mod 11 = 9
2 ^ 7   mod 11 = 7
2 ^ 8   mod 11 = 3
2 ^ 9   mod 11 = 6
2 ^ 10  mod 11 = 1

The Diffie-Hellman Key Exchange

1. Alice and Bob publicly agree to use a modulus p = 11 & base g = 2

2. Alice chooses private integer a = 5

3. Alice derives public integer A = g^a mod p then sends it to Bob

4. Bob chooses private integer b = 7

5. Bob derives public integer B = g^b mod p then sends it to Alice

6. Alice computes the shared secret sA = B^a mod p

7. Bob computes the shared secret sB = A^b mod p

8. Alice and Bob now share a secret (the number 10)

Answer 1

One of the most important requirement is missing: for security, $p$ must be large, in the thousands bits. That's a necessary (not sufficient) condition for the Discrete Logarithm Problem modulo $p$ to be hard. Current wisdom is to use a 2560-bit prime, give or take 512, for 128-bit security. $p=11$ used as example has is only 4-bit!

Safe primes are not necessary to get a subgroup of prime order. They allow the largest possible subgroup of prime order. And while it's required for security to have a subgroup of large prime order, having the largest possible is not a requirement for security: a subgroup of 256-bit prime order $q$ allows 128-bit security, thus is ample when $p$ is 2048-bit and $g$ of order multiple of $q$.

For these reasons, it's not necessary for security of Diffie-Hellman modulo $p$ to have $p$ a safe prime. Some Schnorr groups are fine, too. One advantage of having $p$ a safe prime in Diffie-Hellman modulo $p$ is that it's a sufficient condition to insure that no precaution is required against the small subgroup attack.

$\varphi(p)=p-1$ is valid for any prime (not just safe primes), because the reason stated (all integers from $1$ to $p−1$ are relatively prime to $p$) applies for any prime.

Using $g=2$ and a safe prime $p$ does not insure $g$ is a generator. One counterexample is $p=23$, where the subgroup generated by $g=2$ has order $q=11$. For some safe primes $p$ (about half), $g=2$ is of prime order $q=(p-1)/2$, and for the others $g=2$ is a generator.