# Prove that Alice’s solution x is equal to Bob’s plaintext m

The answer to the second part of this question exists already. However, I need help understanding how the first part of the question is solved. I have a feeling that it must have something to do with FLT, although I can't figure it out.

Could someone post the proof or hint me in the right direction? It feels like I am missing something very obvious although I'm not sure what.

Alice chooses two large primes $$p$$ and $$q$$ and she publishes $$N = pq$$. It is assumed that $$N$$ is hard to factor. Alice also chooses three random numbers $$g$$, $$r_1$$, and $$r_2$$ modulo $$N$$ and computes $$g_1\equiv g^{r_1\cdot(p−1)}\pmod N\text{ }\text{ and }\text{ }g_2\equiv g^{r_2\cdot(q−1)}\pmod N.$$

Her public key is the triple $$(N,g_1,g_2)$$ and her private key is the pair of primes $$(p,q)$$.

Now Bob wants to send the message $$m$$ to Alice, where $$m$$ is a number modulo $$N$$. He chooses two random integers $$s_1$$ and $$s_2$$ modulo $$N$$ and computes $$c_1\equiv m\cdot{g_1}^{s_1}\pmod N\text{ }\text{ and }\text{ }c_2\equiv m\cdot{g_2}^{s_2}\pmod N.$$ Bob sends the ciphertext $$(c_1,c_2)$$ to Alice.

Decryption is extremely fast and easy. Alice use the Chinese remainder theorem to solve the pair of congruences $$x\equiv c_1\pmod p\text{ }\text{ and }\text{ }x\equiv c_2\pmod q.$$

(a) Prove that Alice’s solution $$x$$ is equal to Bob’s plaintext $$m$$.
(b) Explain why this cryptosystem is not secure.

• Hint: $g^{p - 1} \equiv 1 \pmod p$. Can you write ${g_1}^{s_1}$ in terms of $g^{p - 1}$? – Squeamish Ossifrage Mar 20 at 23:13
• @SqueamishOssifrage I think I get it. Is the jist of the solution the fact that if lets say: m = pk and m = qc, then since c1 ≡ k (mod p) and c2 ≡ c (mod q), m ≡ k (mod p) and m ≡ c (mod q)? – Grom Mar 20 at 23:56
• Not quite: $p\cdot k \equiv 0 \pmod p$ for any $k$. Here's another hint: What's $g_1 \bmod p$? – Squeamish Ossifrage Mar 21 at 0:00
• @SqueamishOssifrage Ooops, sorry, I meant m = k + pg, and m = c + qn, for example. – Grom Mar 21 at 0:03
• I am not quite sure what your letters all mean now; is $g$ the base, and $n$ the modulus called $N$ in the answer? You don't need to write it out as explicitly as all that—can you follow the previous hints? – Squeamish Ossifrage Mar 21 at 0:06