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

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 Python code to achieve this:

a=0
b=0

while (sympy.gcd(a,p-1)!=1):
  a=random.randint(1,p-1)
while (sympy.gcd(b,p-1)!=1):
  b=random.randint(1,p-1)

In this case, the GCD (Greatest Common Denominator) returns a 1, when the two values do not share a factor (that is, they are co-prime). An overview of the three messages passed is:

And there you go. Alice has a secret, and she needs Bob to know it. With just three messages passed, Bob can discover it too. The coding is here:

import random
import libnum

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
import sys
import sympy

primebits=64

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])

if primebits>512: primebits=512

p = getPrime(primebits, randfunc=get_random_bytes)

key=random.randint(1,p-1) 

a=0
b=0

while (sympy.gcd(a,p-1)!=1):
  a=random.randint(1,p-1)
while (sympy.gcd(b,p-1)!=1):
  b=random.randint(1,p-1)

print(f"a={a}")
print(f"b={b}")
print(f"p={p}")

Alice_to_Bob = pow(key,a,p)
print(f"\nAlice to Bob={Alice_to_Bob}")

Bob_to_Alice = pow(Alice_to_Bob,b,p)
print(f"Bob to Alice={Bob_to_Alice}")

Alice_to_Bob2 = pow(Bob_to_Alice,libnum.invmod(a,p-1),p)
print(f"Alice_to_Bob2={Alice_to_Bob2}")

key_recovered= pow(Alice_to_Bob2,libnum.invmod(b,p-1),p)

print(f"\nKey={key}")
print(f"Key recovered={key_recovered}")

if (key==key_recovered): print("Success!!!")

A sample run is:

a=770901245
b=608393671
p=2693734777

Alice to Bob=2562445516
Bob to Alice=131559405
Alice to Bob2=2564893669

Secret=2268403234
Secret recovered=2268403234
Success!!!

And:

Conclusions

The Internet we have created is not good in terms of security. We have a sticking plaster protocol named SSL/TLS, and which only provides security between two machines. The Shamir No Key approach is one example of passing messages, without encryption keys, and where ever message is secure.

Here is the main demo for the Sharmir No-Key protocol:

And, if you are interested, here’s how Signal does it: