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.