RSA encryption is based on the assumption that factoring large integers is hard. However, it’s possible that breaking RSA is easier than factoring. That is, the ability to factor large integers is sufficient for breaking RSA, but it might not be necessary.
Two years after the publication of RSA, Michael Rabin created an alternative that is provably as hard to break as factoring integers.
Like RSA, Rabin’s method begins by selecting two large primes, p and q, and keeping them secret. Their product n = pq is the public key. Given a message m in the form of a number between 0 and n, the cipher text is simply
c = m² mod n.
Rabin showed that if you can recover m from c, then you can factor n.
However, Rabin’s method does not decrypt uniquely. For every cipher text c, there are four possible clear texts. This may seem like a show stopper, but there are ways to get around it. You could pad messages with some sort of hash before encryption so that is extremely unlikely that more than one of the four decryption possibilities will have the right format. It is also possible to make the method uniquely invertible by placing some restrictions on the primes used.
I don’t know that Rabin’s method has been used in practice. I suspect that the assurance that attacks are as hard as factoring integers isn’t valuable enough to inspire people to put in the effort to harden the method for practical use [1].
There’s growing suspicion that factoring may not be as hard as we’ve thought. And we know that if large scale quantum computing becomes practical, factoring integers will be easy.
My impression is that researchers are more concerned about a breakthrough in factoring than they are about a way to break RSA without factoring [2, 3].
Related encryption posts
[1] One necessary step in practical implementation of Rabin’s method would be to make sure m > √n. Otherwise you could recover m by taking the integer square root rather than having to take a modular square root. The former is easy and the latter is hard.
[2] There are attacks against RSA that do not involve factoring, but they mostly exploit implementation flaws. They are not a frontal assault on the math problem posed by RSA.
[3] By “breakthrough” I meant a huge improvement in efficiency. But another kind of breakthrough is conceivable. Someone could prove that factoring really is hard (on classical computers) by establishing a lower bound. That seems very unlikely, but it would be interesting. Maybe it would spark renewed interest in Rabin’s method.