ElGamal Signing (alternative method - \(r=ah(m)+ks\))[ElGamal Home][Home]
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 \(r=ah(m)+ks\).
|
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:
\(r=ah(m)+ks\)
Thus to compute \(s\):
\(s=k^{-1}(r-ah(m))
The signature is then (\(r,s)\). Bob verifies the signature by computing two values:
\(v_1 = y^{s} r^{h(m)} \pmod p\)
and:
\(v_2 = g^{r} \pmod p\)
If \(v_1\) is equal to \(v_2\) the signature has been verified. This works as:
\(v_1 = y^{s} r^{s} \pmod p = {(g^a)}^{h(m)} {(g^k)}^{s} \pmod p = = g^{ah(m)+ks} \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' ) # Signing equation r=ah(m)+ks s=(invk*(r-a*h_m)) % (p-1) print ("Signing equation r=ah(m)+ks") 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,h_m,p)*pow(r,s,p))%p v2=pow(g,r,p) print (f"\nVerification: v1={v1},v2={v2}") if (v1==v2): print ("Signature checks!")
A sample run:
Signing equation r=ah(m)+ks Public key: p=1014222667595539279,g=2, y=572783008069754714 Private key: a=252690177808861835 Random: k=753738792213146483 Message: m=Hello Signature: r=972419735721725868,s=997164760215035363 Verification: v1=564705555609039333,v2=564705555609039333 Signature checks!