Example use case of signature using RSA

Question

I understand how RSA can be used for message encryption:

1. Alice wants to send a message to Bob.
2. Bob generates a public key $(n, e)$ and private key $d$; he keeps the private key for himself only, and sends the public key to Alice.
3. Alice encrypts the message with the public key.
4. Alice sends the encrypted message to Bob.
5. Bob can decrypt it with the private key.
6. Eve who stole the encrypted message (but who has not the private key) cannot decrypt it.

Can we describe a similar situation (in Layman's terms, with two people and a third malicious person) to explain how RSA can be used for message signature?

Note: My problem is not the maths (I studied RSA and understand the maths in it) but more an example of situation showing how signature works.

Answer 1

1. Alice wants to prepare Bob for a future message.

2. Alice generates a public key $(n, e)$ and private key $d$; she keeps the private key for herself only, and gives the public key to Bob up front.

3. When Alice has decided on the message $m$, she scrambles it and compresses it irreversibly into an integer $h$ the same size as $n$ by a public hash function $H$ of the message, giving $h = H(m)$, and computes $s \equiv h^d \pmod n$.

4. Alice sends Bob the signed message $(m, s)$.

5. When Bob gets a possibly forged signed message $(\hat m, \hat s)$, he computes $\hat h = H(\hat m)$ using the public hash function $H$, and rejects it unless $\hat h \equiv \hat s^e \pmod n$.

   For Alice's original legitimate message, $s^e \equiv (h^d)^e \equiv h^{de} \equiv h \pmod n$, so Bob always accepts a legitimate message from Alice.

6. Mallory, who intercepted the message $m$ in transit, and wants to replace it by $\hat m$ (but who does not have the private key $d$), does not know the corresponding $\hat s$ that Bob will accept.

7. Bob can show the message to Charlie, if he also has Alice's public key, and Charlie can verify it too using the same procedure—Alice can't send one message to Bob and claim to Charlie she didn't sign that message. (This property is called ‘nonrepudiation’ or ‘undeniability’.)