Why is it important that phi(n) is kept a secret, in RSA?

Question

Why is it important that $\phi(n)$ is kept a secret, in RSA?

Answer 1

From the definition of the totient function, we have the relation:

$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$

It then easily follows that:

$$(n + 1) - \varphi{(n)} = p + q$$ $$(n + 1) - \varphi{(n)} - p = q$$

And you know from the definition of RSA that:

$$n = pq$$

Substituting one into the other, you can derive:

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

With some rearranging, we obtain:

$$p^2 - (n + 1 - \varphi{(n)})p + n = 0$$

This is a quadratic equation in $p$, with:

$$\begin{align}a &= 1 \\ b &= -(n + 1 - \varphi{(n)}) \\ c &= n \end{align}$$

Which can be readily solved using the well-known quadratic formula:

$$p = \frac{-b \pm \sqrt{|b|^2 - 4ac}}{2a} = \frac{(n + 1 - \varphi{(n)}) \pm \sqrt{|n + 1 - \varphi{(n)}|^2 - 4n}}{2}$$

Because of symmetry, the two solutions for $p$ will in fact be the two prime factors of $n$.

---

Here is a short example, let $n = 13 \times 29 = 377$ and $\varphi{(n)} = (13 - 1) \times (29 - 1) = 12 \times 28 = 336$. Using the quadratic equation shown above, we need to use the following coefficients for the equation:

$$\begin{align}a &= 1 \\ b &= -(377 + 1 - 336) = -42 \\ c &= 377 \end{align}$$

Thus we have the following quadratic to solve:

$$p^2 - 42p + 377 = 0 ~ \implies ~ p = \frac{42 \pm \sqrt{|-42|^2 - 4 \times 377}}{2} = \frac{42 \pm 16}{2}$$

Finally, we calculate the two solutions, which are the two prime factors of $377$ as expected:

$$\frac{26}{2} = 13 ~ ~ ~ ~ ~ ~ ~ ~ \mathrm{and} ~ ~ ~ ~ ~ ~ ~ ~ \frac{58}{2} = 29$$

---

In conclusion, knowledge of $\varphi{(n)}$ allows one to factor $n$ in time $O(1)$. The other answers are equivalent, in that knowing $d$ achieves the same result (loss of any security properties of RSA), but just for completeness I thought it would be a good idea to show how $n$ can be factored with this information.

Answer 2

1. If you know $\phi(n)$ it's trivial to calculate the secret exponent $d$ given $e$ and $n$.
   In fact that's just what happens during normal RSA key generation. You use that $e \cdot d =1 \mod \phi(n)$, and solve for $d$ using the extended Euclidian algorithm.

   Wikipedia about RSA key generation:

   Determine $d$ as: $d = e^{-1} \mod \phi(n)$
   i.e., $d$ is the multiplicative inverse of $e$ mod $\phi(n)$.

   • This is more clearly stated as solve for d given $(de) = 1 \mod \phi(n)$
   • This is often computed using the extended Euclidean algorithm.
   • $d$ is kept as the private key exponent.

2. Given $\phi(n)$ and $n$ it's easy to factor $n$ by solving the equations $n = p \cdot q$ and $\phi(n) = (p-1)\cdot(q-1)$ for $p$ and $q$.

Answer 3

Because with $\varphi(n)$ and $e$, you are able to calculate $d$ (which is the secret part of the RSA key) as $d$ is the modular multiplicative inverse of $e \bmod{\varphi(n)}$

Answer 4

Remember that with RSA the number $N$ is the product of two large secret primes. Let's call them $P$ and $Q$. We will treat them as our unknowns:

$$N = P \cdot Q$$

Also remember that we know that:

$$\phi(N) = (P-1) \cdot (Q-1)$$

Now $N$ is known, as part of the public key. If an atttacker also knows $\phi(N)$ it becomes trivial to recover $P$ and $Q$. Let's start:

$$\phi(N) = (P-1) \cdot (Q-1) \Leftrightarrow$$ $$\phi(N) = (P \cdot Q) - Q - P + 1$$

But remember that $N = P \cdot Q$ so we have:

$$\phi(N) = N - Q - P + 1 \Leftrightarrow$$ $$P + Q = N - \phi(N) + 1$$

Now let's now express $Q$ in terms of $P$ and $N$:

$$P + \frac{N}{P} = N - \phi(N) + 1 \Leftrightarrow$$ $$\frac{P^2}{P} + \frac{N}{P} = N - \phi(N) + 1 \Leftrightarrow$$ $$\frac{P^2 + N}{P} = N - \phi(N) + 1 \Leftrightarrow$$ $$P^2 + N = P \cdot (N - \phi(N) + 1) \Leftrightarrow$$ $$P^2 - P \cdot (N - \phi(N) + 1) + N = 0$$

This looks like a quadratic where $P$ is our variable, and $a = 1$, $b = (N - \phi(N) + 1)$ and $c = N$, so use the quadratic formula to solve calculate the two solutions as: $$\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

Those two solutions are the values of the secret primes $P$ and $Q$. In other words, knowing both $N$ and $\phi(N)$ an attacker can trivially recover $P$ and $Q$ and therefore recreate the RSA public and private keys.

That is why it's important to keep $P$, $Q$ and $\phi(N)$ secret and never reveal them.