# 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)) =$? 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? 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 Dec 19 '18 at 12:50
• en.wikipedia.org/wiki/Rabin_cryptosystem Dec 19 '18 at 12:52
• The public exponent merely has to be relatively prime to λ(modulus), where λ is the Carmichael function. It is often chosen to be near a power of two because such an exponent eliminates all but one of the multiplies in the standard binary exponentiation square-and-multiply algorithm. Dec 19 '18 at 22:29

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. Dec 19 '18 at 13:37
• @ThomasPornin You are of course correct. 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). 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. 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. Dec 19 '18 at 16:45

I had this question in my homework and here how I answer it

When we want to pick $$d$$ as a private key, we calculate it by

$$ed = 1\ mod\ \phi(n)$$ this means d is modular multiplicative inverse of e in mod $$\phi(n)$$

and $$\phi(n) = (p-1).(q-1)$$, $$p$$ and $$q$$ are prime numbers.

$$\phi(n)$$ is always an odd number if $$e=2$$, $$gcd(2,\phi(n)) \neq 1$$ so there is no modular multiplicative inverse of e in mod $$\phi(n)$$. this means we cant calculate $$d$$

This method can be used for all numbers with the form of $$2^n$$