On the Equivalence of RSA and Factoring regarding Generic Ring Algorithms

G. Leander, Andy Rupp

Advances in Cryptology - ASIACRYPT 2006, 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, Dezember 3-7, 2006.


To prove or disprove the computational equivalence of solving the RSA problem and factoring integers is a longstanding open problem in cryptography. This paper provides some evidence towards the validity of this equivalence. We show that any e cient generic ring algorithm which solves the ( exible) low-exponent RSA problem can be converted into an e cient factoring algorithm. Thus, the low-exponent RSA problem is intractable w.r.t. generic ring algorithms provided that factoring is hard.


tags: Computational Equivalence, Factorization Problem, Generic Algorithms, RSA Problem