---

What is it good for?

Remember from Symmetric Key Cryptography, both parties need to have the same keys in order to communicate with each other securely. But there is a problem, how can they decide upon the keys without letting an eavesdropper listen to the conversation. And remember, at this point, they are not encrypting their messages, since we need keys for encryption, and agreeing upon which key to use is the main problem.

Someone can easily listen to your conversation on the internet, there is nearly no perfect solution against this (we cannot prevent other people from listening to our conversations). But we can encrypt our messages, and even if they receive our messages, they cannot decrypt them without the necessary keys, rendering this malicious activity useless.

Coming back to our main problem, how can 2 parties (namely Alice and Bob) agree upon a secret key, without letting an eavesdropper (Eve) learn about this secret key? Public Key Cryptography is the magic, that solves this problem.

In short, Alice and Bob can securely agree upon a secret key, and the eavesdropper Eve cannot learn the value of secret key, even if she is listening to the communication.

---

How it works?

I can directly give you the technical definitions and math equations, which will prove that the system works. But probably you wouldn’t understand WHY is it working.

So, let’s start with a high-level abstraction. Say, our keys will be represented by colours. And in this fantasy scenario, Alice has the colour(key) RED, whilst Bob has BLUE. They keep these colours(keys) to themselves, in other words, these are private keys. Private keys are meant to be private, you never share them.

Don’t ever share your secret keys

Anyone with a brain

So, Eve does not know about Alice has RED. and Bob has BLUE, since this private information is not being communicated.

Although not being helpful to our case, notice that Alice is fatter than Bob.

Now, both Alice and Bob, agree on a new random colour, YELLOW. If you are a smartie, and asking the question “BUT EVE WILL LEARN ABOUT YELLOW!!”. Yes, Eve (who is eavesdropping) can learn about this YELLOW, it’s okay :)

This YELLOW is representing the public key, which means, everybody can know about it, there is no privacy for this information.

As the next step, Alice will cover her private key, with the public key (she will simply mix the colours RED and YELLOW together, achieving an orangey colour. Bob will do the same, mixing YELLOW and BLUE together, ending up with a greenish colour.

We are almost there! Now, Bob and Alice will send these mixed-up colours (orangey for Alice, greenish for Bob) to each other. Again, Eve can learn about these messages, since we are assuming that she is able to listen to the conversation.

And it’s done! Bob will use his private key (BLUE), to mix with the orangey colour that Alice sent, and will end up with a disgusting colour probably (brownish). Also, if Alice mixes her private key (RED) with the greenish colour Bob sent, she will achieve the exactly same disgusting colour as well. They will do these final mixing on their own, without telling anybody, so Eve will not learn about this process.

What did we get? Alice and Bob now have access to a key (that brownish colour), which is secret, and hidden from Eve. They can use this key to apply Symmetric Key Cryptography for their communication from now on.

---

Problems in this representation (and how we fix it)

Although colour-key metaphor is brilliant, it is inaccurate at one point. Consider this: if Eve knows the public key YELLOW, and she also knows that Alice sent orangey colour to Bob, can’t she figure out Alice has RED by using her superior knowledge on colours?

The answer is: YES. And that’s why, we are not using colours.

After here, it will get mathematical, if you are not interested in the technical details, and convinced upon how the public key cryptography works in the big picture, feel free to skip the below part altogether, and confidently claim that you know how public cryptography works, in a sophisticated talk, just by explaining it with colours. I’m not kidding.

If you want to know the solution to the above problem, I present you, the mighty ONE-WAY FUNCTIONS:

Let’s identify the problem, we need a function, that Alice can compute ORANGE from RED and YELLOW easily, but Eve cannot compute RED from ORANGE and YELLOW easily. Probably you remember our encryption and decryption functions from Symmetric Key Cryptography.

$$encryption \rightarrow f(x, s) = x+s = y$$ $$decryption \rightarrow f^{-1}(y,s) = y-s =x$$

We are going to develop something really similar:

$$easy \rightarrow f(red, yellow) = orange$$ $$hard \rightarrow f^{-1}(orange,yellow) = red$$

The difference is, both the encryption and decryption were easy to perform if you know the inputs. In this case, we want the hard function to be infeasible (Eve cannot compute it). It might be sounding stupid and impossible to design such a problem (easy to compute in one way, hard to compute in the other way). But in fact, it is possible. A popular one-way problem is prime factorization. If I were to give you 2 prime numbers (say, $p$ and $q$), you can multiply them, and get their multiplication (say $n$) without any difficulty.

$$pq = n$$

Yet, if I were to give the $n$, and want you to find me $p$ and $q$, then your best chance is to brute-force, trying all the combinations one by one, without any efficient algorithm. On top of that, if $p$ and $q$ are large numbers (I mean 49048569048509823487234568947 is kind of large), good luck to you finding $p$ and $q$ before humanity extinct.

$$easy \rightarrow f(p, q) = n$$ $$hard \rightarrow f^{-1}(n) = p, q$$

You may be not convinced that how prime factorization solves the problem we have at hand, and you are right to be not convinced. Because the examples are not matching. In the colour metaphor, Eve had to compute the hard function, which has 2 inputs (ORANGE, YELLOW), and 1 output(RED). Now, we are asking Eve to compute 2 outputs (ORANGE and RED?) with a single input(YELLOW). It’s not fair! Eve already knows more than 1 input.

$$hard \rightarrow f^{-1}(orange,yellow) = red$$ $$hard \rightarrow f^{-1}(n) = p, q$$

Well, yeah… Prime factorization will not solve our problem. The reason I explained prime factorization is, it is easy to understand for all the audience, knowing the 4 basic operations (addition, subtraction, multiplication, division) is enough to understand prime factorization. And this alone, proves that, one-way functions do really exist, and there are variations of them.

Don’t worry, there exists a one-way function, which perfectly fits our scheme, and I will explain it now. Why did I not explain it in the first place? Because it is more complicated than prime factorization, requires you to know how to do modular arithmetic (and some people may not know this). I did not want to scare you off :)

Now, if you want a perfect example for our case (a scheme that can replace the colour metaphor), it would be Discrete Logarithm Problem. Say $g$ is a random integer, and we have a secret input $x$. And keep in mind that we will do all our operations in modulo $n$ in this setting.

If I raise $g$ to the power of $x$ in modulo $n$, I will get a new integer $h$. This is easy to compute.

$$h = g^x mod n$$

But if I provide you with the values of $g$ and $h$ (everybody knows $n$ in this setting, it is implicit, and no need to give it to you personally), and ask you to compute $x$, this will be really hard.

$$easy \rightarrow f(g, x) = h$$ $$hard \rightarrow f^{-1}(g, h) = x$$

---

Summary

Now you know the logic behind the Public Key Cryptography (thanks to colours). And you know how it is implemented in real-world (one-way functions, and a bit of mathematics).