Please explain encryption to me.

Factual Questions
21

I think talk of factoring a number into its prime constituents is really a red herring. There’s a basic concept that anybody who wishes to understand modern cryptography must grasp: some computations are harder than others (and some are impossibly hard).

Once this is accepted (the fact that there’s very real limits on what is efficiently computable isn’t at all intuitive, so don’t worry about it) then it doesn’t matter about the specifics of the mathematical problem being used. Any “hard” mathematical problem may be used (and lots are, e.g. problems involving elliptical curves).

Further, I don’t think anybody in this thread has addressed the purpose of public key cryptography (apologies if I missed it). Basically, prior to the middle of the twentieth century, if you wanted to send a coded message to another person, you both had to meet beforehand, acquire a “secure channel” (which is question begging), or send a messenger, to agree on your code. However, this was only as secure as your messenger—if your messenger is compromised, or he’s a turncoat, then you’re screwed.

Public key cryptography allows two people to send secure messages without using a third party. That’s why public key cryptography is useful (and interesting).

22

Thank you, this is what I was having trouble grasping relative to “symmetric” ciphers like Blowfish or AES. What is the point?

To clarify, it is still necessary to have a secure channel, meeting, or messenger to exchange the private key between two parties, correct? And for symmetric ciphers, it is this private key that essentially determines how the encrypting algorithm will alter the input to create the output (that is, the encrypted file), correct?

23

Here’s my response in an old thread asking to explain Public Key Encryption.

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 (except a one time pad.)* 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.

  • Corrected in new post
24

No, the private key is never shared, it is a secret. Public keys, which are related to the private key somehow may be spread freely (i.e. it’s perfectly safe to tell everybody about your public key).

To encrypt and send a message to a person using a public key cryptography algorithm, you only need to know your own private key and the target’s public key. To decrypt, you need to know your private key and the target’s public key.

25

No; the whole point of public key encryption is that only the public keys need to be shared. The idea is that you alone know your private key, since anybody with your private key can generate messages “signed” by you, and decrypt messages sent to you. So, if somebody else has your private key, that’s a bad thing.

If you want to send a secure message to someone, you encrypt it using their public key. Then the message can only be decrypted using their private key, so the intended recipient is the only one with enough information to read its contents.

Similarly, to send a message that can be verified as having come from you, you can encrypt it with your private key. In that case, your public key will decrypt it. Since everyone has your public key, anybody can read it, but the fact that your public key decrypts it certifies that it was encrypted using your private key; i.e., you definitely wrote it. These can be combined to both sign and secure a message.
EDIT: Ah, beaten to the punch. :stuck_out_tongue:

26

Actually, my description of decryption is slightly wrong (and doesn’t make sense anyway), so you were only half beaten.

27

I think this is part I of the puzzle for most people, and

Part II of this, is understanding that it isn’t just a matter of technology catching up. For any given level of technology, it is possible to encrypt something in such a way that it takes a reasonable time to encrypt and decrypt (if you have the key) and takes longer than the expected remaining lifetime of the universe to crack using that same technology level. In fact, barring any kind of flaw in algorithm or implementation, and any sort of exotic, quantum or parallel universe computation, it is possible to encrypt things in reasonable time that would take longer than the expected remaining lifetime of the universe to crack using any technological level in the future. The key sizes, although small for a computer, are immense if you would ever have to go through any set of combinations. A 2048-bit encryption key has 2^2048 possible keys – this is a decimal number that would take a good chunk of a standard printed page (about 616 digits) and that’s just the number of possible keys. That’s way more than atoms in the universe.

Part III is understanding that decoding a particular message without a key is more than just trying every single key. Unless you know at least part of the message, or the algorithm or implementation are faulty in a manner you can identify and exploit, there is no way to know if you cracked something. This is due to the fact that for a lot of algorithms, any key in the key space will decrypt a cypertext into something. If you manage to try every key (say the key space was small) but don’t know what you’re looking for, you won’t find it. You need a sufficient amount of encrypted data (usually referred to as cypertext) in relation to the size of the key before you can say that the key you are trying is likely correct.

Part IV is understanding that things that make some things easy to crack are a) user error, b) implementation error or c) algorithm weakness. While c) is probably the most interesting, a) and b) are certainly much more common.
I noticed a lot of people gave math examples, so here’s mine :). Here is an example of the RSA algorithm using actual (but very small) numbers you can do using good calculator software (or a piece of paper if you have a day or so). I just did it using bc. Since the numbers are small, this is not secure, but it illustrates the concept of public key cryptography pretty well (I hope):

The high level sequence:

  1. Say Bob wants to send Alice a message.

  2. Alice generates a pair of keys – a public and a private.

  3. Alice sends her public key to Bob.

  4. Bob takes his plaintext (the message) and encrypts it using Alice’s public key.

  5. Bob sends the cyphertext (encrypted message) to Alice

  6. Alice uses her private key to decrypt the message

  7. Eve, who wants to spy, gets ahold of both Alice’s public key as well as the cyphertext, but cannot decrypt the cyphertext using the public key.
    Low level sequence (using small numbers):

  8. Bob wants to send Alice the number 399 (plaintext).

  9. Alice generates a pair of keys:
    [list=a]
    [li]Alice picks two random prime numbers p and q. Say p = 17 and q = 29.[/li][li]Alice computes n = p * q. n = 493 (This is shared part of the keys)[/li][li]Alice computes the totient Phi(n) = (p - 1)(q - 1) = 448[/li][li]Alice picks a random positive number e that is relatively prime to Phi(n) and is less than Phi(n). Let’s say she picks e = 79 – this is public part of her key. [/li][li]Alice picks a number d such that d * e = 1 + k * Phi(n) for some integer number k. Let’s say she picks d=431 (which satisfies the relation for k = 76). d becomes the private part of her key.[/li][/list]

  10. Alice sends her public key (the numbers n=493 and e=79) to Bob.

  11. Bob takes his plaintext (m=399) and encrypts it using Alice’s public key:
    [list=a]
    [li]c = m^e mod n = 399^79 mod 493 = 270. This is the cyphertext.[/li][/list]

  12. Bob sends the cyphertext (270) to Alice.

  13. Alice uses her private key to decrypt the message:
    [list=a]
    [li]m = c^d mod n = 270^431 mod 493 = 399 (success)[/li][/list]

  14. Eve, only has n = 493, e = 79 and c = 270. To get the plaintext, she will have to figure out the Phi(n) that Alice used, which is equivalent to figuring out p and q. In this case because the demonstration numbers are so small, this is trivial. If n is hundreds of digits long, the difficulty of factoring it grows exponentially with value of n (unless somebody gets an unexpected proof that P=NP)
    Hope this sheds some light on things.

28

Of course, if Eve is doing her job a little more carefully and has managed to insinuate herself into the channel of communication between Alice and Bob, she can conduct a man-in-the-middle attack to eavesdrop (heh):

  1. Bob wants to send Alice a message.
  2. Alice generates a pair of keys, and sends her public key to Bob.
  3. Eve, who has been waiting for this, intercepts the message. She surreptitiously replaces Alice’s public key with her own (Eve’s), and sends it along to Bob.
  4. Bob unwittingly encrypts his plaintext using Eve’s public key, thinking it belongs to Alice.
  5. Bob sends the cyphertext to Alice.
  6. Eve again intercepts the message, decrypts it using her own private key, and reads the message.
  7. Eve then re-encrypts the message using Alice’s public key, and sends it along to Alice.
  8. Alice uses her private key to decrypt the message.

Thus, Eve has successfully read the encrypted message without the knowledge of either Alice or Bob. Of course, if they attempt to communicate later without Eve’s interference, they will discover that Alice’s key no longer matches the key they used in their first message, but by then the damage will have been done, and Eve will already be off to make nefarious use of the knowledge that Bob intends to send Alice 399 monkeys or what have you.

This does, of course, depend on Eve having some level of control over the channel between Alice and Bob, but key spoofing in general is a real enough threat that it’s a good idea to set up some kind of system to help ensure the “trustworthiness” of public keys. For many purposes, this is done using “certificates” issued by trusted authorities, which are documents assigning a specific public key to an individual or organization. A certificate authority will sign the certificates it issues using its own key so that their legitimacy can be verified.

For example, for SSL encryption on the web, there are a variety of certificate authorities that are generally trusted (VeriSign, Entrust, etc.), so web browsers come packaged with those authorities’ “root certificates,” which the browser uses to verify the authenticity of other certificates purporting to be issued by a given authority. Website owners can obtain keys from such authorities (usually for a fee) to conduct secure traffic on their site.

When I was an undergrad, I took a computer security class in which one of our projects was to build a system for executing a man-in-the-middle attack via certificate spoofing. Basically it consisted of an SSL proxy with its own key pair that it would use to generate phony X.509 certificates to pass on in the place of the legitimate requests it received from its users, with the end result that it kept a plaintext log of all the “encrypted” traffic it received. Actually employing this for evil purposes would require convincing somebody to use the proxy, and furthermore convincing them to ignore the “warning” boxes that their browser will display to alert them to the fact that a site’s certificate is issued by an untrusted authority, but it was a nice demonstration of the concept, anyway. :smiley: