Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I was reading that a current open problem is if inverting the RSA function is as hard as factoring.
Does this mean that, its an open problem whether, if given a subroutine that computes in probabilistic polynomial time (i.e. in BPP) the inverse of the RSA function, then its not actually known if we can factor numbers in (probabilistic) polynomial time (i.e. if an algorithm in BPP exists)?
We are dealing here with two assumptions and we always refer to $N=pq$ the product of two $n$ bit primes $p$ and $q$. The one is factoring and the second is the so called RSA assumption which is a formalization of "inverting the RSA function is hard".
These two assumption can be described as follows:
Factoring assumption: There exists no probabilistic polynomial-time algorithm that, given an RSA modulus $N$, finds a non-trivial factor of $N$ with non-negligible probability in $n$.
RSA assumption: There exists no probabilistic polynomial-time algorithm that, given the pair $(N,e)$ with $N$ being an RSA modulus and $e > 2$ with $\gcd(e,\varphi(N)) = 1$ and an element $y$ chosen uniformly at random from $Z_N^*$, computes $x\in Z_N^*$ such that $x^e\equiv y \pmod{N}$ with non-negligible probability in $n$.
Now you ask
I was reading that a current open problem is if inverting the RSA function is as hard as factoring
Yes, this means that it is an open question whether these two things are equally hard. In a formal language this means whether a solver for the first problem yields a solver for the second and vice versa.
Now, it is quite obvious that when one has an efficient algorithm $\cal A$ that breaks the factoring assumption, this implies an efficient algorithm $\cal B$ that breaks the RSA assumption. Basically, if $\cal A$ outputs a non-trivial factor of $N$, say $p$, then $\cal B$ can efficiently comptue $q$ and thus knows $p$ and $q$ which allows to efficiently compute $\varphi(N)$ and futher to efficiently compute $d$ such that $e\cdot d \equiv \pmod{}\varphi(N)$ (e.g., using extended euclid) and outputs $y^d \mod N$.
Consequently, if the RSA assumption holds then the factoring assumption holds or equivalent if the factoring assumption does not hold, then the RSA assumption does not hold. However, it is not known whether the converse is true, i.e., if the factoring assumption holds then the RSA assumption holds or equivalent if the RSA assumption does not hold then the factoring assumption does not hold.
Latter would require to show that an efficient algorithm $\cal B'$ that breaks the RSA assumption implies an efficient algorithm $\cal A'$ to break the factoring assumption. But as you said, this is an open problem.
If one could establish the latter result, then we would know that the RSA problem and the factoring problem are equally hard.
