RSA when N=pq and p = q

I was curious what's to happen when $p = q$ for $N=pq$ in RSA scheme.

First I realize that one can easily find out $p$ and $q$ by taking a square root of $n$.

However, it appears to me that under $\pmod{N}$ where $p = q$, one cannot reliably retrieve the original message via $m^d$ where $m$ denotes an encrypted message and $d$ denotes the decryption key. Can someone explain why?

Thank you.

Solution 1:

There is Euler's theorem, and then RSA's recommended way of using it for encryption. I think your confusion arises from not realising the distinction. For any positive integers $k$ and $n$ and any $b$ relatively prime to $n$ we have, by Euler's theorem, $$b^{k\varphi(n)+1}\equiv b\pmod{ n}\qquad(*) $$ It does not matter whether $n$ is product hundred primes are a square or a cube. Now if we can factorize $k\varphi(n)+1 = d\times e$ we can rewrite the above equations as $$ (b^e)^d\equiv b\pmod n$$ And so $e$ can be used for encryption sending $b$ to $b^e\pmod n$, and $d$ can be used for decryption, these are inverse operations follows from the Eqn.$(*)$.

RSA recommends us to choose $n$ as product of two large primes. The only reasons for that is all $b<p$ (assuming $p<q$) are guaranteed to be coprime to $n$ and more importantly calculating $d$ with the knowledge of the public key $e$ and $n$ will be difficult, as it rests on the known difficult problem of factorizing $n$. If a number is a product of many numbers factorization attempts have better chances of succeeding.

You may ask why not choose $n$ as a prime then without factorizing one can calculate $d$ from $e$ and $n$ ($=p$), using Extended Euclidean Algorithm.