# 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?

-

## migrated from security.stackexchange.comDec 20 '12 at 12:08

This question came from our site for information security professionals.

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

-

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

-

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.

-
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