1
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
3
  • 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 Dec 9 '15 at 6:36
  • $\begingroup$ @RickyDemer, oh, right, good point! Thanks for the correction. $\endgroup$ – D.W. Dec 9 '15 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 Dec 9 '15 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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