I think Shamir's no key protocol (also known as three-pass protocol) is a secure cryptography scheme but the designer only proposed the XOR function to encrypt the message which could be easily broken when the eavesdropper has all the encrypted messages: all the eavesdropper has to do is to XOR them and there he has the plain text


I don't remember reading Shamir's original proposal, but I would strongly suspect that he never endorsed the use of XOR in the protocol; if he mentioned it at all, it was as an illustration.

Instead, here is what is commonly referred to as Shamir's three pass protocol:

  • Alice and Bob agree on a large prime $p$ (larger than any message Alice wants to send)
  • Alice wants to send Bob the message $M$
  • Alice selects a random $a$ (relatively prime to $p-1$)
  • She computes $M^a \bmod p$ and sends it to Bob
  • Bob selects a random $b$ (relatively prime to $p-1$)
  • Bob computes $(M^a \bmod p)^b \bmod p = M^{ab} \bmod p$ and sends it to Alice
  • Alice computes $(M^{ab} \bmod p)^{a^{-1} \bmod p-1} \bmod p = M^b \bmod p$ and sends it to Bob
  • Bob computes $(M^b \bmod p)^{b^{-1} \bmod p-1} \bmod p = M$

That is, instead of using XOR, they perform modular exponentiation modulo a prime; with this, recovering $M$ from $M^a, M^b, M^{ab}$ is essentially the computational Diffie-Hellman problem, that is, believed hard given appropriate parameters.

  • $\begingroup$ Thank you. It's clear that I didn't read this topic from the primary source, I'll read it soon $\endgroup$ – polan Sep 28 '16 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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