Converse of RSA

The security of RSA encryption depends on the difficulty of factoring the product of two large primes. If you can factor large numbers efficiently, you can break RSA. But if can break RSA, can you factor large numbers?

Sorta. It's conceivable that there is a way to break RSA encryption without having to recover the private key. But if you can recover the private key, then you can factor efficiently. That is, if you can start with a public key (N, e), where N is the modulus and e is the encryption key, and recover the private key d, then you can efficiently factor N. See Fact 1" in [1].

Let n = log₂ N. Then the algorithm alluded to above can be run in O(n^3) time. But the best known factoring algorithms take more than O(exp(n^1/3)) time.

Related posts

• Encryption as hard to break as factoring
• RSA implementation flaws
• RSA factoring challenges

[1] Dan Boneh. Twenty Years of Attacks on the RSA Cryptosystem. Available here.

The post Converse of RSA first appeared on John D. Cook.