Breaking RSA if small subset invertible I am trying to solve a problem which states that one can invert RSA if a small subset of the cipher text are invertible, the problem is as follows:
Given a function which can invert the RSA encryption that is given $C=M^e$, the function can compute $M$ for small subset (typically 1% of the ciphertext  space) of the ciphertexts. Then show that all the ciphertexts generated by RSA can be inverted with a good probability.
There was a hint given with the question that : $M_1^e*M_2^e \equiv (M_1*M_2)^e mod N$, suggesting to take a direction that uses this property

Let $\mathcal{K}$ be your pairs of known ciphertexts and plaintexts (the ~1% you mention in your question). You know $N$ and $e$ and receive $C = M^e$. You want to compute $M$.
Algorithm:


*

*If $(C,\color{gray}{M}) \in \mathcal{K}$, decode to $M$.

*Else, pick an arbitrary $(C_1,M_1) \in \mathcal{K}$ and compute
$$C_2 = C_1 C = M_1^e M^e = (M_1 M)^e \pmod{N}.$$
If $(C_2,\color{gray}{M_2}) \in \mathcal{K}$, decode to $M_2 M_1^{-1} \pmod{N}$.

*Else, repeat step 2 for a different pair.
Experimentally, this appears to work. I haven't attempted to work out the probability of failure.
