0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – awestover89
    Mar 17, 2016 at 23:07
  • 1
    $\begingroup$ @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? $\endgroup$
    – poncho
    Mar 18, 2016 at 0:18
  • $\begingroup$ 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. $\endgroup$
    – awestover89
    Mar 18, 2016 at 1:33
  • 1
    $\begingroup$ @awestover89: yup. It was homework, so I didn't want to give you the entire answer. $\endgroup$
    – poncho
    Mar 18, 2016 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.