1
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ If $y^3 \equiv c \pmod n$ and $z^3 \equiv c \pmod n$ then $\gcd(y-z,n)$ should give a factor of $n$. $\endgroup$ – user94293 May 31 '16 at 2:34
  • 1
    $\begingroup$ If the public exponent divides $(p−1)(q−1)$, then there is no well-defined private key, and that's not RSA. $\endgroup$ – fgrieu May 31 '16 at 7:53
  • $\begingroup$ @user94293 I am not sure that this is true if $c$ has more than $3$ qubic roots $(\mod n)$. Can you explain more precisely ? $\endgroup$ – brick May 31 '16 at 10:15
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for answer! One more question: if $gcd(y - z, n) = 1$, then $y^2z$, $yz^2$ and $x$ are $3$ different qubic roots of $x^3$, but this is again not enough to factorize $n$. However if somehow $4$ qubic roots of some element can be constructed $p$ or $q$ can be calculated for sure. So is there some trick to construct $4$ or more different qubic roots from the given two ? $\endgroup$ – brick May 31 '16 at 16:51
  • $\begingroup$ @brick: It is incorrect to say that $y^2z$ and $yz^2$ are additional cubic roots in this case. $\endgroup$ – user94293 May 31 '16 at 21:50

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.