# RSA Decryption: Doubts: knowing p or $\phi(n)$ can lead to find private exponent?

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$$?
• 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$... – poncho Mar 16 '20 at 17:45

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