The ElGamal cryptosystem is making use of the discrete logarithm problem to make it secure, therefore it's fundamental to know what that is about.

The discrete logarithm problem is a numerical procedure that is hard to evaluate on one way and easy another. In the congruence , p is a large prime number and e is a primitive root mod p, or e at least has a high order. To find y when you know x, e, and p is easy. To find the exponent e when you know x, y and p is hard.

For the public key in the ElGamal cryptosystem, you choose a large prime number and a primitive root , and a secret number between 1 and . Then you calculate , and your public key consists of the integers and . If someone wants to use your public key to send you an encrypted message m they first have to choose a number k between 1 and , and then compute and . The ciphertext consists of the numbers and .

Since , you can find the message m by using Euclid’s algorithm to find the inverse of , and then compute .

To make sure the message is coming from the person you’re expecting it to come from, the other person can sign it. Suppose that the other persons public key depend on the numbers , and , where . The random number k should be chosen such that so the inverse I of can be computed. The signed message consists of m, , and. These three numbers are encrypted with your public key. When you have decrypted the ciphertext, you can check if the signed message is valid by checking if the congruence holds.

Author

2020-06-15

Introduction to cryptography methods that uses a public key

Introduction to the knapsack problem

Introduction to the Merkle-Hellman Knapsack Cipher