semantic security of RSA variant I am thinking of a variant of RSA. 
I know that RSA itself is not semantically secure as it is "deterministic". I have a "randomized" variant of RSA in mind. 

Suppose that the public key is $&lt;e,n&gt;$. To encrypt a plaintext $p$, this variant first randomly choose a value $v$, and output the ciphertext as:
$$E(p)=&lt;v,(v+p)^e \text{ mod }n&gt;$$
The ciphertext consists of 2 parts, the value of $v$ in clear, and the ciphertext of $(v+p) \text{ mod }n$ computed using the original RSA.

Is this variant of RSA semantically secure? How do I prove it?
No it's not.

As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult.

In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The attacker wins if he can guess $b$ correctly. And we consider the encryption scheme secure, if the advantage of the attacker compared to random guessing is negligible.

So, let's play the CPA game with this variant:


The attacker chooses $m_0$ and $m_1$ arbitrary (but not equal)
He gets back $Enc(m_b)$. In your scheme that would be some value $v$ and $(v+m)^e \mod n$.
Since he knows both $m_0$ and $m_1$, he can check both possibilities by calculating both $(m_0 + v)^e$ and $(m_1 + v)^e$. Comparing that with the challenge, he immediately knows $b$
The attacker wins.


If you want to have an IND-CPA RSA variant, there is RSA-OAEP. In the random oracle model and with the RSA assumption, this is proven to be IND-CCA2, which is much stronger than IND-CPA.