Explained Like to a 10-year old: Public Key Encryption

As someone whose mental age never increased since it hit 10, I take this as my responsibility to explain stuff I find interesting to my fellow beings who may be often put off by verbose and jargon-rich topics. I love Wikipedia, but I get into this chain of reading the Wiki page for every term I don’t understand until it’s been 2 hours already and starting from Deepnet, I am now reading Intrusion Detection Systems. Not that it’s not great to read about interesting stuff, but I often lose sight of what I intended to learn about in the first place. I hope I can help on at least one topic today.

Each of the three words — Public Key Encryption already guide us in the right direction (yes, I am looking at you, “Smart Contracts” which are unarguably neither smart nor contracts).

Encryption

Encryption in the most simplified terms is making changes to a written message, such that just about everyone couldn’t understand it. Say, your parents are away for the weekend and you want to host a part on Friday secretively without your parents’ knowledge. You want to invite your friend. And for whatever made-up reason, because it helps me explain the idea with this hypothetical situation, let’s also assume that you communicate with your friend with letters (hey, hey, letter writing is a lost art).

The problem is before that letter reaches your friend, one of your parent might see it and read it, and there goes the plan for the most happening party ever. So you want to write something that your friend will understand but not your parents.

A simple trick is just substituting every character by another character in a systematic manner. For example, we can substitute every letter with the next one with Z being replaced by A (an example of Caesar Cipher).

“LET’S PARTY THIS FRIDAY” becomes “MFU’T QBSUZ UIJU GSJEBZ”, which now looks like complete gibberish. This “changed” version of the original text is often called cipher text.

A → B → C → D ….. X → Y → Z → A

But the tricky thing is, both the intended recipient and the writer needs to know how the letters are replaced to reverse the steps and recreate the original message by substituting every letter with the previous one with A being replaced by Z, i.e., going backwards from the above chain.

M becomes L, F becomes F, and so on…

A ← B ← C ← D ….. X ← Y ← Z ← A

Of course, this is easily broken if one tries all possible substitutions (think, how many such substitutions are possible?) which is not so difficult to do quickly with a modern computer.

There are also ingenious ways to uncover the original message without knowing the mapping AND without trying all possible substitutions. But the idea of encryption is simple — you want to send a message to only a limited intended receivers and don’t want anyone else to read and understand it, so instead of sending the text as it is, you change it and then send it.

Decryption is the reverse process, in which the receiver reverts the changes and gets the original message back with ease.

Key

This term stems from the lock-and-key analogy. If you wanted to inform your friend about your party plan, you could also buy a safe, somehow give him the key without anyone getting their hands on it. And whenever you want to send a message to him/her, write it on a piece of paper, keep it inside the safe, lock the safe and send it to your friend. He has the key to the safe and can open it and read your message. If someone manages to steal the safe, without the key they still wouldn’t know the message (unless, of course, they break the lock — which is called brute-force attack).

This is all there is — knowing the “key” in an encryption/decryption process is equivalently knowing how to get from the original message to a cipher text and vice versa.

In the example above, “LET’S PARTY THIS FRIDAY” becomes “MFU’T QBSUZ UIJU GSJEBZ” and the “key” would be the shift of 1 in substituting the letters. With that information, you can take any message in English and convert it to cipher text and if you happen to get a cipher text created using this key, you can reconstruct the original text. The example we just discussed involved a method of encryption — letter by letter substitution and a key — shift of 1.

Note: And no, this is not how your login passwords are being encrypted anywhere when you use a browser. This is just an example to take away the idea of encryption, because of the low security this encryption, it’s never used. The algorithms/methods involved in current day communication are too complex and without a computer, even after knowing the method, reverse engineering will take a loooooooooong time, if at all one manages to get there.

Public

In the example above, the same “key” is used during both encryption and decryption.

The security of a such a message relies on the author and only the intended receivers knowing the “key” and no one else, i.e., it should be private. After all, the whole point of doing all this nasty business was after reading the piece of paper, the parents shouldn’t know about the party plan but your friend does.

This is also an example of symmetric encryption, which is a fancy word for saying that both the sender and the intended receiver use the same “key” (substitution of every letter with the next one in the alphabet order) to encrypt as well as decrypt a message/cipher text, therefore, the “key” must be private (known only to a limited number of people).

There are also methods in which there are two “keys” — one of which is shared with just about anyone. The interesting thing is — just knowing the public “key” does not help in understanding the cipher text sent.

Public Key Encryption

Now that we know some basic terms and get an abstract idea, let’s explore the setup required for Public Key Encryption.

Let’s say there are 3 people involved — you, your friend and your dad. Each person trying to communicate with another person needs to have 2 keys each — one is private to only him/her and the other one is public, i.e., shared with everyone. For all you care, you could wear a tattoo with your public key and it wouldn’t matter, well, depending on your cool your parents are with that.

If you’re wondering, what a “key” here means, just think of a series of steps to take the original message to a version of cipher text, and depending on the algorithm used to do that, we would need one or two numbers to implement the algorithm. (Exactly like Caesar Cipher we looked at before, but for this substitution we need the key, i.e., the number of letters shifted)

Let’s look at who knows which key:

You know:

1. your public key (of course, since you’ve been making it public for anyone to read)
2. your private key (which only you know)
3. your friend’s public key
4. your dad’s public key

Similarly, your friend knows:

1. your public key
2. his/her public key
3. his/her private key (which only he/she knows)
4. your dad’s public key

And your dad knows:

1. your public key
2. your friend’s public key
3. his private key (which only he knows)
4. his public key (which we’ll see in a moment, no one cares about ;) )

The idea is instead of using the same key for both encryption and decryption (which is called symmetric encryption). The private-public key pair work in conjunction with each other. If the public key is used for encryption, the resulting cipher text can only be “read” using the private key, and similarly if the private key is used for encryption, the resulting cipher text can only be “read” using the public key. But whose public/private key? Each person has their own, how to decide which one to use?

The simple rule of thumb is if you want a text to be read only by person A, use person A’s public key for encryption before sending it to person A. Since the private key is needed for decryption (public-private keys work in pair, remember?) and only person with person A’s private key is person A, only he/she can read the cipher text. For everyone else, it’ll be plain gibberish.

Similarly, if you want someone to send you a message, you expect them to use your public key.

Taking our original example, you want to send a message to your friend and don’t want the message to be read by your dad, so you use your friend’s public key — which is completely public for everyone, including your dad, to encrypt your message and send it to him. If your dad gets hold of that message, he/she cannot “read” it since he doesn’t have access to your friend’s private key. Remember that, once you have encrypted your message using your friend’s public key, only he/she can decrypt it, that implies even you can’t understand what you’re sending after encryption, if you have a weak memory like mine and have already forgotten the message. ;)

If your friend wants to reply back, he/she uses your public key for encryption and again, the only people who have access to your private key, i.e., only you can read the reply.

This, my friend, is how you can keep your parents out of the loop. And in the process, you learned a bit about encryption, symmetric encryption, public key encryption.

In case you’re wondering how do such public-private key pairs work, the idea is that some mathematical function are easier to compute in one direction — like given two large prime numbers, it’s easy to multiple them together, but if you’re provided with the product of two large prime numbers and are asked to find the prime factors of this number, the process is not straight forward. Don’t believe me?

Take the prime numbers 23 and 71, and find their product. You can easily do this to get 1,633. Even if the numbers had been actually big, it wouldn’t have mattered too much. But if you were given 1,633 and asked to find the prime numbers whose product is 1,633: it would take you a while to reach 23 (if you try every prime number starting from 2) and once you have 23, you will quickly get 71 after division.

We can see two things here:

1. the computation is easier in one direction but reversing it takes much more time (imagine prime numbers of 50 digits getting multiplied to give a much larger product.)
2. once you know one of the two, getting the other prime factor is straightforward.

Think, how does that translate to having a private key and a public key?

I am explaining already a bit in detail about a specific Public Key Cryptosystem called RSA Cryptosystem, but I’d like to stop here and cover this in detail in a separate post with a plain implementation in Python