This article is a part of a series on Cryptography. Use the navigation boxes to view the rest of the articles.
How can two people in a crowded room derive a secret that only the pair know, without revealing the secret to anyone else that might be listening?
That is exactly the scenario the Diffie-Hellman Key Exchange exists to solve.
The Diffie-Hellman Key Exchange is a means for two parties to jointly establish a shared secret over an unsecure channel, without having any prior knowledge of each other.
They never actually exchange the secret, just some values that both combine which let them attain the same resulting value.
Conceptually, the best way to visualize the Diffie-Hellman Key Exchange is with the ubiquitous paint color mixing demonstration. It is worth quickly reviewing it if you are unfamiliar with it.
However, in this article we want to go a step further and actually show you the math in the Diffie-Hellman Key Exchange.
DH Math
Before you get into the math of Diffie-Hellman, you will want to have a basic understanding of what a Prime number is, and what the Modulus operation is (aka, remainder division). Both of these terms have been defined in another article.
Below is an infographic outlining all the steps of the Diffie-Hellman exchange between Alice and Bob.
Notice how both Alice and Bob were able to attain the same Shared Secret of 3. Anyone listening in on their DH Key exchange would only know the Public Values, and the starting P and G values. There is no consistent way to combine those numbers (13, 6, 2, 9) to attain 3.
If you’d like to try it yourself, here are some combinations of Prime numbers and Generators you can use:
| Prime | Generator |
| 227 | 17 |
| 347 | 19 |
| 991 | 22 |
DH Numbers
In our example, we used a Prime number of 13. Since this Prime number is also is used as the Modulus for each calculation, the entire key space for the resulting Shared Secret can only ever be 0-12. The bigger this number, the more difficult a time an attacker will have in brute forcing your shared secret.
Obviously, we were using very small numbers above to help keep the math relatively simple. True DH exchanges are doing math on numbers which are vastly larger:
| DH Group 1 | 768 bits |
| DH Group 2 | 1024 bits |
| DH Group 5 | 1536 bits |
| DH Group 14 | 2048 bits |
| DH Group 15 | 3072 bits |
| DH Group 16 | 4096 bits |
| DH Group 17 | 6144 bits |
| DH Group 18 | 8192 bits |
The number of bits is a reference to the size of the Prime number. This directly equates to the entire key space of the resulting Shared Secret. To give you an idea of just how large this key space is:
In order to fully write out a 768 bit number, you would need 232 decimal digits.
In order to fully write out a 1024 bit number, you would need 309 decimal digits.
In order to fully write out a 1536 bit number, you would need 463 decimal digits.
In order to fully write out a 2048 bit number, you would need 617 decimal digits.
The wild thing is every DH group below 2048 bit is considered no longer secure by today’s standards. It is recommended to only use DH Group 14 and above. Or, move on to Elliptic Curve Diffie-Hellman, but that will be a subject for another article.
The concept of a group in the DH Groups above is in reference to the starting values. Notice in the illustration above, Alice and Bob start with a Prime number and a Generator (13 and 6). These starting values are pre-selected in various Diffie-Hellman RFCs. RFC 2409 define DH Groups 1 and 2, and RFC 3526 define DH groups 5, 14, 15, 16, 17, and 18.
Using the Shared Secret
Once the Shared Secret has been attained, it typically becomes used in the calculation to establish a joint Symmetric Encryption key and/or a joint HMAC Key – also known as Session Keys.
But it is important to point out that the Shared Secret itself should not directly be used as the Secret Key. If it were, all you can be assured of is that throughout the secure conversation you are still speaking to the same party that was on the other side of the Diffie-Hellman exchange.
However, you still have no confirmation or assurance as to who the other party is. Just that no one else can all of a sudden pretend to be them in the middle of your secure conversation.
The generation of the actual Session Keys should include the DH Shared Secret, along with some other value that would only be known to the intended other party, like something from the Authentication scheme you chose.
Prefer video content to text? The majority of this article has been recorded and can be viewed on Youtube:
Great series on Cryptography! I found you guys via the ARP video on youTube which was very good too. I hope you guys will add other topics soon. Looking forward to it!
Glad you enjoyed the videos and the article series, Roger. The Network Address Translation articles are releasing this week! Sign up to get an e-mail when it comes out.
Ed- In the Alice / Bob example, I randomly selected a different private key to do the math as an exercise. I ran into a strange combination with these numbers-
I freakishly random selected Alice private key as 8 and Bob’s private key as 3. When I calculate the public keys, it turns out that Alice gets a public key of 3 and Bob has a public key of 8.
Alice Public key = 6^8 mod 13 = 3
Bob Public key = 6^3 mod 12 = 8
Scratching my head what’s so strange about these numbers, to reveal the private keys. Hope I did that math right.
Any thoughts are appreciated. Again, great series. Thanks much.
– m
Hi M,
Yea, I’m getting the same 3/8 8/3 oddity there.
All I can say is you run into these strange occurrences when you’re using small numbers. When you’re doing MOD P with a P of 13, it means there are only 13 possible values that can be the result. So you’re bound to run into a bunch of overlaps.
With “big number” DH, there are also certain combinations that are known to be not secure, and most implementations of DH explicitly/manually account for avoiding those combinations. That is part of why it’s dangerous to try to “roll your own Crypto” — I could create a simple bash script or excel spreadsheet to do the math above, but I’ll likely miss out on industry best practices in regards to DH.
Glad you enjoyed the series =)
Generator (G) = 6
Prime (P) = 13
###
Alice Private = 8
Bob Private = 3
###
Calculate public key (G^Private mod P)
Alice = 6ˆ8 mod 13 = 3
Bob = 6ˆ3 mod 13 = 8
Alice will send to Bob = 3
Bob will send to Alice = 8
###
Calculate Shared Secret (received^Private mod P)
Alice = 8ˆ8 mod 13 = 1
Bob = 3ˆ3 mod 13 = 1
The Shared Secret is 1.
Oh I love/hate you. These will be the Alice and Bob I think of eon every crypto example from now until I die.
Thanks for that.
Sorry… not sorry =). 😉
Huge Thanks.
I don’t get only one thing.
How does it come that Bob and Alice agreed on the same Prime and Generator if they did not even exchange any information between each other based on your photo?
The above is the exchange required for only the DH calculation itself, not necessarily the control/administrative communication where they decide to do Diffie-Hellman to begin with.
In that communication, the peers agree on a specific Diffie-Hellman “group”, which each have pre-determined Prime and Generator values.
For instance, in IPsec/ISAKMP, the peers agree on a Diffie-Hellman group (2, 5, 14, etc..). Each of those are defined with a specific Prime / Generator in mind. This article defines the Prime & Generators for DH groups 1, 2, 3, and 4:
https://www.rfc-editor.org/rfc/rfc2409#section-6
(note, not all are considered secure by today’s age)