Probabilistic padding to avoid Håstad’s Broadcast Attack

Question

Can someone explain why probabilistic padding like OAEP is particularly useful for avoiding Håstad’s Broadcast Attack? I don't really get the reason why.

Answer 1

If you use the same padding on the same messages, sent to multiple different public keys, then you have satisfied the criteria of the Håstad attack.

Randomizing the padding as in OAEP means that you don't use the same padding for each message. Even better, in a modern system like RSA-KEM, there's no ‘padding’ per se, or even any ‘message’ involved directly in the RSA part of the computation—the sender just

• picks $0 \leq x < n$ uniformly at random,
• uses $H(x)$ as a secret key for an authenticated cipher to encrypt an arbitrarily long message, and then
• sends $x^3 \bmod n$ alongside the authenticated ciphertext.