RSA: Probalistic algorithm to compute $x$ from $y$ and $(n,e)$ with probability $\epsilon>0$ given set of weak ciphertexts? Suppose there exists a set of ciphertexts $S \subset Z_n^*$ of size $\epsilon (p-1)(q-1) $ for $\epsilon&gt;0$, that is easy to decrypt, i.e. there exist some algorithm $A_1 : \mathcal C \rightarrow \mathcal P \cup \{\text{void}\}$ that given ciphertext $y \in S$ and public key $(n,e)$ outputs correspoding plaintext $x$ and otherwise returns $\text{void}$.

I want to create a probalistic algorithm $A_2$ that given ciphertext $y$ and public key $(n,e)$ returns corresponding plaintext $x$ with probability at least $\epsilon$.

In the textbook a hint is given: Use $A_1$ as a subroutine and the RSA multiplicative property $$e_K(x_1x_2 \bmod n) = e_K(x_1)e_K(x_2) \bmod n$$

I've already proven that if $y\in Z_n \setminus Z_n^*$ then the secret key $(n,d)$ can be computed easily, which in turn yields the ciphertext $x$.

However, I'm stuck in the case $y\in Z_n^*$.

I've tried to consider how to split $y$ into prime factors $\prod_i p_i$, and then use the RSA multiplicative property, but this gets me nowhere.

Also, I've tried to consider picking plaintexts (or ciphertexts) at random, and then see if the product of their encryption their yields $y$.

Note:

For $y \in Z_n^*$, I cannot simply run $A_1$, because then the probability of returning $x$ would be $0$.
Let $d_k$ denote decryption and $x = d_K(y)$. I further assume that $\epsilon &lt; 1$.
First note that $A_1$ calculates a randomly chosen cipher text $y$ with probability $\epsilon$.
But the task is to construct a probabilistic algorithm $A_2$ which decrypts a fixed cipher text $y$.
Therefore, proceed as follows:  


choose a random $r \in Z^*_n$
calculate $y' = y* e_K(r)$ 
Use $A_1$ to decrypt $y'$ to $x'$ 
calculate $x = r^{-1}*x'$


This algorithm calculates the decryption of $y$ with probability $\epsilon$:
 - In step 2, $y'$ lands with probability $\epsilon$ in $S$
 - In step 3, the calculation yields
$$x'= d_k(y') = d_k(y*e_K(r)) = d_K(y)*d_K(e_K(r)) = d_K(y)*r = x*r$$