Trusted Generation of Public Keys — Based on Your Identity

Trusted Generation of Public Keys — Based on Your Identity

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

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:

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

With IBE (Identity Based Encryption) we use a trust centre (T). The trust centre 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üther’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:

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 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:

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 (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:

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))%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 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^a

Bob 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^a

Bob recovers Alice's Public Key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Checking Alice's key: 109145868988609169229666201120970111197965029652983574881111854109393877108663
Keys match!

Conclusions

The PKI (Public Key Infrastructure) has built the security of the Internet, and where trusted signers distributed public keys. It is by far from perfect, and IBE (Identity Based Encryption) provides an alternative and where we can have trust centres controlling public keys, and where they can be generated purely from someone’s identity.

The code is here for the method we have outlined:

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

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.

[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].