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.
Shamir's No-key Protocol |
Theory
Let's say that Alice has a secret (\(k\)). Now Alice creates a random value (\(a\)) and Bob create a random value (\(b\)). Initially Alice generates:
\(A_1 = k^a \pmod p\)
And passes this to Bob. Bob then takes this value and generates:
\(B_1 = {(A_1)}^b \pmod p\)
Bob sends this to Alice, who performs:
\(A_2 = {(B_1)}^{a^{-1}} \pmod p\)
To perform the \(a^{-1}\) operation we take \(a^{-1} \pmod {p-1} \). When Bob receive this he does the following and recovers the secret:
\(key = {(A_2)}^{b^{-1}} \pmod p\)
To perform the \(b^{-1}\) operation we take \(b^{-1} \pmod {p-1} \). This works because:
\({(A_2)}^{b^{-1}} \equiv {({(B_1)}^{a^{-1}})}^{b^{-1}} \equiv {({({(A_1)}^b)}^{a^{-1}})}^{b^{-1}} \equiv {{A_1}^{a^{-1}}} \equiv {{k^a}^{a^{-1}}} \equiv k \pmod p\)
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:
Coding
The coding is here:
import random import libnum from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes from Crypto.Random import get_random_bytes import sys import sympy primebits=64 msg="hello" if (len(sys.argv)>1): primebits=int(sys.argv[1]) if (len(sys.argv)>2): msg=(sys.argv[2]) if primebits>512: primebits=512 p = getPrime(primebits, randfunc=get_random_bytes) key= bytes_to_long(msg.encode('utf-8')) % p 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"msg={msg}") 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"\nSecret={key}") print(f"Secret recovered={key_recovered}") if (key==key_recovered): print("Success!!!") if (primebits>32): key_recovered=long_to_bytes(key_recovered).decode() print(f"Secret message recovered={key_recovered}")
A sample run is:
msg=hello a=9400647726439118133 b=12560138385653638465 p=13153412975656338107 Alice to Bob=9724330600413133118 Bob to Alice=9187191784760291844 Alice to Bob2=6354158871700673416 Secret=448378203247 Secret recovered=448378203247 Success!!! Secret message recovered=hello