# What is the best way to sign a message using RSA?

I was preparing for competitive exam, and I came across this question. I had a lot of discussion with my friends before I resorted to posting it here and I wanted myself to be clear on this.

Let $$M$$ be a confidential email that Alice wants to send to Bob, $$K_B$$ be Bob’s encryption public key, and $$K_A^{-1}$$ be Alice’s private key for signing. Which of the following options would be the best choice for protecting confidential emails?

(A) Send $$E_{K_{B}}(M),Sign_{K_A^{-1}}(K_B)$$

(B) Send $$E_{K_B}(M),Sign_{K_{A}^{-1}}(M)$$

(C) Send $$E_{K_B}(M),Sign_{K_{A}^{-1}}(E_{K_B}(M))$$

(D) Send $$E_{K_B}(M),Sign_{K_{A}^{-1}}(K_{A}^{+1}(M))$$

I marked (B), but correct answer is given to be (C).

I understand the first part, that we are encrypting the message with Bob’s public key, but my understanding says, that we sign the message using Alice’s private key and send it to Bob along with the encrypted message.

But seems like option (C) says that along encrypted message, Alice should sign the encrypted message and then should send this signature along with the encrypted message to Bob.

My query is as per option (C), Why are we signing the whole encrypted message instead of the original message as shown in (B).

• perefer to use $pub_A$ and $priv_B$ or $A_{pub}, A_{prv}$ to represent the keys? – kelalaka Nov 28 '18 at 11:20
• @Kelalaka-didn't get you. – user3767495 Nov 28 '18 at 11:23
• The inverse, -1, is not comment to represent the private and public keys, and what is +1 then. and you can use numbered lists – kelalaka Nov 28 '18 at 11:24
• @user3767495 You are completely fine with asking such questions here, as long as you've shown incentive to solve the issue, which you clearly did. It is a good sign that you questioned the given answer. – Maarten Bodewes Nov 28 '18 at 12:42

Option A signs the public key rather than the message. As the goal is to authenticate the message, the signature over the public key is useless for this purpose.

Option B signs the message. It however has the disadvantage that it is possible for an adversary to guess the message and verify the correctness of the guess. As such, it doesn't provide full confidentiality. It may also be vulnerable against oracle attacks unless a IND_CCA2 secure cipher is used; it could be that the receiver leaks information when trying to decrypt unauthenticated ciphertext.

Option C signs the encrypted ciphertext. It doesn't provide any authenticity of the message for email encryption because somebody can simply strip off and replace the signature. It would only provide authenticity if Bob only expects signatures of Alice, and disregards any other public keys that can be used to verify the message. This is however commonly not the case for person-to-person mail encryption.

Option D is clearly some mumbo jumbo to have a fourth option. As the operation $$K_{A}^{+1}(M)$$ doesn't make any kind of sense even with regards to the notation, it is probably best to ignore it.

Option B is an encrypt-and-sign scheme, option C is an encrypt-then-sign scheme.

Generally we use a (missing) sign-then-encrypt scheme where we send $$E_{K_B}(M, \text{Sign}_{K_{A}^{-1}}(M))$$. Obviously sign-then-encrypt should be used with care as well; it does require a IND_CCA2 secure cipher just like option B. Note that I've left out some kind of encoding function to merge the message with the signature.

Now that you know the terms you can look up Q/A and discussions such as the one here. Note that we often need to include additional information in the scheme for it to be secure in a practical sense; protocol design is however a separate topic.

EDIT: Come to think of it, it is also possible to replace the signature for option B, so that would make option C marginally better.

• A drawback of (B) is that it doesn't prove who Alice intended to send the message to. Unless M itself contains additional information about sender and receiver the first receiver of the signed message could decrypt it and reencrypt it for a different recipient and the original signature from Alice would remain valid. As far as (D) goes I think the wording in the question is ambiguous but it's possible to interpret the two operations involving $K_A$ as cancelling out, which would be bad. – kasperd Nov 28 '18 at 17:27
• True, that's a good point. I was skipping that part as there seems to be no notion of ID here in the question either. Generally you would at least include a sender & receiver in the (encoding of) the message / protocol. Not such a big issue as the replacement of the signature, but still something to think about. I guess the question is kind of an oversimplification. – Maarten Bodewes Nov 28 '18 at 17:36
• I'm not sure about what you have in mind with "It would only provide authenticity if Bob only expects signatures of Alice, and disregards any other public keys that can be used to verify the message". I see that the signature can be replaced and the message appear to be from other than Alice; and that a new public key could be crafted that also verifies the existing signature. However I see no case where Bob would wrongly accept a message as approved by the entity associated to the public key against which the message is verified, which is how an attack on authenticity is defined, right? – fgrieu Nov 28 '18 at 17:50
• @fgrieu Possibly this is not how an attack is defined, but the fact that you can send a message from Alice and replace the signature to show that it was signed by Mallory can certainly be an issue in real life. Note that this would not be possible - or at least much harder - for sign-then-encrypt, in which the message and the signature stays confidential. Hopefully the message itself contains information that indicates who created the signature, making the resigning a moot point as the information in the message and the (certificate of) the public key would differ. – Maarten Bodewes Nov 28 '18 at 21:34

Most common symmetric-key modes of operations and AEAD algorithms operates in Encrypt-the-MAC fashion, so similarly, one better use encrypt-then-sign paradigm.

All of the choices correctly stated that one should use Bob's public key to encrypt, so the only question remains is how to sign.

Remove A from consideration immediately as you realize that protects not the integrity&authenticity of $$M$$ but Bob's public key. Also remove D from consideration as that's a bad case of reusing signing key for encryption.

Choice B may have some problem if the signature can be used to recover the message (e.g. Unhashed), so it may be bad for confidentiality in some cases.

So go with C.

• @DannyNiu-As far as I Know, signature is one-way Hash of the message right? Can signature be used to recover message?How? And, wouldn't be it an overhead to first encrypt the message and then sign it? – user3767495 Nov 28 '18 at 11:30
• @user3767495 Signature is actually a cryptographic so-called "binding" between the private signing key and the message, verifiable through the public key, it's not always the one-way hash of the message, as examplified in CRYSTAL-DILITHIUM. The recovery can be achieved as described by Maarten by guessing. The overhead is negligable in most real-world use cases. – DannyNiu Nov 28 '18 at 14:28