# RSA limiting down the possible values for $n,q$, and $d$? given only $e$ and $p$ [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Dec 5 '18 at 15:17

• 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. – 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.
• 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.) – Maeher Dec 5 '18 at 10:37
• 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. – Maeher Dec 5 '18 at 10:44