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$