How is RSA-OAEP secure from CCA2?

Question

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?

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.