How does public key encryption work?

[ColKurtz]

I've often wondered how 2 computers that want to communicate securely over an insecure medium are able to establish a secret key. It seems like whatever information is passed from one computer to another regarding how to encrypt messages (which alogrithm to use, what prime number to factor, etc) could be intercepted and acted upon by a 3rd party just as easily as the intended party.

Can anyone elaborate?

 

[Mark R]

Here you go

Admitted, a long and potentially a bit complicated - but should tell you most of what you want to know.

A very brief simple summary:

Alice wants to send Bob a secret message.
Bob creates a key-pair for the encryption method that A and B will be using - the key is always created as a matching pair. One key he keeps private, and one key (the public key) he sends to A.
A encrypts the message using B's public key.
B uses his private key to decrypt the message from A.

The fundamental point is that the public half of the key can only *encrypt*. It doesn't matter that anyone can access the public key because it can't decrypt. The decryption can only be performed by the private key.

 

[harrkev]

One more thing...

You can also encrypt with the private key and decrypt with the public key. This serves as a type of signature. Because only you know the private key, only you can encrypt the contents. Of course, the content can be read by anybody who has access to the public key. So if A wants to send a message to B, A encrypts it twise with A's own private key and B's public key. Now, B knows for sure that it came from A, and that only B can read it.

 

[ColKurtz]

Thanks Mark (and harrkev). I was looking for the layman's explanation, so that's perfect.

 

[theeedude]

Ok, this was a while ago when I took the class, but basically it's modular arithmetic. Basically if you encode the message as a polynomial, and then raise that polynomial to certain power, you get it back (modulo another polynomial). So they take that power and factor it into two factors. Then they give you one of the two factors as a public key, you raise the polynomial to that power to encrypt. Then they use the second factor (the private key) and raise what you send them to that power to decrypt, and get the original polynomial back. Like I said, this was 8 years ago I took this class, so someone can correct me if I am wrong. So ((message)^(public key))^(private key)=(message) mod (something)

 

[AnthraX101]

I just wanted to add one note to this.

Except for particularly strict situations, it is impossible for two users to communicate securely without a pre-shared secret. They are always vulnerable to an active man in the middle attack. In this attack we have Alice ("Good" player 1), Bob ("Good" player 2), Eve (Active eavesdropper).

Alice asks to talk to Bob
Eve says "I'm Bob!"
Eve asks to talk to Bob
Alice sends Eve her public key
Eve sends Bob her public key
Bob sends Eve his public key
Eve sends Alice her public key

In this manner, Eve looks like Bob to Alice, and looks like Alice to Bob. This is sometimes referred to as the grandmaster chess problem. The culmination of it is unless some information is preshared (or you are allowed to place some unrealistic constraints on the communication algorithm), you have no way of verifying that the person you are talking to is really Bob.

If anyone is interested I can describe the actual grandmaster chess problem (the above is simply an offshoot of it), or show how with only a few shared secret bytes identity can be assured. I can also describe the communication constraints that prohibit an active eavesdropper without any secret information.

AnthraX101