Editing RSA cryptosystem (section)

===Signing messages===
Suppose [[Alice and Bob|Alice]] uses [[Alice and Bob|Bob]]'s public key to send him an encrypted message. In the message, she can claim to be Alice, but Bob has no way of verifying that the message was from Alice, since anyone can use Bob's public key to send him encrypted messages. In order to verify the origin of a message, RSA can also be used to [[digital signature|sign]] a message.

Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a [[cryptographic hash function|hash value]] of the message, raises it to the power of {{mvar|d}} (modulo {{mvar|n}}) (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice's public key. He raises the signature to the power of {{mvar|e}} (modulo {{mvar|n}}) (as he does when encrypting a message), and compares the resulting hash value with the message's hash value. If the two agree, he knows that the author of the message was in possession of Alice's private key and that the message has not been tampered with since being sent.

This works because of [[exponentiation]] rules:
<math display="block">h = \operatorname{hash}(m),</math>
<math display="block">(h^e)^d = h^{ed} = h^{de} = (h^d)^e \equiv h \pmod{n}.</math>

Thus the keys may be swapped without loss of generality, that is, a private key of a key pair may be used either to:
# Decrypt a message only intended for the recipient, which may be encrypted by anyone having the public key (asymmetric encrypted transport).
# Encrypt a message which may be decrypted by anyone, but which can only be encrypted by one person; this provides a digital signature.