Introduction to Cryptography with Coding Theory, 3rd Edition

10.5 The ElGamal Public Key Cryptosystem

In Chapter 9, we studied a public key cryptosystem whose security is based on the difficulty of factoring. It is also possible to design a system whose security relies on the difficulty of computing discrete logarithms. This was done by ElGamal in 1985. This system does not quite fit the definition of a public key cryptosystem given at the end of Chapter 9, since the set of possible plaintexts (integers mod $p$) is not the same as the set of possible ciphertexts (pairs of integers $(r\text{,}t)$ mod $p$). However, this technical point will not concern us.

Alice wants to send a message $m$ to Bob. Bob chooses a large prime $p$ and a primitive root $\alpha$. Assume $m$ is an integer with $0\le m<p$. If $m$ is larger, break it into smaller ...