The Diffie-Hellman key exchange is a way of securely establishing a common secret between two parties in an unsafe public environment.
What does this mean? Consider this situation:
Imagine you are in a room with hundreds of people. You wish to establish a common secret with only one other person B in the room. Everyone else can hear everything that is being said. How can you make sure that only you and the other person know the secret, hiding it from the rest? Once again math magic solves this problem…
The solution builds upon the discrete logarithm problem. To understand what this means, take a base number such as 17 and square it with another number such as 49 (calculate 1749).
Giving someone the result 1958831807773342257691221904789587637189069813834520650586897 and the base number 17, it is very hard for him to figure out what the exponent (49) was. This, just like prime factorisation, is an example of a one-way-function.
Now back to establishing the shared secret:
1. You publicly disclose a base number g.
2. Privately, you square it with a secret number of your choice a to obtain (ga)
3. You ask the other person to also do step 2 with his own secret number b. He obtains (gb)
4. Both of you exchange the squared numbers (ga) and (gb). Everyone else in the room will be able to hear them.
5. Now you take the number you received and square it with your own secret number. You obtain (gb)a
6. The other person does the same with the number he received from you. He obtains (ga)b
Mathematically, those two numbers are identical: (gb)a = (ga)b. Only you and the other person know them, and everyone else is left with a big questionmark. This is your shared secret.
Explanation: The crucial step is 4. At this point everyone in the room knows the base g and the results of both exponentiations. They can not, however easily deduce the exponents a and b used by you and the other person (they can not solve the discrete logarithm for g).
Let us do the same steps with actual numbers:
1. g = 13
2. a = 7, thus ga = 137 = 62748517
3. b = 4, thus gb = 134 = 28561
4. You obtain 28561 from the other person and he obtains 62748517 from you
5. You compute (gb)a = 285617 = 15502932802662396215269535105521
6. The other person computes (ga)b = 627485174 = 15502932802662396215269535105521
Nobody else can find out this number, because the secret exponents a and b are never exposed, but required for its computation.
Figuring out a and b would require systematically trying all exponents (132,133 ,134 ,135 , …) until the right one is found. If the exponents are big enough (hundred-digits long), this task becomes equivalent to finding the needle in a… universe.
Whats the point of all this?
This is all nice and smart, but where can it be applied? Its simple – after establishing this initial shared secret, both parties can use it as a password to encrypt all further communication. This would provide them with the needed privacy to exchange sensitive information, while hiding it from any eavesdroppers.