Breaking RSA may not be equivalent to factoring. (Extended abstract) (Q4249628)

This paper presents an argument which supports the claim that breaking the RSA algorithm is easier than factoring the RSA modulus. This is not to say that RSA is easy to break, but that it may be easier to break than the underlying hard mathematical problem on which it is based. The method used is interesting and novel. The authors present a class of algorithms called ``algebraic algorithms''. This is a restricted class of algorithms in which only algebraic operations are allowed, so for example bit manipulations are not allowed. Given this definition they go on to show that any efficient algebraic algorithm which factors a product of two primes, given a finite number of calls to a low exponent RSA oracle can be converted into a true efficient factoring algorithm with no oracle calls. Hence the use of the RSA oracle does not really help us in factoring the integer. So unless factoring is easy the two problems cannot be equivalent. For the entire collection see [Zbl 0889.00042].