1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: $g^{p - 1} \equiv 1 \pmod p$. Can you write ${g_1}^{s_1}$ in terms of $g^{p - 1}$? $\endgroup$ – Squeamish Ossifrage Mar 20 at 23:13
  • $\begingroup$ @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)? $\endgroup$ – Grom Mar 20 at 23:56
  • 1
    $\begingroup$ Not quite: $p\cdot k \equiv 0 \pmod p$ for any $k$. Here's another hint: What's $g_1 \bmod p$? $\endgroup$ – Squeamish Ossifrage Mar 21 at 0:00
  • $\begingroup$ @SqueamishOssifrage Ooops, sorry, I meant m = k + pg, and m = c + qn, for example. $\endgroup$ – Grom Mar 21 at 0:03
  • $\begingroup$ 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? $\endgroup$ – Squeamish Ossifrage Mar 21 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.