I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message.

If Bob wants to send a message $M$ to Alice:

  1. Bob takes $M$ and encrypts it (using Alice's public key): $P_A(M) = C$.
  2. Sends $C$ to Alice.
  3. She decrypts it using her private key: $S_A(C) = S_A(P_A(M)) = M$.

If Alice wants to send a signed message $M'$ to Bob (page 961):

  1. She computes the digital signature of $M'$ (with her private key): $\sigma = S_A(M')$.
  2. Sends the pair $(M', \sigma)$ to Bob.
  3. Bob receives the pair and check the message authenticity by comparing $M'$ and $P_A(\sigma)$.

If Alice want to send an encrypted, signed message $M'$ to Bob.

In cursive is what I think (I don't know how) it goes.

  1. Alice first appends her digital signature to the message. I guess we get $M'' = M'\sigma$, where $\sigma = S_A(M')$.
  2. Encrypts the resulting message/signature pair with the public key of Bob (the recipient): Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?. If the former, then what is the point of encrypting the digital signature?.

  3. The recipient decrypts the received message with his or her secret key to obtain both the original message and its digital signature. I don't how this is done, since I don't know how steps 2 is performed.


  • $\begingroup$ Note: RSA is a trapdoor function and should never be used without proper padding. And, usually, we use hybrid encryption. a recent answer. $\endgroup$
    – kelalaka
    Aug 16, 2019 at 9:25

2 Answers 2


Encrypts the resulting message/signature pair with the public key of Bob (the recipient): Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?

Neither. It's simply $P_B(M'')$. The resulting message/signature pair refers to $M''$.

  • $\begingroup$ Since $M'' = M'\sigma$, it is assumed that, after applying $S_B(P_B(M''))$, Bob will be able to tell where $M'$ ends and $\sigma$ begins in the concatenation? $\endgroup$
    – asd
    Aug 16, 2019 at 9:24
  • 2
    $\begingroup$ @Jazz Usually a special symbol is inserted beteween $M'$ and $\sigma$ so that Bob can tell where $\sigma$ begins. $\endgroup$
    – xskxzr
    Aug 16, 2019 at 11:29

Practically, you don't need to encrypt the appended message again. You will encrypt the message and for the signature first you will create a message digest which is a hash of the original message. This message digest will then be encrypted with the private key using a mutually decided encryption algorithm.

Now you have an encrypted message and a digital signature (encryption of hash). You can append the two using a delimiter and send on the other side.

Once the other side recieves the combination, it can decrypt the message and also decrypt the signature. Now you have the original message and the original message digest. Now you will evaluate the hash of original message and match with the original message digest. If it matches it proves the authenticity.

Re-encrypting the appended message will not make sense because it will unnecessarily slow down the process.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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