In RSA, is it possible to compute the private key if one knows one of the primes used to generate n?

Question

Within RSA the private key can be derived if one knows both $p$ and $q$. Is it possible to derive the RSA private key or decrypt / learn something about encrypted messages if you only know one of the prime numbers and not the modulus $n=pq$? The only available knowledge of the crypto-system is the ciphertext of a single encrypted message and the exponent ($e$) used.

EDIT: In actuality what I want to do is to retrieve the original message $m$ that was encrypted with the private key resulting from $p$ and $q$. I assumed that finding the original message would be equal in difficulty to calculating the private key.

Answer 1

I'll read the problem as stating we have $c$, $e$ and $p$ from some encryption $c=m^e\bmod(pq)$. But for some reason we do not have $n$ (even thought it is part of the public key, which is assumed public).

We know the order of magnitude of $q$, which likely is little above $\log_2(c)-\log_2(p)$-bit. But that's a far cry from $q$.

We can compute $d_p=e^{-1}\bmod p$, then $m_p=c^{d_p}\bmod p$ which is $m\bmod p$. Depending on context, that might let us guess $m$. For textbook RSA encryption and a narrow message (bit size of $m$ less or comparable to the bitsize of $p$), we will have $m=m_p$ or $m=m_p+k\,p$ for some small $k$, revealing $m$ or allowing to guess $k$ and $m$ if $m$ has some redundancy.

If we somewhat get the full $m$, we can compute $a=(m^e-c)/p$ and that's a multiple of $q$. If we are lucky, $a$ can be fully factored, revealing $q$. That's not entirely impossible for very small $e$ when using ECM to try to pull the factors of $a$.

If we can similarly find the full $m'$ for another $c'$, then we can compute $a'=(m'^e-c')/p$ and then compute $\gcd(a,a')$. That's a multiple of $q$, and has an excellent chance to be easy to fully factor, revealing $q$.

With $p$ and $q$, we can compute a working private key per any of the usual methods in RSA.

Answer 2

So, basically, we have $c = m^e \bmod pq$, where $p$ and $q$ are both primes, $c$, $e$ and $p$ are known, and you want to determine $q$.

Obviously, we have a trivial lower bound $q > c/p$, since otherwise $c$ could not be a reduced residue modulo $pq$. However, if $c$, $e$ and $p$ are all we know, then that's basically all you can say about $q$. The key observation here is that the RSA encryption operation $m \mapsto m^e \bmod pq$ is a permutation on the message space $\{1, 2, \dots, pq-1\}$, so for each $c$, $e$ and $pq > c$ there exists an $m$ satisfying the equation.

(We can say a little more, since the permutation property only holds if $p \ne q$ and if $e$ is coprime to both $p-1$ and $q-1$, which may allow us to rule out a few candidate $q$ primes. But if $e$ is a moderately large prime, e.g. 65537, then the coprimality rarely fails.)

If we also know the plaintext message $m$, however, then in principle we can rule out most primes $q$ simply by computing $m^e \bmod pq$ for each candidate $q$ and checking if it equals the known ciphertext $c$. However, doing this checking naively by brute force would be as hard as breaking normal RSA (where we don't know $p$ a priori, but can calculate it from the known public modulus $n = pq$ and its candidate factor $q$) the same way.

Off the top of my head, I don't see any obvious shortcut for determining $q$, given $m$, $c$, $e$ and $p$, faster than by brute force. That said, I also don't see any obvious way to reduce this to a known (presumably) hard problem, so I cannot be sure that no shortcut exists. It's possible that someone more familiar with these kinds of number theoretical problems than me might spot some obvious way to apply some known theorem to settle this question. Or, for all I know, it might be an open problem waiting for someone to take an interest in it.