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

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

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

An attacker who can compute the $phi(n)$ then he can 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 the history, and a short history can be found in Twenty Years of Attacks on the RSA Cryptosystem

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.

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)}$

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