The algorithm:

I have to determine if the following algorithm is secure:

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


  • $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$

  • $\begingroup$ we have $m \cdot d_1 \equiv m \pmod p$ and $m \cdot d_2 \equiv m \pmod q$. Then by using CRT we get $m$ $\endgroup$ – Jeremy May 28 '16 at 13:35

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.

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