The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is there some other reason?
$\begingroup$
$\endgroup$
5
-
3$\begingroup$ Can you compute square roots over the integers efficiently? $\endgroup$– DrLecterJul 11, 2015 at 8:02
-
$\begingroup$ @DrLecter Yes, given an integer $N$, do a binary serch in $\{1^2,2^2,\dots,N^2\}$ for a value which equals $N$, you need to perform $O(\log_2 N)$ squarings. $\endgroup$– fkraiemJul 11, 2015 at 11:29
-
4$\begingroup$ @fkraiem It was intended as a hint for the OP ;) $\endgroup$– DrLecterJul 11, 2015 at 11:57
-
$\begingroup$ @fkraiem since you brought it up: perhaps it can be done even quicker by restricting to a small range around half the bit length of $N$. $\endgroup$– David ZJul 11, 2015 at 16:34
-
$\begingroup$ Newton's method with integer division also works quite good. Complexity should be similar to binary search, but I think it approximates slightly faster. $\endgroup$– tyloJul 13, 2015 at 11:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The main reason why the prime factors $p$ and $q$ of RSA modulus $N$ must be distinct is stated in the question: if they are equal, given $N$ (which by definition is public in RSA), it is trivial to find $p=q=\sqrt N$.
A secondary reason is that with $p=q$, a few messages $x\in\{0\dots N-1\}$ can't be reliably deciphered from $x^e\bmod N$: all those $x$ such that $x\equiv0\pmod p$ encipher to $x^e\bmod N\;=\;0$. This would not be so much of a problem, because those $x$ are rare when $p$ is large, and in practice (when proper padding is used) $x$ is substantially random over $\{0\dots N-1\}$, thus the problematic $x$ are used with negligible probability.
Update: as pointed by Ricky Demer, there's an additional reason: with $p=q$, the private exponent $d$ would need to be computed with $d\equiv e^{-1}\pmod{p\cdot(p-1)}$ rather than the usual $d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}$
If $p$ and $q$ are suitably large and randomly chosen, they are distinct with overwhelming probability, thus the need that they are distinct is often not specified without invalidating quantitative theoretical results. In an implementation, if an explicit test is made, it can only hope to ever catch some gross malfunction of the key generator; same for customary tests that $p$ and $q$ are different enough, like FIPS 186's prescription that $|p-q|>2^{\lfloor\log_2(N)\rfloor/2-100}$ .
-
$\begingroup$ Just to clarify, instead of $d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}$ we could have done modulus with (p-1)*(q-1) also,right? $\endgroup$– rt_mnJul 11, 2015 at 8:57
-
1$\begingroup$ @rt_mn: in RSA with distinct primes $p$ and $q$, $d\equiv e^{-1}\pmod{(p-1)\cdot(q-1)}$ is a sufficient, but not necessary condition for $d$ being a valid private exponent. $\endgroup$– fgrieu ♦Jul 11, 2015 at 13:07