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?

  • 2
    $\begingroup$ The main mistake is that Bert should be Bob, or else Eve gets confused ... :) $\endgroup$ – 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.

  • $\begingroup$ So then its not true that $M^{sk} ≡M (mod p)$, right? $\endgroup$ – user140161 Nov 27 '18 at 23:13
  • $\begingroup$ 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 $\endgroup$ – user140161 Nov 27 '18 at 23:16
  • $\begingroup$ @user140161 bad example as $21$ is not relatively prime to $91$. $\endgroup$ – Henno Brandsma Dec 1 '18 at 14:19
  • $\begingroup$ 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. $\endgroup$ – 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.)

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

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.