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

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

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}

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

• Beat me to it... perfect explanation. – Nik Bougalis Dec 20 '12 at 13:15
• This is excellent. Very well done. – Polynomial Dec 20 '12 at 13:40
• I think since it is important to keep the private exponent secret is a more important reason than since it hides the factorization – RSA's goal is not to hide the factorization of $n$, but to securely encrypt or sign. – Paŭlo Ebermann Dec 21 '12 at 9:02
• @PaŭloEbermann That is true, and the reason this answer is meant to be complimentary to CodesInChaos's one (expanding on his second point). That said, $n$ might be used in multiple cryptographic primitives (not just RSA) in any given protocol, so assuming you know $\varphi{(n)}$ (which in itself is rather contrived) you will want to get $p$ and $q$ to help attack those parts of the protocol as well, depending on what your goals as an attacker are. – Thomas Dec 21 '12 at 10:02
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.

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

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.

• This misses a bit about "why do we need these primes to be secret". RSA's goal is not to hide the factorization, but to be a trapdoor one-way function. – Paŭlo Ebermann Dec 21 '12 at 9:07
• That's a fair point; I could have added a note about that, but the fact is that $P$ and $Q$ should be kept secret is well known and the original question was: "Why is it important that $ϕ(n)$ is kept a secret, in RSA?" – Nik Bougalis Dec 21 '12 at 18:21

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

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