# 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{,}\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 ...

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.