Did you notice the flaw in the public key message exchange described in What is public key cryptography?? How can Bob prove that the message really came from Alice? Eve could have substituted her public key for Alice's, then Bob would be exchanging messages with Eve thinking she was Alice. This is known as a Man-in-the-Middle attack.

We can solve this problem by using a digital signature -- a bit pattern that proves that a message came from a given party.

One way of implementing a digital signature is using the reverse of the public key process described in What is public key cryptography?. Instead of encrypting with a public key and decrypting with a private key, the private key is used by a sender to sign a message and the recipient uses the sender's public key to decrypt the message. Because only the sender knows the private key, the recipient can be sure that the message really came from the sender.

In actuality, the message digest (What is a message digest?), not the entire message, is the bit stream that is signed by the private key. So, if Alice wants to send Bob a signed message, she generates the message digest of the message and signs it with her private key. She sends the message (in the clear) and the signed message digest to Bob. Bob decrypts the signed message digest with Alice's public key and computes the message digest from the cleartext message and checks that the two digests match. If they do, Bob can be sure the message came from Alice.

Note that digital signatures do not provide encryption of the message, so encryption techniques must be used in conjunction with signatures if you also need confidentiality.

You can use the RSA algorithm for both digital signatures and encryption. A U.S. standard called DSA (Digital Signature Algorithm) can be used for digital signatures, but not for encryption.