2
$\begingroup$

I know that decryption in the RSA cryptosystem works because$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv \left(P^{\phi\left(n\right)}\right)^kP\equiv P\pmod n,$where $ed=k\phi\left(n\right)+1$ for some integer $k$, because $ed\equiv1\pmod{\phi\left(n\right)}$, and by Euler's theorem, we have that $P^{\phi\left(n\right)}\equiv1\pmod n$, because $\left(P,n\right)=1$.

However, it also works when $\left(P,n\right)\neq1$, and I am not sure how to show this. I know that if $\left(P,n\right)\neq1$, then either $P=p$ or $P=q$, where $n=pq$, but that does not seem to help much. Could someone shed some light on this for me? Thanks in advance!

  • 0
    This might help: http://crypto.stackexchange.com/questions/1004/does-rsa-work-for-any-message-m2013-02-28

0 Answers 0