enter image description here

Here the encryption is done as follows : $$C=P^e \textrm{mod} \, n =(P_1||P_2)^e \textrm{mod} \, n.$$ Here's my scenario that the adversary with CCA2 wins.

The adversary chooses $X_1, X_2$ of the same size with $P_1, P_2$ and multiplies $C'=(X_1||X_2)^e \textrm{mod} \, n$ by $C$ to get $CC'=(P_1X_1||P_2X_2)^e \textrm{mod} \, n$. The adversary asks the decryption oracle to decrypt $CC'$ to get $(P_1X_1||P_2X_2)$. Then the adversary can get $(P_1||P_2)$ by just multiplying the inverse of $(X_1||X_2)$. Finally, the adversary can decrypt the original message as Bob does.

This is the same as CCA on textbook-RSA. I see that RSA-OAEP is IND-CCA2 secure, but why is this attack impossible?


1 Answer 1


The attack assumes $$(P_1\mathbin\|P_2)(X_1\mathbin\|X_2)\equiv P_1X_1\mathbin\|P_2X_2\pmod n$$ which has no reason to holds for most parameters.

Note: the bit size of $P_2X_2$ has no standard definition. In the following I assume the intention is to make it the sum of the size of the arguments $P_2$ and $X_2$ expressed as fixed-size bitstrings¹.

Counterexample with 4-bit parameters $P_1$, $P_2$, $X_1$, $X_2$ all set to 1111: $P_1\mathbin\|P_2$ and $X_1\mathbin\|X_2$ are 11111111, $P_1X_1$ and $P_2X_2$ are 11100001, left hand side $(P_1\mathbin\|P_2)(X_1\mathbin\|X_2)$ is 1111111000000001, right hand side $P_1X_1\mathbin\|P_2X_2$ is 1110000111100001. They have no reason to be equal modulo $n$.

¹ Another sensible defintion would be that $P_1X_1\mathbin\|P_2X_2$ has value $P_1X_1\,2^\ell+P_2X_2$ where $\ell$ is the common bit size of bitstrings $P_2$ and $X_2$, but that does not make the equality hold either.

  • $\begingroup$ I didn't know that it doesn't work as simple as numbers. Thank you! $\endgroup$ Jul 22, 2022 at 8:19
  • $\begingroup$ @이승우 : It does not work "with numbers" either. In decimal, $99\times99$ is not $8181$. $\endgroup$
    – fgrieu
    Jul 22, 2022 at 8:22
  • $\begingroup$ It is because they are not a single numbers but padded numbers, am I right? Does padding remove malleability of textbook-RSA? $\endgroup$ Jul 22, 2022 at 8:35
  • $\begingroup$ @이승우 : Padding the plaintext by concatenation breaks the multiplicative property of textbook RSA: that $\operatorname{Enc}(P_1)\operatorname{Enc}(P_2)\bmod n\ =\operatorname{Enc}(P_1\,P_2\bmod m)$. Large amount of random padding seems safe for encryption, but we have no proof that it is, when we have such proof for RSAES-OAEP. However deterministic padding is always unsafe in encryption, and deterministic padding with constants sometime is unsafe for signature. $\endgroup$
    – fgrieu
    Jul 22, 2022 at 9:18
  • $\begingroup$ Thank you so much! $\endgroup$ Jul 22, 2022 at 13:42

Your Answer

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

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