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$
$\begingroup$
$\endgroup$
5
-
3$\begingroup$ $gcd(2,(p-1)(q-1)) =$? $\endgroup$– kelalakaDec 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$– MaeherDec 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$– President James K. PolkDec 19, 2018 at 22:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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
-
-
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$– MaeherDec 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
$\begingroup$
$\endgroup$
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$
