In RSA, why would we ever want to find the values of p and q if we already know phi(n)?

Question

I'm studying RSA for the first time, and I know that $p$ and $q$ must be kept secret because with them we can calculate $\phi(n)$, which then lets us calculate the private key $d$. So $p$, $q$, and $\phi(n)$ are all kept secret.

Is there any reason we'd want to find $p$ and $q$ by working from the definition of $\phi(n)$ though? I'd think that an attacker wouldn't care about the specific values of $p$ and $q$ - if they have $\phi(n)$, they can calculate $d$ rightaway.

I ask this because I read this thread which showed how to get $p$ and $q$ from $\phi(n)$. I just don't see why we'd ever want to do that though. Why would an attacker care if $p$ = some number and $q$ = some other number, if they already have $\phi(n)$?

Answer 1

From an attacker's perspective, when we have $(n,e)$ and $\phi(n)$, we can compute a working $d\gets e^{-1}\bmod\phi(n)$. It will allow decryption or signature forgery in time polynomial to $\log(n)$: the attacker thus has won. Yet for repeated decryption or signature, the attacker may want to use the Chinese Remainder Theorem for efficiency, just like some legitimate users of RSA routinely do (see next section), which requires factoring $n$.

Also, the attacker might want to look at what the factors of $n$ are in hope to find patterns, in order to carry more attacks for other keys generated by the same method. And as kelalaka puts it, mathematical enthusiasm, curiosity, and searching for where that leads for better understanding are reasons enough.

---

The Chinese Remainder Theorem to speed-up RSA

A pragmatic reason both legitimate users of RSA and attackers want the factors of $n$ is they allow computation of the private-key function $x\mapsto y=x^d\bmod n$ several times faster using the Chinese Remainder Theorem.

When $n=p\,q$ with $p$ and $q$ distinct primes, that goes:

• precomputations done once:
  • $d_p\gets e^{-1}\bmod(p-1)\;$ or equivalently $\;d_p\gets d\bmod(p-1)$
  • $d_p\gets e^{-1}\bmod(q-1)\;$ or equivalently $\;d_q\gets d\bmod(q-1)$
  • $q_\text{inv}\gets q^{-1} \bmod p$
• for each computation $y\gets x^d\bmod n$ :
  1. $\;x_p\gets x^{d_p}\bmod p$
  2. $\;x_q\gets x^{d_q}\bmod q$
  3. $\;y\gets\big((x_p-x_q)\,q_\text{inv}\bmod p\big)\,q+x_q$

The execution time is dominated by steps 1 and 2. The cost of exponentiation modulo $m$ with the exponent the same size as $m$ grows about as $(\log m)^\alpha$ with $2<\alpha\le3$ (depending on arithmetic algorithms used for modular multiplication), and using the CRT roughly halves $\log m$. Thus (for large $p$ and $q$ of comparable magnitude) the work is reduced by a factor in the order of $3$ (obtained as $2^\alpha/2\,$). Also, it is possible to parallelize steps 1 and 2, further halving the wall clock time on a machine with two otherwise idle CPUs.

The technique is even more useful if $n$ has more than two prime factors, that's multi-prime-rsa. For the disputed history of that realization, see this. For the computations, see this.

It is not uncommon that software accepts a private key as $(n,e,d)$ yet use that speedup, in which case it will need to factor $n$, as follows.

---

Getting the factorization of $n$ from $(n,e,d)$ or $(n,\phi(n))$

When given $(n,e,d)$, we can factor $n$, but the usual method for this does not find $\phi(n)$ first, for that's not trivial. Sure, computing $(e\,d-1)/\left\lceil(e\,d-1)/n\right\rceil$ can yield $\phi(n)$ if $e$ is small and $d$ was computed as $d\gets e^{-1}\bmod\phi(n)$. However, neither condition is required by the modern definition of RSA¹.

The method generally used to factor $n$ from an RSA $(n,e,d)$ or $(n,\phi(n))$ computes $f\gets e\,d-1$ or sets $f\gets\phi(n)$, then uses that for any $w$ coprime with $n$, if holds $w^f\equiv1\pmod n$. The factorization of $n$ is possible using an algorithm in Gary L. Miller's Riemann's hypothesis and tests for primality, in Journal of Computer and System Sciences, 1976 (free PDF available). For odd composite square-free $n$, that goes:

• $r\gets 2f/(f\oplus(f-1))$ [this $r$ is odd and such that $f=r\,2^s$ for some $s$]
• repeat (few times, since each iteration succeeds with probability better than 50%)
  • draw a random integer $w$ in $[2,n-2]$
  • optional (and not useful for $n$ an RSA modulus)
    • $u\gets\gcd(w,n)$
    • if $u\ne1$
      • output "$u$ is a non-trivial factor of $n$" and stop.
  • compute $v\gets w^r\bmod n$
  • if $v\ne1$
    • while $v\ne1$ (that's at most $s$ times)
      • $u\gets v$
      • $v\gets v^2\bmod n$
    • if $u\ne n-1$
      • $u\gets\gcd(u+1,n)$
      • if $u\ne1$
        • output "$u$ is a non-trivial factor of $n$" and stop.

When $n$ has more than two factors, the algorithm can be used to fully factor $n$, by running it again replacing $n$ by $u$ or $n/u$, for any of these two that is not prime. We have not handled some tractable difficulties arising when $n$ is divisible by the square of a prime, but that's not the case in standard RSA.

Try It Online! This generates an $(n,e,d)$ with 2048-bit $n$ the product of two large distinct primes $p$ and $q$, and $\gcd(p-1,q-1)$ with a 256-bit prime factor, a large random $e$, and large $d$ with $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ [which makes computing $\phi(n)$ non-iteratively impossible AFAIK]; then finds the factorization of $n$ by Miller's algorithm.

---

¹ The de-facto definition of RSA is PKCS#1. It prescribes $e\in[3,n)$, $d\in[1,n)$, and $e\,d\equiv1\pmod{\lambda(n)}$. This uses the Carmichael function $\lambda$. When $n=p\,q$ with $p$ and $q$ distinct primes, it holds $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\phi(n)/\gcd(p-1,q-1)$. Using $\lambda$ (rather than $\phi$) makes the later equation the necessary and sufficient condition (rather than a sufficient but not necessary condition) for RSA encryption/decryption to succeed for any message in $\Bbb Z_n^*$, and in the whole $\Bbb Z_n$ when $n$ is squarefree. Using $\lambda$ allows at least $\gcd(p-1,q-1)$ working private exponents $d$ values, of the form $d_j=(e^{-1}\bmod\lambda(n))+j\,\lambda(n)$. That's at least two, and can be many (though rarely for random choice of primes $p$ and $q$). The FIPS 186-4 standard requires using $d_0$, which is often smaller than $e^{-1}\bmod\phi(n)$, often making raising to the power $d$ faster.

Answer 2

It shows that computing $\phi(n)$ is exactly as hard as factoring $n$. If one of these problems is easy, then the other is easy. If one is hard then the other is hard.

We acknowledge that RSA can be broken if an attacker computes $\phi(n)$, but now we know that this is not a fundamentally different attack than factoring $n$. We can no longer imagine a world in which one attack might be possible but the other impossible.

Suppose you're seeing the definition of $\phi$ for the first time. How much intuition do you have for the claim that computing $\phi$ is hard? Seeing that RSA is broken by computing $\phi$, you might not know how much faith to put into the security of RSA. But then you learn that computing $\phi$ is equivalent to factoring $n$, and factoring is probably the most fundamental/natural problem you could imagine! Factoring has been well-studied for thousands of years and still known to be hard, restoring your confidence in the security of RSA.

To be honest, RSA is not the best example of this concept, because the actual security property we use for RSA is that it is a "trapdoor function", and this property is not known to be equivalent to factoring. The best we can say is "key recovery attacks on RSA are equivalent to factoring," which is a big improvement from simply saying "factoring is one way to break RSA." (Factoring is one way to tackle lots of easy problems too, like computing GCD!) In general, it is desirable to show that "some class C of attacks" are equivalent to "hard problem P", where C is as large as possible and P is as thoroughly studied as possible.