What am I doing wrong decrypting this RSA message?

Question

Here's a basic understanding I have of how RSA works from my notes.

Alice generates two primes $p$ and $q$ such that $n= pq$ and finds a $k$ such that $gcd(k,(p-1)(q-1))=1$.

She then finds an s such that $ks \equiv 1 (mod\space (q-1)(p-1))$ and publishes $(k,n)$.

Bert wants to send a message $M$. So he computes $M^k \equiv M^*$ (mod n).

Then Alice computes $(M^*)^s (mod \space n) $ to get the message.

The proof that I have that $(M^*)^s \equiv M (mod \space n) $ is as follows.

$(M^*)^s \equiv M^{sk} (mod \space n) $

$sk \equiv 1 \space (mod \space (p-1)(q-1))$

so $sk= l (p-1)(q-1) + 1$ where $l$ is an integer

Then $M^{sk} \equiv M $ (mod p) and $M^{sk}\equiv M $ (mod q)

Then because $p$ and $q$ are coprime

$M^{sk}\equiv M $ (mod n)

What I don't understand is that if $M^{sk}\equiv M $ (mod p) and $M^{sk}\equiv M $ (mod q) then to get $M$ why can't Alice simply compute $M^{sk} $ (mod p) or $M^{sk} $ (mod q) to get the message M, instead of computing $M^{sk}$ (mod n)? I tried this with an example but $M^{sk} $ (mod p), $M^{sk} $ (mod q) and $M^{sk} $ (mod n) all yield different results. Shouldn't they all give the same result?

Answer 1

If we know $x\bmod p$ and $x\bmod q$, we can uniquely determine $x\bmod pq$. This is the essence of the Chinese Remainder Theorem. For example if $p=5$, $q=11$ and we know $x\equiv 2\pmod 5$ and $x\equiv 9\pmod{11}$, then we must have $x\equiv 42\pmod{pq}$. You can use the extended Euclidean algorithm to obtain the $42$ result. In practice we compute $x^s\bmod {pq}$ directly because the extended gcd would just mean an additional step.

Answer 2

What you will see is that $M^{sk} \equiv M \pmod{p}$ and $M^{sk} \equiv M \pmod{q}$ as well, from which the CRT will tell us that $M^{sk} \equiv M \pmod{pq}$. In general knowing $M$ modulo $p$ or $q$ only will not tell you what $M$ is, you need both.

A simple example to illustrate: $p=7$, $q=13$, $n=91$, $M=16$, $k = 5$, $s=29$, where we indeed have that $5 \times 29 \equiv 1 \pmod{72}$, where $72=(p-1)(q-1)$.

So $M=16$ yields the encrypted value $E(M) = 16^5 \pmod{91} = 74$.

We see that working modulo $p$: $E(M)^s \equiv 2 \pmod{p}$, and indeed $M\equiv 16 \pmod{7}$ as promised.

Modulo $q$ we get $E(M)^s \equiv 3 \pmod{q}$ and indeed $M =16 \equiv 3 \pmod{13}$. Applying the CRT to the values $2$ and $3$ will give us back $M$ again, as does $E(M)^s \pmod{n}$, as standard RSA promises. The CRT implementation makes it easier to do the decryption if we want to work only modulo $p$ and $q$, e.g. see the Chinese Remainder section in the wikipedia page for RSA. Then we only need to take $E(M)$ to the powers $5 = 29 \pmod{6}$ modulo $7$ and $5= 29 \pmod{12}$ modulo $13$, as described there. Indeed $E(M)^5 = 2 \pmod{7}$ and $3= E(M)^5 \pmod{13}$ so all numbers involved get smaller. From the $2$ and $3$ we reconstruct the $M=16$ value again. (With a few extra computations, see the mentioned page.)