ElGamal is named after its creator, Taher ElGamal. Although it was not patented directly, a patent covering Diffie-Hellman key exchange was considered to cover ElGamal as well. Lucky for us, the patent expired as I wrote this book. ElGamal is now free.
I won’t try to explain the math or demonstrate why it’s a secure set of algorithms. The equations themselves are not too hard to understand.
Key Pair Generation
Here’s the recipe for generating a key pair:
Create a random prime number, p. This number is called the modulus. The size of p is the same as the key size, so a 2048-bit key has a p that is 2048 bits.
Choose two other random numbers, g and x, both less than p. The private key is x.
Calculate y = gx mod p. The public key is p, g, and y.
To generate a signature using the private key, follow these steps:
Choose a random number, k, that is relatively prime to p - 1. Relatively prime means that k and p - 1 have no factors in common (except 1).
Calculate and , where m is the message. The signature is the numbers a and b.
To verify such a signature, you just have to check that
ElGamal encryption consists of two steps:
Choose a random number, k, that is relatively prime to ...