0
$\begingroup$
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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is homework, and so I won't give you the answer outright; I will give hints:

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?

Hint 2: how could you use the above observation to accelerate your algorithm?

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Tom Corless
    Commented Apr 13, 2016 at 21:25
  • $\begingroup$ @TomCorless: Look at your step 2: $y_2 = y \cdot y_1^{-1}$; what does that make $x_2$ (assuming success)? $\endgroup$
    – poncho
    Commented Apr 13, 2016 at 21:31
  • $\begingroup$ 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? $\endgroup$
    – Tom Corless
    Commented Apr 13, 2016 at 21:43
  • $\begingroup$ @TomCorless: nope, you got it; 1% probability (that is, the probability that the Oracle has) is the best you can do. $\endgroup$
    – poncho
    Commented Apr 13, 2016 at 21:48
  • $\begingroup$ Oh, I got confused with 'fast' and was expecting something much faster; but looks like this is the best we can do. Thanks! $\endgroup$
    – Tom Corless
    Commented Apr 13, 2016 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.