# Why do $p$ and $q$ have to be different in RSA? [duplicate]

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?

## marked as duplicate by Squeamish Ossifrage, Ilmari Karonen, kelalaka, Maarten Bodewes♦ encryption StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 25 at 23:28

• Sidenote: $\varphi(n) = p (p-1) \neq (p-1)(p-1)$ in this case. – CodesInChaos Nov 13 '17 at 21:10
• 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! – Maarten Bodewes Nov 14 '17 at 9:51

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.

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).