# ElGamal algorithm

# cat elgamal.py
def egcd(a, b):
 if a == 0:
  return (b, 0, 1)
 else:
  g, y, x = egcd(b % a, a)
  return (g, x - (b // a) * y, y)

def modinv(a, m):
 g, x, y = egcd(a, m)
 if g != 1:
  return None  # modular inverse does not exist
 else:
  return x % m

p = 467 # prime
g = 2 # generator
ru = 127 # random
pu = g**ru % p # public
m = 100 # message

print '[+] Encryption'
print
print 'm =', m
re = 140 # random
pe = g**re % p # public
c = (pu**re * m) % p # cipher
print 'c =', c
print

print '[+] Decryption (c, p, g, pe)'
print
print 'c =', c
# m = (c / (pe**r1)) % p
m = (c * pe**(p - 1 - ru)) % p
print 'm =', m
print

print '[+] Signature'
print
hm = m * 2 # 'hash'
print 'h(m) =', hm
rs = 213 # random
ps = g**rs % p
s = ((hm - (ru*ps)) * modinv(rs, p - 1)) % (p - 1) # sign
print 's =', s
print

print '[+] Verification (hm, s, p, g, pu, ps)'
print
print 'h(m) =', hm
print 's =', s
v1 = g**hm % p
v2 = (pu**ps * ps**s) % p
if v1 == v2:
        print 'v1 = v2 =', v1, '- Signature is ok'

# python elgamal.py
[+] Encryption

m = 100
c = 391

[+] Decryption (c, p, g, pe)

c = 391
m = 100

[+] Signature

h(m) = 200
s = 279

[+] Verification (hm, s, p, g, pu, ps)

h(m) = 200
s = 279
v1 = v2 = 229 - Signature is ok

Reference

https://en.wikipedia.org/wiki/ElGamal_encryption