encryptionrsapublic-keypublic-key-encryption

RSA trick in email reply


A uses RSA encryption for her email. B finds an encrypted email to A: c = m^e mod n that he wants to know the plain text. B knows that when A replies to her email, she always includes the text of the message she is responding to in the reply.

Assume A only receives messages that are bit strings of length at most log n, which can be mapped to Zn.

Also assume that B cannot simply send c as his own email to A and expect a reply, but that A will respond to email messages other than c.

How can B learn m using only c, e, n and random values from Zn?


Solution

  • From wikipedia:

    RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is m1^e m2^e≡(m1m2)^e (mod n) Because of this multiplicative property a chosen-ciphertext attack is possible. E.g. an attacker, who wants to know the decryption of a ciphertext c = m^e (mod n) may ask the holder of the private key to decrypt an unsuspicious-looking ciphertext c' = cr^e (mod n) for some value r chosen by the attacker. Because of the multiplicative property c' is the encryption of mr (mod n). Hence, if the attacker is successful with the attack, he will learn mr (mod n) from which he can derive the message m by multiplying mr with the modular inverse of r modulo n.

    That's actually pretty neat, thanks for asking the question that lead me to learning this.
    As for your question of 3020 vs 600, it's multiplicative; rarely are concatenations used in mathematics, since after all we should always be working independent of base.