Imagine, you are in the room with a group of total strangers and you are able to share secret information out loud with the one person of your choice, while everyone else is listening. Sounds a bit impossible at first thought, right? How could you say something out loud so that only one person will be able to understand what you are saying? Ok, you might start talking in Dumi language in hope that only that person understands it. But what if that person doesn’t understand Dumi or, the worst case, someone else does and your secret suddenly becomes compromised? What if you could publicly create a shared language only that person and you will understand? This is where the Diffie-Hellman key exchange method comes into play.
Diffie-Hellman key exchange
“The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.” - Wikipedia
Now when we are done with the formal definition, let’s see what this really means.
Let’s say that our well-known security friends Alice and Bob want to perform a Diffie-Hellman key exchange. In the first step, they agree on publicly known information, let’s call it a common key, which will later be used to create a shared secret - key that will be used to encrypt all the communication between them. After they agree on the common key, both of them create a secret key that they keep for themselves. In the third step, both Alice and Bob combine the common key with their secret key and exchange that combination publicly. The most important presumption here is that it is nearly impossible to disassemble that combined key into initial parts - common key and secret key. Otherwise, this method wouldn’t make sense. Now you might be asking yourself how is this possible, but we will tackle this later on.
After the exchange of the combinations (Alice gets the combination of Bob’s private key and common key and vice versa), they again, each on their side, combine the private key with the combination they got from the other party. After this process is done, they will end up with the same key, the one that only Alice and Bob know and which is then used to encrypt the communication between them.
Mathematics behind the Diffie-Hellman
In the first part of this post, we talked about how Diffie-Hellman works in a more abstract way. In this part, you will dive deeper and see how Diffie-Hellman works in terms of mathematics and how it is even possible to perform such a method.
Before we start, I hope you are all familiar with the modulo arithmetic, but let’s have a quick look.
a mod b (a modulo b) is a remainder of dividing a with b.
E.g. 11 mod 3 = 2, because 11/3 is 3 with the remainder 2.
You can imagine modulo arithmetic as circling around a clock which has numbers from 0 to (b - 1). According to the above example, the clock would have numbers 0, 1, 2 and you will make 3 circles around the clock ending up at number 2.
Now we are ready to see what happens under the hood while performing Diffie-Hellman.
Remember that assumption about how it is nearly impossible to disassemble the combination of private and common keys? Let’s have a look at the fourth step where all the “magic” happens.
Imagine you are an attacker who wants to break the encryption. All you have to do is to find out what is the number A or B (Alice’s or Bob’s secrets) from (P^A mod N) or (P^B mod N). Because, if you find out, for example, A, then you can easily calculate (P^B)^A mod N to get the shared secret and break the encryption.
It may sound easy at first, but it is a difficult problem, even for supercomputers. The problem is called the Discrete logarithm problem and it is not feasible in polynomial time. You can think of a solution for this problem as a brute-force algorithm, which iterates through all numbers between [1, N] and finds the numbers that satisfy the formula (P^A mod N) where only one corresponds to the real A.
When it comes to encrypted communication there is always a challenge to exchange symmetric keys so both parties can encrypt and decrypt the data with only one key, since the asymmetric encryption (one key is used for encryption and the other is used for decryption) is time-costly and unsuitable for fast communication. Diffie-Hellman is one way of tackling this problem. Another way of doing this is to use asymmetric encryption to encrypt and exchange the symmetric key which will then be used to encrypt the communication (encrypt the symmetric key with the public asymmetric key so it can be only decrypted with the private key). For example, this kind of key exchange happens every time you visit some website via HTTPS protocol in the so-called HTTPS handshake.
That’s all folks! Thanks for reading, and if you have any questions, feel free to leave them in the comments section. Cheers! :)
Top comments (0)