A few background issues about public-key cryptography (I'll use the traditional names "Alice" and "Bob" for the parties communicating, with "Alice" sending messages and "Bob" receiving them if the communication is one-way.)
- All public key cryptography is based around some mathematical problem that is believed to be hard to solve in the general case, but becomes trivial with some extra piece of information, a so-called trapdoor function. For RSA this is factoring (though RSA is not proved to be as strong as factoring - in fact, it is proven that an oracle against RSA will not help in cracking factoring), and for Diffie-Hellman, ElGamal, DSA, KEA, etc it is Discrete Logarithms. Systems has been attempted built on other problems, but none of them has so far gained full trust.
- Public key cryptography is usually expensive. As a result of this, it is used sparingly when designing cryptographic protocols. For instance, the cryptographic protocol described by flamingweasel above wouldn't actually be used - instead, you would use this protocol for a randomly generated key for a symmetric cipher.
- flamingweasel mention that the private key may be available if the key generation process isn't completely random. This is correct, and it is the most common failure when implementing cryptography. However, the private key can be calculated from the public key, too. This is what the trapdoor function mentioned above is supposed to protect against - it should be so hard to calculate the private key from the public key that it is completely unfeasible for an attacker.
- It is also possible to use public-key encryption to sign a message without encrypting it. This is done by Alice calculating a secure hash of the message she wants to send to Bob, encrypting the secure hash using her private key, and sending the encrypted result along with the message to Bob as a signature. When Bob receives this, he computes the secure hash of the message using the same algorithm as Alice, decrypts the signature from Alice using her public key, and is satisfied Alice sent the message if the decrypted value match the calculated hash value.
- Public key cryptography is hard to implement correctly.
As an example: One seemingly reasonable way for Alice to authenticate that Bob is Bob (and thus has Bob's private key) is for Alice to generate a random number, send the number to Bob, have Bob encrypt it with his private key, send the result back to Alice, and have Alice check that when she decrypts it using Bob's public key the result match what she sent to "Bob". And, indeed, this will prove that "Bob" possess Bob's private key. However, if Alice is in fact Mallory, and the algorithm used is RSA, it will also give Mallory a copy of Bob's private key - as specially constructed numbers can, when encrypted with RSA, be used to extract the private key.