If we encrypt a message $m$ as $m || H(m)$ using textbook RSA encryption algorithm, $H$ is random oracle modeled. In this case the message can be recovered.

Is this encryption CCA secure? If so how can we prove it or not?

  • 1
    $\begingroup$ It isn't even CPA secure.... $\endgroup$
    – SEJPM
    May 4, 2018 at 16:08

1 Answer 1


CCA security assumes CPA security, and $m || H(m)$ is not CPA secure. This is simple to show: say that $C = E(m || H(m))$ is known, then an adversary can simply guess $m'$ and encrypt that. Then $C' = C$ will show the adversary that $m'=m$.

To show a CCA attack you can use this attack. You can of course replace the value $2$ in that question with $y$ where $y = x || H(x)$ for any $x$. In that case you end up with $z \cdot m || H(m)$ after decryption. Calculating $m || H(m)$ will then just consist of division with $z$.

To avoid this it is of vital important that the signature is over data protected by randomized padding, and that this randomization is well distributed over the input to the RSA exponentiation. This is what OAEP does with the MGF(1) padding.

Alternatively a hybrid scheme such as RSA-KEM combined with a block cipher could be used.

Deterministic encryption cannot be fully CPA or CCA secure; some kind of randomness or at least uniqueness is required to be CPA / CCA secure to not leak information for repeated messages.

  • 3
    $\begingroup$ Also there is a general result that a public key encryption operation must be randomized in order to be CPA secure... $\endgroup$
    – SEJPM
    May 4, 2018 at 17:53
  • $\begingroup$ Anything missing from my answer, pinofer? $\endgroup$
    – Maarten Bodewes
    May 9, 2018 at 15:01

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.