Textbook El Gamal and variants


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)