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. Normally we sign with \(s=k^{-1} (h(m)-ar) \pmod {p-1}\), but in this case we will use the signing equation of \(s=ar + kh(m) \pmod {p-1}\).
ElGamal Signing (alternative method) |
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 would normally sign with \(s=k^{-1} (h(m)-ar) \pmod {p-1}\), but in this case we will use an alternative of:
\(s=ar + k h(m) \pmod {p-1}\)
The signature is then (\(r,s)\). Bob verifies the signature by computing two values:
\(v_1 = y^r r^{h(m)} \pmod p\)
and:
\(v_2 = g^{s} \pmod p\)
If \(v_1\) is equal to \(v_2\) the signature has been verified. This works as:
\(v_1 = y^r r^{h(m)} \pmod p = {(g^a)}^r {(g^k)}^{h(m)} \pmod p = g^{ar} g^{kh(m)} \pmod p = g^{ar+kh(m)} \pmod p = g^{s} \pmod p = v_2 \)
Coding
The coding is here:
from Crypto.Util.number import * 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=(a*r+k*h_m) % (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,h_m,p))%p v2=pow(g,s,p) print (f"\nVerification: v1={v1},v2={v2}") if (v1==v2): print ("Signature checks!")
A sample run:
Public key: p=644713333376080253,g=2, y=234533155654631520 Private key: a=127494220965412486 Random: k=57702408634516861 Message: m=Hello Signature: r=94585145486152320,s=125242976436126961 Verification: v1=596147405254176186,v2=596147405254176186 Signature checks!