Calculating RSA Public Modulus from Private Exponent and Public Exponent

Question

If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?

Answer 1

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.

I'll assume

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

It holds $h\,(p-1)(q-1)=(e\,d-1)$ or $h\,(p-1)(q-1)=g\,(e\,d-1)$ for some unknown $h<e$, and a $g$ that can be found by enumeration, for it is a small even integer, often $2$ (always in some key generation strategies), rarely above $10$.

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

The factorization strategy could be similar to that for arbitrary integers:

• pull the small factors of $e\,d-1$ by trial division.
• pull more small factors by Pollard's rho
• optionally but somewhat advantageously, some Pollard's p-1.
• optionally but still somewhat advantageously, some William's p+1.
• a lot of ECM, where most of the effort should be when we get barely enough $(e,d)$ pairs to hope find one allowing success.
• perhaps, if a large composite remains that needs to be factored, MPQS or GNFS.

---

Illustration, based on the the 829-bit RSA-250 recently factored.

We get $e=65537$ and the following 828-bit $d$ known to be $d=e^{-1}\bmod\varphi(n)$.

1219002363472329316632678572665837077877528004905520939230037996503041169769564562618818603930146413036298872224725717654149810234132887053185714832075764978825457518728410705223332728199047961645304133836997233492855592278022423674340390891560261753

We compute the 844-bit $m=e\,d-1$, and pull out its smalls factor $2^3\times3\times5\times13\times6221\times6213239\times440117350342384303$ (that's seconds), leaving a 740-bit $m_1$ to factor.

The command¹ ecm -pm1 1e7 <m1 found a 73-bit factor $8015381692860102796237$ in <3s, leaving a 667-bit $m_2$ to factor.

The command ecm -pp1 1e7 <m2 found a 67-bit factor $101910617047160921359$ in <7s, leaving a 600-bit $m_3$ to factor.

The command ecm -pp1 1e8 <m3 found a 72-bit factor $4597395223158209096147$ in <77s, leaving a 528-bit $m_4$ to factor.

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.

I did not really factor $m_4$ with GNFS², but that's well within reach. The factors of $m_4$ are 276-bit and 253-bit (the first two in the list below)

$p-1$ and $q-1$ are even, thus we have these 12 factors to split between $(p-1)/2$, $(q-1)/2$ and $h$:

72769022935390028131583224155323574786067394416649454368282707661426220155269516297
11015842872223957032465527015746975907581857223611379316467045416408679146689
8015381692860102796237
4597395223158209096147
101910617047160921359
440117350342384303
6213239
6221
13
5
3
2

There are a mere $3^{10}<2^{16}$ possibilities to explore after we assigned the first two entries to $(p-1)/2$ and $(q-1)/2$. We want to explore those with $\max(p,q)<2\min(p,q)$ and $h<e$. Pruning this tree requires only addition of approximate logarithms. That's a near-trivial knapsack problem. I've not coded it, but I'd be surprised if there was a solution yielding $p$ and $q$ prime other than $h=2\times3\times6221$, and these $p$ and $q$ which immediately yields $n=p\,q$, here RSA-250.

33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367

---

¹ GMP-ECM implements carefully optimized Pollard's p-1, William's p+1, and ECM. I let it use a random seed, thus some of the results may take a few runs to reproduce.

² I'm hearing a lot of good of the implementation in CADO-NFS.

Answer 2

In the normal setting $n=pq$ is public knowledge and $\varphi(n)$ is hidden, for a start.

I will assume $$ed\equiv 1 \pmod {\varphi(n)}\quad(1).$$ Since

$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$

Also, $n = pq$ and some manipulation gives

$$n = p \left ( n + 1 - \varphi{(n)} - p \right ) = -p^2 + (n + 1 - \varphi{(n)})p$$ and then $$p^2 - (n + 1 - \varphi{(n)})p + n = 0$$

which can be solved by the quadratic formula for $p.$ In conclusion, knowledge of $\varphi{(n)}$ allows one to factor $n$ in constant time.

But we don’t know $n$ and we only know $ed-1=k\varphi(n)$ for some positive integer $k$ from (1).

We can look for small divisors of $ed-1,$ since $k$ may have small divisors in an attempt to find $\varphi(n).$ This may give us a few small divisors but it may not be enough to determine $\varphi(n).$

However [see comments] this actually leaves only a few possibilities for $k$ and thus for we can quickly determine $\varphi(n)$.