# 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?

• Would you actually need to use the encrypted messages for anything? If I am understanding correctly, I'd check the two possible plain texts, a and b, against p for quadratic residuosity. If a is a quadratic residue of p, it is the message, if b is a quadratic residue of p, it is the message. – awestover89 Mar 17 '16 at 23:07
• @awestover89: that's not how it works; we don't know apriori that the plaintext was the quadratic residue; the encryptor could have very easily selected a quadratic nonresidue. However, we also get to look at the exchanged messages as well. What could we determine from that? – poncho Mar 18 '16 at 0:18
• Ah, gotcha. Check the exchanged message, and see if it is a quadratic residue. If it is, then by the second point, we know that the original x must be as well, since x^e couldn't be a residue if x wasn't. – awestover89 Mar 18 '16 at 1:33
• @awestover89: yup. It was homework, so I didn't want to give you the entire answer. – poncho Mar 18 '16 at 2:43