How can one run a chosen plaintext attack on RSA?
If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
Slight revision based on Paulo's remark in the comments - in a public key system a chosen plaintext attack is pretty much part of the design - arbitrary plaintexts can be encrypted to produce ciphertexts at will - by design, however, these shouldn't give any information that will allow you to deduce the private key.
A chosen ciphertext attack can be used with careful selection of the plaintext, however, to perform an attack - it's actually fairly straightforward on textbook RSA. Firstly, we have a piece of ciphertext we'll denote by:
$$C = t^e \mod n$$ Which is RSA as we know and love. Now, Eve has $C$ - this is perfectly ordinary, since Eve is supposed to be able to see $C$. Now eve has the ability to chose a plaintext - so, she choses $2$ as her plaintext and computes $C_a = 2^e \mod n$. However, to our unsuspecting victim she sends $C_b = C_a * C$, so:
$$C_b = C\cdot 2^e = t^e 2^e\mod n$$
All good so far. Now since this is a chosen plaintext attack we're reliant on having access to the decryption of our substituted value - so now the unsuspecting victim computes:
$$(C_b)^d = [t^e 2^e]^d = (t^e)^d \cdot (2^e)^d \mod n$$
However for any plaintext $x$, we know $C \equiv x^e$ and $x \equiv C^d$; so: $$(x^e)^d \equiv x \mod n$$
Therefore from the preceding result: $$(C_b)^d = t \cdot 2 \mod n$$
Hence when we get that value back, we can quite easily compute $t$. We simply need to halve it.
This can actually apply for any plaintext we wish to chose - I simply chose $2$ because I like it as a number. This paper covers the general technique and a lot more.
This only applies to textbook RSA. The proper application of RSA in the wild involves the use of padding schemes which defeat this attack by ensuring the ciphertext is not malleable in this way.