How multiplicative property of RSA can be exploited

Question

It is known that RSA has the multiplicative property

$E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)$

because

$m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e \pmod n$

But how can this property be used to break the RSA system?

What are the attacks that use this property?

If you have the encryption of the plaintext numbers 2, 3 and 5 you could create every ciphertext which can be composed as product of this numbers, like 4, 8, 16, 32, ..., or 6, 9, 12, 15, 18, 24... If the prime factorization of a number only contains the number 2, 3 or 5 then you can create the ciphertext for that number. — Nova, Apr 9 '15 at 16:40
@Nova, but since the public key is public, what does this gain an attacker? — mikeazo, Apr 9 '15 at 16:52
you don't have in practice this attack since you hash the msg before you sign it or encrypt it — 111, Apr 9 '15 at 19:38
@111: Just hashing the message using e.g. SHA-1 is not quite enough protection for signature; and you can't replace the message with its hash for encryption, for then it can not be efficiently deciphered. $\;$ It remains that indeed, RSA encryption and signature schemes used in practice do not externally have the multiplicative property. — fgrieu♦, Apr 27 '15 at 4:22

SEJPM · Accepted Answer · 2015-04-09 18:37:24Z

4

Using this property, you can't fully break RSA (meaning you can't get the private key).

However there are a few attacks.

If you're using RSA for public-key encryption, there's an adaptive chosen ciphertext attack. Suppose you want to decrypt $c$ and A is decrypting everything but $c$ for you. Now you can chose your $c_1=x^e*c$ with $x\in Z_n^*$. Now you you send $c_1$ to A, he decrypts this. Now you'll have $m_1=c_1^d=c^d*(x^e)^d=m*x$ $(mod$ $n)$, now you simply compute $m=m_1*x^{-1}$ $(mod$ $n)$ and decrypted an arbitrary ciphertext
If you're using RSA for digital signature with message recovery you can basically mount the same attack as above, by basically using blind signatures so you can get arbitrary data signed. (If not using proper methods to protect)

answered Apr 9 '15 at 17:24

SEJPM♦

41.6k6 gold badges79 silver badges171 bronze badges

$\begingroup$ Thank you! Do you think the first attack may occur in practice? Because this scenario where the attacker has an oracle do decrypt messages seems very "non-realistic" to me... $\endgroup$ – Marcos Apr 9 '15 at 17:30
1

$\begingroup$ Nit: an attack doesn't have to be a key-recovery attack to be considered a break. An attack that recovers the plaintext (for public key encryption), or generates a forgery (for signature) is a break, even if it gives us no clue what the private key is. $\endgroup$ – poncho Apr 9 '15 at 17:48
$\begingroup$ @poncho, thank you, edited answer. First, in practice you'd use OAEP to prevent this style of attack. Second wikipedia says this actually happened once, but I'm not aware of any way to exploit this unless an application allows me to do so (by fault? / by exploit?) $\endgroup$ – SEJPM♦ Apr 9 '15 at 18:41

add a comment |

1 Answer 1