# Does a 2047-bit factoring oracle affect 2048-bit RSA security?

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.

• 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. Jun 9, 2022 at 22:43
• @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? Jun 10, 2022 at 5:22
• 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. Jun 10, 2022 at 9:49
• 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. Jun 11, 2022 at 19:41

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.