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=ah(m) + kr \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=ah(m) + kr \pmod {p-1}\)
The signature is then (\(r,s)\). Bob verifies the signature by computing two values:
\(v_1 = y^{h(m)} r^{r} \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^{h(m)} r^{r} \pmod p = {(g^a)}^{h(m)} {(g^k)}^{r)} \pmod p = g^{ah(m)} g^{kr} \pmod p = g^{ah(m)+kr} \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=721731273329937691,g=2, y=286421807968652695 Private key: a=359261486248830835 Random: k=159279283979910809 Message: m=Hello Signature: r=324120463349001707,s=89558916587828288 Verification: v1=621657046497842037,v2=621657046497842037 Signature checks!