7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow! Love the example! That is an awesome answer! Thanks! $\endgroup$ – Markus A. Jul 2 at 4:20
5
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – fgrieu Jun 30 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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