Digital Signatures

We the first equation we considered when looking at public/private key cryptography was

$$M = S_A(P_A(M))$$

(Recall $S_A()$ and $P_A()$ are inverses)

And we looked at how this enabled private messages to be sent across an insecure channel. Now consider the equation

$$M = P_A(S_A(M))$$

This represents Alice encrypting a message ($M$) using her secret key. Anybody can now decrypt the message using her public key, but since only Alice can use $S_A()$ they can be sure it was her who encrypted the message. Suppose Alice didn't want to hide the message, merely provide a means for people to verify it was her who sent it. She could send both the origional message, $M$, and $S_A(M)$. Clearly anybody can read $M$ and anyone who bothers to find Alice's public key can apply $P_A$ to $S_A(M)$. If the result of this matches $M$ they can be reasonably sure it was Alice who sent the message, so by providing $S_A(M)$ with the message Alice has `signed' it.

Of course transmitting $S_A(M)$ and $M$ is a waste, since we are now sending a message that is twice as long as $M$.