9.3 Digital signatures based on discrete logarithms
Other than for RSA signatures, we cannot create a signature based on discrete logarithms simply by encrypting the message m with a private key. This is because in the Diffie-Hellman protocol, we only agree on a shared secret between Alice and Bob. In the ElGamal scheme, Alice uses this shared secret, but not her private key for encryption. Moreover, Alice needs Bob’s public key to compute the shared secret. A digital signature scheme should work without knowing any other public keys than the signer’s, however.
The solution is to compute a number that depends on the private key α and to add this number to the hash value of the message to be signed. This number is masked with another secret parameter k so that the private key cannot be computed from the signature. The basic scheme can be found in the paper by ElGamal [62] from 1985. However, today, ElGamal signatures are not widely used because in 1990, Schnorr...