-1
$\begingroup$

Suppose someone forgot the value of $n$ and you only knew the values for $e$ and $p$. How could one go about limiting down the possible values for $n,q$, and $d$?

I'm thinking to try and solve $\gcd(e, (p-1)(q-1)) = 1$ first for possible values of q and work backward from there but I don't really know/

$\endgroup$
2
  • $\begingroup$ This question is curiously similar to crypto.stackexchange.com/questions/64563/rsa-solve-equation asked a few hours ago under a different username. $\endgroup$
    – kodlu
    Dec 5, 2018 at 6:10
  • $\begingroup$ Do you know a rule that was used in the choice of $p$ and $q$ (like, they both belong to $]2^{(k-1)/2},2^k[$ for some $k$ (which is very common)? Do you also have examples of ciphertext, or signature? A single RSASSA-PKCS1-v1_5 signature and the matching message also allows to walk back to the full public and private key, given that $p$ is known. $\endgroup$
    – fgrieu
    Dec 5, 2018 at 8:51

1 Answer 1

1
$\begingroup$

As there are an infinite number of prime numbers, and $q$ can be any prime number other than $p$ and which his not coprime with $e$, it would be literally impossible to limit the possible values to any finite number. That is, you could limit it to any possible $q$, of which there are infinity.

$\endgroup$
4
  • $\begingroup$ Commonly it should be that $|p|=|q|$, so you are limited to primes of length $|p|$ which makes the number finite. (Not that this actually helps.) $\endgroup$
    – Maeher
    Dec 5, 2018 at 10:37
  • $\begingroup$ @Maeher It's still valid even if the sizes are different, even if it's uncommon. $\endgroup$
    – forest
    Dec 5, 2018 at 10:40
  • $\begingroup$ Valid in what sense? Yes, the RSA TDP works fine with any choice of $p,q$ as long as both are prime and $p\neq q$, but $p$ and $q$ are always sampled from a finite set of prime numbers. It is impossible to efficiently sample uniformly from the infinite set of all prime numbers, so that would not be a viable option. $\endgroup$
    – Maeher
    Dec 5, 2018 at 10:44
  • $\begingroup$ @Maeher Sure, but the question is about possible values, not realistic values or values that you'll commonly find coming from OpenSSL. RSA itself would work even if one prime is one digit and the other is 8192-bits in size. It wouldn't be secure, of course, but it would be possible. $\endgroup$
    – forest
    Dec 5, 2018 at 10:45

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