The First Thing a Spy Must Master is…Mathematics?
Gems in STEM: Introduction to Public-Key Cryptography
I remember watching Spy Kids when I was younger and wishing that I, too, was a spy. I would daydream about doing killer gymnastics between sharp red laser beams and flying with those insane gadgets that they somehow let tiny children use. Then I grew up and realized that I am not at all physically fit enough for all the running they do, and that it was essentially free child labor (not once did I see those kids receive monetary compensation for their hard work).
Anyways, a lot of the trouble in spy movies seems to lie within the inability to communicate safely or securely, oftentimes because of an inside mole who has access to sensitive information that they use to thwart the ‘good’ spies. So, while I may not be able to contribute physically as a spy, perhaps we can do so intellectually–like one of those characters who rapidly types on like three different computers while relaying crucial information to the main characters.
To do this, today we will be talking about one of the four primary types of cryptography: public-key cryptography (also called asymmetric key cryptography)! To learn more about some other basics of cryptography, make sure to check out my last article!
As we learned last time, symmetric encryption (another one of the four types) is when the same key is used to encrypt and decrypt messages, and said key is previously agreed upon by both parties. Some examples of this include Caesar’s Cipher and Vigenère’s cipher (both of which are discussed in the other article)!
But, there’s a clear, enormous disadvantage of symmetric encryption: the lengthy process of creating and relaying keys. If you truly wanted to send secure spy messages, you presumably would not use the same key for each message. So how do you efficiently exchange keys to send more and more messages, maybe to hundreds of different people–each with a different key? Simply put: you can’t. Your spy mission will probably fail if you try to manage this many key switches, thus resulting in the end of the world (as these things typically go).
So what do we do? Do we just make all our secret messages public and hope for the best? As you have hopefully figured out, no! (In fact, this would probably end the world faster.) Fear not, we do not have to solve this problem all by ourselves–smart people have been working on it for a while! Indeed, American cryptographers Whitfield Diffie and Martin Hellman proposed a solution to this glaring problem in their innovative 1976 paper.
Diffie-Hellman
Their method is creatively called the Diffie-Hellman key exchange (but should officially be Diffie-Hellman-Merkle to recognize computer scientist Ralph Merkle’s equal contribution), and was one of the first protocols to make use of public-key cryptography. To explain this method properly, let’s set up a situation: me, an intelligent and experienced™ spy, wants to send you, a new spy with lots of potential, a secret message about my corrupt boss (who is actively trying to eavesdrop on our messages), but I can only send it on our public network. Now, unlike in symmetric encryption where there is one key, we have two keys: one that is public and one that is private. While the actual method involves big, big numbers, let’s first think about it with a paint analogy!
First, we publicly agree on a key that doesn’t need to be secret. In this analogy, we suppose this public key is a paint bucket filled with yellow paint that anyone can use. Now, we both separately select a secret paint color that we keep private. I select red and you select turquoise (the left and right column, respectively, in the picture).
Now, here’s the important part: we both take that public yellow paint bucket and mix it with our respective secret colors. After this, I now have an orange-ish paint (left column) and you have a light-blue paint (right column). Now, we can publicly exchange our new mixed paints. Finally, I mix the light-blue paint I got from you with my original secret paint (red), and end up with a muddy brown. Similarly, you mix the orange-ish paint you got from me with your original private paint (turquoise), and you end up with the same muddy brown color! Voila! We both now have a shared secret (the paint color) that no one else knows.
But what’s to stop my corrupt boss from eavesdropping on our art exchange and recreating it? Well, he has access to the yellow paint and our public exchange of our first mixed colors (orange-ish and light-blue paint). However, he can’t easily figure out our secret paints because, while it’s easy to mix paint, it’s not so easy to reverse this process and isolate the paint mixtures that went into it. Therefore, it’s very difficult for him to create our final secret paint message. Hooray, corruption exposed!
Obviously, we can’t really use this paint method to send our secret messages, so how does this translate to real-life numbers? Well, we can replicate the difficulty of “un-mixing paint” with prime numbers. It’s easy to multiply two huge prime numbers together, but reversing the process of trying to factor a number into two huge primes is much, much harder. Intuitively, it does make sense because multiplication is, well, multiplication (which can also be thought about as adding)–it’s pretty straight-forward for a computer to compute and is thus quick. But factoring an enormous number (I’m talking hundreds of digits long) requires a computer to run through and check prime after prime after prime, which therefore takes a super long time.
Alright, enough theoretical talk–let’s see first-hand how Diffie-Hellman works with a numerical example! To make things clear, I’m choosing a simple example with small primes (which would not be used in real life) and brushing over some technical conditions. As a heads up, this example does require a little familiarity with modular arithmetic, so if that means nothing to you–feel free to skip! If you understand the above analogy, you’re pretty much set.
Once again, I am trying to send you a secret message! (It’s getting kind of tiring, to be honest. We should take this boss down soon.)
First, we publicly agree on a public prime p = 37 (which is our modulus) and base number m = 5.
Then, I choose a secret integer a = 6, and I calculate the number 11, as seen below.
(For those unfamiliar with modular arithmetic, note that taking a number A “mod p,” for any p, is just finding the remainder of dividing A by p. For example, 38 is equal to 1 (mod 37) because 38/37 has remainder 1.)
Now, you choose a secret integer! …I’m waiting…CHOOSE FASTER. Okay, b = 3 it is! Then, you calculate the number 14, as seen below.
Bringing it back to the paint analogy, we see that the yellow paint is like our prime p = 37 and base number m = 5 here (both of which are available to everyone), and our secret integers are akin to our secret paint colors. Then, computing these congruences is like mixing our private paint with the public paint, as both the public values and private values are intertwined in the calculation!
Now, we exchange our numbers: I give you 11 and you give me 14 (just like how we exchanged our mixed paint colors).
Finally, I compute the below and get the number 36!
Similarly, you compute the below and get…36 too! (Feel free to check this yourself!)
Just like how we previously mixed our exchanged paint with our private paint, in the last step we involved our secret numbers in the computation and ended up with the same secret (the number 36), like we ended up with the same paint color at the end of the other example.
The reason, or proof, for why this works out numerically is actually fairly straight-forward, but in the interest of time and keeping things simple, I’m not going to discuss it here. If you’re interested, definitely search it up!
Like I mentioned before, real-world execution of this method would involve much bigger and badder primes and values (with hundreds of digits), so that even the fastest computers today would take at least hundreds of years to crack it, if at all. It’s talented, brilliant, incredible, amazing, show-stopping, spectacular, …
…Hold up, what do we even do with this shared secret? How does it allow us to pass secret messages? Well, since no one else has this number, we can make it our secret encryption key! With this key that only the two of us know, we can securely send messages on our public network. Mission accomplished. Now when do I get paid?
Until next time! If you found this interesting, claps are greatly appreciated! Make sure to follow me if you want a notification for the next column! If you have any questions or comments, please email me at apoorvapwrites@gmail.com.
To be the first one to hear about all my new articles, recent events, and latest projects, make sure to subscribe to my newsletter: Letter? I Hardly Know Her!
This column, Gems in STEM, is a place to learn about various STEM topics that I find exciting, and that I hope will excite you too! It will always be written to be fairly accessible, so you don’t have to worry about not having background knowledge. However, it does occasionally get more advanced towards the end. Thanks for reading!
