RSA - is it possible to find the modulus from both the private and public exponents?

Let $$e$$ be the public exponent (which is equal to $$65537$$) and $$d$$ the private exponent. Knowing the values of those two, is it possible to deduce $$N$$, the modulus, and if yes, how?

Note: the value of $$N$$ is not known! I also don't need to get the values of $$p$$ and $$q$$, but seeing how $$d$$ is actually calculated makes me think it'd be easy to get them anyway.

• stack fu – kelalaka Oct 10 '18 at 5:22
• @MaartenBodewes The value of N is not known. – sx86 Oct 10 '18 at 5:55
• @kelalaka As far as I can see, there are no questions where you do not have the modulus. Only those looking to find its prime factors. – sx86 Oct 10 '18 at 6:10
• The question's "(which is not known)" is contradicted in the sentence that follows! Also: depending on the definition of RSA, there can be several private exponents $d$ for a given public exponent $e$. Even when there is only one, there are two alternate definitions of the private exponent around: $d=e^{-1}\bmod\lambda(N)$ (mandated in FIPS 186-4) and $d=e^{-1}\bmod\varphi(N)$ (used in some textbooks), where $\lambda(N)-\text{lcm}(p-1,q-1)$ and $\varphi(N)=(p-1)(q-1)$ when $N=p\,q$ with $p$ and $q$ distinct primes. Is it settled which definition is used? Is it settled on small $e$? – fgrieu Oct 10 '18 at 6:36
• You said $d$ is not known, but then you say that it is known. Which is it? – forest Oct 10 '18 at 6:46

It turns out that recovering $$N$$ from $$e, d$$ is a hard problem; in particular, if you can, you can factor values that are currently believed to be intractable (!).

To start with, a necessary and sufficient condition on $$e, d$$ being valid RSA exponents to a square-free modulus $$N$$ is that, for every prime factor $$p$$ of $$N$$, we have:

$$ed - 1 = k(p-1)$$

for some integer $$k$$.

Now, let us assume that we have an Oracle that, given $$e, d$$, will recover a value $$N$$ for which $$e, d$$ are valid RSA exponents (assuming there is such an $$N$$); we further assume that it gives a reasonably large value $$N$$, specifically, one in the range $$\ell \sqrt{eq} < N < 5ed$$ (for a modest constant $$\ell$$).

Now, suppose that we have a value $$N = pq$$, where $$p, q$$ are both unknown Sophie-Germain primes (that is, $$2p+1$$ and $$2q+1$$ are also prime), and are approximately the same size; that is $$q < p < 2q$$. We will also assume that the value $$2pq+1$$ and $$4pq+1$$ both happen to be composite (which it will be for a majority of the possible $$p, q$$ pairs).

Assuming $$N$$ is sufficiently large, there is no known way to factor it.

We note that $$p \equiv q \equiv 2 \pmod 3$$, and hence $$2N + 1$$ is a multiple of 3. So, we set $$e = 3$$ and $$d = (2N + 1)/e$$; and give $$d, e$$ to our Oracle.

What the Oracle will do is return a value $$N' = p_1' p_2' … p_n'$$ (where $$p_1', p_2', …, p_n'$$ is the prime factorization of $$N'$$. Such an $$N'$$ will always exist, as $$N' = (2p+1)(2q+1)$$ is such a valid modulus (hence the Oracle must return some value, if not necessarily $$(2p+1)(2q+1)$$

Because of the condition on RSA exponents, we have $$ed - 1 = 2pq = k_i(p_i' - 1)$$ for every prime $$p_i'$$.

Because of the range limitation on $$N'$$ (that is, $$\ell \sqrt{eq} < N'$$), we must have $$p$$ as one of the factors of $$p_i' - 1$$ (for some $$i$$), and similarly have $$q$$ as a factor of $$p_j'-1$$ (for some different $$j$$; it must be different, otherwise this prime factor would be $$2kpq+1$$; we assumed that $$k=1$$ and $$k=2$$ didn't yield a prime, and $$k>2$$ have a value outside the $$5ed$$ range we assumed).

Hence, we have $$N' = k''(k'''p + 1)(k''''q + 1)$$, for modest $$k'', k''', k''''$$. Given that, and $$N = pq$$, it's easy to factor $$N$$.

This is much more of a sketch than I originally intended; there are a number of missing details. However it should not be hard to fill in the details...