0
$\begingroup$

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!

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Assume that $g$ is coprime to $N$ (most likely the case). Then $g_1=g^{p-1}\equiv 1\pmod{p}$ by Little Fermat. Similarly $g_2=g^{q-1}\equiv 1\pmod q$. Therefore irrespective of the values of the integers $s_1$ and $s_2$ we have $$ c_1=mg_1^{s_1}\equiv m\pmod p\qquad\text{and}\qquad c_2=2mg_2^{s_2}\equiv m\pmod q. $$ Therefore $m$ can calculated with the aid of the CRT.

But also, because Eve knows $g_1$ and $g_2$, she can calculate $$ p=\gcd(g_1-1,N),\qquad q=\gcd(g_2-1,N), $$ so this cipher cannot really be called secure :-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .