# RSA using 2 as a public exponent

I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.

There's a similar question asking why it has to be in the form of $$2^n$$+1 but why not $$2^n$$

• $gcd(2,(p-1)(q-1)) =$? – kelalaka Dec 19 '18 at 12:41
• if p is odd a q is even it will be 1. if both are odd/both are even it will be 2? – S. L. Dec 19 '18 at 12:46
• $p$ and $q$ are prime >2 implies both odd. – kelalaka Dec 19 '18 at 12:46
• right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable – S. L. Dec 19 '18 at 12:50
• en.wikipedia.org/wiki/Rabin_cryptosystem – Maeher Dec 19 '18 at 12:52

It is not that RSA becomes insecure when used with public exponent $$2$$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.

The problem is that for $$N = pq$$ for two primes $$p$$ and $$q$$, the function $$f : x \mapsto x^2 \bmod N$$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $$4$$ preimages under $$f$$. (As pointed out by Thomas Pornin, the multiples of $$p$$ and $$q$$ have $$2$$, while $$0$$ has only one.)

We can get around this problem by choosing $$p\equiv q\equiv 3 \bmod 4$$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.

One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.

• Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck. – Thomas Pornin Dec 19 '18 at 13:37
• @ThomasPornin You are of course correct. – Maeher Dec 19 '18 at 13:44
• The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect). – R.. Dec 19 '18 at 16:25
• @R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now. – Maeher Dec 19 '18 at 16:35
• @Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent. – R.. Dec 19 '18 at 16:45