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$

  • 3
    $\begingroup$ $gcd(2,(p-1)(q-1)) =$? $\endgroup$
    – kelalaka
    Dec 19, 2018 at 12:41
  • $\begingroup$ if p is odd a q is even it will be 1. if both are odd/both are even it will be 2? $\endgroup$
    – S. L.
    Dec 19, 2018 at 12:46
  • $\begingroup$ right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable $\endgroup$
    – S. L.
    Dec 19, 2018 at 12:50
  • 6
    $\begingroup$ en.wikipedia.org/wiki/Rabin_cryptosystem $\endgroup$
    – Maeher
    Dec 19, 2018 at 12:52
  • $\begingroup$ 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. $\endgroup$ Dec 19, 2018 at 22:29

2 Answers 2


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.

  • 5
    $\begingroup$ 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. $\endgroup$ Dec 19, 2018 at 13:37
  • $\begingroup$ @ThomasPornin You are of course correct. $\endgroup$
    – Maeher
    Dec 19, 2018 at 13:44
  • 2
    $\begingroup$ 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). $\endgroup$ Dec 19, 2018 at 16:25
  • $\begingroup$ @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. $\endgroup$
    – Maeher
    Dec 19, 2018 at 16:35
  • $\begingroup$ @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. $\endgroup$ Dec 19, 2018 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.