Let p be a n-bits prime number, that is drawn uniformly. Let e and m uniformly drawn from Z(p-1) and Z*(p) respectively. Let y= (m^e) mod p Prove that the probability to find m while knowing only p,e,y is greater from negl(n).
I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!
The hardness of RSA lies in the difficulty of computing $e$th roots modulo $n$, which seems to be feasible only when the order $\varphi(n)$ of the group $(\mathbb Z/n\mathbb Z)^\times$ is known. This is exactly what the difficulty of RSA relies on: Calculating $\varphi(n)$ depends on factoring $n$, and for all we know, this is quite hard.
However, when $p$ is a prime, it is already factored, so trivially, $\varphi(p)=p-1$. Just like for "real" RSA, the decryption exponent must satisfy $$de\equiv 1\mod\varphi(p)$$ and can easily be calculated using the extended Euclidean algorithm. Then, $$m\equiv y^d\mod p$$ with probability $1$.