This Video was Not Encrypted with RSA

Last time, we discussed symmetric encryption protocols which rely on a user supplied number called the key to drive an algorithm that scrambles messages.

Since anything encrypted with a given key can only be decrypted with the same key, then Alice and Bob can exchange secure messages once they agree on a key.

But what if Alice and Bob are strangers who can only communicate over a channel monitored by eavesdroppers like Eve.

How are they supposed to agree on a secret key in the first place?

Symmetric key protocols like AES-- the Advanced Encryption Standard-- are simple, fast, and for all practical purposes, unbreakable.

But unless they can time travel, Alice and Bob can't use a symmetric key to share that key in the first place.

This chicken and the egg problem is the Achilles heel I alluded to last episode.

Yes, Alice and Bob could share a key in person or through a courier.

But typically, offline exchanges like this are impractical or impossible.

Now sense in practice AES directly encrypts almost everything, there's clearly got to be a way for Alice and Bob to get over the key sharing hump.

Actually, broadly speaking, there are three ways.

And in this episode, we'll discuss two of them and foreshadow the third that we'll get to another time.

Here we go.

Option one for sharing a symmetric key is don't do it at all.

Instead, use asymmetric key cryptography, also known as public key cryptography for reasons that will be clear in a moment.

The idea here is to use two keys with the property that anything encrypted with one of them can only be decrypted by the other.

Not to work as I just described, these keys will have to be related somehow.

And we'll come back to how they are generated shortly.

But for now, let's just assume these key pairs exist and outline the steps used to communicate securely with them.

Here are the steps.

Alice generates two keys.

She disseminates one publicly and keeps the other private never sharing it with anyone not even Bob.

Bob follows suit.

Now to send Bob a message, Alice encrypts it with Bob's public key.

Why?

Because only Bob knows the counterpart key.

That's his private key.

So only he can decrypt that message.

And of course, Bob could message Alice using her public key.

Note that Alice can also use this system to authenticate herself to Bob.

How?

Well, first she encrypts a message with her own private key and then encrypts that result with Bob's public key.

When Bob decrypts the outer layer, he still sees an encrypted inner layer.

If he can decrypt that with Alice's public key, then he knows the message was encoded with Alice's private key, meaning she in fact sent it.

Now extrapolate.

If everyone generates a key pair and publishes half of the pair, then anyone can in principle communicate securely with anyone else, even if the conversing parties had never previously spoken or even met.

Now the nitty gritty.

How do we actually generate a pair of keys that function like this?

Because the fact that the keys have to be related seems to be a flaw in the system.

I mean, if I know the protocol for creating keys, which is public, and I know Alice's public key, which is also public, then there has to be a way to reverse engineer her private key.

And in fact, there is which means that an asymmetric key scheme will only be viable if the math you use under the hood guarantees three things.

First, that the keys will actually work in tandem like this.

Second, that synthesizing the keys is fast and easy.

And third, that reverse engineering the private key from the public one while theoretically possible is computationally infeasible.

In short, we need something called a one way function-- some operation that's easy to do but exceedingly difficult to undo.

In the famous RSA protocol, the one way function is plain old multiplication.

I won't get into details because so much has been written about this elsewhere.

But in a nutshell, RSA begins by choosing two prime numbers at least one of which has hundreds of decimal digits.

Those primes then get multiplied to form a large composite number, n. If you know the prime factors of n, and you do since that's how you built n in the first place, then it turns out that you can also produce two other numbers e and d with the following fascinating property.

In mod N arithmetic, raising any number m to the e power and then to the d power, or vise versa, will give you back the original number n. In this picture, n is the message you want to send.

n and e are published together as a public key.

And d is kept private.

Now technically the modular exponentiation that we just performed is also a one way function.

Raising something to the e-th power mod N is easy.

But taking an e-th root mod N is really hard.

The reason we don't identify that as a one way function in RSA is because there is another attack against RSA, a so-called trap door.

Namely, given how they are generated, d could be deduced from e if you knew the prime factors of n. And this is why we identify multiplication, which can only be undone with super slow factoring, as the relevant one way function in RSA.

And because factoring is so much slower than multiplication, the private key is de facto safe despite having n out in the open.

Now here's the dirty little secret of crypto.

Modern factoring algorithms have actually gotten pretty good.

RSA can stay a head of these algorithms, but it does so by using even bigger n values, i.e.

longer keys.

And this comes at a cost.

Already, asymmetric encryption schemes are thousands of times slower than symmetric ones.

And they use way more computational resources.

If on top of that, you keep generating ever more gigantic keys than this overhead can become a problem, especially on mobile devices where the processors are weak and power is scarce.

Now I just said that all asymmetric schemes are slow, even without extra huge keys.

For this reason, most real world encryption relies on a hybrid scheme.

And this is option two for Alice and Bob.

They will encrypt stuff quickly and inexpensively via a symmetric protocol like AES.

But they'll use an asymmetric scheme up front just to transmit the shared symmetric key as a message that Eve can't read.

Note that this is why cracking RSA would compromise symmetric encryption even though symmetric encryption has nothing to do with factoring large numbers.

It's because the main thing you encode with RSA is symmetric keys.

Now for extra safety, most modern web security protocols don't allow reuse of either the symmetric or the asymmetric keys.

You generate a public-private key pair for just your current session.

And you use that pair to share a symmetric key that you also throw away after that session.

Nevertheless, if you encrypt upfront with RSA and RSA gets cracked, everything will fall apart.

And this vulnerability, along with the increasing bloatedness of RSA keys, raises two interesting questions.

One, if we are going to use asymmetric encryption are there any other one way functions we could base it on for which the undo algorithms are slower than the ones for factoring?

Because if there were, we could get away with smaller keys.

And second, does the option three that I referenced at the top of the episode actually exist?

In other words, is there some other way for Alice and Bob to share a symmetric key besides full blown asymmetric encryption?

Now, as it turns out, these questions are related.

And the answer to both of them is yes.

Diving into why will take us into much heavier math, specifically cyclic groups and finite fields.

And we'll do that in upcoming episodes.

In the process, I think you'll get a much clearer picture of how real world encryption actually takes place.

See you soon.