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 1


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

  • 1
    $\begingroup$ 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)$. $\;\;\;\;$ $\endgroup$
    – user12859
    Commented Dec 9, 2015 at 6:36
  • $\begingroup$ @RickyDemer, oh, right, good point! Thanks for the correction. $\endgroup$
    – D.W.
    Commented Dec 9, 2015 at 7:39
  • $\begingroup$ @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. $\endgroup$
    – Ragnar
    Commented Dec 9, 2015 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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