The Cryptographic Algorithm You Use Most That You Have Never Heard Of
How does your web browser and a web server agree on an encryption key, over a dangerous internet, to serve you a secure website?
Some solutions to problems are so elegant that they make me smile every time I come across or think of them. The Diffie-Hellman algorithm is one of them. It is the algorithm which you use everyday, multiple times, that you have never heard of. In fact, by looking at this webpage, you have used the Diffie-Hellman algorithm: it is the basis of the encryption between web servers and your web browser, and it is elegant in its simplicity.
There was a time when most web servers served up content without encryption. Imagine you are in high school sitting in the back of a class. You write a note on a piece of paper to a friend who is sitting in the front row, fold it, and pass it to the person in front of you telling them who it’s for. That person passes it to the next person in front of them repeating the name of the intended recipient and so it goes until your friend receives the paper and reads it. Of course, anyone who is in the chain that handled your message can read what you had written. (Or worse, the message could have been intercepted by the teacher and read out loud!)
That essentially is how the internet works. Messages generated by, say a web server, are passed along a chain of machines in the internet in the “direction” of the recipient (your web browser) in small, more or less fixed-sized packets. (Imagine that you can only use small Post-It® notes to write your messages to your friend in class — you’d have to break a long message into several notes.)
Serving web content in plain text may be fine if the information is innocuous and is one-way — such as a nerdy blog — but what if you wanted to do internet banking? Or pay for yet another computer gadget that you don’t need with your credit card? Or view your company’s secret files whilst reluctantly working from home?
More nefariously, what if someone in the chain that passed your message along not only read it but also changed the message? In the internet, a bad actor can hijack a webpage served to you and change parts of the page, like the destination of credit card details, or insert ads about blue pills.¹
You can see where this is heading.
If only the messages were encrypted so that anyone in the chain intercepting those small Post-It® notes or internet packets see only gibberish.
Ciphers and keys
Let’s back up a little. In order for you and your high school friend to cunningly use encryption in your messages, you’d first have to agree on a method of encryption between yourselves. Let’s say you use one which every child has probably played with: the Caesar cipher². The Caesar cipher is also known as the “shift cipher”: we simply substitute every letter of a message with a letter a fixed number of places downstream or upstream in the alphabet. Say we shift 3 letters downstream, this would mean “A” would be replaced with “D”, “B” with “E”, and so on.
MEET ME UNDER THE BRIDGE
|||| || ||||| ||| ||||||
PHHW PH XQGHU WKH EULGJHNotice that both parties have to agree on two things: 1) the cipher to use (Caesar cipher) and; 2) the key (the number of letters to shift).
It probably isn’t a good idea to use the same key all the time for obvious reasons: it provides more examples and time for code cracking; and if the key is compromised, any messages sent to another friend with the same key would also be compromised. I wonder how well Caesar actually did with his cryptograms…
So back to the class where you have agreed with friends dotted around the room to use the Caesar cipher, but each time anyone wants to start a dialogue with you, the two of you first have to agree on a key.
How do you do this when all you can send are plain text messages across a field of untrustworthy classmates? It’s a catch-22: you can’t encrypt your messages until you agree on a cipher key, and you can’t send the cipher key to each other safely because you haven’t agreed on how to encrypt messages.
This is the same problem we encounter on the internet. How does your browser and a web server agree on an encryption key, given an agreed cipher, across the vast cloud of bandits, pirates and gangly, sun-starved teenage hackers?
On your browser, if you see an “s” in front of “http” in the URL, it means that messages/data between your browser and the web server are encrypted, such as this website. This is done using agreed cryptographic protocols, where a suite of encryption methods are presented for one to be chosen and agreed, and is called Transport Layer Security, or TLS.
The ciphers employed in TLS are much more sophisticated than what the Romans used for their love and other letters, and the key used between your browser and the server has to be unique, that is, none of the millions of other browsers connected to the same server should have the same encryption key. And this key has to somehow be agreed between the web server and your browser.
This is where the Diffie-Hellman algorithm comes in. It is an elegant way to exchange keys in plain sight.
Exchanging cryptographic keys in plain sight
The solution that is used in TLS was proposed, and patented³, by Martin Hellman, Baily Diffie and Ralph Merkle⁴ in 1977.
In order to understand how it works we have to first understand what a one-way function⁵ is. A one way function is an operation, or a series of operations, that you perform on an input number to produce an output number, where knowing the output number, and even the function, will not enable you to compute the input number.
A --some mathematical operation--> B
knowing B & the mathematical function above won't give you AThere are many one-way functions and the one used in the original Diffie-Hellman protocol is the simple modulo: that is, the remainder after division.
Consider dividing 12 by 7. This gives a remainder of 5. If we knew the output number (5) and the function (modulo 7), we might work out the input number as 12. But it could also be 19, or 26, etc. We won’t actually know which input number was used as there is an infinite number of them. And in actual use, the input number is very, very big.
12 mod 7 = 5
19 mod 7 = 5
26 mod 7 = 5
... and so on
(where mod is "the remainder after division")This is the first piece of the puzzle — a number that we can use in plain sight. How do we use that to build a key which both the browser and web server agrees?
Keys are the key
Imagine you have a padlock key, and your friend across the class has another, but different, padlock key. If you got together, you could use both keys to design a lock tumbler such that either of your key could unlock that padlock, but which no other key could.
If you kept your respective keys secret, and you received a padlock that you can open, you would know that it could only have come from your friend.
In cryptography, the key that you own and keep secret is called a private key. Your private key, let’s call it x, can be a very big random number:
x = 23592985774582873467256734568723457687356238456871235356185565And your friend’s, let’s call that y, is also a very big random number that only she knows:
y = 93984324284712643285614840183291815164057248§93842747298475532If you could use both of these numbers to somehow calculate another number, which could only have come from using those private keys, that could be your cipher key to encrypt the messages you want to pass in class. In other words, you have both agreed on a cipher key that can only be created mathematically if both private keys are present, much like creating that special padlock tumbler mentioned above.⁶
It turns out that we can modify the one-way modulo function mentioned above to do just that. First, let’s remind ourselves of the function:
We know that an infinite number of p’s using the same q can come up with the same K, but finding which one is non-trivial especially if p and q are very large. Conversely, we also know that we need both p and q to calculate K.
We can use the modulo function again to calculate this large number p, but also incorporate the 2 private keys, x & y, thus:
This way, like the special padlock, we are using both private keys to create the number K.
The x and y not only make the numerator of the division very large, but also have a curious property: we can swap x and y around and get the same result!⁷ That is:
How does that help with our problem of agreeing on a cipher key to communicate in encrypted messages that only you and your friend can decrypt and read?
It means that you can create a half-baked tumbler with your private key (the calculation inside the brackets in Equation 2), send the tumbler to your friend, who then uses her private key on the half-baked tumbler to create the padlock (completing Equation 2).
She will then do the same — create a half-baked tumbler with the parts you sent, imprinting her private key (the calculation inside the brackets of Equation 3) and send that to you. On receiving her half-baked tumbler, you use your private key to complete the lock (completing Equation 3).
Let’s see how this actually works.
Hiding in plain sight
First, you select what numbers p & q are going to be. Then, using your private key, x, you calculate what’s in the brackets in Equation 2 above. Let’s call this D:
Let’s say x=100, p=26, q=7. Hence D = 26¹⁰⁰ mod 7 = 24.
You then send all the numbers (p, q, D) to your friend except, of course, your secret private key x.
Your friend uses those numbers to calculate the cipher key, K, using Equation 2 & 4:
Let’s say her private key, y, is 300. Hence K = 24³⁰⁰ mod 7 = 30. The cipher key will be 30.
So far so good. One of you now has a cipher key. Note that this cipher key was calculated using both your secret private key, x, and your friend’s private key, y, like the special padlock tumbler.
Note also that you did not reveal what x is to your friend, nor to anyone else who might have intercepted your message. Since the modulus operation is one way, anyone intercepting p, q and D wouldn’t have been able to work out x.
Your friend now needs to wrap up her secret key, y, in a similar fashion and send it to you so you can calculate the same cipher key, K. She calculates the number in the brackets of Equation 3 above, and sends that to you (in plain text since you still haven’t got the agreed cipher key). Let’s call that number E:
Which in our example, E = 26³⁰⁰ mod 7 = 28.
On receiving E=28, you use Equations 3 & 6 to calculate the same cipher key:
Here, K = 28¹⁰⁰ mod 7 = 30! You have now incorporated both your friend’s private key, y, indirectly from E and yours, x, when calculating the cipher key.
Et voilà! From this moment on, all messages between you and your friend are snoop and teacher proof!
What the world sees
What your hapless classmates could intercept and read in plain text are 4 numbers: p, q, D & E. With those 4 numbers, even if they knew you were using a modulo function, it would be impossible for them to calculate the cipher key, K.⁶
That is how the Diffie-Hellman algorithm works. It is elegant and really, if you think about it, quite simple.
So now, back in your classroom, any one of your other friends with their own secret private key, can use this protocol to exchange a few numbers with you so that you both too can create a shared cipher key and start encrypting messages.
If we snooped at the packets of messages being sent between a web server and a browser, that is exactly what is happening:
Of course, there is much more to this when a browser tries to get a secure encrypted channel with a web server up and running, including having to agree on the encryption protocol. But that is for another day!
I hope, if you have understood how the Diffie-Hellman algorithm solves the problem of sharing keys over the dangerous, seething internet, and that you too will break out with a smile each time you spy that “s” in “https”.
Notes and citations
¹ This is called a “man-in-the-middle” attack. https://en.wikipedia.org/wiki/Man-in-the-middle_attack
² The shift cipher, also known as the Caesar cipher, was all the rage in ancient Rome (https://www.liquisearch.com/caesar_cipher/history_and_usage). And here is a translation of Suetonius, the Lives of the Twelve Caesars: see #56. (https://droitromain.univ-grenoble-alpes.fr/Anglica/Suetonius1_engl.gr.htm).
³ US Patent 4200770, Hellman, Diffie & Merkle. Cryptographic Apparatus and Method. 1977. https://patents.google.com/patent/US4200770
⁴ Yes, of Merkle-trees in blockchain hashes used in Bitcoin, Ethereum, etc.
⁵ One way to think of a one-way function: https://computersciencewiki.org/index.php/One-way_function
⁶ In reality, it is difficult to find a one-way algorithm that will produce a single result out of 2 numbers, so we use strategies where the number of possible keys are so large that it would be computationally too expensive to find the correct one(s) by brute force. The modulo function mentioned, applied with a very large numerator, is one such example.
⁷ Technically, we say that the exponentiation in this function is commutative.
You can test this out for yourself with some code. Here is an example in Python (as a calculator!) using random numbers for the variables:
>>> p = 138234735>>> q = 8438216>>> x = 1478213901432>>> y = 9274281247195>>> D = (p^x % q) ; D139689591>>> E = (p^y % q) ; E140153588>>> (D^y % q) == (E^x % q)True
