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 α. Alice next chooses a secret integer a such that 1ap2 and calculates βαa  (mod p). The values of p, α, and β 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, α, β) 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.