ElGamal signature scheme

First part: ElGamal encryption system, cracking it using CADO-NFS

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, 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:

... can be transformed to:

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

... and can be rewritten further to:

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:

Would result in:

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

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.)

List of my other blog posts.

Subscribe to my news feed

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.