In A World With No Encryption Keys: Shamir’s No-key Protocol

Why do we need encryption keys to pass secret? Well, it is a convenient way for Bob and Alice to share something that Eve can’t get access too. But could we just pass messages without needed to know encryption keys, or even using key-based encryption? Well, the magic of discrete logs comes to our rescue here.

The Shamir’s No-key Protocol allows Bob and Alice to create random numbers, and end up with the same shared secret. It involves three messages, one from Alice to Bob, another from Bob to Alice, and then the final one from Alice to Bob. After this, Bob and Alice should know the secret that Alice generated.

Let’s say that Alice has a secret (k). Now Alice creates a random value (a) and Bob creates a random value (b). Initially, Alice generates:

And passes this to Bob. Bob then takes this value and generates:

Bob sends this to Alice, who performs:

To perform the a−1 operation we take a−1(mod p−1) . When Bob receive this he does the following and recovers the secret:

To perform the b^{−1} operation we take b^{−1}(mod p−1). This works because:

To make this work, we must be sure that a and also b do not share a factor with (p-1). We define these as being co-prime to (p-1). Here is some…