Three-pass Protocol - Shamir Three-pass Protocol

Shamir Three-pass Protocol

The first Three-Pass Protocol was the Shamir Three-Pass Protocol developed circa in 1980. It is also called the Shamir No-Key Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses exponentiation modulo a large prime as both the encryption and decryption functions. That is E(e,m) = me mod p and D(d,m) = md mod p where p is a large prime. For any encryption exponent e in the range 1..p-1 with gcd(e,p-1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p-1). It follows from Fermat's Little Theorem that D(d,E(e,m)) = mde mod p = m.

The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)).