with ElGamal signing, we create a secret signing exponent (\(s\)) and a public verification of \(v=g^v \pmod p\), and where \(p\) is a large prime number and \(g\) is a generator value.
ElGamal Signing in 12 lines of Python (Signing) |
Outline
With ElGamal signing, we create a secret signing exponent (\(s\)) and then a signing exponent of:
\(v=g^s \pmod p\)
To sign a document (\(D\)), we create an ephereral key (\(e\)). Next we calculate two signature values:
\(S_1 = g^e \pmod p\)
\(S_2 = (D-eS_1) e^{-1} \pmod {p-1}\)
We then check that these values are the same:
\(v_1=v^{S_1} S_1^{S_2} \pmod p\)
\(v_2=g^D \pmod p\)
The public verification part of the signature is \(g,v,p\) and the signature is \(S_1,S_2\). The secret is \(s\).
This work because:
\(v^{S_1} S_1^{S_2} = g^{sS_1} g^{eS_2} = g^{sS_1 + eS_2} = g^{sS_1+e(D-sS_1)e^{-1}}= g^{sS_1+(D-sS_1)}=g^D\)
Coding
The coding is here:
from Crypto.Util.number import * from Crypto import Random import Crypto import libnum import sys from random import randint import hashlib bits=60 msg="Hello" if (len(sys.argv)>1): msg=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 s= randint(0, p-1) v = pow(g,s,p) e= Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) # e_1=(gmpy2.invert(e, p-1)) e_1=(libnum.invmod(e, p-1)) #D= bytes_to_long(msg.encode('utf-8')) // if you want direct signing D = int.from_bytes(hashlib.sha256(msg.encode()).digest(),byteorder='big' ) S_1=pow(g,e, p) S_2=((D-s*S_1)*e_1) % (p-1) v_1 = (pow(v,S_1,p)*pow(S_1,S_2,p))%p v_2 = pow(g,D,p) print ("Message: %s " % msg) print ("g: %s" % g) print ("p: %s" % p) print ("\nv: %s" % v) print ("e: %s" % e) print ("\ns: %s" % s) print ("\nS_1= %s" % S_1) print ("S_2=%s" % S_2) print ("\nV_1=%s" % v_1) print ("v_2=%s" % v_2)
A sample run:
Message: hello g: 2 p: 658798421238984618675121 v: 437661683087514416119832 e: 1010916384396588402092587 s: 325568261434781783373940 S_1= 200704511985540962833175 S_2=415262543157436969072312 V_1=297290447516914045329174 v_2=297290447516914045329174