# Issues in RSA setup

Suppose we have public key: $$n= 1015, e= 3$$ and private key: $$d= 635, p= 35, q= 29, \phi(n)= 952$$ For $m = 100$, we have $$c = m^e ~mod~n = 100^3 mod~1015 = 225.$$ To decipher this, let us take $$c^d~mod~n$$ which is $$225^{635}~mod~1015$$ which equals $$680$$ But $680 \neq 100$ so this means that RSA incorrectly decrypted it right? Why does this happen?

## 1 Answer

Your public key is not a legal RSA public key. In RSA, $n$ must be a product of two primes, but 35 is not a prime. Therefore, things don't work right: for instance, you got the wrong value of $\phi(n)$.

• RSA works even when the "message $m$ is not relatively prime to the modulus $n$". $\:$ The real problem is that, since $p$ is not prime, he got a wrong value of $\phi(n)$. $\;\;\;\;$ – user12859 Dec 9 '15 at 6:36
• @RickyDemer, oh, right, good point! Thanks for the correction. – D.W. Dec 9 '15 at 7:39
• @D.W. My implementation of isPrime(n) was slightly wrong...it went up to √n , when I adjusted it to go up to (√n) + 1 it works correctly. – Ragnar Dec 9 '15 at 15:27