Image for post
Image for post

Trusted Generation of Public Keys — Based on Your Identity

Prof Bill Buchanan OBE
Jan 17 · 5 min read

In 1984, Adi Shamir proposed an alterative to PKI (Public Key Infrastructure) [here][1]:

Image for post
Image for post

Identity-based Encryption (IBE) involves generating the encryption key from a piece of identity for the recipient, and considerabley simplied the method of generating public keys. For this, instead of getting public keys from digital certificates, we could use the email address of the recipient to generate the key for an entity.

For this, we have some shared parameters with a trust centre that both Bob and Alice trust. If Alice wants to send Bob an email, she takes the parameters from the trust centre, and then uses Bob’s email address to generate his public key:

Image for post
Image for post

When Bob receives the encrypted email, he contacts the trust centre and the centre generates the private key required to decrypt the email. So let’s look at a method that allows Bob to generate Alice’s public key, in a trusted way.

Günther’s implicitly certified identity-based public keys

Image for post
Image for post

t is then the private key, and the trust centre will then publish a public key of:

Image for post
Image for post

The trust centre will then give Alice a distinguishable name of I_A. For example, this might be Alice’s email address. Next, the trust centre will generate a random integer of k_A and computes a reconstruction public key value of:

Image for post
Image for post

The trust centre will then select a hashing method (h) and will calculate a to make the following true:

Image for post
Image for post

The trust centre then sends Alice (P_A,a), and where a is Alice’s private key, and Alice’s public key is {P_A}^a. Bob can then recreate Alice’s public key using g,I_A,u,P_A,p with:

Image for post
Image for post

The coding is here [link]:

# https://asecuritysite.com/encryption/guther
from Crypto.Util.number import *
import Crypto
import libnum
import sys
from random import randint
import hashlib
bits=60
IDA="Alice"
if (len(sys.argv)>1):
IDA=str(sys.argv[1])
if (len(sys.argv)>2):
bits=int(sys.argv[2])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
g=2
t= randint(0, p-1)
u = pow(g,t,p)
Ka=2
while (libnum.gcd(Ka,p-1)!=1):
Ka= randint(0, p-1)
Pa = pow(g,Ka,p)inv_Ka=(libnum.invmod(Ka, p-1))D = int.from_bytes(hashlib.sha256(IDA.encode()).digest(),byteorder='big' )a=((D-t*Pa)*inv_Ka) % (p-1)AlicePub = (pow(g,D,p)*pow(u,-Pa,p))%pprint (f"Alice's ID: {IDA}")
print (f"g: {g}" )
print (f"p: {p}" )
print ("\nTrust centre generates:")
print (f"t (secret): {t}" )
print (f"u: {u}" )
print (f"\nKa (secret): {Ka}" )
print (f"Pa: {Pa}" )
print (f"h(ID): {D}" )
print ("\nTrust centre computes private key (a)")print (f"a: {a}" )print ("\nBob uses h(ID), g, p, Pa to generate Pa^a")print (f"\nBob recovers Alice's Public Key: {AlicePub}")AlicePubCheck= pow(Pa,a,p)print (f"Checking Alice's key: {AlicePubCheck}")if (AlicePub==AlicePubCheck):
print ("Keys match!")

A sample run is:

Alice's ID: AliceID
g: 2
p: 1040036132433661127
Trust centre generates:
t (secret): 660713498401150081
u: 980986780230779448
Ka (secret): 589723904035103703
Pa: 723160803210645123
h(ID): 67595362884446021875105118399538667587610985753592658773354317154313003189111
Trust centre computes private key (a)
a: 395971050764850570
Bob uses h(ID), g, p, Pa to generate Pa^aBob recovers Alice's Public Key: 914640446395302251
Checking Alice's key: 914640446395302251
Keys match!

and for a 256-bit prime number:

Alice's ID: AliceID
g: 2
p: 110852656632201419223507769493894048136848426930220287813503162988662829348977
Trust centre generates:
t (secret): 5420854790828476304309386278954387233740482554973779054205803478913006085301
u: 64697115686470266631492260479221243176048809274825059116718088012573550201057
Ka (secret): 20736369342194049699240222075276879897257228346331438516768198568251740874385
Pa: 82471319207677041543661624897197701284235288542061131181106361468660770667435
h(ID): 67595362884446021875105118399538667587610985753592658773354317154313003189111
Trust centre computes private key (a)
a: 29092559345246744005943907604839436726638585039735344938794362875508476380464
Bob uses h(ID), g, p, Pa to generate Pa^aBob recovers Alice's Public Key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Checking Alice's key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Keys match!

Conclusions

The code is here for the method we have outlined:

And if you are interested in learning more about IBE, try here:

References

[2] Günther, C. G. (1989, April). An identity-based key-exchange protocol. In Workshop on the Theory and Application of Cryptographic Techniques (pp. 29–37). Springer, Berlin, Heidelberg [here].

ASecuritySite: When Bob Met Alice

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