How is the following different than RSA Signing of a document?

Question

If the goal is to demonstrate that you are who you say you are, I think the following will work: Bob wants to know that you are Amy. Bob encrypts a number using Amy's public key and then asks her what that number is. If Bob gets back the number, "Amy" at least had Amy's private key.

From what I have read, this is not what signing a document using RSA is. It is clear that it requires more emails to be exchanged; but is the fundamental idea different from Bob encrypting using Amy's public key and wanting to get back the correct decrypted message?

Answer 1

Two scenarios:

1. Alice sends a document to Bob that she has signed using her private key. Bob verifies the signature.
2. Alice sends a document to Bob. Bob encrypts a random message for Alice's public key. Alice decrypts it and sends it back to Bob. Bob verifies it's the same.

Both will only be possible if Alice has access to the private key, so you might think they are similar. However, the latter does not make any connection between the document and the authentication attempt. In fact, it allows a man-in-the-middle attack:

1. Eve intercepts a document meant for Bob, so Alice expects an encrypted message for decryption.
2. Eve sends another document to Bob, claiming to be Alice.
3. Bob encrypts a random message using Alice's public key and sends it to Eve.
4. Eve forwards it to Alice, who decrypts it and sends it back to Eve.
5. Eve can now send the decrypted message to Bob, convincing him she is Alice and that the document came from Alice.

In comparison, with signatures the document itself is signed. The signature cannot be transferred to a different document, or it will no longer verify. Moving it would require either breaking the asymmetric system to find the key or finding a hash collision.

Answer 2

You've got the vague idea about it, but you've mixed up some terms (you say Bob uses Amy's private key in your first paragraph when I think you meant to say public key; if Bob has Amy's private key it's all over for her).

Also, if it was Bob sending Amy the message, Amy would be trying to verify it was truly Bob who sent her that message, not the other way around.

The number that Amy would be verifying would normally be the result of a hash function of the document minus the signature sent (which technically is a number). Amy would calculate the number for herself using the document, then compare it to the decrypted result of the signature to see if they matched. If they did, then you know it's both from Bob and the document hasn't been tampered with.

Answer 3

It depends on what you think of as "fundamentally different". If you are talking protocol wise then yes, the idea is different. If you are talking about the technology used, then there are similarities.

The first one, where you encrypt a number is basically a challenge / response authentication protocol. As encryption is used the padding (e.g. OAEP) is specific for encryption and the actual message can be encrypted using the public key. That last part is modular exponentiation for RSA for both encryption as decryption.

The second one is indeed a signature generation protocol. If it is used for generating signature over documents it can provide non-repudiation. To do this first a hash over the document is generated. Then the signature specific padding (e.g. PSS) is applied, and then the private key is used for signing $^{*1}$. That last part is similar to decryption; it uses modular exponentiation as well.

So although both schemes use "RSA" one uses the encryption/decryption part (public/private) signature generation part and the other uses the signing/verifying part (private/public). Although the underlying technology of the decryption and signature generation is the same (the RSA trapdoor function that applies the problem of prime factorization) there are differences as well.

$^{*1}$ Ignoring container formats for this explanation.