The Diffie-Hellman (DH) key agreement is a way for participants to arrive at the same key without a 3rd party that monitors the connection being able to do so too. Normally this is done between two parties, but the algorithm supports any number of participants.
DH works on two principles of mathematics.
First, abc = d
is the same as ab*c = d,
and the operands of a multimplication can be swapped: b*c = c*b.
and second, that it's really difficult to guess b
and c if you take d modulo some large number.
DH uses modular arithmetic. Modulo means division with remainder.
12 mod 7 means to divide 12 by 7 and to keep the remainder,
in this case 5.
This guide will use "mod" throughout to signify the modulo operation.
Note: In the computation x mod y,
it does not matters how often you can divide x by y,
only the remainder of the division is important.
The actual result of the division is discarded.
Most calculators lack a modulo operation but you can simulate it.
Let's assume you want to calculate 1234 mod 7.
You calculate 1234/7 which will result in
176.285714... (the 6 decimals repeat indefinitely).
From that result, subtract the part in front of the decimal point,
in this case 176. This leaves you with 0.285714....
Multiply this with 7 again,
and you get 1.99999...5 or similar result.
The remainder will be the closest integer, in this case 2.
And the number you subtracted from the result earlier is how often you can divide.
So 1234/7 = 176 remainder 2.
Note: How close the calculated number is to an integer
depends on how accurate your calculator is.
Good calculators store a few more digits than they display
to hide rounding errors,
very good calculators remember the calculation itself instead of the result
for maximum accuracy.
For DH we need a generator g and modulus m.
m must be a safe prime and is preferrably very large.
A safe prime is any number p
where (p-1)/2 is also a prime.
A prime number is an integer that can only be divided without remainder by itself and 1.
Finding this type of prime number can take quite a long time,
so precomputed primes are used for the DH key exchange.
The generator g should be a primitive root of m.
g is a primitive root if gx mod m = y
will yield all numbers from 1 to m-1. Example:
g = 3 is a primitive root of 7 because feeding 1 to 6 into the formula
will yield 1 to 6 as output exactly once:
31 mod 7 = 3 mod 7 = 3
32 mod 7 = 9 mod 7 = 2
33 mod 7 = 27 mod 7 = 6
34 mod 7 = 81 mod 7 = 4
35 mod 7 = 243 mod 7 = 5
36 mod 7 = 729 mod 7 = 1
Finding a primitive root is easy
if we choose a prime p so that it is a safe prime
in the form of p = 2*q+1 (q is also prime).
To check if a number x is a primitive root of p,
we check if
x mod p ≠ 1, and
x2 mod p ≠ 1, and
xq mod p ≠ 1.
If so, then x is a primitive root of p.
For safe primes, about 50% of all numbers between them and 1
are primitive roots, so it's quite easy to find some
We want to ensure that z = gx mod m can
possibly give us all numbers from 1 to m-1 for z.
If some results are impossible to achieve,
an attacker would not have to check this number at all
when trying to break the algorithm.
And if some numbers are more likely to appear than others,
an attacker would check them first.
g and m can be precomuted and publicly known.
They can also safely be reused.
You do not compute them yourself
because it takes a lot of time to find a prime number
that has hundreds of digits.
Commonly known safe DH primes of various sizes exist.
Any other number involved in the algorithm should be randomly chosen every time the algorithm is used.
In a DH key agreement, the public DH prime is usually dictated by the person that is authenticated to avoid it being swapped by someone monitoring the connection.
Alice and Bob want to agree on a secret number. They're sitting in the same room but between them is a soundproof glass wall. To exchange messages, they can write numbers on slips of paper and give them to Eve, who walks between the two participants. Because the wall is made of glass they can see Eve at any time and would know if she tried to swap the paper slips, however they cannot stop her from looking at the slips and remembering numbers. To simplify this for the reader, we use a key (🔑) for secret information that Eve doesn't knows, and an open lock (🔓) for information that Eve knows.
Alice and Bob first agree to use 23 as the modulus m 🔓
and 5 as the generator g 🔓.
Next, Alice and Bob each pick a secret number they keep for themselves.
The number has to be between 1 and m.
Alice picks 4 as a 🔑
and Bob picks 3 as b 🔑
Alice now computes A = ga mod m = 54 mod 23 = 4
and Bob B = gb mod m = 53 mod 23 = 10.
The fact that A = a = 4 for Alice is purely coincidental
and is almost impossible to happen in a real world scenario where big numbers are used.
They both exchange A 🔓 and B 🔓
Note that at this point, Eve could guess a and b
simply by trying all numbers 1 to 22.
This is the reason why for real cryptography,
massive numbers are used.
The people know these numbers after the key exchange:
| Person | Known values |
|---|---|
| Alice | g 🔓, m 🔓, A 🔓, B 🔓, a 🔑 |
| Bob | g 🔓, m 🔓, A 🔓, B 🔓, b 🔑 |
| Eve | g 🔓, m 🔓, A 🔓, B 🔓 |
Alice now computes Ba mod m = 104 mod 23 = 18 🔑,
and Bob computes Ab mod m = 43 mod 23 = 18 🔑
Both parties arrived at 18 🔑 as their shared secret value.
This works because (wx mod y)z mod y
is the same as wxz mod y,
and wxz is the same as wzx
or wx*z
Alice shared A = ga mod m with Bob,
and Bob completes this by doing Ab mod m = gab mod m = ga*b mod m
Bob shared B = gb with Alice,
and Alice completes this by doing Ba mod m = gba mod m = ga*b mod m
When used with large enough values, the resulting secret number can be used as a key for a symmetric cipher.
Calculating be mod m when e
has hundreds of digits is not feasible
and you would run out of memory very quickly.
Because we're not just doing powers,
but also modulo,
we can apply the modulo operation after each multiplication
and keep the number small.
Doing trillions and trillions of multiplications to compute big powers
can also be done quicker.
To do this, the exponent is converted into base 2 (a stream of ones and zeroes).
Then from the right hand side, multiply the base whenever the exponent has a 1.
The instructions for humans are as shown below.
Note: := means to set the variable on the left
to the result of the computation on the right.
Example: x := x2 means to square x
and setting it to the new value. If x is 4, it will be 16 after this.
be mod mb > m then calculate b := b mod me = 0 then stop processing. Final result is in rd (a 1 or 0) from ed = 1 then calculate r := r*b mod mb := b2 mod mThe source code for the DH key exchange including the powmod function above can be found in dh.js
Precomputed safe primes with their respective generator can be found in dh-const.js
Tools to check if a number is prime and finding primitive roots can be found in prime-tools.js
Below are various tools to perform a DH key exchange
Check if the supplied number is prime. Numbers below 10 million are checked in an exhaustive manner, giving a guaranteed response. Odd numbers above that are checked using the Miller–Rabin primality test (Even numbers except 2 cannot be prime). This test will never say that a number is not prime when in reality it is, but it might in rare circumstances say it is a prime when it isn't. The chance for this is very slim, and the test is performed multiple times to decrease the odds of a false positive even further.
Click the button below to find the primitive root (or generator) for the DH number in the text box above. Make sure the number is a safe prime before trying to find a generator. Note that the precomputed numbers you can select always have 2 as a generator.
Provided the given generator and modulus, you can perform a DH key exchange. This tool allows for experimentation and thus will not stop you from using wrong or unsafe values. You can test prime numbers and find generators with the tool above.