# Inverting RSA using an oracle

Say you are given an efficient deterministic algorithm 'I' that can invert the RSA function on 1% of the points in $$Z^*_{N}$$. That is to say that if y $$\in$$ $$Z^*_{N}$$ is a "good" point for 'I', then $$(I(N, e, y))^e$$ = y. (You don't know what these "good" points for 'I' are, however.) Show that you can use 'I' to build an algorithm 'A' that inverts the RSA function on any input, and that is fast on average. That is, if x $$\xleftarrow{} Z^*_{N}$$ and y $$\xleftarrow{} x^e$$ mod N, then A(N, e, y) returns x. Give a description of your 'A', and explain why it is always correct and fast on average. As a hint, consider using randomization and exploiting the multiplicative property of the RSA function.

My idea was to come up with an algorithm which picks $$y_1$$ and $$y_2$$, which when multiplied together get y and then proceed to invert both those points.

1. $$y_1 \xleftarrow{} Z^*_{N}-\lbrace{1,y\rbrace}$$
2. $$y_2 \xleftarrow{} y.y^{-1} mod N$$
3. $$x_1 \leftarrow I(n, e, y_1)$$
4. $$x_2 \leftarrow I(n, e, y_2)$$
5. $$x \leftarrow x_1.x_2$$ mod N
6. Ret y, x

Now, x has to be the inverse of y because $$x^e \equiv (x_1.x_2)^e \equiv x_1^e.x_2^e \equiv y_1.y_2 \equiv y$$

But, the problem is the probability that I can successfully invert $$y_1$$ or $$y_2$$ is less than 1% with algorithm I(?). So, this algorithm probably fails in 99 out of 100 cases. Even if I repeat it until I get "good" set of points, it is going to be horribly slow. How do I solve this problem and make the new algorithm fast? And, how do I prove its fast?

Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle?
• Yes, this is a homework problem. I worked on it for a couple of days and got stuck with the answer I've given above. Using Hint 1, without using the oracle I could then pick some random $x_1 \in Z^*_N$ and then apply power e, to get $y_1 \in Z^*_N$. But, I still don't see how I can use this to modify my algorithm. Because now, $x_1$ multiplied with $x_2$ may not give x,which is the inverse of y? Still confused. Have I used Hint 1 correctly here? Apr 13, 2016 at 21:25
• @TomCorless: Look at your step 2: $y_2 = y \cdot y_1^{-1}$; what does that make $x_2$ (assuming success)? Apr 13, 2016 at 21:31
• Oh,now I see it, thanks. But, again, assuming success, we get $x_2$ by passing $y_2$ to I. Again, there is just a 1% chance of successful inversion. We have increased our odds by picking $y_1$ in a good way. I still think it may not be fast though? Or am I missing something here? Apr 13, 2016 at 21:43