Skip to main content

Section 5.9 Digital Signatures

Suppose a bank has published a public key encryption algorithm specified and receives a message which states “Hi, this is Bob. Transfer all my money from my account to this other account.” Should the bank do it? Since the public key encryption algorithm is public, anyone could have encrypted this message. How does the bank know this is really from Bob? With symmetric key cryptosystems, only you and the other person share the key (hopefully!) so that this situation does not occur. To solve this problem, we need a digital equivalent of a signature. That is, a way to verify the message really came the person it says it comes from. We can use RSA to do this as well.

Example 5.9.1.

Suppose Alice and Bob are exchanging information and Bob wants to send a signed, but not encrypted message to Alice.

Suppose Bob's RSA setup is as follows:

\begin{align*} \amp \text{Bob's Public: } E_B(x)=x^5 \pmod{91} \\ \amp \text{Bob's Secret: } D_B(y)=y^{29} \pmod{91} \\ \amp \text{Bob's Message: } M=30 \end{align*}

To securely sign the message, Bob needs to make a calculation that only he could do. Thus Bob uses his secret key to sign the message.

\begin{equation*} \text{Bob's signature: } \sigma=D_B(M)=30^{29} \bmod 91 =88 \end{equation*}

He sends the message-signature pair to Alice, \((M, \sigma)=(30,88)\text{.}\) (What is the symbol \(\sigma\text{?}\)) Answer

\(\sigma\) is a lower case letter of the Greek alphabet, called sigma.

Alice can now use Bob's public information to verify that this message came from Bob.

\begin{equation*} \text{ Alice's verification: } E_B(\sigma)=\sigma^5=88^5 \equiv 30 \equiv M \pmod{91} \end{equation*}

Since \(E_B(\sigma) \equiv M \pmod{n}\text{,}\) Alice has verified that the message is from Bob. This works because \(E_B(\sigma)=(\sigma)^5=(M^{29})^5=M \pmod{91}\) by Euler's Theorem.

Note that in order for a public key system to produce a digital signature we need an additional condition on our public key system. We needed \(E(D(M))=M\) in order for the public key system to successfully send messages. For the signature algorithm to work we also need \(D(E(M))=M\text{.}\) In this case, it doesn't matter in which order we raise numbers to an exponent and reduce mod \(n\) so the signature algorithm will work for RSA.

Example 5.9.2.

In this case, we want to sign and encrypt a message. This requires two different public keys one for each person. Suppose Alice and Bob have the following RSA setup.

\begin{align*} \amp \text{Bob's Public: } E_B(x)=x^5 \pmod{91} \\ \amp\text{Bob's Secret: } D_B(y)=y^{29} \pmod{91} \\ \amp \text{Alice's Public: } E_A(x)=x^{11} \pmod{119} \\ \amp\text{ALice's Secret: } D_A(y)=y^{34} \pmod{119} \end{align*}

Bob must do two things: first, sign the message and second, encrypt the message, signature pair. Bob signs his message as before so he has the message-signature pair, \((M,\sigma)=(30,88)\text{,}\) to send to Alice. he he wants to encrypt it. So he encrypts both numbers with Alice's public key.

\begin{equation*} \text{ Bob's encryption to Alice: }\\ E_A(M)=M^{11}=30^{11} \equiv 4 \bmod 119 \\ E_A(\sigma)=\sigma^{11}=88^{11} \equiv 58 \bmod 119 \end{equation*}

So Bob sends the pair \((M',\sigma')=(4,58)\) to Alice. Technically, Bob could just send the encrypted signature and doesn't have to send both, but for clarity we'll use both.

When Alice receives the message, she must do two things but in the reverse order. Alice must first decrypt the message, and then verify the signature. Alice decrypts the message with Alice's secret key. Then, she checks if the message is valid by verifying the signature using Bob's public information.

\begin{equation*} \text{ Alice's decryption: }\\ D_A(M')=4^{34} \equiv 30 \bmod 119 \\ D_A(\sigma')=58^{34} \equiv 88 \bmod 119 \end{equation*}
\begin{equation*} \text{Alice's verification of Bob's signature:}\\ E_B(88)=88^5=30 \bmod 91 \end{equation*}

Thus Alice has decrypted the message to 30 and verified that the signature matches the message so it is really from Bob.

To summarize:

To compute an encrypted message-signature pair.

  1. Construct message, \(M\text{.}\)
  2. Compute signature, \(\sigma\text{,}\) on message using your secret key: \(\sigma=D_\text{your}(M)\)
  3. Encrypt both message and signature using other person's public key: \(E_\text{other}(M,\sigma)=(M',\sigma')\)

To decrypt and validate an encrypted message-signature pair.

  1. Decrypt both message and signature with your secret key. \(D_\text{your}(M',\sigma')=(M,\sigma)\)
  2. Verify signature with other person's public key and see if \(E_\text{other}(\sigma)= M\text{.}\) If it does, accept the message. If not, reject the message.

One last note on encrypted signatures. Since this requires two different mods, Alice's modulus, and Bob's modulus, it is possible that the signature algorithm will fail if the signature falls in between the two mods. In the previous example, if Alice had a signed a message and her signature was 95, then there would be a problem when she encrypts this to Bob mod 91 since \(91 \lt 95\text{.}\) In practice, both mods should be approximately the same size and there are some other implementation procedures to take care of this.