Can someone explain what the Diffie-Hellman Key Exchange algorithm in plain English? I have read that Twitter has implemented this technology which allows two parties to exchange encrypted messages on top of a non-secured channel. How does that work?
21Wikipedia has a pictorial explanation.– Ramchandra ApteNov 24, 2013 at 15:17
9YouTube has a (nice and easy) video explaination :)– TheRookierLearnerNov 26, 2013 at 4:35
3I found this video useful in understanding - youtube.com/watch?v=YEBfamv-_do– Rowana RavenclawNov 7, 2016 at 2:39
My favourite DH video: youtube.com/watch?v=NmM9HA2MQGI– AdambeanJan 4, 2018 at 13:17
I find the color analogy flawed (wikipedia and youtube). Mixing the "private" color with the other party's color does not render the same, secret, color. I actually did the mixing.– PålOliverJan 22, 2019 at 11:48
Diffie-Hellman is a way of generating a shared secret between two people in such a way that the secret can't be seen by observing the communication. That's an important distinction: You're not sharing information during the key exchange, you're creating a key together.
This is particularly useful because you can use this technique to create an encryption key with someone, and then start encrypting your traffic with that key. And even if the traffic is recorded and later analyzed, there's absolutely no way to figure out what the key was, even though the exchanges that created it may have been visible. This is where perfect forward secrecy comes from. Nobody analyzing the traffic at a later date can break in because the key was never saved, never transmitted, and never made visible anywhere.
The way it works is reasonably simple. A lot of the math is the same as you see in public key crypto in that a trapdoor function is used. And while the discrete logarithm problem is traditionally used (the xy mod p business), the general process can be modified to use elliptic curve cryptography as well.
But even though it uses the same underlying principles as public key cryptography, this is not asymmetric cryptography because nothing is ever encrypted or decrypted during the exchange. It is, however, an essential building-block, and was in fact the base upon which asymmetric crypto was later built.
The basic idea works like this:
I come up with a prime number p and a number g which is coprime to p-1 and tell these numbers to you. (FYI: p for "Prime", g for "Generator")
You then pick a secret number (a), but you don't tell anyone. Instead you compute ga mod p and send that result back to me. (We'll call that "A" since it came from a).
I do the same thing, but we'll call my secret number b and the computed number B. So I compute gb mod p and send you the result (called "B").
Now, you take the number I sent you and do the exact same operation with it. So that's: Ba mod p .
I do the same operation with the result you sent me, so: Ab mod p .
The "magic" here is that the answer I get at step 5 is the same number you got at step 4. Now it's not really magic, it's just math, and it comes down to a fancy property of modulo exponents. Specifically:
(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p
Which, if you examine closer, means that you'll get the same answer no matter which order you do the exponentiation in. So I do it in one order, and you do it in the other. I never know what secret number you used to get to the result and you never know what number I used, but we still arrive at the same result.
That result, that number we both stumbled upon in step 4 and 5, is our shared secret key. We can use that as our password for AES or Blowfish, or any other algorithm that uses shared secrets. And we can be certain that nobody else, nobody but us, knows the key that we created together.
FYI: DH Parameters
The numbers from step 1 (p and g) are the "Diffie-Hellman Parameters." You usually compute these well ahead of time since it takes a while. These aren't secret, so they tend to be reused. For a long time many servers all just used the same values for p and g, and not particularly good ones, leading to a bit of a kerfuffle (which got named Logjam) that might be fun to read about if you're interested.
13DH is public key/asymmetric crypto but not encryption. Nov 24, 2013 at 12:15
23I think it's worth mentioning that the reason this is secure is that, unlike normal log(x), the modular log(x) is thought to be hard to compute. Otherwise we could just do
b. Nov 24, 2013 at 19:25
14I think you might also want to add that
gis not just any prime but a generator (or a primitive root) of
pNov 26, 2013 at 4:40
29@TheRookierLearner this answer is a simplified explanation of DH; there are quite a few important details omitted for simplicity. This shouldn't be considered an implementation tutorial.– tylerlNov 26, 2013 at 5:57
3@Mero55 You're not just finding the root of A, you're finding the roots of A, A+p, A+2p, A+3p, ... until the result is an integer.– kbolinoJul 7, 2016 at 2:42
The other answers do an excellent job explaining the maths behind the key exchange. If you'd like a more pictorial representation, nothing beats the excellent paint analogy shown on the Diffie–Hellman key exchange Wikipedia entry:
Image is in the public domain
5This image is great at explaining what it does. My only problem was "If the attacker knows the common paint and he knows the end mixtures, why can't he figure out the original color?". The answer is of course that it's not the color he needs to know, but the actual original mixture, and as you mentioned, the mixture separation is expensive. The actual mathematics that allows for this would be great to know in brief detail as well. Jul 29, 2016 at 13:49
2The math has been explained elsewhere but think of it like this: let's say that the "paint mixing function" is f(a,b) = (a+b)%1000. You and me announce "the shared secret is 793". Then I tell you f(my_secret, 793) = 172. What's my secret? Note that f(a, f(b, 793)) == f(b, f(a, 793)). The actual function used by DH is not so simple but all that's important is that information is lost and this commutative property holds.– TimOct 22, 2016 at 2:51
3The color example is only illustrative. Obviously, calculating the color mixtures is trivial; the discrete log problem that DH uses is not. See en.wikipedia.org/wiki/Discrete_logarithm.– sovempMar 28, 2017 at 17:15
That is very clever and easy way to make other understand the fundamentals.– MubasharDec 17, 2018 at 5:37
And either Bob or Alice starts it off by publically sending the common paint to the other?– LightCCJan 17, 2019 at 20:44
Diffie-Hellman is an algorithm used to establish a shared secret between two parties. It is primarily used as a method of exchanging cryptography keys for use in symmetric encryption algorithms like AES.
The algorithm in itself is very simple. Let's assume that Alice wants to establish a shared secret with Bob.
- Alice and Bob agree on a prime number,
p, and a base,
g, in advance. For our example, let's assume that
- Alice chooses a secret integer
awhose value is 6 and computes
A = g^a mod p. In this example, A has the value of 8.
- Bob chooses a secret integer b whose value is 15 and computes
B = g^b mod p. In this example, B has the value of 19.
- Alice sends
Ato Bob and Bob sends
- To obtain the shared secret, Alice computes
s = B^a mod p. In this example, Alice obtains the value of
- To obtain the shared secret, Bob computes
s = A^b mod p. In this example, Bob obtains the value of
The algorithm is secure because the values of
b, which are required to derive
s are not transmitted across the wire at all.
18It's nice, but you could've also quoted that it's from Wikipedia. May 4, 2015 at 2:50
If you want a simpler plain English explanation of DH that can be readily understood by even non-technical people, there is the double locked box analogy.
Alice puts a secret in a box and locks it with a padlock that she has the only key to open. She then ships the box to Bob.
Bob receives the box, puts a second padlock that only he has the key to on it, and ships it back to Alice.
Alice removes her lock and ships the box to Bob a second time.
Bob removes his lock, opens the box, and has access to the secret that Alice sent him.
Since the box has always had at least one lock on while in transit, Eve never has the opportunity to see what's in side and and steal the secret: In this a cryptographic key that will be used for encrypting the remainder of Alice and Bob's communications.
8Now this is what I call a plain English explanation. love you man.– user15119Nov 24, 2013 at 16:31
65While plain English, this doesn't describe Diffie-Hellman. It describes the Three-pass protocol which has significantly different properties from DH. For example it requires three passes, whereas DH only requires a single pass. Nov 24, 2013 at 18:21
1I think CodesInChaos is expecting a lot of accuracy from a purposefully simplified analogy. This helped me understand the paint analogy better, which helped me understand the more accurate ones better. (Note the boxes have unlocker-holes too small to get the cookies out of the innermost box. That's what threw me at first.) Sep 27, 2016 at 22:15
17It's not a matter of "a lot of accuracy". The locked box analogy doesn't resemble Diffie Hellman at all.– TimOct 22, 2016 at 2:58
2DH does not exchange secrets as this does, it generates them, but it's a fun read– sivannAug 30, 2018 at 13:02
The key exchange problem
A secure connection requires the exchange of keys. But the keys themselves would need to be transfered on a secure connection.
There are two possible solution:
- exchange the key by physically meeting and sharing the keys.
- Somehow established a shared secret on a public unsecure channel. This is easier said than done, and the first such implementation of this is the Diffie-Hellman Scheme.
Diffie-Hellman makes use of a mathematical function with the following properties:
- It is EASY to compute
- It is HARD to invert
- It is EASY to calculate
- It is EASY to calculate
- It is HARD to calculate
How DH scheme works
- Alice comes out with a random number
A. She computes
f[A], and sends
f[A]to Bob. Alice never discloses her
A, not even to Bob.
- Bob comes out with another random number
B. He computes
f[B], and sends
f[B]to Alice. Bob never discloses his
B, not even to Alice.
- Alice computes
f[B]. Bob computes
- Mallory, who is Eavesdropping, has only
f[B], and so it is HARD for her to calculate
- Alice and Bob now share a common secret which can be used as (or to come up with) a key to establish a secure connection.
The Diffie-Hellman Scheme does not provide authentication of any kind. It only allow 2 anonymous parties to share a common secret. But for all Alice knows, she could be shaking hands with the devil (instead of Bob). This is why we need at least one party to be authenticated.
For example: SSL (https), the webserver is authenticated using PKI (Public Key Infrastructure), and then a secure connection is established (D-H) between the website and the client. Since the website has been authenticated, the client can trust the website, but the website cannot trust the client. It is now safe for the client to provide his own authentication details on the webpage.
5I really appreciate the side note here, it answered a nagging question I had but couldn't quite elucidate. Sep 27, 2016 at 22:17
Securing data as it passes through the internet usually requires protecting it in two ways:
- Confidentiality -- assuring no one except the intended recipients can read the data
- Integrity -- assuring no one can modify or tamper the data in transit
Confidentiality is provided using Symmetric Encryption and Integrity is provided using a Message Authentication Code (MAC).
Both Symmetric Encryption and MAC's require that both parties have identical and secret keys (a "key" in this sense being simply a number, converted to binary).
The problem then is How do both parties establish identical and secret keys over the Internet? (or any other insecure medium). This is known as "the key exchange problem".
One of the solutions for this problem is the Diffie-Hellman algorithm.
Diffie-Hellman allows two parties to establish a shared secret over an insecure medium. Or, to put it more simply....
Imagine you and your friend were standing in a crowded room, surrounded by dubious looking people. Assume you and your friend needed to agree upon an identical number, but do not want anyone else in the room to know what number that is. Diffie-Hellman would allow you and your friend to cleverly exchange some numbers, and from those numbers calculate another number which is identical. And even though everyone in the room heard the numbers being exchanged, they have no way to determine the final number you and your friend arrived to.
We can see an example of this occurring in the image below. Alice and Bob will use the Diffie-Hellman key exchange to establish a shared secret.
Anyone "listening in" on the conversation would only "hear" the numbers which were exchanged in the middle:
9. There is no consistent way to combine these four numbers to attain the final shared secret:
3 without knowing one of either Alice or Bob's Private values (
4) which were never shared.
That is the beauty of Diffie-Hellman.
The numbers used in the example above are small to keep the math simple. In reality, numbers used in modern Diffie-Hellman exchanges are (or ought to be) at minimum 2048 bits long -- which would require approximately 617 digits to write out!!
After finishing the Diffie-Hellman key exchange, both parties now possess an identical value, known only to each party.
This value becomes the "starting point" from which additional keys can be generated.
Earlier, we mentioned Symmetric Encryption and Message Authentication Codes each require a Secret Key. Well, take your DH Shared Secret and combine it with a few other values and now you have the Encryption and MAC keys you need.
The additional benefit is combining values to create keys is easy... It can be done as many times as necessary.
In fact, many security protocols (SSL/TLS, IPsec, etc) generate one set of keys to secure traffic in each direction -- a total of four keys (MAC + Encryption in one direction, MAC + Encryption in the other direction). All four keys generated from the same initial starting value, derived from Diffie-Hellman.
2+1 for illustrated sample! Did you draw this or did you pick them elsewhere? If so, could you post origin of this picture? Jan 29, 2020 at 10:58
1@F.Hauri I drew it =). It's originally posted on my blog: practicalnetworking.net/series/cryptography/diffie-hellman– EddieJan 29, 2020 at 23:54
1Nice job, well done! I'm interested by sources for making translation! Jan 30, 2020 at 7:40
Diffie-Hellman is a mathematical algorithm to exchange a shared secret between two parties. This shared secret can be used to encrypt messages between these two parties. Note that the Diffie-Hellman algorithm does not provide authentication between these two parties.
It lacks explanation, I wish you could explain a little bit more...– user15119Nov 24, 2013 at 2:11
11You wanted an english explanation without math. Nov 24, 2013 at 8:56
In the case of an HTTPS connection, authentication is handled by the SSL certificate framework. You can be certain (as you can be) that you are communicating with the intended parties through verification and trust. The handshake/negotiation of an SSL connection is expensive in terms of overhead. The DH algorithm allows both parties to securely negotiate a symmetric key for encryption/decryption which is much more efficient.– k1DBLITZNov 25, 2014 at 15:53
Computerphile's Diffie-Hellman videos are absolutely spectacular when it comes to explanations of this key exchange. Their video "Secret Key Exchange (Diffie-Hellman)" is quite thorough, but their explanation of the math behind DH is the best one I've come across so far in any medium (and certainly better than what I personally could write for you here). Take a watch here.
Goal of Diffie–Hellman: secretly share a number between two parties over an open channel.
First recall from school these exponentiation rules:
(2³)⁴=(2⁴)³=4096. The idea is that if Alice sends
xᵃ to Bob then neither Bob nor anyone else can calculate
a. It's easy to say what 2³ is, but given 8 it's hard to say which power 2 has to be brought to to get 8. So it boils down to:
- Alice and Bob agree on a number
xthat can be known to anyone, let's say
- Alice generates
- Bob generates number
- Alice calculates
16³=4096and Bob calculates
So both Alice & Bob know 4096, but no one else knows
b so can't calculate xᵃᵇ.
In reality calculating logarithms is not that complicated. But it becomes complicated once modular arithmetic is included.
In plain English without using any math expression like in the above answers, the
Diffie-Hellman Key Exchange is an invention by Diffie and Hellman.
The invention is about a way for two persons to agree on the same number. This common agreed upon number will then be used for whatever purposes the two persons wished. For example, after following the
DH Key Exchange steps, the end result is that both persons now arrive on the same number. None of the two persons has control over what this common number will be. The
DH Key Exchange invention only guarantees that both persons will arrive to a common number. An example usage once this common number is achieved is to forward the letters of the alphabet using this number. For example, if the common number is 5, then the letter A becomes F, the letter B becomes G and so on when sending a message. The other person receiving the message will then backward each letter of the message to read it.
person-B could not just talk loudly in order to agree on a common number because a third
person-C will hear it. If
person-C knows the agreed number, then he can read the secret message too. The
DH Key Exchange always requires that there is always a third
person-C that can listen to the messages between
person-B and this three-persons scenario is the whole purpose of the invention on how to make
person-C unable to read the secret encoded messages between
In the first steps of the
DH Key Exchange,
person-B will send some numbers back and forth and at this early phase
person-C can read these first messages. In the second phase,
person-B will be sending encrypted messages that
person-C can no longer read. Despite the fact that
person-C can hear the initial messages during the first steps,
person-C cannot arrive to the agreed number that
person-B now have.
Diffie and Hellman have been awarded the
Turing Award in 2015 for this invention.
I wrote this once as a concept of a talk that I never gave. It demonstrates some real cryptography using a level of math that everyone can do after high school.
Since it's written as a talk, this is Diffie-Hellman in plain English!
Hey you! Let's setup an encrypted channel. I'll send you my key and you send me yours, and then we can talk privately.
What did you say? Everyone can hear us? Yes, that is no problem!
We can use Diffie-Hellman. Just think of a random number and raise 5 to the power of that random number. Divide the result by 23 and take the remainder. Give that to me. The original random number, you should keep secret, the other numbers are all public knowledge.
Your remainder is 8? Okay. My remainder is 10. Now raise my remainder to the power of your secret random number again, and divide by 23 again, and take the remainder. Same thing, easy peasy. I'll do the same thing with your number and my secret random number.
You got the result? Great, me too! I know you got 6, just like me, and yet nobody else in this room could have computed that. They could have tried every possible combination until finding the random numbers that match what they heard (8 from your side and 10 from mine), but there is no way to compute this more efficiently than by trying all possibilities. We could have used the result, 6, as password. Nobody would have known the password we use, despite hearing the exchange. But it's a very weak password. Next time, we should choose bigger numbers and use a calculator to create a longer and stronger password.
Note that this worked because we can see each other. I know it's not someone else talking when you tell me your number is 8 because I can see your lips move. On the internet, someone could setup attacks against this by pretending to be the other side and giving us fake numbers. How we prevent these attacks is a topic for another day.