3
$\begingroup$

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$

$\endgroup$
1
  • $\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, 2016 at 13:35

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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