Sunday, October 18, 2015

The secrets of secrets

joão pestana

What is a secret? If you do a Google search, you'll probably encounter a reality show, a movie, a book or lingerie. That all seem good results — particularly the last one — but they ain't the definition of a secret, per se. It's a two syllable adjective and, according to Merriam Webster, it means "kept hidden from others" and "known to only a few people." Certainly, this feels much more correct.

There are many times in which we wish to have information available to only a handful of people — or even just one more person — that we trust. The question is how to do that? There is a field of study that is dedicated to precisely that and it's called Cryptography.

Probably, you can recall a time in your life when you needed to pass a secret message to someone. For example, when you were at school. Imagine what would happen if the other kids — or even the teacher — caught your message instead of the intended recipient! Now... Do you remember the method that you used back then? I would bet my money that it was a simple letter swap method. You and your friend knew the right key to code and decode and an A could become a N and a N would become an A and so on to all the other letters in the alphabet.

Just because I called it simple, it doesn't mean it's a weak type of encryption and someone could easily break your code. The real strength of any encryption depends on how long it takes to break. Yes, every encryption does break because, if it didn't, then decoding a message would be impossible. The single method that breaks all codes is called brute force hacking and it does just that. If you know how it works, you can program any Turing machine — computers, for example — to try every single possible combination of keys.

I'll illustrate the whole method with an example. I have a message I want to pass to Sarah and we're the only two people that know the key. This key is presented in Table 1.

Table 1 — Example of a letter swap encryption key.

To make it simple, all the letters are ordered but they didn't need to be. The ones in the top row switch for the ones in the bottom row and vice-versa. The process of encrypting and decrypting a message is pretty straightforward and follows these simple steps:

  1. Write down the message you intend to send;
  2. Run your message against the key and switch all the letters accordingly;
  3. Send your gibberish message to your intended recipient;
  4. The recipient runs the message against the key you both share;
  5. Switching back all the letters should reveal the original message.
The message I want to send to Sarah is the following.
Let's meet tomorrow at 14 p.m. for coffee and smalltalk.
 Notice that it contains several revealing elements that could be too revealing even when encrypted. I mean the numbers, the spaces, the apostrophe and the dots. I should either remove or switch these elements with words and also convert it all to uppercase, because my key has no lowercase correspondences. My message becomes now quite different.
It already resembles some sort of secret code, but it's still understandable. Let's run it against the key we have and see what comes out.
Success! I now have an unreadable message that I can send to Sarah and only her will be able to decode it. Or is it? What are the chances that, if fallen into the wrong hands, that person can decode the message?

If the code breaker assumes that the code is based only on the 26 letters of the english alphabet and is a simple letter swap method, it means that it's simply a matter of finding out the right key for which the one in Table 1 is just one of many. Precisely, how many? Let's see...

We have 26 available letters to fill the first cell on the table and we choose one. We are left with 25 letters to fill in the second available cell. We choose the second one and proceed until we have only one letter left for the last cell. It's a simple multiplication and we can write it as a factorial.


Because we cannot repeat letters, the available choices get reduced along the line. This is known as permutations without repetition and calculated using the factorial function. This gives us the number of all possible keys which is just...

`26! = 403   291   461   126   605   635   584   000   000`

Now that's a really big number! Well... Yes and no. It's a big number of combinations for you to resolve on your own, but a computer can go through all of them in a relatively short time. Since we cannot make our messages indecipherable — it would render all this useless — by introducing a random element, we can only alter the complexity of the encryption process. In this sense, we can make the number of possible combinations so astronomically high that it would take the best computer a time larger that the age of the universe to go through all of them.

You were also right to feel secure while sending your secret messages as a kid.