Image for post
Image for post

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

Prof Bill Buchanan OBE
Oct 24 · 4 min read

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:

Image for post
Image for post

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

Image for post
Image for post

Bob sends this to Alice, who performs:

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

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=512p = 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:

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:

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store