Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key?

Question

I grasp that having known plaintext encrypted with the public key doesn't provide a means of discovering the private key (that being the whole point...).

But if one were in a situation where they didn't have access to the private key, but did have access to decryption by the private key, would the actual key be vulnerable?

So the attacker generates a plaintext and passes it to the decryption program as though it were a message encrypted with the public key. That plaintext thus gets transformed via the private key (though instead of going from ciphertext to plaintext as usual, it goes from plaintext to ciphertext). Would that plaintext-ciphertext pair reveal information about the private key or is it similar to trying to deduce the private key from a known plaintext and ciphertext pair encrypted using the public key?

On that note, is it possible to deduce the public key from a known plaintext and ciphertext encrypted with it?

Answer 1

With RSA, there is no known way to deduce the private key based on chosen ciphertext; that is, even if the attacker has oracle access to the private operation, the key is still safe.

However, this doesn't mean that it's safe to give an attacker this access; he can't deduce the key, but he can use this access to decrypt anything he wants (and this is the nonobvious part) he doesn't have to reveal what he's decrypting to the RSA implementation. That is, even if you design the implementation to attempt to not tell him the decryption of a specific message, he can decrypt that message anyways.

The technique he would use is called 'blinding', and here is how it works; assume that the attacker has a ciphertext $C$ that he wants to decrypt; what he does is pick a random number $r$ and compute: $C_{blind} = r^e C$ (where $e$ is the public exponent). He then presents $C_{blind}$ to the Oracle for decryption.

Now, $C_{blind}$ is effectively independent of $C$; the Oracle cannot deduce any information about $C$ (because for every possible $C$ value, there is a value of $r$ that makes it work).

The Oracle then returns $P_{blind} = C_{blind}^d = r C^d$. The attacker then computes $P = P_{blind} r^{-1} = C^d$, which is the decryption he is looking for.

As for your second question; whether it is possible to deduce the public key, no, from a single plaintext/ciphertext pair, it isn't possible.

However, from two plaintext/ciphertext pairs, it is (as long as the public exponent $e$ is sufficiently small). Here is how it works: if we have a plaintext/ciphertext pair $P_1, C_1$, we know that: $$P_1^e - C_1 = k_1N$$ where $e$ is the public exponent, $N$ is the modulus, and $k_1$ is some integer. If we have a second pair $$P_2^e - C_2 = k_2N$$ we can then compute $$gcd( P_1^e - C_1, P_2^e - C_2) = gcd(k_1N, k_2N) = N gcd(k_1, k_2)$$ $gcd(k_1, k_2)$ is almost certainly a small integer; allowing us to recover $N$.

If we don't know $e$ apriori, we can just search through the various possibilities (we're assuming $e$ is small, hence there aren't that many)