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

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

Answer 4

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 5

The RSA paper is giving a simple argument in their IX-B section;

Computing $\phi(n)$ Without factoring $n$

An attacker who can compute $\phi(n)$ can then break the system by computing the inverse of $d$ of $e$ modulo $\phi(n)$.

They argue that finding $\phi(n)$ is not easier than factoring since it will enable factoring as follows;

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

As a result, breaking the system by computing $\phi(n)$ is no easier than by factoring.

---

For the breaking part; there is a nice paragraph in the conclusion of the paper;

The security of this system needs to be examined in more detail. In particular, the difficulty of factoring large numbers should be examined very closely. The reader is urged to find a way to “break” the system. Once the method has withstood all attacks for a sufficient length of time it may be used with a reasonable amount of confidence

The rest is history, and a short history can be found in Twenty Years of Attacks on the RSA Cryptosystem