# 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}\text{}\text{}(\mathrm{m}\mathrm{o}\mathrm{d}\text{}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{,}\text{}\alpha \text{,}\text{}\beta )$ since the discrete log problem is considered difficult.

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

Get *Introduction to Cryptography with Coding Theory, 3rd Edition* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.