Do you want to know a secret? You probably do, question is, would you like it if anyone else knew your secret as well? I am guessing not. That is why, on the Internet, we use encryption for the data that we send and receive, just to make sure that someone else is not listening in on our conversation. Encryption is not only used when directly communicating with each other, it is also used for something we call “integrity”, a.k.a. “I want to make sure that I get what the other end is sending without anyone modifying it in transit”. So, use encryption anywhere!
The basis of encryption is that the parties that want to exchange information agree on a common secret. However, the challenge that they have is to exchange that secret without anyone else knowing it. And that’s where the fun begins. Let us take the following as an example.
Let’s suppose that Michael wants to send a confidential message to Rick without the ‘Evil dude” in the middle listening in. Obviously, they want to use encryption for that, but for this to work, they both need to agree on a secret that only they know. This secret needs to be transferred in such a way that only Michael and Rick know its content. So they need to figure out a way to do that without our “Evil dude” getting his hands on it.
The basis for this “key exchange” involves a mathematical solution called modulus divisions. In its most simplistic form it’s like how many times does x fit into y and what remains is the result. Let’s take this example:
23 Mod 13 = 10
The statement above says, “How many times does 13 fit into 23 and what is the remainder”? That’s really it. Now it can get very complex, but in essence, this is modules divisions. For our encryption to work we can’t just take any number, it needs to be a prime number. The reasoning behind it is that we need to use a unique capability from a prime number later on in the calculation. Remember that a prime number is a whole number that cannot be made by multiplying other whole numbers, if you can make it by multiplying other whole numbers it is a Composite Number.
Back to our modules example “23 Mod 13”, where we call 23 the generator and 13 the exponent. So first Michael and Rick agree on the generator (G) and the exponent (P) that they will use. As this is all send in clear text, our “Evil dude” will receive a copy as well.
To start with the fun, Michael will add a random (private) number to the generator and send the result to Rick. For kicks let’s add something like 15. So we get the following:
2315 Mod 13 = 12
The resulting number of 12 is send, in clear text (public information), to Rick, needless to say that our ears dropping person in the middle also gets a copy. Rick, receiving the package now does exactly the same with a random number he makes up. Let’s say the number 26. The result is
2326 Mod 13 = 9
This resulting number is send back to Michael for him to use.
So now both Michael and Rick have some public and private information. Michael has a private number (Let’s call it a key) of 15 and received a public key of 9. Rick has a private key of 26 and received a public key of 12. Our hacker has all the public information.
Now comes the magic. To calculate the shared secret both Michael and Rick will use the public information that they received and use it with their own key to generate the shared secret for further communications. So it goes like this.
Michael: (Rick’s public key)9 15 (Michael’s Private key) Mod 13 = (shared key)1
Rick: (Michael’s public key)12 26 (Rick’s private key) Mod 13 = (shared key)1
So what we have done here is take the public information we received from the person we want to set up a secure communications with and use exponentiation to calculate the secret. Once we have generated our secret we can now use that to further encrypt all our messages. Coincidental we could also use multiply both secrets and use that as an exponential in both cases. This is possible only by using prime numbers.
23(15*26=390) Mod 13 = 1
What I’ve shown you here are the essentials for public key exchange using Diffie-Hellman key exchange which is a popular cryptographic algorithm that allows Internet protocols to agree on a shared key and negotiate a secure connection. It is fundamental to many protocols including HTTPS, SSH, IPsec and protocols that rely on Transport Layer Security (TLS). Obviously, in my example, I’ve over simplified things just to make it understandable, in practice it’s a bit more complex using larger numbers, but the technique is the same.
As always if you have any questions, comments or remarks, just let me know.