# How is RSA-OAEP secure from CCA2?

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?

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.

• I didn't know that it doesn't work as simple as numbers. Thank you! Jul 22, 2022 at 8:19
• @이승우 : It does not work "with numbers" either. In decimal, $99\times99$ is not $8181$.
– fgrieu
Jul 22, 2022 at 8:22
• It is because they are not a single numbers but padded numbers, am I right? Does padding remove malleability of textbook-RSA? Jul 22, 2022 at 8:35
• @이승우 : 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.
– fgrieu
Jul 22, 2022 at 9:18
• Thank you so much! Jul 22, 2022 at 13:42