Asymmetric Encryption is Magic

The key distribution problem has plagued symmetric encryption since day one. If you need to send a secret to someone, getting the key to them without it being intercepted is a real issue. Sure, you could meet in a dark alley and whisper it into their ear but what if they live on the other side of the planet? Would you trust your phone or the mail? You shouldn't.

Asymmetric encryption is the answer.

Asymmetric (aka public-key) cryptography is a cryptographic system where you have two different (i.e. asymmetric) keys. One public and one private. As the names imply, private keys are secret and public keys can be shared anywhere. Hell, put your public key on a billboard, it doesn't matter. Keep that private key secret though.

The magic here is that anyone can encrypt messages with your public but only you can decrypt it using your private key.

I'm getting ahead of myself though. First we need to understand one-way functions.

The One-Way Function

In the 70s Whitfield Diffie, Martin Hellman and Ralph Merkle were trying to solve the key distribution problem and got obsessed with this mathematical concept.

A one-way function (unlike a two-way function) can't be easily reversed.

Say we have a function that doubles numbers:

f(x) = 2x

This is a two-way function because it's easy to deduce x. If x = 4 then f(4) = 8. If f(x) = 128 then x = 64, right? For most functions we can home in on the solution with minimal effort.

However, one-way functions don't work like this. Think of a one-way function like smashing a window. It's easy to break the thing but try putting it back together. One-way functions are easy to compute but make it difficult to get back to the inputs.

Modular Arithmetic

Using mod is "one way" (heh) to produce one-way functions.

If you are unfamiliar with modular arithmetic check this article from Khan Academy and get yourself educated.

Consider this two-way function

f(x) = 2ˣ

If we say 2ˣ = 128, this is easy to deduce. However, if we add some modular arithmetic things get wonky. Given 2ˣ(mod 6) = 2 what is x? Well:

x                 1   2   3   4   5   6   7   8
f(x) = 2ˣ         2   4   8   16  32  64  128 256
f(x) = 2ˣ(mod 6)  2   4   2   4   2   4   2   4

Notice that f(x) = 2ˣ grows predictably but adding mod causes this repeating thing, making it difficult (impossible) to tell which value of x we started with. In other words, with modular arithmetic, you can't put the broken window back together.

Why does this matter? Well, as Martin Hellman realized, this sort of one-way function can be used to exchange public information without sharing any secrets.

The classic names in crypto explanations are Alice, Bob and Eve. I'm sick of them, let's meet Ron, Leslie and Tammy (our eavesdropper).

Using this general mod function is the ticket:

f(x) = Yˣ(mod P)

Over an unsecured line Ron and Leslie decide that Y = 9 and P = 13. Here's what happens next:

Leslie chooses a secret x value, say 5.
Ron chooses his own secret x value, say 7.
Leslie solves her one-way function... 9⁵(mod 13) = 3 (call this L).
Ron solves his one-way function... 9⁷(mod 13) = 9 (call this R).
Leslie and Ron share their results (3 and 9) with each other.
Ron solves for Leslie's value (L = 3) using Lˣ(mod 13) => 3⁷(mod 13) = 3
Leslie solves for Ron's value (R = 9) using Rˣ(mod 13) => 9⁵(mod 13) = 3

Look at that, they both got the same exact value, 3. Magic! This can be used as a key.

Now, say Tammy was eavesdropping.

She first learns that Ron and Leslie are using the one-way function f(x) = Yˣ(mod P) and that Y = 9 and P = 13. Steps 1 - 4 are done in private but, at step 5 Ron and Leslie must share important information once more. Tammy learned that Leslie came up with the answer 9 and Ron came up with 3.

Here's what Tammy now knows:

9ˣ(mod 13) = 9
and
9ˣ(mod 13) = 3

So, what is x? Hard tellin' not knowin' as my buddy Peter would say.

Since these numbers are small you could probably get to the right answer but doing this with huge numbers for Y, P and x make this incredibly difficult.

Hellman's discovery was a cryptographic revolution. It proved that public information could generate a key that no one but Leslie and Ron could deduce. They'd would no longer need to meet in a dark alleys. The key distribution problem was solved... sort of.

A Special Type Of One-Way Function

Diffie-Hellman-Merkle key exchange, though revolutionary, was a total pain in the ass. However, it led Whitfield Diffie to theorize a new type of one-way function. One in which a message could be encrypted using one key and decrypted only by using a different key. In other words, an asymmetric one-way function.

RSA

Ron Rivest (R), Adi Shamir (S) and Leonard Adleman (A) got all fired up on what Diffie, Hellman and Merkle had going and after a year or so of painstaking effort Ron had a bright idea. Basically, he combined Diffie-Hellman-Merkle key exchange with the problem of prime factorization.

For large primes, factoring their composite can take a crazy long time. In other words, given N = pq (where p and q are massive primes), good luck learning p and q if all you know is N.

He realized that the primes p and q could act as a secret key and their composite, N, could be the public key.

How does this enable asymmetric encryption? Let's dig into the RSA algorithm itself and find out.

Encryption with C=Mᵉ(mod N)

That looks familiar right? Diffie, Hellman and Merkle were so close.

Recall that N = pq where p and q are secret/massive primes. What about this C, M and e business?

C is our ciphertext (represented as a number)
M is out plaintext (represented as a number)
e is another public value chosen by Leslie which makes up the rest of the public key.

If Ron wants to encrypt M and knows e and N what does he do? Convert the plaintext to a number and plug and chug.

Let's look at an example.

For simplicity sake I'm going to go with the same example from The Code Book (Appendix J). The numbers are small to keep it simple but in a real life situation these would be a lot bigger.

Before anything happens Leslie has to pick her primes and her e value. She goes with p = 17, q = 11 and e = 7. Therefore N = 17 × 11 or 187.

Technical side note: e and (p - 1) × (q - 1) should also be "relatively prime."

Ron wants to send Leslie something very simple, say, the letter X as in "No Leslie, I will not approve funding to fill the hole and build a park." Using ASCII we convert this character to the number 88. There's our M value.

Check out my article on number systems, encoding and more if you need to understand how this conversion works.

Since Ron knows Leslie's public key (e = 7 and N = 187) he plugs like so...

C = 88⁷(mod 187)

Now we chug. If you work this out you'll find that C = 11 which is our ciphertext!

Since C = Mᵉ(mod N) is a one-way function, getting from 11 back to 88 is difficult without knowing p and q. Extremely difficult if the primes are large enough. In other words, even if Tammy learns the values of C, e and N she cannot deduce M.

Decrypting

How is Leslie going to do it? Another equation.

Using her secret primes (p and q) and the public value e she can calculate a number d which acts as the decryption key.

 e × d = 1(mod((p-1) × (q -1)))

Plug and chug...

7 × d = 1(mod (16 × 10))
7 × d = 1(mod 160)
d = 23

From this Leslie can use a familiar formula (M = Cᵈ(mod N)), swapping e for d and M for C. In other words:

M = 11²³(mod 187)

Work that sucker out and you've got M = 88. Our plaintext! Now all Leslie needs to do is convert that into a character and she'll get the letter X. Pretty cool right?

Why Primes?

This was my first question. It turns out that the composite result (N) of two multiplied primes will have only four factors: 1, itself and the chosen primes p and q. This creates a needle in the haystack sort of problem.

On the other hand, if p and q are not prime, N will likely have more factors and more factors mean the problem of finding p and q can be broken into smaller problems, streamlining the factorization process.

Using current factorization methods, when p and q are large enough and prime, even with massive computing power, it's going to take a lot longer than you have to find them.

Which begs the question, how large should primes be?

At least 1,024 bits.

That's a number with 309 digits. If you're really paranoid use 2,048 bits (617 digits).

In 2009 a group of 13 people factored a 768 bit composite number (232 digits) successfully. It took 2 years and at the time of this writing it's the largest prime composite ever factored. If you're feeling motivated there are real cash prizes for successfully factoring some of these... $100,000 for a 1,024 bit composite and $200,000 for a 2,048 bit composite.

Why so much focus on RSA?

The title of the post isn't "RSA is Magic" right? Well, there are indeed other asymmetric encryption algorithms but most of the time when people say "asymmetric encryption" they mean RSA.

Uses

Asymmetric encryption is slow. Finding sufficiently large primes is a process in itself and having a huge M value can really take it's toll on a CPU. You wouldn't use RSA to encrypt War and Peace but you may use it to encrypt a symmetric key that was used to encrypt War and Peace (with, say, SHA-256). In essence it acts as a key distribution solution for the more traditional symmetric schemes.

A well known example of an end to end asymmetric/symmetric encryption system is Pretty Good Privacy or PGP.

Asymmetric encryption is also often used for digitally "signing" data. I'll save the details but basically a private key can be used to "sign" a message and the public key can be used to verify that it's from the person you expect it's from.

There's your primer. If you want to learn more dig into the links below (I highly recommend The Code Book).

Enjoy!