# Does there exist an agreeable algorithm to substitute XOR function in Shamir's no Key Protocol?

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

## 1 Answer

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.

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