4

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.

Maurice
  • 43

1 Answers1

2

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.

P Vanchinathan
  • 19,504
  • Let $p = 3$ and $N = p^2 = 9$. $(p-1) = 2$, so $(p-1)(p-1) = 4$. We let $e$, the encryption key to be $3$, since $gcd(3, 4) = 1$, and $d$, the decryption key $d = 3$. So, $ed = 1 \pmod{4}$. We intend to send message $5$. We encrypt, so $5^3 = 8 \pmod{9}$. Now, we decrypt, $8^3 = 648 = 1*8 = 8 \pmod{9}$. Am I missing something?... – Maurice Oct 16 '15 at 08:05
  • @Maurice: Your are wrong with computing $\varphi(n)$. It is $\varphi(9)=6$ and not 4. The formula $\varphi(n)=(p-1)(q-1)$ is valid only if $p\ne q$. – gammatester Oct 16 '15 at 08:18
  • Ohhhhhh thank you so much! :) This is so enlightening! In our class, they only taught that we should just compute (p-1)(q-1), not specifically mentioning that this IS the euler totient function! – Maurice Oct 16 '15 at 08:27