Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation:
$$x \equiv c \ (mod \ n)$$
are known (for some qubic residue $c$).
Then can $p$ and $q$ be effectively calculated using $y$ and $z$ and how ? Thanks in advance !
Let $n = pq$. By assumption, $3$ divides $\varphi(n) = (p-1)(q-1)$. Without loss of generality, I assume that $3$ divides $(p-1)$ or, equivalently, that $p \equiv 1 \pmod {3}$.
Fact Let $p$ be a prime such that $p \equiv 1 \pmod 3$. Let also $c$ be a cubic residue modulo $p$. If $y$ is a cubic root of $c$ then so are $y\cdot \omega \pmod p$ and $y \cdot \omega^2 \pmod p$, where $\omega$ is a non-trivial root of unity modulo $p$ (i.e., $\omega$ satisfies the equation $\omega^2 + \omega + 1 = 0 \pmod {p}$).
In your case, given $c \in \mathbb{Z}_n^*$, you know that $y$ and $z$ are two (distinct) cubic roots of $c$ modulo $n$. Namely, $y^3 \equiv z^3 \equiv c \pmod n$. In turn, this implies $y^3 - z^3 \equiv 0 \pmod n$ and thus $(y-z)(y^2+yz+z^2) \equiv 0 \pmod n$. Since $n = pq$, it follows that
$(y-z)(y^2+yz+z^2) \equiv 0 \pmod p$, and
$(y-z)(y^2+yz+z^2) \equiv 0 \pmod q$.
Subcase 1 Assume $q \equiv 2 \pmod 3$ —in this case, cubic roots modulo $q$ are unique. This implies that $y \equiv z \pmod q$. But you cannot have then $y \equiv z \pmod p$ because otherwise you would have $y = z \pmod {n}$ (and $y$ and $z$ are supposed to be distinct). Therefore, since $y \equiv z \pmod q$ yields $(y-z) \equiv 0 \pmod q$ and $y \not\equiv z \pmod p$ yields $(y-z) \not\equiv 0 \pmod p$, you get $\gcd(y-z,n) = q$.
Subcase 2 Assume now $q \equiv 1 \pmod 3$. In this case, there is no guarantee that $\gcd(y-z, n)$ will reveal a factor of $n$. Indeed, it may be the case that, even if $y \neq z \pmod n$, $y^2 + yz + z^2 \equiv 0 \pmod p$ and $y^2 + yz + z^2 \equiv 0 \pmod q$. But you can always give it a try...
