Return to Answer

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including much too large to be factored.

In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the constraints on $p$ and $q$ (primes in a known range), few possibilities will remain, often a single one. $n$ follows. That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$ (which is plausible if that remaining composite is much below $p$ an $q$).

The proportion of keys where that works depends on the modulus size, how hard we are willing to try to factor $e\,d-1$, and how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored.

In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the size and primality constraints on $p$ and $q$, few possibilities will remain, often a single one. $n$ follows. 

That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$. This is possible only if that remaining composite is less than $\max(p,q)$, and then only with low probability.

The proportion of keys where the methods works depends on the modulus size, on how hard we are willing to try to factor $e\,d-1$, and on how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).

• unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of known order of magnitude, say $\max(p,q)<2\min(p,q)$.
• given $(e,d)$ with small $e$ (e.g. one of the 5 Fermat primes).
• a known one of $d=e^{-1}\bmod\varphi(n)$ (as often in textbook RSA) or $d=e^{-1}\bmod\lambda(n)$ (as in FIPS 186-4) holds.

It holds $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\varphi(n)/g$, with $g=\gcd(p-1,q-1)$.

In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $h$, $p-1$ and $q-1$. Given the constraints on $p$ and $q$ (primes in a known range), few possibilities will remain (or is it often a single one). $n$ follows. That can also work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$ (which is plausible if that remaining composite is much below $p$ an $q$).

The proportion of keys where that works depends on the modulus size, how hard we are willing to try to factor $e\,d-1$, and how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. $2k/3$ bit), the task will be hard; but typical parametrization is lower).

• unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<2\min(p,q)$.
• given $(e,d)$ with small $e$ (e.g. one of the 5 Fermat primes).
• a known one of $d=e^{-1}\bmod\varphi(n)$ (as often in textbook RSA) or $d=e^{-1}\bmod\lambda(n)$ (as in FIPS 186-4) holds.

It follows from their respective definition that $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\varphi(n)/g$, with $g=\gcd(p-1,q-1)$.

In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the constraints on $p$ and $q$ (primes in a known range), few possibilities will remain, often a single one. $n$ follows. That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$ (which is plausible if that remaining composite is much below $p$ an $q$).

The proportion of keys where that works depends on the modulus size, how hard we are willing to try to factor $e\,d-1$, and how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest.

We need to factor that $m_4$, because it is still too large to be a divisor of $p-1$ or $q-1$. The commands ecm -pm1 3e8 <m4 failed after ≈85s. The command ecm -pp1 1e8 <m4 failed after ≈69s. The command ecm 1e8 <m4 launched repeatedly on multiple cores repeatedly failed after ≈272s. We are not particularly unlucky there.

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including much too large to be factored.

We need to factor that $m_4$, because it is still too large to be a divisor of $p-1$ or $q-1$. The command ecm -pm1 3e8 <m4 failed after ≈85s. The command ecm -pp1 1e8 <m4 failed after ≈69s. The command ecm 1e8 <m4 launched repeatedly on multiple cores repeatedly failed after ≈272s. We would have been very lucky if that had worked.