What am I doing wrong decrypting this RSA message?

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?

• The main mistake is that Bert should be Bob, or else Eve gets confused ... :) – Hagen von Eitzen Nov 27 '18 at 22:58

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.

• So then its not true that $M^{sk} ≡M (mod p)$, right? – user140161 Nov 27 '18 at 23:13
• I was just wondering because calculating mod n is much harder by hand. For example i'm doing a problem right now and am finding it really tedious to calculate $21^{29}$ mod 91 – user140161 Nov 27 '18 at 23:16
• @user140161 bad example as $21$ is not relatively prime to $91$. – Henno Brandsma Dec 1 '18 at 14:19
• In fact it's very common to use the CRT when decrypting; most common RSA implementations use a special representation of the private key to facilitate it. So the private key is no longer just $(n,d)$ but also includes $p,q, d_p, d_q$ and some precomputed CRT-coefficient. – Henno Brandsma Dec 2 '18 at 13:28

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

• Why the downvote? Mistake somewhere? – Henno Brandsma Dec 1 '18 at 15:17