RSA public key identification
Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Well, he can eliminate some of the possibilities (which means with $k=2$, he has a decent chance at finding the correct one).
There are two observations he can use:

He can eliminate all public keys $K_i$ for which $C \ge K_i$.  This is pretty obvious, but (if he is lucky) might eliminate some.

For each public key $K_i$, he can compute the Jacobi Symbols $\left( \frac{M}{K_i}{} \right)$ and $\left( \frac{C}{K_i}{} \right)$; if they differ, then he knows that $K_i$ is not the correct key.


This works because we're assuming textbook RSA, and textbook RSA always preserves the Jacobi symbol (which can be efficiently computed).  For an incorrect key, this test will disqualify it with probability circa 0.5, and so about half the incorrect ones will be eliminated.