5
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ $gcd(2,(p-1)(q-1)) =$? $\endgroup$ – kelalaka Dec 19 '18 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 '18 at 12:46
  • $\begingroup$ $p$ and $q$ are prime >2 implies both odd. $\endgroup$ – kelalaka Dec 19 '18 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 '18 at 12:50
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Rabin_cryptosystem $\endgroup$ – Maeher Dec 19 '18 at 12:52
13
$\begingroup$

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.

$\endgroup$
  • 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$ – Thomas Pornin Dec 19 '18 at 13:37
  • $\begingroup$ @ThomasPornin You are of course correct. $\endgroup$ – Maeher Dec 19 '18 at 13:44
  • 1
    $\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$ – R.. Dec 19 '18 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 '18 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$ – R.. Dec 19 '18 at 16:45

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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