Anybody understand cryptography?

[dan@george]

This question has been nagging me for a while, and nothing I've read has helped me figure it out:

From what I understand, you use a public key to encrypt a message that can only be decrypted with the private key. But if the encryption software uses the public key to encrypt the message, and you can read the source code of the encryption software to see how it does that, why can't someone listening in just reverse the process using the public key, which they know because it's public?

I'm obviously missing something here, but I just can't figure out what it is.

[hchasqueira]

Although you can see how the message is encrypted using the public key, the algorithms used make it impossible to use the public key to decrypt the message.

The encryption algorithms use one-way functions to achieve this. These functions, as their name says, cannot be reversed.

You might want to google for "pgp explained" for more technical explanations...

[newuser123]

why can't someone listening in just reverse the process using the public key, which they know because it's public?

This is the essential idea of understanding public key cryptography.
Not every algorithm can be "reversed". this is the P=NP question. Hope that it helps.

[Thrillhouse]

I think this is a legitimate question that some people may have and I think the best place to start is right here on Wikipedia. Essentially, I think public key encryption may be less intuitive than symmetric encryption but it is no less secure. In fact, I would bet that is more widely-used than symmetric encryption.

[Cabhan]

I can try and offer the reader's digest version of RSA encryption (a popular public-key cryptography), if you would like. It should clarify the issue somewhat.

RSA works as such:

You choose two numbers called P and Q. These are both prime numbers somewhere between 1 and 2^1024 (note: 2^1024 is a HUGE number).

You now have P and Q. You also have a number PQ, which (as you might guess), is simply the product of P and Q. Finally, you have the number (P-1)(Q-1).

We now need our number E. E is relatively prime to (P-1)(Q-1). This means that E and (P-1)(Q-1) share no factors except for 1.

The last number that we need is D. D is the multiplicative inverse of E mod (P-1)(Q-1). That was quite a mouthful. What does it mean?

The multiplicative inverse of a number is the number that makes the equation = 1. So for instance, the multiplicative inverse of 3 is 1/3. Modular arithmetic means that we only use a certain subset of integers. For instance, in a mod 4 world, we only use 0, 1, 2, and 3. So 4 mod 3 = 1. So does 7 mod 3, etc.

So in a modular world, multiplicative inverses are different. For instance, the multiplicative inverse of 3 mod 5 is 2. This is because 3 * 2 = 6, and 5 * 1 = 5. So 3 * 2 = 1 in a mod 5 world.

Do you follow so far?

So now that we've explained the hard part, let's go over our numbers again:

P = A huge prime number
Q = A different huge prime number
PQ = The product of P and Q
(P-1)(Q-1) = Self explanatory
E = A number relatively prime to (P-1)(Q-1)
D = The multiplicative inverse of E mod (P-1)(Q-1)

Now then, I publish only 2 numbers to the world: PQ and E. You will note that P and Q are NOT revealed (and therefore (P-1)(Q-1) is also not revealed), nor is D. Only I know (P-1)(Q-1) and D.

So now, you send me a message (we'll call it M). You would do this:

M ^ E mod PQ = T

T is a completely jumbled message. However, one of the coolest properties of RSA is that:

T ^ D mod PQ = M

So you send me this jumbled up message, and I can easily use D to decrypt it!

Now, RSA has a theoretical flaw in that if we knew a quick way to break down numbers into prime numbers, we could discover what P and Q were from PQ (and therefore, (P-1)(Q-1) and therefore D). However, it turns out that this process (called prime decomposition) is EXTREMELY inefficient to perform, and that even a modern supercomputer could not perform this process on a number in the range of 2^1024 before the sun burned out.

So you see that despite my giving out information to the world, due to the presence of hidden information, my code is still essentially uncrackable.