How can a system be non-deterministic? Newbie here, so forgive me if this is a stupid question.
In math class we learned about RSA encryption (as a practical application of what we learned about the Euler phi function and Fermats little theorem), and I wondered that since the same input always yields the same output, if eve had a couple of guesses for what the message is (for instance a yes or a no), she could try encoding them herself and compare that to the ciphertext. I googled how to get around this, and I gathered that a process can be non-deterministic, meaning it yields different results if done repeatedly. However, when I looked into how this was possible, I never really understood the explanations, they got really complicated really fast.

So what I'm asking is, can anyone explain fairly simply (high-school level math) how a ciphertext can be generated with an element of randomness, but still be decipherable. Surely the receiver can't easily undo those random changes, if the same message could come in in many different forms?
As a high level concept, nondetermistic encryption is where the encryption function takes three inputs, the key $k$, the plaintext $P$ and a random value $R$, generating a ciphertext $C = E_k(P, R)$; the idea is that a) two different random values $R$ gives completely different ciphertexts $C$, even if the plaintexts where the same (or related), and b) no matter what value $R$ we picked, decryption still works, that is, $P = D_k( C )$ (where, in an assymetric system, $k$ may be the private key).

All this should have been covered in your math class; your question is "how does this work in practice?"  Since you mentioned RSA, I'll give you a simple version of it:

RSA has a relatively large plaintext size; for example, 2048 bits.  So, to encrypt a 256 bit plaintext $P_{256}$, what we do is select 1784 random bits $R_{1784}$, and generate an RSA block:

$$01 || R_{1784} || P_{256}$$

The initial byte is a fixed 01 value (so that the resulting plaintext will always be less than the modulus size); the resulting block is precisely 2048 bits long.  We can then give it to RSA, which converts it into a ciphertext.

$$(01 || R_{1784} || P_{256})^e \bmod N$$

We can see that:


Depending on what values we select for $R_{1784}$, the resulting ciphertext will look completely different
The decryptor can easily recover the original plaintext (by decrypting the ciphertext, and just looking at the last 256 bits).


Now, it turns out simple RSA padding schemes like this tend to have issues with chosen ciphertext attacks, and so in practice, we generally use more sophisticated ways of padding the message (that is, don't use the simple scheme I mentioned directly).  However, it should clarify how deterministic encryption can work in general.