John Napier’s Legacy Lives on in the 21st Century within ElGamal Encryption

I am lucky to work in the tower where John Napier discovered logarithms:

Now discrete logarithms are used as a base to perform key exchanges over the Internet. They are also being used within encryption — using the ElGamal method.

Public key encryption is typically used to sign for things (and where we use the private key to encrypt something and prove this with the public key) and within key exchange methods. The core methods used are RSA and Elliptic Curve. But an alternative is to use discrete logarithms. One of the most interesting is ElGamal, and was created by Taher Elgamal in 1985.

With ElGamal, initially Bob creates his public key by selecting a g value and a prime number (p), and then selecting a private key (x). He then computes Y which is:

His public key is then (Y,g,p) and he will send this to Alice. Alice then creates a message (M) and selects a random value (k). She then computes a and b: