In 1984, Adi Shamir proposed an alterative 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.
Günther's implicitly certified identity-based public keys (IBE) |
Outline
In 1984, Adi Shamir proposed an alterative 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. First the trust centre generates a prime number (\(p\)) and a random number (\(t\)), and where the GCD (Greatest Common Divisor) is:
\(\textrm{gcd}(t,p-1)\)
\(t\) is then the private key, and the trust centre will then publish a public key of:
\(u=g^t \pmod p\)
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:
\(P_A = g^{k_A} \pmod p\)
The trust centre will then select a hashing method (\(h\)) and will calculate \(a\) to make the following true:
\(h(I_A) = t \cdot P_A + k_A \cdot a \pmod {p-1} \)
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:
\({(P_A)}^a = g^{h(I_A)} \cdot u^{-P_A} \pmod p\)
This will work as:
\(g^{h(I_A)} = g^{t \cdot P_A + k_A \cdot a} = u^{P_A} \cdot {P_A}^a \)
and so:
\({(P_A)}^a = g^{h(I_A)} \cdot u^{-P_A} = u^{P_A} \cdot {P_A}^a \cdot u^{-P_A} = {P_A}^a \pmod p\)
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:
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:
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:
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!
Reference
[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].