1
$\begingroup$

I have some doubts about RSA (the public key $n$ and $e$ is public):

Note $n = pq$ and $\phi (n) = (p-1)(q-1)$

  • 1) Say if some hacker knew $p$, why would it be easy for them to find $q, \phi (n), d$?

$d$ is a prime larger than $p, q$ so that $1 = k\cdot \phi(n) + d\cdot e$

  • 2) Now, say if a hacker knew $\phi (n)$, why would it be easy to find $p,q,d$?
$\endgroup$
1
  • $\begingroup$ BTW: in general, $d$ needn't be prime (and, for that matter, it isn't always the case that there exists an integer $k$ s.t. $1 = k \cdot \phi(n) + d \cdot e$... $\endgroup$ – poncho Mar 16 '20 at 17:45
1
$\begingroup$
  • 1) Say if some hacker knew $p$, why would it be easy for them to find $q, \phi (n), d$?

Since $n = p \cdot q $ this implies $q$ is also known by simple division $p = n/q$.

Then $\phi(n) = (p-1)(q-1)$ is known

By using $e \cdot d \equiv 1 \bmod \phi(n)$ then $d$ is known. This can be found by the extended Euclidean algorithm.

$d$ is a prime larger than $p, q$ so that $1 = k\cdot \phi(n) + d\cdot e$

$d$ doesn't need to be prime. It can be larger or smaller than the $p$ and $q$ depend on the value of $e,p,q$.

  • 2) Now, say if a hacker knew $\phi (n)$, why would it be easy to find $p,q,d$?

$d$ is as above.

1. Method with the knowledge of $\phi (n)$

$\phi(n) = (p-1)(q-1) = (n + 1)- (p+q) $ implies $$p+q = (n +1) - \phi(n)$$ and

$$q = (n+1) - \phi(n) - p $$ since we have $$ n = pq $$ substitue

$$n = p \left ( n + 1 - \phi{(n)} - p \right ) = -p^2 + (n + 1 - \phi{(n)})p$$ $$p^2 - (n + 1 - \phi{(n)})p + n = 0$$

Now, we got a quadratic equation that can be solved by the quadratic polynomial root-finding formula;$$p = \frac{-b \pm \sqrt{b^2 -4ac}}{2a}.$$ Using the formula one gets;

$$p = \frac{(n + 1 - \phi{(n)}) \pm \sqrt{(n + 1 - \phi{(n)})^2 - 4n}}{2}$$

Therefore the knowledge of the $\phi(n)$ enables factoring the $n$ in constant time, $\mathcal{O}(1)$

2. Method with the knowledge of $\phi (n)$

  • $(p+q)$ can be obtained from $n$ and $\phi(n)$ as $$\phi(n) = (p-1)(q-1) = n - (p+q) +1$$
  • $(p-q)$ can be obtained from $(p+q)^2-4n$, since $(p-q)$ is the square root of it.

    Then one can find $q$ as $$q = \frac{(p+q)-(p-q)}{2}.$$

$\endgroup$

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.