4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$
  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’.)

$\endgroup$
  • $\begingroup$ Good explanation, but in this digital day and age it may be a good idea to stress that the public key must be trusted to be from Alice. $\endgroup$ – Maarten Bodewes Nov 3 '17 at 22:13
  • $\begingroup$ There are some things I would do differently if writing from scratch, but I was trying to echo the original story without (too) much extra verbiage. $\endgroup$ – Squeamish Ossifrage Nov 3 '17 at 22:16
  • $\begingroup$ Right you are. If you don't mind I'll leave the little warning below, just in case. $\endgroup$ – Maarten Bodewes Nov 3 '17 at 22:20
  • $\begingroup$ @MaartenBodewes Maybe can you write another answer explaining this? $\endgroup$ – Basj Nov 3 '17 at 23:03
  • $\begingroup$ @Basj: Not exactly an answer to the question you asked, but Alice and Bob must have some way to confirm the authenticity of the public keys they exchange, whether you are using them for encryption or for signature. There's no problem if an eavesdropper learns the public keys, but there is a problem if a man-in-the-middle surreptitiously replaces them in transit. $\endgroup$ – Squeamish Ossifrage Nov 3 '17 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.