## ElGamal signature scheme

All variable names as in Wikipedia's explanation of ElGamal signing scheme.

As in ElGamal encryption scheme, we reuse these parameters and keys:

g, p are public parameters. x, y are keys. x - private, y - public.

Let m be a message.

Generate 'ephemeral key', k. Must be coprime to p-1.

Compute $$r=g^k \pmod p$$. This is how k is transmitted in 'obfuscated' way.

Now find such a s, so that the following equation would hold:

$m = xr + sk \pmod{p-1}$

m, r and s are published as message + signature.

Here, let's recall generalized version of Fermat little theorem. If g and p are coprimes and $$x=y \pmod p-1$$, then $$g^x=g^y \pmod p$$.

Back to our equation. Verification step. Since g is coprime to p, due the theorem:

$m = xr + sk \pmod {p-1}$

... can be transformed to:

$g^m = g^{xr + sk} \pmod p$

(g and p must be coprimes -- they are, since g is a primitive root of p.)

... and can be rewritten further to:

$(g^{x})^r (g^{k})^s \pmod p$ $(y)^r (r)^s \pmod p$

Verification step doesn't use x (private key), only y (public key). So anyone, having g, p, y can verify signature.

So the last verification step is:

if pow(g, m, p) == divmod(pow(y, r, p) * pow(r, s, p), p)[1]:
print ("verification passed")


Now let's back to finding "such a s".

Rewriting this:

$m = xr + sk \pmod {p-1}$

Would result in:

$\frac{m - xr}{k} \pmod {p-1}$

However we can't use division operation, we must use inverse modulo:

$(m - xr)k^{-1} \pmod {p-1}$

As in ElGamal encryption scheme, the problem of cracking is the problem of finding the 'ephemeral key' k. And again, to do this, the discrete logarithm is to be found.

Now a practical example. g/p parameters and key generation functions are the same as in the previous example.

Parameters:

p, g = (1123, 2)


Keys:

secret key =  108
full public key g, p, y =  (2, 1123, 368)


The signing code:

#!/usr/bin/env python3
import math, random

# private key:
x=108
# g/p parameters and public key:
g, p, h = 2, 1123, 368

m=123
assert m>=0 and m<=p

# AKA ephemeral key
# random for each message
# must be coprime to $p-1$
while True:
k=random.randint(2, p-2)
if math.gcd(k, p-1)==1:
break

r=pow(g, k, p) # publish $k$ in 'obfuscated' form
s=divmod((m - x*r) * pow(k, -1, p-1), p-1)[1] # the same as (m - x*r) / k mod p-1
assert s!=0

print ("m, r, s=", m, r, s)


The verification code:

#!/usr/bin/env python3
import sys

# g/p parameters and public key:
g, p, y = 2, 1123, 368

m=int(sys.argv[1])
r=int(sys.argv[2])
s=int(sys.argv[3])

if pow(g, m, p) == divmod(pow(y, r, p) * pow(r, s, p), p)[1]:
print ("verification passed")
else:
print ("verification NOT passed")


The log:

 % ./sign.py
m, r, s= 123 107 159

% ./verify.py 123 107 159
verification passed


###### (the post first published at 20220430.)

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.