With ElGamal signing, Alice has a public key (\(y,g,p\)) and a private key of \(a\). She then takes a message \(m\) and creates a signature (\(r,s\)). This signature can then be checked by Bob. We will use the signing equation of \(h(m)=ar+ks\) and where \(s=k^{-1}(h(m)-ar) \pmod {p-1}\).
ElGamal Signing |
Outline
With ElGamal, Alice selects a generator (\(g\)), prime number of \(p\) and a private key of \(a\). Her public key is then (\(y,g,p\)) and where \(y\) is:
\(y=g^s \pmod p\)
To sign a message (\(m\)) we generate a secret random number (\(k\)) and we must make sure:
\(gcd(k,p-1)=1\)
Next we compute:
\(r=g^k \pmod p\)
Next we compute:
\(k^{-1} \pmod {p-1} \)
and then:
\(s=k^{-1} (h(m)-ar) \pmod {p-1}\)
The signature is then (\(r,s)\). Bob verifies the signature by computing two values:
\(v_1 = y^r r^s \pmod p\)
and:
\(v_2 = g^{h(m)} \pmod p\)
If \(v_1\) is equal to \(v_2\) the signature has been verified. This works as:
\(v_1 = y^r r^s \pmod p = {(g^a)}^r {(g^k)}^s \pmod p = g^{ar} g^{ks} \pmod p = g^{ar+ks} \pmod p = g^{h(m)} \pmod p = v_2 \)
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 a= randint(0, p-1) y = pow(g,a,p) k=2 while (libnum.gcd(k,p-1)!=1): k= randint(0, p-1) r = pow(g,k,p) invk=(libnum.invmod(k, p-1)) h_m = int.from_bytes(hashlib.sha256(msg.encode()).digest(),byteorder='big' ) s=(invk*(h_m-a*r)) % (p-1) print (f"Public key: p={p},g={g}, y={y}") print (f"Private key: a={a}") print (f"Random: k={k}") print (f"Message: m={msg}") print (f"\nSignature: r={r},s={s}") v1=(pow(y,r,p)*pow(r,s,p))%p v2=pow(g,h_m,p) print (f"\nVerification: v1={v1},v2={v2}") if (v1==v2): print ("Signature checks!")
A sample run:
Public key: p=985059149918107939,g=2, y=365019271558668688 Private key: a=772186369965831309 Random: k=685221576498728729 Message: m=hello Signature: r=142146226667128086,s=849220266258452442 Verification: v1=322357449174353922,v2=322357449174353922 Signature checks!