0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ stack fu $\endgroup$ – kelalaka Oct 10 '18 at 5:22
  • $\begingroup$ @MaartenBodewes The value of N is not known. $\endgroup$ – sx86 Oct 10 '18 at 5:55
  • $\begingroup$ @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. $\endgroup$ – sx86 Oct 10 '18 at 6:10
  • $\begingroup$ 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$? $\endgroup$ – fgrieu Oct 10 '18 at 6:36
  • $\begingroup$ You said $d$ is not known, but then you say that it is known. Which is it? $\endgroup$ – forest Oct 10 '18 at 6:46
1
$\begingroup$

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

$\endgroup$

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.