Diffie Hellman Key Exchange
The technique that makes the Internet possible
In short, the Diffie Hellman is a widely used technique for securely sending a symmetric encryption key to another party. Before proceeding, let’s discuss why we’d want to use something like the Diffie Hellman in the first place. When transmitting data over the Internet as plain text, it’s easy for someone to use some kind of packet sniffer like WireShark to capture packets. A malicious person, could listen in on the conversation you had with your girlfriend or worse yet, steals passwords and credit card information. Fortunately, some very smart people came up with a way to encode information for transit. The process by which we convert ordinary plain text into something unintelligible and vice-versa is known as cryptography. The most basic example of cryptography is called the Caesar Cypher.
In essence, both parties have a symmetric key which specifies what characters map to what symbol of the encrypted text. Those who don’t possess the key cannot read the message. For example, in the preceding image, the character ‘A’ would be encoded as a ‘T’ in the encrypted message. An individual on the receiving end could then use the same Caesar Cypther to decode the message.
In the realm of computer networking, the problem with symmetric encryption algorithms is that the key must be inevitably be sent over the network to the other party so that they can decrypt incoming messages, and encrypt them in turn. If a malicious actor happened to be listening to the network at that point in time, they could obtain the key, and use it for nefarious purposes.
This is where asymmetrical encryption comes in to play. Asymmetrical encryption works by generating a public and private key pair. The public key can only be used to encrypt messages whereas the private key can only be used to decrypt messages. For example, when you do your online banking, you give the bank your public key which is then used to encrypt the data sent back to you. If a bad guy gets their hands on the public key, they can’t do any real harm since they only have the ability to encrypt data.
Today, the most widely used asymmetrical encryption algorithm is RSA. RSA stands for Rivest–Shamir–Adleman after the people who first described the algorithm back in 1977. The RSA algorithm encrypts messages by raising the message to the power of the public key and then taking the modulo of the result. To decrypt a given message, we raise it to the power of the private key and then take the modulo of the result. RSA relies on a mathematical concept known as a one-way function. Suppose we had the following equation:
Now, say you were given the number 8 and asked to get back to 2**³**. Could you do it?
It’s relatively easy to work our way backwards in order figure out all the factors of 8.
In contrast, the modulo (synonymous with remainder) operation is an example of a one-way function. Suppose we had the following equation:
If you were asked to derive 11 from 3, could you do it?
You may be able to obtain the correct answer (11_)_ by trying out all the different possibilities (i.e. 3 % 4 = 3, 7 % 4 = 3, 11 % 4 = 3), but when the numerator is very large, as in the case of RSA (i.e. 4096 bits long), there are a lot and I mean A LOT of permutations that give a remainder of 3. Given this property, hackers would have no choice but to use brute force (try every possibility) to determine the private key from the encrypted message and public key. Given that today’s keys are 4096 bits long, it would take traditional computers centuries to go through all the possible values.
In practice, asymmetrical encryption is 3 to 5 orders of magnitude slower than symmetric encryption. Therefore, we don’t encrypt the actual payload using asymmetrical encryption. Rather, we use a technique like Diffie-Hellman to securely send a symmetric encryption key to the other party, and then use said key to encrypt/decrypt all further messages.
Modulo Arithmetic (RSA) Diffie Hellman
We’ve already described the RSA at a high level. Now, let’s take a look at a concrete example. Suppose, Bob wants to send a message to Alice. Bob will start off by generating a new random prime number N and corresponding generator g.
NOTE: g isn’t random, but how we go about selecting it is beyond the scope of this article.
In practice, N is a large number. However, for the sake of simplicity, we’ll use the following values:
Both g & N are sent over the network as plain text. Bob then generates a secret key a = 2. Next, Bob raises the generator g to the power of his secret key a, and takes the modulo of the result. The end product A = 5 is sent to Alice.
On the other end, Alice performs the same steps — that is, she generates a secret key b, raises the generator g to the power of her secret key b, takes the modulo of the product, and sends the end result B = 3 to Bob.
Even if a malicious actor were to snoop on their traffic. They wouldn’t be able to derive Bob’s or Alice’s secret key from A and B.
Upon receiving B from Alice, Bob raises it to the power of his private key a, and takes the modulo of the result.
Alice does the same.
Alice and Bob both end up with the same number, 9, in this case. They then use 9 as the key for a symmetrical encryption algorithm like AES.
Elliptic Curve Diffie Hellman
Trying to derive the private key from a point on an elliptic curve is harder problem to crack than traditional RSA (modulo arithmetic). In consequence, Elliptic Curve Diffie Hellman can achieve a comparable level of security with less bits.
A smaller key requires less computational steps in order to encrypt/decrypt a given payload. You wouldn’t notice much of a difference when establishing secured connections from your local machine. However, on something like a Medium web server that performs thousands upon thousands of key exchanges every second, the use of Elliptic Curve Diffie Hellman can lead to significant savings.
We can visualize the domain of all possible numbers in a Diffie Hellman RSA key exchange as a circle (due to the nature of the modulo function). The larger the value of n, the larger the circle, and the harder it is to guess the correct number.
In contrast, as the name implies, the domain of all possible numbers for an elliptic curve Diffie Hellman key exchange takes the form of an elliptic curve.
The preceding elliptic curve is characterized by the following mathematical equation:
In the wild, it’s pretty common to take use the equation (mod n).
In practice, you want to use curves that have been developed by professional mathematicians, and vetted to ensure they are secure.
Instead of raising things to powers as in the case of RSA, elliptic curve Diffie Hellman works by adding the point G to itself several times over.
Let’s take a look at an example. Suppose Bob initiates a connection with Alice. Bob selects a generator **G (**a point on the curve) and the parameters a, b, n of the elliptic curve equation, and sends them across the wire as plain text.
Bob and Alice then each generate a private key (number). For the sake of simplicity, let’s assume Bob selects b = 9 and Alice selects a = 3. Bob and Alice are responsible for computing bG = 9G and aG = 3G respectively**.**
In order to compute xG (where x is any number), we use the formulas for adding and doubling a point. For instance, to determine 2G, we use the formula for doubling a point.
To take the modulo of a fraction, we can make use of a modular multiplicative inverse calculator.
Modular Multiplicative Inverse
_This calculator calculates modular multiplicative inverse of an given integer a modulo m. The theory is below the…_planetcalc.com
We then multiply the answer with 77 % 17 = 9, and take the modulo of the result.
The x coordinate of the point can be calculated as follows:
We then use x2G to compute y2G.
To calculate 3G, we use the formula for adding a point.
We start off by calculating the slope.
Then we compute the x position of the new point.
Finally, we use the value of the x coordinate to compute y.
Bob sends bG = 9G = (7, 6) over the network. Similarly, Alice sends aG = 3G = (10, 6). In the event, a malicious actor is listening, it’s damn well impossible to derive the value of aG or bG from the points (7, 6) and (10, 6) on the elliptic curve.
Once Bob receives aG = (10 , 6) from Alice, he computes abG = 9(3G) = 27G = (13, 7). When Alice receives bG = (7, 6) from Bob, she computes abG = 3(9G) = 27G = (13, 7). They then both use the x coordinate of abG as their symmetrical encryption key for all further data transfer.