# Why is Rabin encryption equivalent to factoring?

I don't understand the proof of equivalence I've read everywhere (e.g., in Rabin's paper or on Wikipedia).

Here's my objection: let's say you have a Rabin decryption oracle that takes n and c and returns one of the square roots of c mod n. It always returns the same square root for a given n and c, but the choice of output root is otherwise random over combinations of n and c. In this case, the oracle would decrypt the ciphertext somewhere between 25 and 50% of the time (depending on the number of roots of the ciphertext), but it's unclear to me how you could factor n on this basis.

I agree that an oracle that pops out both s and r allows one to easily factor n, but it's not necessary to do that to break Rabin at least 25% of the time.

• It is helpful if you link to the references you make. – schroeder Jul 23 '15 at 14:45
• That's probably why I didn't find this question posted already. This site is what I got when I Google'd "crypto stackexchange". – Kyle Rose Jul 23 '15 at 14:53

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations.

More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same applies modulo q, and makes four combinations. What you look for is a pair of values (a,b) such that both are square roots of the same value (i.e. a2 = b2 mod n), a = b mod p, and a = -b mod q (or vice versa). If you have such a pair, then c = a-b mod n will be an integer that is equal to 0 modulo p but not modulo q; in other terms, c will be a multiple of p but not of q, so a simple GCD computation between c and n will reveal p.

Suppose that you have a box that can compute square roots modulo n. Then, the attack works thus: generate a random a modulo n; compute a2 mod n and send it to the box. The box will return a square root b (one of the four possible square roots). If the box returns a itself, or n-a, then this round fails, and the attacker must start again with another random a. This happens 50% of the time. But if the box returns one of the two other square roots of a2 then the GCD explained above reveals a factor of n.

There is no square root choosing strategy from the box that can prevent this attack from working, because the attacker chooses a completely at random.

The above does NOT show that "Rabin encryption is equivalent to factoring". What it shows is that the general ability to extract square roots modulo n is equivalent to knowing the factors of n. The term "general" here means that the ability works for a substantial proportion of values which are squares modulo n. Anybody can compute square roots for some values (e.g. if we work modulo n and you challenge me with the value "9" then I can answer that a square root of that value modulo n is "3", and I can do that even without knowing the factors of n); but if you can do that for a non-negligible fraction of all integers modulo n then you can factor n.

There is no actual standard that specifies Rabin encryption, but if there was, then that standard would probably entail some sort of padding, because, as explained above, a square has four square roots. The decryption engine must choose which one is the right one. A simple strategy for that is to add some redundant padding: when encrypting message m, convert it to an integer x by appending h(m) to m (for some hash function h) and then interpreting the whole as an integer. Then, upon decryption, recompute the hash to know whether you got the correct square root, and not one of the three others. (The padding would also have to include some randomness to avoid brute force on the plaintext.)

With such a padding, a box that can decrypt things may return the decrypted value, OR it could say "this does not decrypt to anything that is properly padded". Then the attack explained above no longer works; the attacker will have to find a value a such that another square root b (which is neither a or -a) ends with a proper padding, otherwise the decryption oracle won't return it. Depending on how the padding is exactly defined, then the probability to hit such a value could be too small to actually happen.

Therefore, while extracting square roots modulo n is equivalent to factoring n, it cannot be said, in all generality, that practical Rabin encryption is equivalent to factoring. This depends on the details of padding and usage, details which are not, currently, defined.

After another 5 minutes of thought, I think I solved my own problem.

Choose an arbitrary message m, compute c=m^2 % n and submit c and n to the Rabin oracle. If you repeat this enough times (by which I mean probably within 2 iterations) you will choose m in such a way that the oracle gives you ± the other root, which you can then use to factor n.