What if Alice wants to sign a message to Bob so that he knows with reasonable confidence that the message is genuinely from her? We have already seen that Alice, in principle, could encrypt the whole message with her RSA private key. But this is also unnecessarily CPU-intensive. She has an easier way to go.

Let H refer to our favorite cryptographic hash. And as before, let E_RSA refer to RSA encryption. Here we can refer to Alice's RSA private key as PRIV_A, and her public key as PUB_A. To send a signed message M to Bob, Alice calculates and sends:

		    [ M, S = E_RSA{PRIV_A}(H(M)) ]
		    

Notice that the first part of what Alice sends is simply the plain text message itself with no transformation performed whatsoever. The message itself becomes resistant to tampering by virtue of what follows it. The "signature" to M is calculated with two operations. First, a cryptographic hash is calculated on the message. Alice need not send this hash itself to Bob, since he can calculate it equally well himself. Second, the hash is encrypted using Alice's RSA private key. The hash is of moderate length (e.g., 128 or 192 bits), so it does not take too much work to RSA encrypt. An attacker, Mallory, could invent a false message M'; and he can also easily calculate H(M'). But what Mallory cannot do is compute the RSA encryption of H(M') with Alice's private key. Suppose Mallory substitutes the message [M', S'] for Alice's message [M, S]. When Bob decrypts S' using Alice's RSA public key, he will get a value that is not equal to H(M'); and Bob will know the whole message [M', S'] was not authentically signed by Alice (this alone does not distinguish an attack from a signal corruption, but at least it shows that something is not right).

Suppose, while we are at it, that Alice wants to keep her signed message to Bob private as well. No problem. All Alice needs to do is substitute [M, S] for M in the encryption protocol described above. In other words:

		    [ E_RSA{PUB_B}(PRN), E_SYM{PRN}([M,E_RSA{PRIV_A}(H(M))]) ]