1
$\begingroup$

This question already has an answer here:

When using RSA cryptography, it is possible to have the decrypted message and the initial message the same when $p$ and $q$ are the same. So why are they always different?

$\endgroup$

marked as duplicate by Squeamish Ossifrage, Ilmari Karonen, kelalaka, Maarten Bodewes encryption Apr 25 at 23:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Sidenote: $\varphi(n) = p (p-1) \neq (p-1)(p-1)$ in this case. $\endgroup$ – CodesInChaos Nov 13 '17 at 21:10
  • $\begingroup$ Well, if this was secure it would be faster than "Fast RSA" used in the Infineon chips for sure. And even less secure. Intuitively you already know it is not secure because everyone would be using it already: it would halve the time for RSA key pair generation! $\endgroup$ – Maarten Bodewes Nov 14 '17 at 9:51
9
$\begingroup$

Because factoring $n$ where $n=pq$ and $p=q$ is really, really easy, take a square root. If you can factor $n$, you can break RSA. Therefore, having $p=q$ is detrimental to the security of RSA.

$\endgroup$
3
$\begingroup$

RSA works as long as $\operatorname{GCD}(e,\varphi(N))=1$, in the sense that $(m^e)^d \equiv m \pmod N$. Even if some or all factors of $n$ are the same or $N$ is prime.

But if an attacker knows you chose $N=p^2$, they can simply factor $N$ by computing a square-root. So it is not secure to choose $N$ like that.


Note however that you need to adjust the calculation of Euler's totient function $\varphi(N)$ if there a duplicate factors:

$\varphi(p_1^{k_1} \cdot ... \cdot p_n^{k_n})=\prod\limits_{i=0}^n p_i^{k_i-1} (p_i-1)$ where $p_i$ are the distinct prime factors of $N$

Which in the case of $N=p^2$ works out to $p(p-1)$ and not $(p-1)^2$. So if you were to incorrectly compute $d$ using $e\cdot d \equiv 1 \pmod {(p-1)^2}$ instead of $\pmod{p(p-1)}$ it would not work.


Your exercise asks you to show that $e\cdot d \equiv 1 \pmod {(p-1)^2}$ does decrypt correctly when $n=p^2$. It then claims that:

(This illustrates why RSA requires distinct primes)

But this failure is only due to an incorrect computation of $\varphi$ and not due to RSA requiring distinct primes.


Many RSA implementations and standards only support the common case where $N$ is the product of two distinct primes and thus might misbehave when asked to operate on such unusual choices of $N$ (affects private-key operations like decryption and key generation, not public-key operations like encryption).

$\endgroup$

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