Can an RSA encrypted message be altered?

Question

Let´s suppose that I want to send an RSA encrypted message to Alice, so I use her public key. Such a message contains a number only. If Eve intercepts the message, is it possible for Eve to alter the encrypted message (the number) so that, when Alice decrypts it she gets twice the original number?

I can think of the following approach but it seems to me an innocent one.
Eve can intercept the message using sniffer software and watch the binary representation of the encrypted number. Eve can then right-shift this binary number (multipy by 2), replace it and route it to the final destination.

I will very much appreciate any comments.

Answer 1

Close; what would work would be if Eve encrypts 2 with the public key (forming $2^e \bmod N$), and then multiplies the ciphertext ($P^e \bmod N$ with that. When Alice decrypts it (by raising it to the power of $d$, she'll compute:

$$(2^e \times P^e)^d = 2 \times P$$

which is what Eve wants.

On the other hand, this is assuming that Alice uses raw RSA, without padding. When you add in padding (which any sane use of RSA encryption should use), this doesn't work.

Answer 2

Your general idea is the question if an encryption scheme is malleable. And yes, plain RSA is malleable. That's why textbook-RSA should never be used in any practice.

RSA is multiplicative: $E(m) \cdot E(r) = m^er^e = (mr)^e = E(mr) \mod N$. So that Alice gets twice the number, you have to multiply $2^e$ to the ciphertext and use the modular arithmetic, not binary operations like bitshifts.

As a general rule of thumb: If malleability is an issue , you want a IND-CCA secure cryptosystem. IND-CPA is not enough, e.g. ElGamal is malleable. Plain RSA isn't even IND-CPA. RSA-OAEP is IND-CCA secure in the random oracle model.

But keep in mind malleability can be considered a feature instead of a weakness, but then it's usually called (semi-)homomorphic encryption.