In this article we explain the basics of symmetric encryption with examples of simple schemes. We will encounter the main problem in symmetric encryption (the key exchange) and visualize the solution brought by Diffie and Hellman.
Conversations
A lot of times we find ourselves in a situation where we want to deliver information to someone else. Maybe we want to tell our mother to make our favorite dish on the weekend, alarm someone about an injury we got, or maybe we want to write a new song and upload it on YouTube.
Although all of the examples above are ways of passing information they are inherently different. Each communication has certain traits, it can be:
- Broadcasted or targeted – it can be directed at multiple people or a single person
- Trusted or not – we need to know the identity of the person we are talking to or that we don’t care
- Confidential or public – we care if other people can hear the content of the conversation or not
It is interesting to note that on we think about the traits of our communication in every conversation without even noticing it. Thinking about them is also pretty crucial since if you accidentally confuse one of them you cannot only pass confidential information, but you can also be pretty embarrassed.
Secret information
Obviously there are more traits to different communication methods. I am sure you can find more if you just think about it a little. In this article we are going to focus on confidentiality (since we are talking about encryption).
When we want to pass confidential (or secret) information we don’t want anyone to hear it. Unfortunately, sometimes this constraint is too harsh. Eavesdropping to someone is pretty easy, you can install a microphone in their room and voila. As a consequence, we usually allow the other person to listen, but we don’t want him to understand.
The problem now is pretty straightforward. We (for purely academic reasons lets say our name is), Alice, want to talk to another person (for the same reasons lets say his name is), Bob. Another evil eavesdropping person called Eve hears the confidential information. How can we make Bob understand us but not Eve?
Encryption
The problem described above can be solved by altering the data we want to send Bob in a way where only he can understand it – this is called encryption. Secret information always existed, military plans are a very old concept and gossip even more. In ancient times encryption was pretty much of an art form and some of the schemes used were beautiful. Lets look at some of them!
The most basic encryption scheme is the Caesar’s cipher. In this scheme both Alice and Bob pick a number X and move all the letters forward by X. This is done in a cyclic pattern such that if X=1 then A\rightarrow B and Z\rightarrow A. An example:
X = 9:\ pineapple\ pizza\rightarrow yrwnjyyun\ yriij
If Bob wants to bring the message to its original form (decrypt it) he just needs to move the letter back X places.
Caesar’s cipher is pretty weak. Even if Eve doesn’t know the value of X, if we use the English language X can have just 26 values (27 does the same effect as 1). So Eve can just check all 26 of them and break the code.
A more sophisticated method is the substitution cipher. In this scheme we choose a pair for each letter and replace the letters according to the pairs. For example lets say the pairs are A\rightarrow F; B\rightarrow G; C\rightarrow M; D\rightarrow U;E\rightarrow R,… then we will get BED\rightarrow GRU. To decrypt, Bob only has to replace the letters back. The only thing we need to notice is that two different letters are encrypted to two different letters, otherwise Bob can’t decrypt.
In this scheme Eve has more trouble . If we use the English language there are 26!\approx4\cdot 10^{26} options for these pairs. Unfortunately this scheme is still not good enough because letters in the English language appear in different frequencies. For example the letter ‘e’ appears way more than ‘z’ or ‘q’. The frequencies of the letters in English (including the laughing emoji) are:
Eve can check the frequencies of the letters in the encrypted text and search for unique patterns such as double letters. By comparing the statistics she got to the information she knows about the English language, Eve can know which letters are more likely to be hiding and where. Thereby Eve’s search space can become much smaller and she can decrypt the data.
Another pretty cool scheme is the Vigenère Cipher. In this scheme we pick a key, for example ‘mycoolkey’. After picking the key we shift the letters in the text according to the letters in the key. For example, we want to encrypt the text ‘hello there’. The first letter in the key is ‘m’ which is the 13th letter, so we move the first letter in the text 13 places forward and we get h\rightarrow u. We do the same thing for all letters in the text and their corresponding letter in the key. When we get to the end of the key we just start over.
In this example we would get:
hello\ there\rightarrow udoad\ fsjqr
This method is slightly better. You cannot break it with simple statistical analysis and unique features such as double letters. But the problem is that we use the key in a cyclic way (when we get to the end we start over). If the key is of length X, then if we take each X^{th} letter in the encryption text we get a simple Caesar’s cipher. This means that if the text is long enough or the key short enough we can break this text.
The problem with symmetric encryption
The schemes we covered so far are pretty cool, they can even be usable if we are cautious. But a problem lies in the way Bob decrypts the data. In the Caesar cipher he needed to know the value of X. In the substitution he need to know the pairings. And in the Vigenère he needed to know the key. Essentially, we delivered secret information by relying on other secret information.
The methods of encryption we covered are called symmetric because both Alice and Bob need to have the same key to communicate. All of the symmetric encryption schemes suffer from the problem of distributing the key itself (even the more modern ones such as the Enigma cipher or AES).
In the past the key had to me sent physically in some way. But this is very cumbersome, especially when all you want is to text someone on your phone.
A solution – the Diffie-Hellman key exchange
In 1976 two researchers by the names of Whitfield Diffie and Martin Hellman introduced a revolutionary piece of mathematical wizardry that brought a solution. The underlying principle of the solution is that both Alice and Bob create a secret of their own. Using their secrets and some public data they create the shared key.
The underlying genius is that Alice and Bob don’t send their secrets directly (because then Eve could get them too). They use the public data to obfuscate them in an irreversible way. The way they do this is to rely on the discrete logarithm problem. The problem states that if we have the number c=m^e\mod N it is very hard to discover what e is even if we know the values of m and N.
For example if m=7,\ N=221 and we get c=121, what is the value of e? Unfortunately, there is no substantially better way then just checking all the possible values for e. After checking we can see that e=10. In practice the numbers are much larger and the time it takes to find e is ridiculous.
The way the Diffie-Hellman key exchange works mathematically is:
- One of Alice or Bob picks a prime number p and another number g (for the interested reader, it is important that g will be a primitive root modulo p, but this is a little out of scope).
- The numbers p and g are public and Alice sends them to Bob, Eve also listens and has them
- Alice picks a number a and calculates c_a=g^a\mod p
- Bob picks a number b and calculates c_b=g^b\mod p
- Alice sends c_a to Bob and he sends c_b to Alice
- Alice calculates k = (c_b)^a\mod p=g^{ab}\mod p
- Bob calculates k = (c_a)^b\mod p=g^{ab}\mod p
- Alice and Bob use the key k to communicate
Notice that Eve cannot get k because she can’t get the values of a,\ b because of the hardness of the discrete logarithm problem.
If this was too mathematical for you, here is a nice analogy with colors:
- One of Alice or Bob pick a public color – lets say yellow
- Alice sends the public color to Bob (or vice versa)
- Alice picks a secret color, lets say some shade of red
- Bob picks a secret color too, lets say some shade of blue
- Alice mixes her secret color with the public color, creating a shade of orange, she sends this to Bob
- Bob mixes his secret color with the public color, creating a shade of green, he sends this to Alice
- Alice mixes her red with Bob’s green creating some secret color k
- Bob mixes his blue with Alice’s orange creating the same secret color k
Notice that Eve only has the yellow, orange, and green colors. To create the final color k she needs either Alice’s red or Bob’s blue. The red and the blue are mixed inside the orange and the green using the yellow. But it is very hard for Eve to “unmix” the colors. Therefore she can’t get k and Alice and Bob can use it to encrypt their communication.
