7
$\begingroup$

I can't find any publication that proves this.

$\endgroup$
2
  • 6
    $\begingroup$ A difference should be made between breaking or rather solving the RSA problem, which is a mathematical challenge and breaking real world RSA as specified in PKCS#1 where e.g. padding oracles may exist. I presume you mean the former. $\endgroup$
    – Maarten Bodewes
    May 9 at 10:31
  • $\begingroup$ @kelalaka I found these questions. I don’t think these would be relevant today. It wasn't proven 7-9 years ago. This isn't to say that it isn't proven today. $\endgroup$
    – Tomas
    May 9 at 20:20
15
$\begingroup$

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult.

The RSA problem

RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C \equiv P^e \pmod n$.

Factoring $\implies $ the RSA problem

This is the easiest part. If we can solve the factoring problem then we can solve the RSA problem by factoring the modulus $n$. This implies that the RSA problem is at least as easy as factoring. This doesn't eliminate the case that it might well be easier.

The RSA problem $\stackrel{?}{\implies} $ Factoring

The most well-known work on the reverse of the problem goes back to 1998

  • D. Boneh and R. Venkatesan Breaking RSA may not be equivalent to factoring

    We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any weakness in the RSA system.

Here, we should note that the RSA problem is the decryption of a specific ciphertext, whereas the factoring reveals the private key $d$ thus all ciphertext under encrypted the same public key.

If we consider the problem of finding the private exponent $d$ then it is proven by Miller to be computationally equivalent to factoring $n$;

The below work went on the generic ring model ( in short: a ring has no special property than being a ring) and show the equivalence;

We show that a generic ring algorithm for breaking RSA in $\mathbb Z_N$ can be converted into an algorithm for factoring the corresponding RSA-modulus $N$. Our results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input in $\mathbb Z_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

This work creates a strong belief in the reverse problem; factoring is equivalent to the RSA problem, however, no proof yet!

Also a notable work on comparing $e$-th root algorithm with the factoring algorithms to see the trend;

  • 2007: Antoine Joux and David Naccache and Emmanuel Thomé When $e$-th Roots Become Easier Than Factoring

    We show that computing $e$-th roots modulo n is easier than factoring n with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i+c$.

As a result, we still have;

$$\text{the RSA problem} \stackrel{?}{\implies} \text{Factoring }$$


If factoring can be solved in polynomial time ( a common belief noted by Meir Moar) then by using the reduction from Hamiltonian Path to Factoring as Haldeman did in their DNA factoring then with the Karp's 21 reductions we can solve the $NP$-complete problems in polynomial time with factoring.


Dan Boneh's article with 977 citations is a good starting point to see the RSA's 20 years;

$\endgroup$
6
  • $\begingroup$ If we consider the problem of finding the private exponent d then it is proven to be computationally equivalent to factoring n. – Can you elaborate on this? Is this referring to the idea that an attack may (theoretically) exist which could find the plaintext without finding d? $\endgroup$
    – forest
    May 9 at 21:27
  • 1
    $\begingroup$ @forest The first work is due to the Miller,'76. knowing $d$ is equal to factoring. The joint work Aggarwal and Maurer work on the generic ring model to show that breaking RSA is equal to factoring. This is the reverse of $\text{factoring} \implies \text{RSA problem}$ in the generic ring model ( that ring has no special properties than to be a ring). So if there is one, then once you solve the RSA problem then you can factor and get $d$ very easily. $\endgroup$
    – kelalaka
    May 9 at 21:48
  • 1
    $\begingroup$ If factoring is solvable in Polynomial time which I believe is the common belief. Then trivially there is a polynomial reduction from any problem to factoring. $\endgroup$
    – Meir Maor
    May 10 at 13:27
  • $\begingroup$ @MeirMaor Yes, the hamiltonian path can be turned into factorization. Adleman used this in DNA factoring algorithm. Karp's 21 NP-Complete problems include the Hamiltonian paths directed and undirected. $\endgroup$
    – kelalaka
    May 10 at 14:54
  • $\begingroup$ @forest: I think the idea here is that if d and e are of vastly different lengths (e.g. e is simply the number 3), the effort required to compute a text s given (pq), and (s³ mod pq), may be much less than the effort to factor pq. That's trivially true for some messages (e.g. if s³ is less than pq, one could simply take the cube root of s³, and if s³ isn't much larger than pq one could simply try taking the cube roots of (s³ mod pq)+Npq for successive values of N until one yields an exact integer) but might be true even for general values of s. $\endgroup$
    – supercat
    May 10 at 15:25
12
$\begingroup$

No, it's not proved that solving the RSA problem [that is, finding $x$ from the value of $x^e\bmod n$ for unknown random integer $x$ in interval $[0,n)$, and $(n,e)$ a proper RSA key ] is equivalent to factoring.

It's even widely believed that does not hold, for $e$ of fixed magnitude (as used in practice) in particular. Trivially, ability to factor implies ability to solve the RSA problem. But there is no evidence whatsoever that the converse holds.

Finding a working private key $(n,d)$ from a proper RSA public key $(n,e)$ is proven equivalent to factoring, and is not the RSA problem.

Breaking RSA in the sense that has in cryptographic practice (deciphering a ciphertext or forging a signature with knowledge of the public key $(n,e)$ but not a private key) is no more difficult than breaking the RSA problem (thus no more difficult than factoring). More often that not, side channel attacks, implementations errors, or poor padding make it easier.

$\endgroup$
2
  • $\begingroup$ "It's even widely believed that does not hold, for 𝑒 of fixed magnitude (as used in practice) in particular. " I've never seen someone claim this. Who do you know you believes this ? $\endgroup$
    – duckstar
    May 11 at 12:59
  • $\begingroup$ I guess you are referring to the paper "Breaking RSA May Be Easier Than Factoring" but this result only applies to a type of reduction the authors call "algebraic." This condition is extremely restrictive. The paper itself is probably excellent but that title is just slick marketing. $\endgroup$
    – duckstar
    May 11 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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