Fix $N$, $e$ with $\text{gcd}(e, \phi(N))$ = 1, and assume there is an adversary $A$ running in time $t$ for which $Pr[A([x^e \mod N]) = x] = 0.01$, where the probability is taken over uniform choice of $x ∈ Z_N^*$ .

Show that it is possible to construct an adversary $A'$ for which $Pr[A'(x^e \mod N) = x] = 0.99$ for all $x$. The running time t' of $A'$ should be polynomial in t and $|N|$ (the number of bits it takes to write down $N$).

New contributor
Tusanni is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

put on hold as off-topic by Maeher, fkraiem, Squeamish Ossifrage, Mikero, AleksanderRas Jun 13 at 7:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

Browse other questions tagged or ask your own question.