4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Can you compute square roots over the integers efficiently? $\endgroup$ – DrLecter Jul 11 '15 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$ – fkraiem Jul 11 '15 at 11:29
  • 3
    $\begingroup$ @fkraiem It was intended as a hint for the OP ;) $\endgroup$ – DrLecter Jul 11 '15 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 Z Jul 11 '15 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$ – tylo Jul 13 '15 at 11:15
8
$\begingroup$

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}$ .

$\endgroup$
  • $\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_mn Jul 11 '15 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 '15 at 13:07

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.