ElGamal signature scheme

The ElGamal Signature scheme is a digital signature scheme which is based on the

Signature generation

To sign a message m the signer performs the following steps.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Choose a random k such that
• Compute $r\; ,\; equiv\; ,\; g^k\; pmod\; p$.
• Compute $s\; ,\; equiv\; ,\; (H(m)-x\; r)k^\{-1\}\; pmod\{p-1\}$.
• If $s=0$ start over again.

Then the pair (r,s) is the digital signature of m.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The signer repeats these steps for every signature.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~