Introduction to Cryptography with Coding Theory, 3rd Edition

13.2 The ElGamal Signature Scheme

The ElGamal encryption method from Section 10.5 can be modified to give a signature scheme. One feature that is different from RSA is that, with the ElGamal method, there are many different signatures that are valid for a given message.

Suppose Alice wants to sign a message. To start, she chooses a large prime $p$ and a primitive root $\alpha$. Alice next chooses a secret integer $a$ such that $1\le a\le p-2$ and calculates $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The values of $p$, $\alpha$, and $\beta$ are made public. The security of the system will be in the fact that $a$ is kept private. It is difficult for an adversary to determine $a$ from $(p\text{,}\alpha \text{,}\beta )$ since the discrete log problem is considered difficult.

In order for Alice to sign a message $m$, she does the following: ...