1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Which padding are you using? OAEP is common secure choice. Your question makes it sound like you're using textbook RSA, which is broken in many ways. $\endgroup$ – CodesInChaos May 2 '17 at 9:11
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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