Brute forcing the value of m in RSA
If an eavesdropper intercepts their conversation and gets the value of $c$ (namely, $m^e \bmod n$) and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?


Yes!

This is part of why we do not use the function $x \mapsto x^e \bmod n$ to encrypt messages directly.  Instead, a sensible sender will pick $x$ uniformly at random from all positive integers below $n$, use $k = H(x)$ to encrypt a message $m$ with their favorite symmetric-key authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and then transmit $x^e \bmod n$ alongside the ciphertext, so that the receiver can recover $x$ and derive $k$ to decrypt the ciphertext.

This system is called RSA-KEM.  There are also more complicated systems like RSAES-PKCS1-v1_5 and RSAES-OAEP, where we pick $k$ up front and then shoehorn it into something that's close to a uniform random positive integer below $n$, but invariably we use a symmetric-key authenticated cipher to encrypt the actual message.



A little more generally, this goes beyond RSA: any public-key encryption scheme is necessarily randomized, because otherwise anyone could verify a guess about what plaintext is concealed in a ciphertext $c$ is simply by testing whether $c \stackrel?= E(m)$ for a candidate message $m$ where $E$ is the public-key encryption function.