RSA Encryption using Chinese Remainder Theorem and Fermat's Little Theorem

Question

Self-learning RSA encryption, came across this problem and would like help getting a better understanding of it. Already solved 7(a) and 7(b), but need help with number 8. Thanks!

Here is my work for the first part:

Answer 1

Note: there is a typo in your book. $s$ should be relatively prime to $q-1$ rather than $r-1$.

Case $M\equiv 0(\mod p)$ is trivial. Consider $M\not\equiv 0(\mod p)$:

$M^{(p-1)}\equiv 1(\mod p)$ (Fermat's little theorem)

$M^{x(p-1)}\equiv (M^{(p-1)})^{x}\equiv 1^{x}\equiv(\mod p)$

$(M^{s})^{a}\equiv M^{sa}\equiv M^{sa}\times 1\equiv M^{sa}M^{x(p-1)}\equiv M^{sa+x(p-1)}\equiv M^{1}\equiv M(\mod p)$

Same go for $q$.

Now as for my earlier comment, it's just abstract algebra. The proof in abstract algebra language is as follow:

As $r\mathbb{Z}$ and $p\mathbb{Z}$ are ideals of the ring $\mathbb{Z}$, third isomorphism theorem say there is a canonical isomorphism $(\mathbb{Z}/r\mathbb{Z})/(p\mathbb{Z}/r\mathbb{Z})\cong\mathbb{Z}/p\mathbb{Z}$ which induce a ring homomophism $\phi_{p}:\mathbb{Z}/r\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$. Same for $q$ there is a ring homomorphism $\phi_{q}:\mathbb{Z}/r\mathbb{Z}\rightarrow\mathbb{Z}/q\mathbb{Z}$. They in turn induce a product homomorphism $\phi:\mathbb{Z}/r\mathbb{Z}\rightarrow(\mathbb{Z}/p\mathbb{Z})\times(\mathbb{Z}/q\mathbb{Z})$. Chinese Remainder Theorem say that this homomorphism have trivial kernel, and hence is an isomorphism. Thus $\mathbb{Z}/r\mathbb{Z}$ is also a product of $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$ with canonical projection $\phi_{p}$ and $\phi_{q}$. Hence once we know $\phi_{p}(M)$ and $\phi_{q}(M)$ we can certainly identify $M$. We consider $\phi_{p}$ first. The case $\phi(M)=0$ is trivial. Otherwise, $\phi(M)\in U_{p}$ as $\mathbb{Z}/p\mathbb{Z}$ is a field. Since $U_{p}$ is an abelian group, we have the action $\mathbb{Z}$ on $U_{p}$ by exponentiation is an automorphism. The corresponding homomorphism $\mathbb{Z}\rightarrow Aut(U_{p})$ have kernel containing $\mathbb{Z}/(p-1)\mathbb{Z}$ since $U_{p}$ have order $p-1$. Henc this induce the action of $\mathbb{Z}/(p-1)\mathbb{Z}$ on $U_{p}$. Since $a$ is the inverse of $s$ in $\mathbb{Z}/(p-1)\mathbb{Z}$ their action are also inverse of each other. Hence $\phi(M)=\phi(E^{a})$ and the result follow.