We should keep it secret

I enjoy amazing myself with technologies we use in a daily basis. A couple of days ago, while I was researching the possibility of improving my performance at a repetitive task (I was trying to do the lvl 87 of Candy Crush), I saw my screen invaded by an ad about an app that allowed me to pay services and taxes online. Stared at it a bit. Decided to take off my XXI y th century glasses and thought how amazing it is that I may, laying partially naked from the sofa at home, with hello kitty shorts and flip flops, pay the electricity, Internet, the phone... do all those troublesome tasks we monthly do.

So, where's the money, bills, gold, bitcoins, salt, anything that makes reference to an exchange of currency? Nowhere. Only me in my shorts and flipflops. Well, me and that gigantic network we call Internet.

Lets suppose that we grab a couple of Ethernet cables and arrange a LAN with two of our neighbors to play a match of Age of Empires II. Internet is exactly the same, but larger, connecting computers of (almost) the whole world, and with certain mechanisms, or protocols, that serve the purpose of identifying and transferring data among them.

The thing is distances are sometimes longer than the neighbor's house, but the need of playing Age Of Empires is larger (not to mention watching porn). So, we laid underwater cables that cross oceans and connect us with other continents. This is how I can communicate with my uncles at the USA so that they may show me live on HD the barbecue they are preparing, without need of having the pork chops to bounce at a satellite dish in space.

But there's a problem: since this is a network, to reach my uncles's house the data packets that I send have to go through a lot of other computers we call nodes. Now, what guarantees me that there wont be a guy in one of those nodes and laughing out loud about how raw that meat is? And yes, I'm using that example to not use the other potential one: Ingrid, a gorgeous German girl I met at a Biochemistry conference, IT IS MY PRIVACY, YOU WILL RESPECT IT. But, if privacy is not enough reason for you, it becomes critical if we are sending our credit card data! Or the data we use to make a bank transfer!!!

One could think that it's ok, everything is nice, safe and cute, but truly nothing guarantees me that there wont be somone intercepting that data.

Ok, forget it, lets go back to bartering. Paying the phone bill with cattle is kind of complicated, so we need to test something else. What about sending a message in such a way only the receiver may understand it? In other words, can we encrypt the message before sending it? Instead of sending it raw, we convert it into something unreadable, an encrypted text, it will only become readable after decrypting it. In this way, the method's security resides on what the receiver of the message may decrypt from it.

This is called cryptography, a very powerful discipline that since ancient times creates tools that allows us to send information in a safe way. And I'm not talking about your Whatsapp pictures where you try to avoid taking photos of any tatoos, face while you show the places of your body where the sun does not shine. I'm talking about serious stuff, like military instructions during WW2. Ok, yes, your Whatsapp pictures too, don't worry. Of course, like many scientific discoveries and Whatsapp pictures, their development was not always guided by the most innocent and altruist objectives in the world.

The procedures to make this conversion, or better called encryption algorithms are formed in base of a secret key and consist in mathematical accounts that take the raw message and transform them into an encrypted message. On the other side, the decryption algorithms do this task in reverse (Ha! you didn't see that coming, huh?), so only the ones that possess the secret key are able to decrypt the message.

This is easier to see in a concrete situation, lets resurrect the network we built to play Age of Empires. So, Mary, is very good looking, and now that you two know each other better you want to ask her out. For research purposes, say that you don't dare to ask her face to face, so you are going to ask her out with network messages (that's how it works, right?); but you don't want Peter, the other network user, to know anything about it. First, because of privacy, second, because he's way better looking than you; competitors are not good. Before you're even able to start the chatting at a tone you really like (high, kinky tone), Mary needs to know the key to decrypt your messages. You cannot send it over the network, because Peter may also see it! The safe exchange of keys is a problem by itself.

One option is to go to her house and give her the key in person, this is, transmit it over a Safe Channel. You will both use the same key to encrypt and decrypt the messages, this is called symmetric key encryption. But you don't always have a safe channel to send keys over, and you just don't dare to go face to face yet! Then you can use what is called public key encryption, each participant has 2 keys: a public one, sp that others may encrypt messages and send them to you, and a private key to decrypt messages. In this case, if Peter gets the public key there's no big deal, since only you have the private key that is used to decrypt the messages that were encrypted with your public key. Your private and public keys are mathematically related so that they may work this way. You only need Mary to make her own set of keys and send you her public one to start sending messages one to the other.

With this idea in our heads, during the '77 three guys invented a method to make this plausible. We know it as RSA (their surname's first letters), it is one of the most used cryptographic systems in the world.

This happened nearly 40 years ago. How is it that even today, with computers thousands of times more powerful, nobody "broke" it?

The security of the use of a public key resides in, even if the public and private key are mathematically related, it is impossible to calculate the private key by taking the reference of the public key (under a logic lapsus of time, of course). In RSA, the keys consist on large numbers, humongous numbers. And by the mathematical relation RSA imposes, the form to calculate the private key from its public key is taking a part of it and decomposing it into prime factors.

Yes, just as in school: 12 = 2 x 6; 6 = 2 x 3... Sounds easy, right?

No. it turns out that at the moment there's no algorithm that solves the factors of such huge numbers in a reasonable amount of time. Contemporary methods would take thousands of years to solve that equation.

What you can do in a reasonable amount of time is verify if the solution is valid. For instance, if someone told me that the factor of 123 is 3 x 41, I only need to multiply to see if the result is right or not. Like this one, there's a lot of problems that can be verified, if the solution is right, what we cannot do, is efficiently. It does not matter if we have an Intel 700 cores, slave midgets, soda and large fries. It's just not enough to make just "larger CPUs", because it is an algorithmic problem. The difficulty resides in; the time it takes to calculate the solution of these problems grows at an exponential rate as we have larger data input every single time.

The craziest part is, we do not know if there's not an efficient way of solving this algorithms, nobody came up with the brilliant idea; and algorithm that will solve the problems in a reasonable amount of time. As a matter of fact, this is one of the most important questions at math today. So important it is, that if you solve it you get a 1 million dollar prize. And a hug. And access to all the state secrets in the world and bank accounts... And Megan Fox's phone number.