Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.