El Gamal special construction 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$
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.