# Calculating RSA Public Modulus from Private Exponent and Public Exponent

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

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

• Wow! Love the example! That is an awesome answer! Thanks! – Markus A. Jul 2 '20 at 4:20

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

• Remark that if $d=e^{-1}\bmodφ(n)$ as customary, then it holds $e\,d-1=k\,φ(n)$ for some positive $k<e$. And then for usual $e$ that leaves few choices for $k$, thus for $φ(n)$. – fgrieu Jun 30 '20 at 8:44