This question already has an answer here:

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/


marked as duplicate by kelalaka, Geoffroy Couteau, Maarten Bodewes encryption Dec 5 '18 at 15:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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 '18 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 '18 at 8:51

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.

  • $\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 '18 at 10:37
  • $\begingroup$ @Maeher It's still valid even if the sizes are different, even if it's uncommon. $\endgroup$ – forest Dec 5 '18 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 '18 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 '18 at 10:45

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