Implicitly Certified Identity-based Public keys: Meet Günther’s Method

Implicitly Certified Identity-based Public keys: Meet Günther’s Method

In 1984, Adi Shamir proposed an alternative to PKI (Public Key Infrastructure)[1] named IBE (Identity Based Encryption). With this, we use trust centre (T) and which is responsible for generating Bob and Alice’s public and private keys. Anyone who wants to send Alice some encrypted data can generate her public key based on her identity.

Günther’s method [2] defined implicitly certified identity-based public keys. In this case, Bob will generate Alice’s public key from a signed version of Alice’s identity from T. Alice can then gain the private key to recover any encrypted data:

In this case Bob will generate Alice’s public key from a signed version of Alice’s identity from T. Alice can then gain the private key to recover any encrypted data. First the trust centre generates a prime number (p) and a random number (t), and where the GCD (Greatest Common Divisor) is:

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

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

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

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

This will work as:

and so:

(PA)a=gh(IA)⋅u−PA=uPA⋅PAa⋅u−PA=PAa(modp)

Coding

The coding is here:

# 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))%p

print (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 of a 60-bit random prime number [here]:

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^a
Bob recovers Alice's Public Key: 914640446395302251
Checking Alice's key: 914640446395302251
Keys match!

and for a 256-bit random prime number [here]:

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^a
Bob recovers Alice's Public Key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Checking Alice's key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Keys match!

And for a 512-bit random prime number [here]:

Alice's ID: AliceID
g: 2
p: 11594711316410846967916853565132250862037894680138050720795756067432045878659584226527851546936883041655136093357160565150064729045680859586390435534509527
Trust centre generates:
t (secret): 2191214164617329390502800577257515102872263679113374667143645471782966249711520153195921397876416498321613910219550129463176077054705997822626692047476857
u: 5051299130299031047387839752448406883155966307472756568024424502283535855857556790339072400676772634206952316207408818108634058040443947427171921062033161
Ka (secret): 3199736435805188213122536402386225080894710347614613907456680584534308636464340762329569136631033965302586291398155867143830224449382353523442138690161583
Pa: 9999117489268092011334185996544288393708071829119283167481610028681214226700497534510697738924501849829555349175534403951016027867677868378836513909438911
h(ID): 67595362884446021875105118399538667587610985753592658773354317154313003189111
Trust centre computes private key (a)
a: 9031294101194153277120983691313395748402010344578031815542871905666914503967045868680784618701444404548097796843564039060802400036862864806170446022817368
Bob uses h(ID), g, p, Pa to generate Pa^a
Bob recovers Alice's Public Key: 4044332461710321742528279247057690808186827681132095994916664619736714349281452983822229104162394903124064381837437562214612084174280349532663621999453357
Checking Alice's key: 4044332461710321742528279247057690808186827681132095994916664619736714349281452983822229104162394903124064381837437562214612084174280349532663621999453357
Keys match!

Conclusion

While PKI has worked for the trust infrastructure for the Web, it does not scale well in many other areas, especially where we need our own centralised trust infrastructure. IBE provides an opportunity to enhance trust and keep control of the encryption keys that we need. And, just because a method isn’t used in practice, doesn’t mean we should exclude it from our learning, as you just never know when it could be used with a new problem.

References

[1] Shamir, A. (1984, August). Identity-based cryptosystems and signature schemes. In Workshop on the theory and application of cryptographic techniques (pp. 47–53). Springer, Berlin, Heidelberg [here].

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