Digital Signatures:

As a bonus, RSA gives us a way to digitally "sign" messages, thereby proving who wrote them.  This uses the same public n and e and private d as before.

For each plaintext P, compute

The numbers S are your signed message.

Since only you know the decryption d, only you can sign a message.  The person you send it to can prove it was you by computing

(since e is public) and getting back

which we know is congruent to P.  If this matches the P you sent separately, then the message was correctly signed, so it must have come from someone who knows d.

Example: suppose that instead of encrypting the message "cats and dogs" we wanted to sign it.

Then anyone who looked up our public n and e could prove that we had sent it:

Next Section