Homemade Randomized RSA

Question

Considering the following encryption scheme where RSA is used to encrypt a plaintext m and then we choose a random r and compute: $$A = r + m^e \bmod N$$ and $$B = r^e \bmod N$$ So the ciphertext is a pair: $$(A,B)$$ and to recover m we compute: $$m = (B^d - A)^d \bmod N$$ IMHO This scheme has not randomized encryption since this padding approach is wrong, but i cannot figure out why. Can anyone give me a little hint?

Answer 1

• Spartacus: Maybe i came out with the solution, since the cryptosystem described above is not CCA-secure, an adversary A can intercept (A,B) and compute a new ciphertext $$C = 2B\bmod N = 2^er^e \bmod N$$ Since he's carring out a CCA-attack he has access to a decryption oracle and since: $$C\neq B$$ the oracle output $$RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\bmod N$$ So he can simply recover r by half of computed plaintext, and computing r - A he obtains the deterministic encryption of the message. Is it right?
• Artjom-B: You forgot something $2^eB\bmod N=2^er^e\bmod N$. I don't think this is complete, because the decryption oracle would decrypt $(A,C)$ and not $C$ alone.
• Spartacus: Maybe it's true but by definition i can't query a decryption oracle with original challenge ciphertext A. If it were possibile we got zero chance of getting a CCA-secure cryptosystem
• SEJPM: Hint1: This scheme isn't even IND-CPA secure. Hint2: What Henrick said. Hint 3: Given $(A,B,m,e,N)$, can you somehow recover $r$, possibly using A and m somehow?

---

Okay, let's prove that the scheme is not IND-CPA secure:

1. An adversary A outputs two messages $m_0,m_1$.

2. A uniform bit $b$ is chosen $b \leftarrow \{0,1\}$ and then the challenge ciphertext $C$ is computed as follows: $$ A = r + m_b^e \bmod N$$ $$B = r^e \bmod N.$$

3. The pair $(A,B)$ is output to the adversary A.

4. Before guessing the value of $b$ the adversary A still has access to the public key, so he can compute the two deterministic encryptions of $m_0$ and $m_1$ as follows: $$C_0 = m_0^e \bmod N $$ $$C_1 = m_1^e \bmod N$$.

5. Now he can compute the two possible plaintext values of r as follow $$P_r^1 = A - C_0 $$ $$P_r^2 = A - C_1.$$

6. A doesn't know yet which of the two possible computed plaintext values was used, but he has the ciphertext of the right one and the public key, so he computes $$ C_r^1 = (P_r^1)^e \bmod N$$ $$ C_r^2 = (P_r^2)^e \bmod N.$$

7. Now he can simply compare the ciphertexts as follows: if $C_r^1 = B$ then use $P_r^1 $, else use $P_r^2 $.

8. Let $P_r^k$ be the chosen value. Now the adversary can simply compute the deterministic encryption of the challenge ciphertext $C$: $$ C_d = A - P_r^k \bmod N.$$

9. Now it's easy guess the value of $b$: if $C_d = C_0$ then $b'=0$, else $b'=1$.

So the probability that A output $b'=b$ is equal to $1$; the encryption scheme is not IND-CPA secure.