RSA signature signing

Question

For asymmetric encryption such as RSA, I understand that Alice can sign a document with her secret key and send it to Bob, which he can then verify.

Sign: $\sigma=m^d \bmod N$

Verify: $v=\sigma^e \bmod N$

This may be a silly question, but what if it was the other way around, Bob wants to send a document to Alice. How would he sign it to say it was from him. Can he do it without introducing "Bob's secret key" and just use the scheme provided, or does he have to do that? or is there better way?

Answer 1

For Bob to prove that he signed the document, he needs to know something that other people do not. In Alice's case, she knows her private key (we generally use the word private rather than secret when talking about signing keys), and we assume no one else knows it.

In Bob's case, everyone knows Alice's public key; hence if he used it somehow to sign a document, well, so could anyone else, and so that signature wouldn't prove that it came specifically from Bob.

There are other ways that Bob could try to prove authenticity (perhaps Bob and Alice share a symmetric key that no one else does; perhaps Bob has a secure connection with a Trusted Third party which is willing to vouch for Bob), however staying within the bounds of a simple asymmetric protocol, yes, Bob would need his own private key.

Answer 2

The "secrecy" in public key encryption has to originate somewhere. If everything that Bob has is public, then anyone can impersonate him. There has to be something that is unique to Bob for other parties to identify him. Thus, Bob too requires a secret key.

Here's something that might be of interest to you: Identity-Based Encryption

This approach utilizes the unique identity of Bob (for eg. Bob's email) rather than a "secret key" for encryption. The "secrecy" in this case originates from the Trusted Third Party which provides a unique identity to Bob (eg. Bob's email provider).