8
$\begingroup$

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)?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ While it is unknown whether RSA and factoring are (probabilistic) polynomial time equivalent, it is known that factoring a RSA-modulus is polynomial time equivalent to finding the secret key $d$ (see Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring). This is closely related to the mentioned problem, but not quite the same. $\endgroup$
    – tylo
    Jan 23, 2014 at 16:23
  • 1
    $\begingroup$ Yes, also in the generic ring model it can be shown that the RSA problem is equivalent to factoring. $\endgroup$
    – DrLecter
    Jan 23, 2014 at 16:38
  • 1
    $\begingroup$ So we know that $factoring \leq_M RSA^{-1}(x)$ but we don't know whether $factoring \geq_M RSA^{-1}(x)$ is true? $\endgroup$ Jan 24, 2014 at 4:12
  • $\begingroup$ I guess I am a little confused about how this relates to reductions. I agree that if factoring is efficiently solvable then inverting RSA is easy. Does that mean that RSA reduces to factoring? $\endgroup$ Jan 24, 2014 at 4:15
  • 1
    $\begingroup$ @Pinocchio I didn't mention this since I did not know how to interpret "semi-rigorously". Yes this means that RSA poly-time reduces to factoring, but the other direction is not known, which would establish that they are equivalent. But I would rather say equally hard instead of equally easy, since we assume that they aren't easy ;) $\endgroup$
    – DrLecter
    Jan 24, 2014 at 6:09

Your Answer

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

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