9
$\begingroup$

I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), would that in any way help in breaking 2048-bit RSA encryption?

My insticts says no, but I can't be sure.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Interesting, but that's of course not how factorization works; if you can easily factor such large numbers then you should be able to factor slightly larger numbers as well. Basically the question is invalidated by itself. I guess that if you have such an oracle then you can produce a whole lot of primes that could also have been used for the 2048 bit key pair, but as there are so many primes I don't think it would help you much. $\endgroup$
    – Maarten Bodewes ♦
    Jun 9, 2022 at 22:43
  • $\begingroup$ @MaartenBodewes My original thought was more if someone found an efficient way to factorise large primes. Then as proof created e.g. a public website allowing people to factorise any number, but limited input to 2047-bit (to not to break encryption). Could this be exploited to actually break higher bit encryption? $\endgroup$
    – Christer
    Jun 10, 2022 at 5:22
  • 1
    $\begingroup$ I suspect that there's not a great win to be had. Unless we think that there's something magic about the number 2048, a means to cheaply factor 2047-bit numbers would follow from a means to cheaply factor 2046-bit numbers and so on downwards until we hit, say, 2-bit numbers (which I know how to factor very quickly). That said, there are auxiliary stages in factoring algorithms such as the multiple number field sieve where it is necessary to efficiently factor smaller numbers (or at least test for smoothness), but these numbers are usually much smaller. $\endgroup$
    – Daniel S
    Jun 10, 2022 at 9:49
  • 1
    $\begingroup$ Assume that there is an oracle that factors $x$-bit two prime RSA and we have a polynomial algorithm that factors RSA $(x+1)$-bit two prime RSA with the help of $x$-bit Oracle. Now, we have $(x+1)$-bit polynomial-time oracle. With this, we can factor all two prime polynomial RSA modulus in polynomial time. $\endgroup$
    – kelalaka
    Jun 11, 2022 at 19:41

1 Answer 1

Reset to default
1
$\begingroup$

I think the answer is that we don't know.

I will only consider only the classical model of computation, not a quantum one cause I'm not really experienced on it.

First of all we need to clarify something, the strongest assumption that RSA can rely on is the RSA assumption, factoring is a weaker assumption. This means that if we can solve prime factoring problem we can solve many problems including RSA. If we can solve the RSA problem we don't really know if we can solve the prime factoring problem. Something else we also need to mention is that we suppose this oracle is running in efficient space and time, otherwise it should really make that sense.

I haven't heard of any algorithm that can convert a 2047-bit prime factorization oracle to a 2048-bit one being efficient in both time and space. If you have heard of one you can mention it in the comments. Particularly, I don't think anyone is interested in solving such a problem, it is actually useless. To summarize I think there are very few probabilities that we ever discover such an algorithm.

Another option would be to discover an algorithm that would convert a $n$ bit prime factorization oracle to an $n+1$ bit one both efficient in space and time. We can prove here by induction that such an oracle would be equivalent to solving the RSA. I think that would be far far far less likely to happen because it would mean actually solve the RSA problem.

A last comment is I think such an oracle may only help only in the case of a small prime factor (for example such a weak prime factor may appear in an RSA impelmentation with multiple prime factors).

Improve this answer
$\endgroup$
0

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.