import numpy
import hashlib
from decimal import *
from random import *
getcontext().prec = 800
# Utility function
def XEuclidean(u, v):
# extended euclidean algorithm
U = numpy.array([1, 0, u])
V = numpy.array([0, 1, v])
while V[2] != 0:
q = U[2] // V[2]
T = U - V * q
U = V
V = T
print(u, "*", U[0], "+", v, "*", U[1], "=", U[2], "\n")
# (u0,u1,u2) -> u*u0+v*u1=u2
return U
# Define a group:
# multiplicative group of Zp
class GroupMulZp:
id = 1
def __init__(self, p):
self.order = p - 1
self.characteristic = p
def mul(self, x, y):
return (x * y) % self.characteristic
def inv(self, x):
SX = XEuclidean(x, self.characteristic)
return (
SX[0] + self.characteristic
) % self.characteristic
def pow(self, x, n):
return pow(x, n, self.characteristic)
# Additive group of Zn
class GroupSumZn:
id = 0
def __init__(self, n):
self.order = n
def mul(self, x, y):
return (x + y) % self.order
def inv(self, x):
return (self.order - x) % self.order
def pow(self, x, n):
return (n * x) % self.order
def pairing(self, x, y):
return (x * y) % self.order
class ElGamal:
def __init__(self, G, g):
self.group = G
self.generator = g
def genPublicKey(self, d):
return self.group.pow(self.generator, d)
def Encrypt(self, m, e):
k = randrange(2, self.group.order)
u = self.group.pow(self.generator, k)
er = self.group.pow(e, k)
v = self.group.mul(m, er)
return [u, v]
def Decrypt(self, c, d):
[u, v] = c
dm = self.group.pow(u, d)
dmInv = self.group.inv(dm)
m = self.group.mul(v, dmInv)
return m
# define group
p = 633825300114114700748351602943
g = 12323
G = GroupMulZp(p)
EG = ElGamal(G, g)
# secret key
dk = 12485
# public key
ek = EG.genPublicKey(dk)
# message
m = 2135798237982
# Encrypt
enc = EG.Encrypt(m, ek)
# Decrypt
dec = EG.Decrypt(enc, dk)
# ID-Based encryption
class ID_Elgamal:
def __init__(self, G, P):
self.group = G
# generator
self.P = P
def StringToID(self, m):
H = hashlib.sha256()
H.update(m.encode("utf-8"))
i = int(H.hexdigest(), 16) % self.group.order
return self.group.pow(P, i)
def Setup(self, s):
# s = MASTER KEY
self.s = s
self.Ppub = self.group.pow(self.P, s)
return self.Ppub
def Extract(self, id):
idg = self.StringToID(id)
Did = self.group.pow(idg, self.s)
return Did
def Encrypt(self, m, id):
idg = self.StringToID(id)
k = randrange(2, self.group.order)
u = self.group.pow(self.P, k)
gid = self.group.pairing(idg, self.Ppub)
er = self.group.pow(gid, k)
v = self.group.mul(m, er)
return [u, v]
def Decrypt(self, c, Did):
[u, v] = c
dm = self.group.pairing(Did, u)
dmInv = self.group.inv(dm)
m = self.group.mul(v, dmInv)
return m
G2 = GroupSumZn(p)
P = 214851
IDBased = ID_Elgamal(G2, P)
# master key
s = 23581211
Ppub = IDBased.Setup(s)
ID = "bob@bob.abc.com"
decKey = IDBased.Extract(ID)
m = 12479121284901
enc = IDBased.Encrypt(m, ID)
dec = IDBased.Decrypt(enc, decKey)
# Escrow ElGamal
class Escrow_Elgamal:
def __init__(self, G, P):
self.group = G
# generator
self.P = P
def Setup(self, s):
# s = MASTER KEY
self.s = s
self.Q = self.group.pow(self.P, s)
return self.Q
def KeyGen(self, sk):
PK = self.group.pow(self.P, sk)
return PK
def Encrypt(self, m, PK):
k = randrange(2, self.group.order)
u = self.group.pow(self.P, k)
sg = self.group.pairing(self.Q, PK)
er = self.group.pow(sg, k)
v = self.group.mul(m, er)
return [u, v]
def Decrypt(self, c, sk):
[u, v] = c
ux = self.group.pow(u, sk)
dm = self.group.pairing(ux, self.Q)
dmInv = self.group.inv(dm)
m = self.group.mul(v, dmInv)
return m
def EscrowDecrypt(self, c, PK):
[u, v] = c
sPK = self.group.pow(PK, self.s)
dm = self.group.pairing(u, sPK)
dmInv = self.group.inv(dm)
m = self.group.mul(v, dmInv)
return m
# Samples
G2 = GroupSumZn(p)
P = 214851
Escrow = Escrow_Elgamal(G2, P)
# master key
s = 23581211
Ppub = Escrow.Setup(s)
secKey = 148912
PK = Escrow.KeyGen(secKey)
m = 77479121284901
enc = Escrow.Encrypt(m, PK)
dec = Escrow.Decrypt(enc, secKey)
dec2 = Escrow.EscrowDecrypt(enc, PK)