Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
poncho's answer explains that basically, yes, allowing chosen ciphertext attacks is dangerous for textbook RSA. The solution is to use a proper padding mode, preferably OAEP. The padding restricts valid ciphertexts, and in particular breaks the mathematical relations between ciphertexts (such as $C_1 = r\,C_2$) that cause problems with textbook RSA. –  Gilles Jul 30 '13 at 17:55
add comment

1 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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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