Can someone help me see the flaw in this cryptosystem?

Note: This is homework and it is due today at 1:30pm. An answer before that is not expected; I'd just like to understand what the flaw is.

From An Introduction to Mathematical Cryptography By Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman (Springer, 2008); problem 3.10, found one click away from here:

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.

I can verify A but am having trouble seeing where the cryptosystem is weak. Avenues I've explored:

  1. The modulus is factorable
  2. The encrypted text is easily decryptable

But I'm just not seeing the answer. Can I have some help?

  • $\begingroup$ It is hard to tell from the question what the math is. You can use TeX style formatting to clarify. Also, it is probably not wise to link to material that likely violates copyright law. $\endgroup$ – mikeazo Nov 11 '14 at 13:38
  • 3
    $\begingroup$ Hint: what is $g_1 \bmod p$? How can the attacker use that to factor $N$? $\endgroup$ – poncho Nov 11 '14 at 13:43
  • $\begingroup$ g1 mod p and g2 mod q are both 1. Which would mean that (g1-1)*(g2-1) mod n = 0 which I would think implies that g1-1 and g2-2 are the factors of n but that's not the case. $\endgroup$ – Reuben Tanner Nov 11 '14 at 13:59
  • $\begingroup$ Oh! But they are factors of some multiple of n! $\endgroup$ – Reuben Tanner Nov 11 '14 at 14:06
  • 2
    $\begingroup$ Hint: use GCD... $\endgroup$ – mikeazo Nov 11 '14 at 14:19

From the key creators point of view, notice that:$g_1\bmod p=1$ and $g_2\bmod q=1$.

Which means that $(g_1-1)\cdot(g_2-1)\bmod N=0$.

Which implies that $g_1-1$ and $g_2-1$ share a common divisor with $p$ and $q$.

To obtain $p$ we simply take $\gcd(g_1-1,N)$.

To obtain $q$ we simply take $\gcd(g_2-1,N)$, or $N/p$.

Because we have been able to factor the modulus using only the public keys and with no protocol error on the part of the implementer, this cryptosystem is insecure.

| improve this answer | |

Your Answer

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

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