El Gamal special construction

Question

The algorithm:

I have to determine if the following algorithm is secure:

• $p,q \in \mathbb{P}$

and

• $N = p \cdot q$

$e \in [2, N - 1]$ such that $\gcd(e, N) = 1$

$r_1, r_2$ are random numbers in the range $[2, N - 1]$

• $a_1 \equiv e^{r_1(p-1)} \pmod N$
• $a_2 \equiv e^{r_2(q-1)} \pmod N$

The public key is $(N, a_1, a_2)$ and the private key $(p, q, r_1, r_2)$

We encrypt a message $m$ as follow:

We take two random integers $s_1$ and $s_2$ in the range $[2, N - 1]$

• $d_1 \equiv {a_1}^{s_1} \pmod N$
• $d_2 \equiv {a_1}^{s_2} \pmod N$

Then we compute:

• $c_1 \equiv m \cdot d_1 \pmod N$
• $c_2 \equiv m \cdot d_2 \pmod N$

$(c_1, c_2)$ is the cipher text.

How to recover the message $m$ without the private key?

What I tried:

First, we can decrypt a message (with private key) by using Fermat's Little Theorem.

• I tried to compute $\gcd(c_1 + i \cdot N, c_2 + i \cdot N)$ as usually $d_1$ and $d_2$ are coprime.

• I found that we can have a linear relation between $a_1$ and $a_2$ (i.e. $\exists k \ a_2 \equiv ka_1 \pmod N$) same for $c_1$ and $c_2$

Answer 1

Since $a_1 = e^{r_1(p-1)} \bmod N$ and since $p$ divides $N$, it follows that $a_1 \equiv e^{r_1(p-1)} \equiv 1 \pmod p$. We so have $a_1 - 1 \equiv 0 \pmod p$ or, equivalently, $a_1-1$ is a multiple of $p$. In turn, this implies (with overwhelming probability) that $\gcd(a_1-1,N) = p$ and thus $q =N/p$.

Since $d_1 \equiv {a_1}^{s_1} \equiv 1 \pmod p$ and similarly since $d_2 \equiv 1 \pmod q$, message $m$ can be recovered as $\operatorname{CRT}(c_1 \bmod p, c_2 \bmod q)$, using the values of $p$ and $q$ as obtained above.