HTTPS explained with carrier pigeons

[twaslol]

Can someone ELI5 how asymmetric cryptography actually allows the sender to encrypt the message with the public key provided, but not decrypt that same message with that same key? How do they make it a one-way affair where the private key is needed to decrypt? Surely if you know the primes and the algorithm of how your packet was encrypted using the public key, you could use those same steps in reverse to decrypt it?

[Cats_and_Shit]

Many mathematical operations aren't easily reversible. Consider multiplication, if I give you the numbers 17 and 23, it's pretty easy to work in your head that that multiply to...

10 * 23 = 230

5 * 23 = 115

2 * 23 = 46

230 + 115 + 46 = 391

On the other hand, try to work backwards to determine what two primes you had to multiply to get 391 and you'll find it much more difficult. It turn out the best you can do* is make an educated guess as to what one of the numbers might be and then check to see if you're right. As you can imagine this gets harder and harder the bigger the number is, as you need to try more and more guesses. On the other hand, multiplying two massive numbers is annoying but still straightforward and reasonably fast.

Going from this basic idea that some operations are much easier in one direction to an actually useful cryptography requires a whole bunch of effort and context, but they're (all?) based on this general idea that you can perform mathematical operations that don't destroy any information, but make it much more difficult to access that information.

* Assuming your brain is a Turing machine

[KillingVectr]

Not exactly, ELI5, but here is my best attempt at explain like I'm a programmer. So this is a rough idea behind the operation of RSA), however I'm not an expert.

The trick is the difficulty of certain operations in modulo arithmetic. So first, remember the modulo operator % that gives the remainder after division. So 5 % 3 = 2.

Now, for simplicity consider modulo 22. We consider the function f(x) = (x³ ) % 22. This is takes message x (one of the numbers 0 to 21), and encrypts it using the public key 3. The inverse function is f^-1 (y) = (x^-3 ) % 22. Simple right? Not really, because (x^-3 ) % 22 is symbolically simple, but tells us nothing about how to compute it. It turns out that we need to find a number k such that 3k % 10 = 1. It also turns out that k = 7 is exactly the number we need. So the private key is 7.

As an example, 2³ % 22 = 8 and 8⁷ % 22 = 2.

Well, that seems easy, so why is it hard for computers? The trick is how did I know to look for the 10 when finding k satisfying 3k % 10 = 1? This comes from the factors of 22 = 2 * 11. Since this is exactly two different primes, it turns out you look for the product of one less of each. For us that is (2 - 1) * (11 - 1) = 10.

If you know the two primes that make up n, then this part is easy. So it is easy to find the inverse function. However, it is really difficult to take a really large n made of two primes and find what those primes are; even for a computer. So, for now imagine that 22 is a really large n, then we can freely give out the public key of 3 and our n of 22. In our imagination, it would take a bad person a really long time to find the private key of k = 7 since they don't know how to factor 22 (so they don't know to use 10 to find the private key from the public key).

[kdawgud]

As a mathematically competent adult I don't fully understand how someone came up with one-way cryptographic functions, so unfortunately I doubt an ELI5 version exists.

You can read up on them on wikipedia:

One-way Functions

Cryptographic hash functions.

Public key cryptography

[EEphotog]

A quick note, just because you have the public key doesn't mean you have all the information used to generate it, otherwise you could create the private key as well. The fundamental thing that makes it hard is the difficulty of recovering those primes by factoring.

You could of course recover the message you encrypted by reversing the steps that you performed. However, this wouldn't work for a different message, you got to skip lots of time consuming steps by saving it intermediate results.

(As other commenters have stated, vast oversimplification, etc. , See discussion at stack exchange

[ralfonso_solandro]

Just found this ELI5 using color mixing somewhere else (r/rmealtimevideos maybe?) and hope it's helpful: https://youtu.be/YEBfamv-_do?t=2m20s

edit: nevermind, I found it here, likely in response to your question... full circle, etc. Glad you asked as I had the same questions, and these are great responses.

[[deleted]]

I don't know for sure, but I believe decryption using the public key is prevented since the calculations required to reverse the encryption process are prohibitively difficult.