Public Key Encryption: Layman's Explanation

Factual Questions
1

I did a search on this and the SDMB search engine was not kind - the word “public” turned up hundreds of threads. Of the few hundred I checked I couldn’t find a reference to this one, so hope I am not repeating someone here…

I know that public key encryption is one of the more “unbreakable” commonly available approaches. Can someone explain how it works in a way that a non-codes, non-math-heavy layman like myself can understand?

And what can you tell me about the phrase “public key”? As a phrase, it sounds antithetical to the concept of encryption - if the “key” to the code is a “public key” how can the code be secure?

Thank you!

2

Okay… explanation in two parts, to the best of my abilities:

  1. The requirements. Normally, for an encryption encoding method, all people are capable of encoding and decoding all messages… generally it’s easy to decode any message simply by reversing the encoding process. The idea of public key encryption is basically "Let’s come up with a system where everybody else using the system can encode messages, but only WE will be able to decode them. We could even publish the encoding instructions in the newspaper or whatever if we wanted to, any joe off the street (if he’s relatively bright) would be able to follow them and encode, but not to decode.

  2. This requires, obviously, some operation in the encoding step that cannot easily be reversed for decoding. This is generally accomplished in terms of multiplying large numbers, or something of the sort… it’s very easy to take 11 and 17 and multiply them into 187 - it’s harder to take 187 and, from scratch, figure out which two prime numbers it factors down into. When you can replace 11 and 17 with 9-digit primes, the factoring can be almost impossible, without tying up thousands of computers for hundreds of years, or getting yourself a quantum computing system (which don’t really exist yet, right??)

Exactly how they work out the details of the multiplication into the encoding step to make it nonreversible without factoring, I’m not quite clear on, and apologies if I’ve managed to confuse the issue. :slight_smile:

3

The basic idea in public key cryptography is that you use a different key for decryption from encryption. One of those keys will be the public key, the one that you publish(or at least don’t care if anybody finds out about), and the other(your private key) you have to keep very secret.

For example, say Bob wants to send an encrypted message to Amy. He can use Amy’s public encryption key to encrypt the message and be sure that only Amy can read the message, because only Amy has the private key. If Amy wants to send a reply, she’ll use Bob’s public encryption key.

In practise, however, this doesn’t quite happen. Public key encryption is much slower than symmetric key encryption(the “normal” kind, where the same key is be used for encryption and decryption). So what actually happens is that Bob sends a message encrypted with Amy’s public key that says “I want to talk to you securely.” Amy sends a reply encrypted with Bob’s public key that says “Ok, we’ll use this symmetric key for all future messages.” Bob and Amy can then communicate securely using the faster symmetric key encryption algorithm. So they have all of the benefits of public key encryption(namely, you don’t need to distribute keys) without the cost of doing public key encryption on every message.

4

If you need a non-technical example: Consider that you’re sending a box to a friend. You put two locks on it: One you keep the key (private key); the other, you tape the key to the box (public key).

Your friend gets the box. She uses the key taped to the box to remove the lock. Then she puts her own lock on the box (keeping the key – her private key) and sends it back to you. She also tapes the public lock and key to the box.

You get the box. You use your private key (the one you kept) to remove the lock on the box. You put the lock taped to the box (actually, this would also work if the public lock remained on the hasp) on the hasp, with her lock. Then you send the box (which had her lock on it) back to her, again, with the key to the second lock taped to it.

She now has the key for both locks: the public key is taped to the box; and her private key stays in her possession.

So, by diagram:

You --> Box with yourlock & publiclock --> Her
She --> Box with herlock & yourlock* --> You
You --> Box with herlock and publiclock --> Her

Note that at no time can having the key to the publiclock (i.e., the public key) let anyone open the box – there will always be one lock that has a private key. Also, they keys don’t have to be exchanged: you can keep yours, and she can keep hers.

With computers, instead of keys, you have numbers.

*And publiclock in this example; with computers, you just need to know the public key.

5

It certainly does happen in practice - this is how PGP works, for email and other things. Speed doesn’t really matter for desktop applications.

6

Which systems use public key encryption for bulk data? Certainly not PGP.

7

Nope – PGP uses public key encryption to exchange a symmetric key, which is used to encrypt the data. More on PGP.

8

Woah. I stand corrected.

9

Encryption works by having a set way to jumble up data so that it appears random. For instance, you could use a formula that you add each digit in a key to each digit in the data in a loop.

key = 1234
data = 9875204565651930

encrypt = 9 + 1, 8 + 2, 7 + 3, 5 + 4, 2 + 1, 0 + 2, 4 + 3, 5 + 4, 6 + 1, 5 + 2, 6 + 3, 5 + 4, 1 + 1, 9 + 2, 3 + 3, 0 + 4
= 0009327977992164

decrypt = 0 - 1, 0 - 2, 0 - 3, 9 - 4, 3 - 1, 2 - 2, 7 - 3, 9 - 4, 7 - 1, 7 - 2, 9 - 3, 9 - 4, 2 - 1, 1 - 2, 6 - 3, 4 - 4
= 9875204565651930

So even though the encrypted version does not look anything like the original data, it is obvious that there is a mathematical relationship between the encrypted data and the key that was used, and that relationship is the encryption method.

Now if you wanted to break this and knew the method, all you have to do is take the encrypted data and start trying numbers as the key. Eventually you will figure it out (since usually the original data will be meaningful to a human instead of just some random number I made by hitting keys.) Also, there may be ways to detect the key based on flaws in the encryption method. For instance, in the above scheme, if we weren’t paying attention and encrypted 000000000000000000 and sent it out, the encrypted version would be 123412341234123412…so yeah the person might guess what the key you are using is.

Now, let us assume that the people who make encryption methods are really, really smart and can think of mathematical ways to jumble up data that seem impossible to us.

In a simple encryption scheme like the one I used, you jumble the data by applying the key to it using some sort of math. To decrypt you simply reverse what you did to encrypt it. So if your process to encrypt is to add the key to each digit, you decrypt by subtracting the key from each.

If, however, we used multiplication and division instead of addition and subtraction, a magical thing happens. On computers, the amount of time it takes to multiply is much smaller than it takes to divide numbers. For instance, it may take 20 microseconds to get the result of multiplying any two numbers, but take 200 to get the result of any division operation. Addition and subtraction generally take the same amount of time.

This means that in any given moment one computer could send out hundreds of encrypted items, but another computer could only decrypt a tenth of those in the same amount of time. And it means that if you are trying to crack the encryption, it’s going to take your computer a lot longer to try every single possibility than if they had used addition and subtraction. And all the time you’re doing that, the person sending out encrypted messages will be changing his key periodically.

If the average length of data is, for instance, 500 bytes, and we need 20 microseconds to encrypt each byte and 200 to decrypt each. Plus we say that the minimum length of a key is 32 bits.

32 bits for a key means there are 4294967296 possible keys. It will take a person trying to figure out our key an average of 100000 microseconds (200 microseconds * 500 bytes) or, 1 second. On average, he will have to go through half of all the keys before he could find our key. So it will take him 2147483648 seconds from the time we start using a new key until it is broken. That is, about 4189 years.

Because it takes him longer to decrypt than it takes us time to encrypt, we automatically get 10 times the amount of time it will take before he can break the key, where otherwise we would have to use a key that is ten times longer.

But no encryption scheme is unbreakable. Just, like the above example, you can know how long it will take to break and make sure that the minimum key size is large enough that it is unfeasible to try and brute-force it (unless you have 4189 years to spare…)

However, since any encryption method has a relationship between the data and the key, it is theoretically possible to come up with ways to determine the key from the data running a smaller number of tests than a full brute-force attack will take. So a second part of coming up with an encryption scheme is figuring out all the shortcuts and determining that the key is long enough and the shortcut non-specific enough that it will still take 4189 years to run (given current computing speeds.) As computing speeds rise, though, you may have to increase the key-length. Or if more and better shortcuts are discovered, the encryption scheme itself might have to be scrapped.

Since encryption schemes are based around certain mathematical operations that work nicely for being able to munge and return data, any time a shortcut is determined, it will be applicable to the entire field. When they create new encryption schemes, they aren’t just coming up with random things to do with data. They know that certain operations can be performed in a certain order, and that given current and theoretical shortcuts, any given method will have a set probability for how long it will remain a viable method. It just relies on advances in finding shortcuts to be an evolutionary process rather than one where sudden revolutionary ideas can appear which flip everything on its head. So there it is a question of whether modern day mathematicians have advanced to a point where revolutionary ideas of that potential impact are all that probable.

Now, as to the basic question of “public” keys. Well getting back to the idea that cryptologists are really, really smart; public keys work through a method where you can have a function which spits out two numbers that are mathematically related if you use them as keys in a particular order in a particular encryption/decryption scheme. Specifically, if you try to do the reverse of what you did to encrypt the data, you will not get the original data back. It’s been munged in a way that makes the original key insufficient to return the data to a meaningful form. Using the private key, however, you can get the data back.

This isn’t any more secure, or any less breakable, it’s just really damn impressive that mankind was able to come up with such equations which are actually able to make it happen with mathematical certainty.

10

There have been some great explanations in this thread, WordMan, but if you want something very basic about how public-key encryption works:

There is a style of encryption that uses two different keys. If you encrypt (“lock”) your message with one key, then it can only be unlocked with the other one. You keep one of those keys secret. That’s called your “private key.” You tell everyone about the other one. That’s called your “public key.”

There are two ways to use this pair of keys.

To receive private messages, your friends just need to encrypt (“lock”) the message with your public key. Since the message can only be decrypted (“unlocked”) with the key it wasn’t encrypted with, you’re the only person that can read the message.

To digitally sign messages, you encrypt them with your private key. Anyone can unlock and read the messages using your public key. If your public key works for decrypting the message, then your private key must have been used to encrypt it. This guarantees that the message actually came from you.

As is obvious from Sage Rat’s explanation, it’s really much more complex than that, but this should explain the basics.

11

Wrong. At least, theoretically wrong, although this is very close to true in practice. There is an encryption scheme, called the one-time pad, that isn’t even theoretically breakable assuming it is used correctly. It is so difficult to use correctly, however, and so insecure if it is misused, that it’s (almost) never used in the real world.

A one-time pad requires a random key as long as the total numbers of messages that will be sent on a given secure channel, and it requires that all parties involved have the exact same random key and never lose it. It can be implemented by xoring the bytes of the key into the bytes of the message and then sending the result onto the channel. Since the xor operation is commutative, the message may be decoded at the other end by xoring it with the key.

(Above, ‘xor’ referrs to the logical ‘exclusive or’ operation. Xor yields true (or 1) if exactly one of its inputs is true (or 1) and false (or 0) otherwise. It is trivial to build very fast xor gates using standard microchip components.)

The security of the one-time pad comes from the fact that since the key is random and never repeats, the only information about the message an attacker has is its length. (You can obscure even that by padding the message out to whatever arbitrary length you want.) The decrypted message may be any message whatsoever of the length of the encrypted message, and since the key is random there is no way to distinguish between a huge number of possible solutions. For a message ten megabytes long, for example, even storing all possible solutions is impractical.

The difficulty of implementing one-time pads in real life are multifold, and largely come down to the size of the key. The key, as I said above, must be as long as all messages ever sent on the channel, and everyone using the channel must have a copy. If the key is ever lost (and assumed stolen), the security is gone. If the key is ever repeated, the security is reduced so greatly it may be considered lost. (You must assume attackers have heard all traffic on the channel since its inception, and can do statistical analysis to reveal chinks in the randomness.)

This isn’t to say that one-time pads are never actually used. I’m sure someone with more knowledge of the history of encryption than I will give examples of their usage; I seem to recall the teletype line between Moscow and Washingon, D.C. used a one-time pad, but I may be mistaken.

12

This is great stuff - thank you. I really appreciate all the different takes and approaches - across the lot, I have a much better sense of how the concept of public key works.