Three-Pass Protocol number theory I've got a homework problem that I'm having a hard time understanding. It's for the Three-Pass Protocol, and we are given p, the three messages, and are told that the original plain text is one of two values.

The professor says we can use number theory to look at any of the three messages and determine which of the two original plain texts is correct, but I'm not seeing how. We covered the intruder in the middle attack, but since we can't send our own message that can't be the right action to take.

Could anybody point me in the right direction?
I suspect that the professor is thinking of Quadratic Residuosity.  A value $x$ is a quadratic residue (modulo $p$) if there exists a $y$ such that $y^2 \equiv x \pmod p$.

This is important, because:


For any value $x$ (and prime $p$), it's easy to determine whether it's a quadratic residue or not.
If $e$ is relative prime to $p-1$, then $x^e$ is a quadratic residue iff $x$ is.


Now, if we have two plaintext messages, one of which is a quadratic residue, and one is not, can you see how the above observerations can be used to distinguish the two messages from any message in the 3-pass exchange?