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?

  • 1
    $\begingroup$ A good overview of what current (1999) attacks exist on the RSA cryptosystem can be found in this paper by Boneh. crypto.stanford.edu/~dabo/pubs/abstracts/RSAattack-survey.html $\endgroup$ Commented Apr 10, 2012 at 14:46
  • 1
    $\begingroup$ Is there a reason you broadened the scope of this question? The first question was a good answerable one, as of this revision it's too broad. $\endgroup$
    – Zelda
    Commented Apr 10, 2012 at 14:51
  • $\begingroup$ @John: The original question looked better than the current one ... it is now on the way to "non constructive" (as in "give me a list of all attacks"). Is there something missing in the original question which caused you to remove the "chosen ciphertext" part? $\endgroup$ Commented Apr 10, 2012 at 15:54
  • $\begingroup$ I thought it would be better in terms of searchability. Should I revert back to the original question? $\endgroup$
    – user1829
    Commented Apr 10, 2012 at 16:02
  • 1
    $\begingroup$ I think, using "any" instead of "chosen ciphertext" will not improve searchability, except in the rare case that someone searches for the precise phrase in the title (and puts quotation marks). I changed the the title to be a question, reworded the text to ask what I think you actually wanted to ask for, and put some relevant tags ("security" isn't, sorry). Please check that I didn't go overboard with it, and feel free to edit again. $\endgroup$ Commented Apr 10, 2012 at 16:51

2 Answers 2


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 fairly straightforward on textbook RSA. Firstly, we have a piece of ciphertext we'll denote by:

$$C \equiv 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 can choose a plaintext - so, she choses $2$ as her plaintext and computes $C_a \equiv 2^e \mod n$. However, to our unsuspecting victim, she sends $C_b \equiv C_a * C$, so:

$$C_b \equiv C\cdot 2^e \equiv 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 \equiv [t^e 2^e]^d \equiv (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 \equiv 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.

  • 3
    $\begingroup$ Wouldn't this be a chosen ciphertext attack instead of a chosen plaintext one? For asymmetric encryption being able to do a chosen plaintext attack (i.e. encrypting using the public key) is always given, but retrieving the decryption of a chosen ciphertext (whether it comes from some known plaintext or something else) is called a chosen ciphertext attack. $\endgroup$ Commented Apr 10, 2012 at 16:56
  • $\begingroup$ @PaŭloEbermann Hmmm, you could be right, actually. I think I've got my terminology all confused. Gonna edit, two seconds. $\endgroup$
    – user46
    Commented Apr 10, 2012 at 18:31

A chosen plaintext attack means that the attacker, Eve, can encrypt the plaintext of her choice. Since in public key cryptosystems this is always possible, Eve can always acquire Bob's encryption exponent $e$ and encrypt any plaintext. What does this mean when the plaintext space is small?

Say Alice and Bob decide on textbook RSA and they generate the needed public and private keys. Alice sends Bob her age. Eve gets the message $m$ (Alice's age) as $m^e \mod N$. Eve knows $m^e$ decrypts to an age (plaintext space is small). Eve could launch a chosen plaintext attack by encrypting numbers 1-200 and matching it with the cipher text $m^e$.

Here is a SageMath script that shows this attack on textbook RSA.

p,q = next_prime(2^50), next_prime(2^30)
N = p*q
phi = ((p-1)*(q-1))
e = randint(0, phi)
while gcd(e, phi) != 1:
    e = randint(0, phi)
e = Integers(phi)(e)
d = e^(-1)
print('p = {}\nq = {}\nN = {}\nphi(N) = {}\n'.format(p, q, N, phi))
print('Bob\'s private key: d = {}, public key: e = {}'.format(d, e))

# BLOCK: Alice sends Bob a message
m = Integers(N)(39)
c = m^e
print('Alice sends m = {} to Bob as m^e = {}'.format(m, c))

# BLOCK: Bob decrypts c
print('Bob decrypts c = {} to m = c^d = {}'.format(c, c^d))

# BLOCK: Chosen Plaintext Attack on Textbook RSA
plaintext_space = range(200)
for t in plaintext_space:
    t = Integers(N)(t)
    if t^e == c:
        print('Eve has found the message: {}'.format(t))

Here is the Output:

 ---- Bob computes his public and private key ---- 
p = 1125899906842679
q = 1073741827
N = 1208925822992387951034533
phi(N) = 1208925821866486970450028

Bob's private key: d = 663674456840375780568965, public key: e = 761705651416514555276069
 ---- Alice sends Bob a message ---- 
Alice sends m = 39 to Bob as m^e = 25719553046482356303827
 ---- Chosen Plaintext Attack on Textbook RSA ---- 
Eve has found the message: 39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.