Let’s say we have a crowded room of people. Anyone in the room can talk to anyone else, but when they do, everyone else in the room can hear them. If you wanted to exchange secret information with another person, anyone could lean in, listen, and steal your secrets. So maybe you think about the possibility of using a cipher of some kind to mangle your message to the effect that only the person the message was meant for could unscramble it and understand its meaning. The obvious problem with this idea is that you would first have to tell the person the key to your cipher, and you would be back to square one. Anyone could listen, hear the key, and decrypt the messages for themselves. What if I were to tell you, however, that there is a way for two people in the room to each shout a special message and from there be able to encrypt all of their future messages with a secure unbreakable cipher that nobody else could possibly figure out? By the end of this post, you will see how this is possible. Some of you may already know where this is going and for those who don’t, allow me to introduce the magic that is known as the Diffie-Hellman Key Exchange.
What is now known as the Diffie-Hellman Key Exchange was first published by the scheme’s namesakes Whitfield Diffie and Martin Hellman in 1976. Much later, it became known that the British signals intelligence agency, GCHQ, had developed the same scheme as early as 1975. Up until this point it was agreed upon in the cryptography community that the only way to establish a secure cipher between two communication points was to first exchange a cipher key in private. To be able to subjugate the need for this initial private meeting was a really big deal, especially given the implications it has for the Internet (computers communicating across long physical distances). To compare to the above example, the internet can easily be described as the largest crowded room of people ever. I am now more than 300 words into this post without tying it to any subject material from our class, however. It’s time to talk about the mathematical techniques that make this all possible.
Modular arithmetic in the context of cryptography:
I think it was really fortunate that we had a lesson in class on the beginnings of modular arithmetic. As a computer scientist, it has opened up a huge realm of blog post topics that I can speak about from a knowledgeable perspective due to so many CS topics relying on the techniques of modular operations. My favorite layman’s description of modular arithmetic is taking a number of hours, and translating them onto a clock. A clock, of course, only has 12 possible positions for the hour hand to fall under. So given a measurement of time that is greater than 12, what are we to do? Anyone can see how 10 hours measured on a clock would point the hour hand to the number 10. Likewise it’s easy to understand how 22 hours would wrap around and also point the hour hand at the number 10. Our brains have gotten good at automatically doing the modular arithmetic in this situation. In terms of math, all we are doing is dividing our number by 12 and then taking the remainder. 22 / 12 = 1 remainder 10. We would define this by saying 22 mod 12 = 10. Without really thinking about it, using these simple techniques, we have created a mechanism that is both necessary and perfect for cryptography and almost all modern forms of ciphering messages. Modular arithmetic provides us the functions we need to create something that is really easy to calculate in one direction, but is impossible to calculate in the other direction. Given the number 10, is there any way to tell what number of hours we had originally? It could be 10, it could be 22, it could be 34, or it could be any multiple of 12 with an added 10.
Diffie-Hellman Key Exchange example:
So how does the Diffie-Hellman key exchange actually work? Lets lay the key equations out first.
Now these are a lot of terms that mean nothing now, but I will define them as we go. Lets walk through the steps of the exchange:
- The numbers g and p are predefined numbers and known by everyone. For security’s sake and deeper reasons I won’t go into, g and p should be prime.
- For our example, lets use the common values for this problem: g = 5 and p = 23
- Each party involved chooses a secret number they will keep private.
- Lets say that A chooses their number to be a = 6, and B chooses b = 15.
- Party A then computes their shared value to be equal to Sa = ga mod p.
- In this example ga mod p = 56 mod 23 = 8
- Party B then computes their shared value to be equal to Sb = gb mod p.
- In this example gb mod p = 515 mod 23 = 19
- The parties involved now shout their shared values Sa and Sb to each other, not caring if anyone hears.
- A shouts their number 8 to B, and B shouts their number 19 to A.
- Now we take into account the equations above. Each party now calculates the final shared secret, SS, using SS = Sba mod pfor party A, and SS = Sab mod p for party B.
- Party A computes the value: SS = Sba mod p = 196 mod 23 = 2
- Party B computes the value: SS = Sab mod p = 815 mod 23 = 2
- Now both parties have a shared secret SS = 2 that they were able to compute and never send over the wire!
These are a lot of numbers to try and make sense of. The picture of why this works is very unclear. My favorite example of why this works that is easier to understand is one to do with colors and mixtures of paint, the diagram for which comes from a professor by the name of A.J. Han Vinck at the University of Duisburg-Essen.
If we can convince ourselves that raising one number to the power power of a second number and then taking the modulus of that number is similar to mixing two colors of paint together, this example makes a lot of sense. We see that we start out with everyone knowing a common paint color. This would be our values of g and p. Both Alice and Bob then choose a secret color. These would be a and b from our above example. They then mix the color of paint they are going to send over the wire. These are the light orange and blue colors we see going over public transport and from our example, we know them as Sa and Sb. On the other side of the transport, the respective parties add their own secret colors to the mixture they received from the other. In the end, the exact same ingredients have been added to both parties mixture of paint so intuitively the end result is the same. As a third party, even if you knew about the two colors of paint that were publicly shared, you could never separate out those colors and know what the secret colors of Alice and Bob were. You would never be able to construct the all important final color.
Once there is a secret established between the two parties, they can use the key in a wide variety of ciphers including just using it to mangle a single message (known as a one time pad). The practical uses of Diffie-Hellman have a few restrictions on the numbers g, p, a, and b in order to keep the keys unbreakable. For instance, the number p must be a very large prime number. With these proper requirements in place though, you can find this trick employed all over the internet. Versions of it are included in almost all “secure” or “encrypted” network connections.
source material: Color scheme image: A.J. Han Vinck, University of Duisburg-Essen SVG version: Flugaal – A.J. Han Vinck, Introduction to public key cryptography, p. 16