I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution work.
Alice chooses two large primes $p,q$ and denotes $N=pq$; then she also chooses three random numbers $g, r_1,r_2\in\mathbb{Z}_N$ and computes
$$g_1\equiv g^{r_1(p-1)}\mod N,\hspace{5mm}g_2\equiv g^{r_2(q-1)}\mod N.$$
The 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\in\mathbb{Z}_N$. He chooses
two random numbers $s_1,s_2\in\mathbb{Z}_N$ and computes
$$c_1\equiv mg_1^{s_1}\mod N,\hspace{5mm}c_2\equiv mg_2^{s_2}\mod N.$$
Bob sends the ciphertext $(c_1, c_2)$ to Alice. Then Alice uses the Chinese Remainder Theorem to solve the system of congruences $x\equiv c_1\mod p$ and $x\equiv c_2\mod q$ to obtain her solution $x\equiv m\mod N.$
Given only the public key $(N,g_1,g_2)$ and the ciphertext $(c_1,c_2)$, can one still decrypt the ciphertext and obtain $m$?
Intuitionally, I want to somehow use some manipulation on $g_1$ and $g_2$ to either find the primes $p,q$ and solve normally or find the message $m$ directly. But multiplying them, taking inverses, trying to apply the Chinese Remainder Theorem, etc. gets me nowhere. I appreciate any help!
Answer
The fact that $g_1 \equiv 1 \bmod p$ tells you that $g_1 - 1$ is divisible by $p$. But $N$ is also divisible by $p$.
So if you work out the greatest common divisor of $g_1 - 1$ and $N$ using elementary methods then you are sure to recover the value of $p$ (This is because $N=pq$ has only one proper divisor that is divisible by $p$, this is $p$ itself).
No comments:
Post a Comment