Elgamal Signature Scheme

Alice chooses a large prime and a random integer
Let be a primitive root .
The public key is
The private key is
Let be a hash function
To send a message with ,
Alice randomly chooses with coprime to
She computes with and
satisfying:

Since is coprime to , we can always find .
Alice signs the message with
Now:

so Bob accepts a signature if
Any obvious attempt at forging involves the discrete log

Lemma

Let and consider .
This has either no solutions or solutions for

Corollary

Alice HAS TO choose different each time.
Suppose she sends and using the same
with signatures and
Then:

Hence:

By the previous Lemma, we can find solutions for
and then choose such that
Then

This gives so we can find solutions for
Choose the solution that gives .
Now we found Alice’s private key and we are able to sign msgs.