1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ So you know $p$ and $e$ and maybe some ciphertext but not $n$? $\endgroup$ – SEJPM Aug 5 '18 at 20:32
  • $\begingroup$ Do you also know the (padded) plaintext corresponding to the message? If not, I'm pretty sure the answer is unconditionally "no". If yes, it should be theoretically doable if one had unlimited computing power, but I have no idea how computationally difficult it would actually be. $\endgroup$ – Ilmari Karonen Aug 5 '18 at 20:58
  • $\begingroup$ @SEJPM That is correct. The RSA key is essentially used to encrypt and decrypt data on a physical location. As it is deterministically derived (From factors unknown to an external attacker), there is no need to keep a public key available. I have listed all known variables on the original post, we have no information about the plaintext. $\endgroup$ – Alex Papageorgiou Aug 6 '18 at 8:14
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your response. You seem to mention that depending on the context we can guess $m$. I (perhaps) wrongly assumed that reversing the encryption process is equal in difficulty to finding the private key given $p$. Is there a way to actually extract the original $m$? Although I would prefer you not to, you can also assume that we know the $length$ of $m$ and it is also constrained ($length < 256 bits$). $\endgroup$ – Alex Papageorgiou Aug 6 '18 at 8:20
  • 1
    $\begingroup$ @Alex Papageorgiou: if this is textbook RSA (without random padding), and the length of $m$ is less than 256 bit, and the length of $p$ is more (the later being considered necessary for security in standard RSA / balanced bi-prime RSA since any $n$ below about 640 bit can be readily factored), then $m<p$ and thus $m_p=m$ and we can recover $m$ without any guesswork. See edited answer. $\endgroup$ – fgrieu Aug 6 '18 at 10:51
1
$\begingroup$

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.

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