Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

migrated from security.stackexchange.com Dec 20 '12 at 12:08

This question came from our site for Information security professionals.

4 Answers 4

up vote 17 down vote accepted

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.

share|improve this answer
    
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.

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

share|improve this answer
    
Shouldn't that be: $\phi(n) = (p-1) \cdot (q-1)$? –  Nik Bougalis Dec 20 '12 at 12:36
    
@NikBougalis Yes it should. Fixed. –  CodesInChaos Dec 20 '12 at 12:40

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

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.